트리란
- 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조.
- 회로(Cycle)가 없고, 두 노드를 연결하는 길이 하나뿐인 그래프.
트리의 구조
- 루트: 부모가 없는, 가장 상윗단의 노드 (문서 노드: docuement)
- 노드: 트리 구조의 자료 값을 담고 있는 요소 (모든 노드: 문서 노드, 텍스트 노드, 요소 노드, 어트리뷰트 노드)
- 에지: 노드 간의 연결 선
- 부모: 연결된 두 노드 중 상위에 있는 노드($element.parentNode)
- 자식: 연결된 두 노드 중 하위에 있느 노드($element.childNodes[0], js는 자식들을 가리키는 NodeList가 자식에 해당한다.)
- 경로: 두 노드를 연결하는 에지의 시퀀스
- 입새 노드: 자식 노드가 없는 노드(구조상 어트리뷰트 노드, 텍스트 노드가 잎새 노드에 속함)
- 내부 노드: 잎새 노드를 제외한 모든 노드
- 레벨, 깊이: 루트 노드로 부터의 경로 길이
- 트리의 높이: 트리에서 가장 큰 레벨(깊이) 값
트리의 특징
- 하나의 노드에서 다른 노드로 이동하는 경로는 유일함.
- Acyclic하다. (Cycle이 존재하지 않는다. 그래프와 상반된다.)
- 모든 노드는 서로 연결되어 있다. (외딴 섬이 존재하지 않는다.)
- 하나의 Edge를 끊으면 두개의 Sub-Tree로 분리된다.
- Edge의 수는 [Node의 수 -1]이다. (3개의 트리가 있다고 가정하면 Edge는 2)
0
/ \
0 0이진 트리
이진 트리의 종류
- 정 이진 트리: 잎새 노드는 자식을 가지지 않으며, 그 외의 모든 노드는 반드시 2개의 노드와 연결된다.
- 완전 이진 트리: 왼쪽부터 차례대로 입력된 트리.
- 균형 이진 트리: Skewed Tree(연결리스트 형식으로 한쪽 방향으로만 연결된 트리), Balanced Binary Tree: 자식 노드의 수가 0 혹은 2인 트리.
따라서, 돔 트리 구조는 이진트리가 아니다. 이론상으로 자식의 수가 메모리가 허용하는 만큼 늘어날 수 있다.
이진 트리의 순회
- 깊이 우선 순회: (Preorder, Depth-First Traversal) (node -> left -> right)
Preorder는 조회한 노드를 먼저 확인한 후, 왼쪽 노드 방향으로 순회하는 방법이다. - 대칭 순회(Inorder, Symmetric Traversal) (left -> node -> right)
Inorder는 왼쪽 자식 방향으로 먼저 순회한 후 부모노드를 확인하고 마지막으로 오른쪽 노드를 확인한다. - 후위 순회(Postorder) (left -> right -> node)
이진 트리의 탐색(Search)
- 너비 우선 탐색 (Breadth-First Search: BFS)
보통 가까운 곳 부터 서서히 전체를 탐색하고 싶은 경우 이 방법을 사용한다. - 깊이 우선 탐색 (Depth-First Search: DFS)
보통 한쪽 방향으로 순회하여 가장 깊은 곳을 빠르게 탐색하고 싶은 경우 이 방법을 사용한다.
완전 이진 트리의 구현
- 배열을 이용하여 구현하는 방법
- 부모노드(index) = 자식노드(index) / 2, 자식노드(index) = 부모노드 * 2 + (0 or 1) - 노드를 이용하여 구현하는 방법
- value, left, right를 자긴 node class를 이용한다.
이진트리 구현해보기
순회, 탐색 로직은 생각보다 간단하다.
// interface로 BinaryTreeNode 정의
interface BinaryTreeNode<T> {
val: T;
left?: BinaryTreeNode<T>;
right?: BinaryTreeNode<T>;
}
// 파생 트리 BinarayTree의 뼈대가 될 추상 Tree 설계
abstract class Tree<T> {
constructor(protected root?: BinaryTreeNode<T>, arr?: T[]) {
if (root) {
this.root = root;
} else if (arr) {
this.root = this.createTree(arr, 0);
}
}
abstract createTree(arr: T[], index: number): BinaryTreeNode<T> | undefined;
abstract preOrder(): void;
abstract inOrder(): void;
abstract postOrder(): void;
abstract bfs(target: T): T | undefined;
abstract dfs(target: T): T | undefined;
}
class BinaryTree<T> extends Tree<T> {
constructor(root?: BinaryTreeNode<T>, arr?: T[]) {
super(root, arr);
}
createTree(arr: T[], index: number = 0): BinaryTreeNode<T> | undefined {
if (!arr[index]) {
return undefined;
}
const root = {
val: arr[index],
left: this.createTree(arr, index * 2 + 1),
right: this.createTree(arr, index * 2 + 2),
};
return root;
}
preOrder() {
const curNode = this.root;
const preOrder = (node?: BinaryTreeNode<T>) => {
if (!node) {
return;
}
console.log(node.val);
preOrder(node.left);
preOrder(node.right);
};
preOrder(curNode);
}
inOrder() {
const curNode = this.root;
const inOrder = (node?: BinaryTreeNode<T>) => {
if (!node) {
return;
}
inOrder(node.left);
console.log(node.val);
inOrder(node.right);
};
inOrder(curNode);
}
postOrder() {
const curNode = this.root;
const postOrder = (node?: BinaryTreeNode<T>) => {
if (!node) {
return;
}
postOrder(node.left);
postOrder(node.right);
console.log(node.val);
};
postOrder(curNode);
}
bfs(target: T) {
if (!this.root) return undefined;
const queue: BinaryTreeNode<T>[] = [this.root];
while (queue.length !== 0) {
const curNode = queue.shift();
if (curNode!.val === target) {
return curNode!.val;
}
if (curNode!.left) {
queue.push(curNode!.left);
}
if (curNode!.right) {
queue.push(curNode!.right);
}
}
return undefined;
}
dfs(target: T) {
if (!this.root) return undefined;
const stack: BinaryTreeNode<T>[] = [this.root];
while (stack.length !== 0) {
const curNode = stack.pop();
if (curNode!.val === target) {
return curNode!.val;
}
if (curNode!.right) {
stack.push(curNode!.right);
}
if (curNode!.left) {
stack.push(curNode!.left);
}
}
}
}
const binaryTree = new BinaryTree<number>(
undefined,
[1, 2, 3, 4, 5, 6, 7, 8, 9]
);
binaryTree.preOrder(); // 1, 2, 4, 8 , 5, 3, 6, 9, 7
binaryTree.inOrder(); // 8, 4, 9, 2, 5, 1, 6, 3, 7
binaryTree.postOrder(); // 8, 9, 4, 5, 2, 6, 7, 3, 1
binaryTree.bfs(8); // 8
binaryTree.bfs(10); // undefined
binaryTree.dfs(8); // 8
binaryTree.dfs(10); // undefined결론
돔트리, 렌더트리 등의 근원 자료구조 트리를 구현해보며 어떤 식으로 동작할지 다시 한번 짚고 넘어가는 계기가 되었다. 한가지 아쉬운 점은, Tree를 추상 클래스로 만들었는데 이 추상 클래스는 root 노드가 BinaryTreeNode로 지정되었기 때문에 반드시 BinaryTreeNode를 만들어야 한다. 추후에는 코드를 수정해서 조금 더 범용적인 추상 클래스를 만들볼 계획이다.
Front 💔 End