Tree란?
자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있습니다. 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있습니다. 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부릅니다.
트리는 하나의 데이터 아래에 여러 개의 데이터가 존재 할 수 있는 비선형 구조입니다. 트리 구조는 아래로만 뻗어나가므로 사이클(Cycle)이 없습니다.
트리는 루트(Root)라는 하나의 데이터를 시작으로 오러개의 간선(Edge)으로 연결됩니다. 각 데이터를 노드라고하며 상위 노드를 부모 노드, 하위 노드를 자식노드라 부릅니다. 그리고 자식이 없는 노드를 리프 노드라고 합니다.
깊이(depth)
트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있습니다.
레벨(Level)
트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있습니다. 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node) 라고 합니다.
높이(Height)
트리 구조에서 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있습니다. 각각의 리프 노드의 높이는 다를 수 있습니다.
서브 트리(Sub tree)
트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리 라고 부릅니다.
Tree의 실사용 예제
Tree 구조의 가장 대표적인 예제는 컴퓨터의 디렉토리 구조입니다. 어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고, 또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾습니다.
이진 트리(Binary Tree)
트리 구조는 편리한 구조를 만들기 위해서도 사용하지만 탐색을 위해서도 사용합니다. 탐색 방법 중 가장 간단하고 많이 사용하는 이진 트리와 이진 탐색트리를 살펴보겠습니다. 이진트리는 자식 노드가 최대 두개인 노드들로 구성된 트리입니다.
자료의 삽입, 삭제 방법에 따라 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉩니다.
- 정 이진 트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖습니다.
- 포화 이진 트리(Perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.
- 완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
이진 탐색 트리(Binary Search Tree)
이진 탐색 트리란 이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 이진트리입니다. 이진 탐색 트리에서 노드는 부모 요소보다 작은 노드는 왼쪽에, 큰 노드는 오른쪽에 위치합니다. 이러한 특징 때문에 한쪽으로 노드들이 몰리는 현상이 발생할 수 있는데 이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있습니다.
이진 탐색 트리는 기존 이진 트리보다 탐색이 빠르다는 장점이 있습니다. 이진 탐색 트리의 연산은 트리의 높이가 h(height)라면 o(h)의 시간 복잡도를 가지게 됩니다. 그리고 찾은 데이터가 트리 내에 없더라도 마지막까지 탐색이 진행됩니다.
탐색 과정
-
찾고자하는 데이터와 루트 노드와 비교 => 찾을 경우 탐색을 종료합니다.
-
찾고자하는 데이터가 루트 노드 보다 작을 경우 => 왼쪽 서브트리의 탐색을 진행합니다.
-
찾고자하는 데이터가 루트 노드 보다 클 경우 => 오른쪽 서브트리의 탐색을 진행합니다.
-
데이터를 찾지 못할 경우 연산을 종료합니다.
트리 순회
전위 순회(Preorder Traverse)
[Root -> Left -> Right]
첫번째로 루트를 탐색하고 그 후에 왼쪽 노드, 오른쪽 노드로 탐색을 이어나가는 순회 방법입니다. 자식 노드를 탐색할 때, 자식 노드가 서브 트리의 루트이면 그 서브트리 내에서 다시, 루트 -> 왼쪽 노드 -> 오른쪽 노드 순서로 탐색을 이어 나갑니다.
중위 순회(Inorder Traverse)
[Left -> Root -> Right]
루트를 왼쪽 노드와 오른쪽 노드 중간에 탐색하는 순회 방법입니다.
후위 순회(Postorder Traverse)
[Left -> Right -> Root]
왼쪽 노드와 오른쪽 노드를 탐색하고 루트를 제일 마지막에 순회하는 방법입니다.
레벨 순회(Postorder Traverse)
레벨에 따라 왼쪽에 있는 노드 부터 탐색하는 순회 방법입니다.
트리(Tree) 구현
class Tree {
constructor(value) {
this.value = value;
this.children = [];
}
// 트리 삽입 메소드
insertNode(value) {
const childNode = new Tree(value);
this.children.push(childNode);
}
// value값 확인하는 메소드
contains(value) {
if (this.value === value) {
return true;
}
for (let el of this.children) {
if (el.contains(value)) {
return true;
}
}
return false;
}
}이진 탐색 트리(Binary Search Tree) 구현
class BinarySearchTree {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
// 이진 탐색 트리 삽입하는 메메소드
insert(value) {
if (value < this.value) {
if (this.left === null) {
this.left = new BinarySearchTree(value);
} else {
this.left.insert(value) // 재귀함수 사용
}
} else if (value > this.value) {
if (this.right === null) {
this.right = new BinarySearchTree(value);
} else {
this.right.insert(value) // 재귀함수 사용
}
}
}
// value값 확인하는 메소드
contains(value) {
if (this.value === value) {
return true;
}
if (value < this.value) {
return this.left && this.left.contains(value);
}
if (value > this.value) {
if(this.right) {
if(this.right.contains(value)) {
return true;
}
}
return false;
}
}
// 콜백 함수를 매개변수로 받아 콜백 함수에 값을 적용시킨 것을 순회해야 합니다.
// 전위 순회 메소드
preorder(callback) {
callback(this.value);
if (this.left) {
this.left.preorder(callback);
}; // 루트 왼쪽 노드 탐색 종료
if (this.right) {
this.right.preorder(callback);
}; // 루트 오른쪽 노드 탐색 종료
}
// 중위 순회 메소드
inorder(callback) {
if (this.left) {
this.left.inorder(callback);
};
callback(this.value);
if (this.right) {
this.right.inorder(callback);
};
}
// 후위 순회 메소드
postorder(callback) {
if (this.left) {
this.left.postorder(callback);
}
if (this.right) {
this.right.postorder(callback);
}
callback(this.value);
}
}
// 사용 예시
/*
const rootNode = new BinarySearchTree(10);
rootNode.insert(7);
rootNode.insert(8);
rootNode.insert(12);
rootNode.insert(11);
rootNode.left.right.value; // 8
rootNode.right.left.value; //11
let arr = [];
rootNode.preorder((value) => arr.push(value * 2));
arr; // [20, 14, 16, 24, 22]
*/