-
트리(Tree)?
자료 구조의 형태가 나무(=Tree)와 닮아 트리라 이름 붙여졌다. 어떤 특성을 가지고 있길래 나무와 비슷한 구조를 띠게 되었을까? 특징을 한 번 살펴봐야겠다.
특징
- 노드A가 노드B를 가리킬 때 A를 부모 노드(parent node), B를 자식 노드(child node)라 한다.
- 자식 노드가 없는 노드를 잎 노드(leaf node)라 하고 잎 노드가 아닌 노드를 내부 노드(internal node)라 한다.
- 부모 노드가 없는 최상위 노드를 루트 노드(root node)라 한다.
- 여러 노드가 한 노드를 가리킬 수 없다.
- 회로(Cycle)가 없다. 즉, 자식 노드나 자식 노드의 자식 노드가 부모 노드를 가리킬 수 없다.
- 노드를 잇는 선은 간선(edge)라고 하며 서로 다른 노드 사이에 하나만 있다.
활용 사례
- 나무위키의 목차
- RPG 게임의 스킬 트리
- 윈도우/유닉스의 디렉토리 구조
시간 복잡도
이진 트리(Binary Tree)
자식 노드를 2개로 제한하는 트리
- O(N)
이진 탐색 트리(Binary Search Tree)
이진 트리 중, 왼쪽 가지에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있는 트리.
- 이상적인 경우: 탐색/삽입/삭제 모두 O(logN), 탐색/삽입/삭제하려는 n과 비교해 한 쪽 방향의 가지를 배제할 수 있기 때문에 이진 탐색을 하기에 매우 유리한 구조다.
- 최악의 경우: O(N), 비어있는 이진 트리에 1부터 100까지 순서대로 삽입하는 경우 트리가 오른쪽으로만 자란다(?). 이런 경우 50을 찾고자 하면 선형 탐색을 하는 것과 마찬가지다. 즉, 편향된 이진 트리에서는 O(N)만큼의 시간이 걸린다.
AVL-Tree
자가 균형 이진 탐색 트리
이진 탐색 트리가 최악의 경우 O(N)의 시간이 걸리는 것을 보완하기 위해 나온 트리. 단, 모든 노드에서 왼쪽과 오른쪽 트리의 높이(height) 차가 1이하여야만 한다. 이 때문에 삽입/삭제 할 때마다 균형을 맞추기 위해 트리 일부를 왼쪽 또는 오른쪽으로 회전시켜야 한다. 이로인해 삽입/삭제의 속도가 Red-Black Tree 보다 느리고 탐색만 더 빠르다.- 이상적인 경우/최악의 경우: O(logN)
Red-Black Tree
자가 균형 이진 탐색 트리+노드에 색깔 속성
자식이 하나도 없는 노드의 경우 널 리프 노드(트리의 끝이란 것을 알리는 데만 쓰임)라는 것을 붙인다.
조건
모든 노드는 레드 또는 블랙
루트 노드는 블랙
널 리프 노드는 블랙
레드의 자식 노드는 언제나 블랙. 즉, 레드의 부모 노드는 언제나 블랙. (레드는 연속으로 나오지 못함)
임의의 한 노드에서 널 리프 노드까지의 모든 경로에는 널 리프 노드 외 항상 같은 수의 블랙 노드가 있다.- 이상적인 경우/최악의 경우: O(logN),
궁극의 트리
구현
이진 탐색 트리
class Node { constructor(data) { this.data = data; this.left = null; this.right = null; } } class BinarySearchTree { constructor() { this.root = null; } insert(value) { const newNode = new Node(value); if (this.root === null) { this.root = newNode; } else { let currentNode = this.root; while (true) { // 삽입 데이터가 현재 노드보다 작으면 왼쪽 가지 확인 // 왼쪽 가지가 비어있으면 노드 생성하고 삽입 // 아니라면 왼쪽 가지로 이동 if (value < currentNode.data) { if (!currentNode.left) { currentNode.left = newNode; break; } currentNode = currentNode.left; } else { // 오른쪽 가지에 대해 같은 과정 실행 if (!currentNode.right) { currentNode.right = newNode; break; } currentNode = currentNode.right; } } } } search(value) { if (!this.root) { return '트리가 비었습니다.'; } let parentNode = this.root; let currentNode = this.root; while (currentNode) { if (value === currentNode.data) { // 둘 다 root node 일 때, currentNode 대신 null 반환 if (parentNode === currentNode) { return [parentNode, null] } return [parentNode, currentNode] } if (value < currentNode.data) { parentNode = currentNode; currentNode = currentNode.left; } else { parentNode = currentNode; currentNode = currentNode.right; } } } remove(value) { if (!this.root) { return '트리가 비었습니다'; } let searchedNode = this.search(value); let parent = searchedNode[0]; let target = searchedNode[1]; let origin = target; // target가 null이면 root 노드 할당(=parent) if (target === null) { target = parent; } // target 노드에 자식 노드가 없을 경우(= leaf node 일 경우) 삭제 if (target.left === null && target.right === null) { if (parent.data > target.data) { parent.left = null; } else { parent.right = null; } } else if (target.left === null || target.right === null) { // target 노드에 자식 노드가 있을 경우 parent = target; // 왼쪽 자식이 있을 경우, 그 노드를 제거 if (parent.left !== null) { target = target.left; origin.data = target.data; // 왼쪽 자식을 원래 노드의 위치에 넣는다. parent.left = null; } else { target = target.right; origin.data = target.data; // 오른쪽 자식을 원래 노드의 위치에 넣는다. parent.right = null; } } else if (target.left !== null && target.right !== null) { // 자식 노드 둘 다 있을 경우 parent = target; target = target.right; let loopCheck = false; while (target.left !== null && target.right !== null) { loopCheck = true; parent = target; target = target.left; } origin.data = target.data; // 오른쪽 자식 중 가장 작은 노드를 원래 노드 위치에 넣는다. if (loopCheck === true) { parent.left = null; } else { parent.right = null; } } } }트리 순회
참조 - 나무위키 전위 순회(Pre-order traversal)
- 순회 우선 순위: 자신 > 왼쪽 자식 > 오른쪽 자식
- 노드 방문 후 왼쪽 서브 트리부터 끝까지 순회 후 오른쪽 서브 트리 순회한다.
- 깊이 우선 순회(Depth-first traversal)
- 예시 순회 순서: 8 3 1 6 4 7 10 14 13
순회 과정
- 노드를 방문한다.
- 왼쪽 서브 트리를 전위 순회한다.
- 오른쪽 서브 트리를 전위 순회한다.
구현
위의 이진 탐색 트리를 활용한 전위 순회 구현
BinarySearchTree.prototype.preOrder = function() { const arr = []; function traverse(node) { arr.push(node.data); if (node.left) { traverse(node.left); } if (node.right) { traverse(node.right); } } traverse(this.root); console.log(arr); return arr; } let tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(4); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(13); tree.preOrder();실행 결과
[8, 3, 1, 6, 4, 7, 10, 14, 13]중위 순회(In-order traversal)
- 순회 우선 순위: 왼쪽 자식 > 자신 > 오른쪽 자식
- 왼쪽 서브 트리 끝부터 타고 올라오며 왼쪽 서브 트리들을 방문 후 자신, 오른쪽 서브 트리 순으로 방문한다.
- 대칭 순회(symmetric traversal)
- 예시 순회 순서: 1 3 4 6 7 8 10 13 14
순회 과정
- 왼쪽 서브 트리를 중위 순회한다.
- 노드를 방문한다.
- 오른쪽 서브 트리를 중위 순회한다.
구현
위의 이진 탐색 트리를 활용한 중위 순회 구현
BinarySearchTree.prototype.inOrder = function() { const arr = []; function traverse(node) { if (node.left) { traverse(node.left); } arr.push(node.data); if (node.right) { traverse(node.right); } } traverse(this.root); console.log(arr); return arr; } let tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(4); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(13); tree.inOrder();실행 결과
[1, 3, 4, 6, 7, 8, 10, 13, 14]후위 순회(Post-order traversal)
- 순회 우선 순위: 왼쪽 자식 > 오른쪽 자식 > 자신
- 왼쪽 서브 트리 끝부터 타고 올라오며 왼쪽 서브 트리들을 방문 후 오른쪽 서브 트리, 자신 순으로 방문한다.
- 예시 순회 순서: 1 4 7 6 3 13 14 10 8
순회 과정
- 왼쪽 서브 트리를 후위 순회한다.
- 오른쪽 서브 트리를 후위 순회한다.
- 노드를 방문한다.
구현
위의 이진 탐색 트리를 활용한 후위 순회 구현
BinarySearchTree.prototype.postOrder = function() { const arr = []; function traverse(node) { if (node.left) { traverse(node.left); } if (node.right) { traverse(node.right); } arr.push(node.data); } traverse(this.root); console.log(arr); return arr; } let tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(4); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(13); tree.postOrder();실행 결과
[1, 4, 7, 6, 3, 13, 14, 10, 8]레벨 순회(Level-order traversal)
- 순회 우선 순위: 낮은 레벨
- 모든 노드를 낮은 레벨부터 차례대로 순회한다.
- 너비 우선 순회(Breadth-first traversal)
- 예시 순회 순서: 8 3 10 1 6 14 4 7 13
구현
위의 이진 탐색 트리를 활용한 레벨 순회 구현
BinarySearchTree.prototype.levelOrder = function() { const arr = []; const queue = []; queue.push(this.root); while (queue.length) { const node = queue.shift(); arr.push(node.data); if (node.left) { queue.push(node.left); } if (node.right) { queue.push(node.right); } } console.log(arr); return arr; } let tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(4); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(13); tree.levelOrder();실행 결과
[8, 3, 10, 1, 6, 14, 4, 7, 13]Reference