트리: 자식 노드를 지닌 트리 형태의 알고리즘 구조
- 루트 노드: 첫 번째이자 가장 상위 노드
1. 일반적인 트리 구조
트리 구조는 자식 노드를 얼마든지 가질 수 있다.
function TreeNode(value) {
this.value = value;
this.children = [];
}2. 이진 트리
이진 트리: 자식 노드가 왼쪽, 오른쪽 총 두 개 뿐인 트리
function BinaryTreeNode(value) {
this.value = value;
this.left = null;
this.right = null;
}이진 트리에는 항상 루트 노드가 있다.
3. 트리 순회
왼쪽 포인터와 오른쪽 포인터를 이용해 트리의 모든 항목을 방문할 수 있다.
1) 선순위 순회
방문 순서: 루트(현재 노드) -> 왼쪽 -> 오른쪽
선순위 순회는 재귀적으로 구현할 수 있다. (반복문보다 재귀함수로 구현하는 것이 더 간단하고 쉽다.)
BinaryTree.prototype.traversePreOrder = function() {
traversePreOrderHelper(this._root);
function traversePreOrderHelper(node) {
if (!node) return;
console.log(node.value);
traversePreOrderHelper(node.left);
traversePreOrderHelper(node.right);
}
}2) 중순위 순회
방문 순서: 왼쪽 -> 루트(현재 노드) -> 오른쪽
BinaryTree.prototype.traverseInOrder = function() {
traverseInOrderHelper(this._root);
function traverseInOrderHelper(node) {
if (!node) return;
traverseInOrderHelper(node.left);
console.log(node.value);
traverseInOrderHelper(node.right);
}
}
BinaryTree.prototype.traverseInOrderIterative = function() {
let current = this._root;
const s = [];
let done = false;
while (!done) {
if (current !== null) {
s.push(current);
current = current.left;
} else {
if (s.length) {
current = s.pop();
console.log(current.value);
current = current.right;
} else {
done = true;
}
}
}
}3) 후순위 순회
방문 순서: 왼쪽 -> 오른쪽 -> 루트(현재 노드)
BinaryTree.prototype.traversePostOrder = function() {
traversePostOrderHelper(this._root);
function traversePostOrderHelper(node) {
if (!node) return;
traversePostOrderHelper(node.left);
console.log(node.value);
traversePostOrderHelper(node.right);
}
}
BinaryTree.prototype.traversePostOrderIterative = function() {
const s1 = [];
const s2 = [];
s1.push(this._root);
while(s1.length) {
const node = s1.pop();
s2.push(node);
if (node.left) s1.push(node.left);
if (node.right) s1.push(node.right);
}
while (s2.length) {
const node = s2.pop();
console.log(node.value);
}
}4) 단계순위 순회 (너비 우선 검색)
방문 순서: 각 노드 단계별로 방문
BinaryTree.prototype.traverseLevelOrder = function() {
const root = this._root;
const queue = [];
if (!root) return;
queue.push(root);
while (queue.length) {
const temp = queue.shift();
console.log(temp.value);
if (temp.left) queue.push(temp.left);
if (temp.right) queue.push(temp.right);
}
}5) 트리 순회 요약
사용 경우
- 선순위 순회: 잎 노드(자식 노드가 없는 노드)를 방문하기 전에 루트를 조사할 필요가 있을 때 사용
(잎 노드를 방문하기 전에 모든 루트를 방문하기 때문) - 후순위 순회: 부모 노드를 방문하기 전에 잎 노드를 먼저 조사해야 할 때 사용
(잎 노드를 검색할 때 루트를 조사하느라 시간을 낭비하지 않기 때문) - 중순위 순회: 트리를 원래 순서대로 방문하고 싶을 때 사용
(트리를 생성할 때와 동일한 순서로 방문할 수 있기 때문)
순회의 시간 복잡도:
- O(n)
4. 이진 검색 트리
이진 검색 트리: 왼쪽 자식이 부모보다 작고 오른쪽 자식이 부모보다 큰 형태의 이진 트리.
자식 노드가 부모의 왼쪽에만 달리거나 오른쪽에만 달릴 때, 이를 불균형 이진 검색 트리라고 부른다.
불균형 이진 검색 트리는 삽입, 삭제, 검색의 시간 복잡도를 O(log2(n))에서 O(n)으로 증가시키기 때문에 균형을 맞추는 것이 중요하다.
(모든 연산의 시간 복잡도는 이진 검색 트리의 높이와 동일하다.)
1) 삽입
- 루트가 빈 경우: 루트가 신규 노드가 된다.
- 루트가 있는 경우: 조건을 만족할 때까지 이진 검색 트리를 순회하며 신규 노드가 현재 루트보다 크거나 작은지 확인한다.
2) 삭제
삭제할 값을 지닌 노드를 찾기 위해 트리를 순회한다.
- 노드에 자식이 없을 때: null을 반환하여 현재 노드를 삭제한다.
- 노드에 자식이 하나 있을 때: 현재 자식을 반환한다. 해당 자식이 위 단계로 올라가서 부모를 대체한다.
- 노드에 자식이 두 개 있을 때: 왼쪽 하위 트리의 최대치를 찾거나, 오른쪽 하위 트리의 최소치를 찾아서 해당 노드를 대체한다.
3) 검색
현재 루트가 검색 값보다 작은 경우 오른쪽 자식을 방문하고, 검색 값보다 큰 경우 왼쪽 자식을 방문한다.
5. AVL 트리
AVL 트리: 스스로 균형을 잡는 이진 검색 트리
AVL 트리는 이진 검색 트리의 높이를 최소로 유지하며 검색, 삽입, 삭제 연산의 시간 복잡도가 O(log2(n))인 것을 보장한다.
AVL 트리의 높이는 자식의 높이를 기반으로 한다.
1) 단일 회전
삽입 이후에 균형을 유지하기 위해 자식들을 회전한다.
왼쪽 회전:
오른쪽 자식 노드가 너무 길 경우 오른쪽으로부터 (부모 노드와) 회전한다. 즉 오른쪽 자식 노드가 현재 노드의 부모 노드가 되는 것이다.
오른쪽 회전:
왼쪽 자식 노드가 너무 길 경우 왼쪽으로부터 (부모 노드와) 회전한다.
2) 이중 회전
한 번의 단일 회전 이후에도 트리가 불균형일 때 두 번 회전한다.
오른쪽 왼쪽 회전:
오른쪽 회전 이후에 왼쪽 회전을 수행한다.
왼쪽 오른쪽 회전:
왼쪽 회전 이후에 오른쪽 회전을 수행한다.
3) 트리 균형 잡기
왼쪽 자식과 오른쪽 자식의 높이를 비교하여 트리의 균형을 확인할 수 있다. 높이가 균형이 맞지 않는 경우 회전을 통해 균형을 맞춰 준다.
4) 삽입
이진 검색 트리의 삽입과 동일하나, 삽입 이후 부모가 자식의 균형을 잡은 다음 깊이 값을 설정해야 한다는 점이 다르다.
5) 삭제
이진 검색 트리의 삭제과 동일하나, 순회하는 동안 깊이를 조정한다는 점이 다르다.
요약
검색 연산은 다른 자료 구조(연결 리스트, 배열, 스택, 큐)보다 빠르다. 그러나 삽입, 삭제의 시간 복잡도는 다른 자료 구조(O(1))에 비해 높다(O(log2(n))). 더구나 트리가 불균형할 때 모든 연산의 시간 복잡도는 O(n)이 된다.
트리 연산이 항상 로그 시간 복잡도를 지니도록 하기 위해서는 AVL같은 자가 균형 트리를 사용해야 한다.
