자료구조
트리(Tree)
웜블
2021. 12. 31. 04:20
트리(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]