1. Tree
일반적인 트리 자료 구조는 자식 노드를 지닌 노드들로 구성된다.
첫 번째이자 가장 상위 노드를 루트 노드라 한다.
일반적인 트리 구조
2. 이진트리
이진트리는 자식 노드가 왼쪽, 오른쪽 두 개뿐인 트리다.
이진 트리
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this._root = null;
}
}
3. 순회
트리 순회를 위한 방법에는 다양한 방법이 있다.
가장 널리 사용되는 순회 기법으로 깊이 우선 순회(선순위 순회, 중순위 순회, 후순위 순회), 단계순위 순회가 있다.
대부분의 트리 순회는 재귀적인 방식을 통해 쉽게 순회할 수 있다.
트리 구조 자체가 재귀적이기 때문이다.
3 - 1) 선순위 순회, 중순위 순회, 후순위 순회
선순위 순회는 루트(현재 노드), 왼쪽, 오른쪽 순으로 노드를 방문한다.
기저 조건은 현재 노드가 null일 때 종료된다. 노드가 null이 아니면 노드 값을 출력한다.
그런 다음 왼쪽 자식에 대해 재귀 함수를 호출하고 오른쪽 자식에 대해 재귀함수를 호출한다.
중순위 순회는 왼쪽, 루트(현재 노드), 오른쪽 순으로 노드를 방문한다.
기저 조건은 선순위 순회와 같다. 기저 경우가 아닌 경우 왼쪽 자식에 대해 재귀 함수를 호출한 다음 현재 노드를 출력한다.
마지막으로 오른쪽 자식에 대해 재귀함수를 호출한다.
후순위 순회는 왼쪽, 오른쪽, 루트(현재 노드) 순으로 노드를 방문한다.
class BinaryTree {
constructor() {
this._root = null;
}
...
//선순위 순회
traversePreOrder() {
let currNode = this._root;
if (!currNode) {
return;
} else {
console.log(currNode.value);
currNode.left.traversePreOrder();
currNode.right.traversePreOrder();
}
}
//중순위 순회
traverseInOrder() {
let currNode = this._root;
if (!currNode) {
return;
} else {
currNode.left.traversePreOrder();
console.log(currNode.value);
currNode.right.traversePreOrder();
}
//후순위 순회
traversePostOrder() {
let currNode = this._root;
if (!currNode) {
return;
} else {
currNode.left.traversePreOrder();
currNode.right.traversePreOrder();
console.log(currNode.value);
}
}
}
3 - 2) 단계 순위 순회
위 순회에서는 깊이 우선 순회를 알아보았다. 단계순위 순회는 (Breadth First Search, BFS)이라고도 부른다.
단계순위 순회 방법의 핵심은 왼쪽 혹은 오른쪽으로 깊게 들어가는 깊이우선 순회와 달리 각 노드 단계를 방문한다는 점이다.
class BinaryTree {
constructor() {
this._root = null;
}
...
traverseLevelOrder() {
let currNode = this._root;
let queue = [];
if (!currNode) {
return;
} else {
queue.push(currNode);
}
while (queue.length) {
let temp = queue.shift();
console.log(temp.value);
if (temp.left) queue.push(temp.left);
if (temp.right) queue.push(temp.right);
}
}
}
3 - 3) 트리 순회 요약
리프 노드를 방문하기 전에 루트를 조사할 필요가 있다면 선순위 순회를 선택하라.
부모 노드를 방문하기 전에 리프 노드를 먼저 조사해야 하는 경우 후순위 순회를 선택하라.
트리의 노드 자체에 순서가 있어서 트리를 원래 순서대로 방문하고 싶은 경우 중순위 순회를 선택하라.
위의 순회는 모두 모든 노드를 방문해야 하기 때문에 시간 복잡도가 O(n)으로 동일하다.
또한 단계 순위 순회의 경우 그래프 자료구조에서 더욱 자세하게 다룰 것이다.
4. 이진 탐색 트리
이진 탐색 트리(Binary Search Tree) 역시 이진트리와 마찬가지로 왼쪽과 오른쪽 두 개의 자식이 있다.
하지만 이진 탐색 트리의 경우 왼쪽 자식이 부모보다 작고 오른쪽 자식이 부모보다 크다.
이진 탐색 트리가 이런 구조를 지닌 이유는 검색, 삽입, 특정 값을 가진 노드 제거의 시간 복잡도가 O(logN)을 지향하기 때문이다.
binary search tree
4 - 1) 삽입
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this._root = null;
}
...
insert(value) {
let currNode = this._root;
if (!currNode) {
this._root = new Node(value);
} else {
if (value < currNode.value) {
if (!currNode.left) {
this.left = new BinarySearchTreeNode(value);
return;
} else {
currNode.left.insert(value);
}
} else {
if (!currNode.right) {
this.right = new BinarySearchTreeNode(value);
return;
} else {
currNode.right.insert(value);
}
}
}
}
}
이진 탐색 트리의 삽입의 경우 크게 현재 노드의 값보다 작은 경우와 크거나 같은 경우로 분기를 나눈다.
만약 들어온 값이 현재 노드의 값보다 작고 현재 노드의 왼쪽 자식이 null인 경우 받아온 값으로 새로운 노드를 만들고 할당한다.
만약 왼쪽 자식이 null이 아니라면 왼쪽 자식을 새로운 현재 노드로 하여 재귀 함수를 호출한다.
받아온 인자가 현재 값보다 큰 경우도 마찬가지 로직으로 구성된다.
4 - 2) 검색
class BinarySearchTree {
constructor() {
this._root = null;
}
...
findNode(value) {
let currNode = this._root;
if (currNode.value === value) {
return true;
} else {
if (value < currNode.value) {
if (!currNode.left) return false;
currNode.left.findNode(value);
} else {
if (!currNode.right) return false;
currNode.right.findNode(value);
}
}
}
}
검색도 마찬 가지로 재귀를 사용하면 쉽게 원하는 값을 찾을 수 있다.
기저 조건은 현재 노드의 값이 인자로 받아온 값과 같은 경우 true를 반환한다.
4 - 3) 삭제
삭제 알고리즘은 우선 삭제하고자 하는 값을 지닌 노드를 찾기 위해 트리를 순회한다.
해당 노드를 찾은 경우 다음 세 가지 경우가 있다.
노드에 자식이 없는 경우 -> 가장 간단한 경우다. 노드에 자식이 없다면 해당 노드에 null을 반환한다.
노드에 자식이 하나 있는 경우 -> 노드에 자식이 하나 있는 경우 현재 자식을 반환한다. 해당 자식이 위 단계로 올라가서 부모를 대체
노드에 자식이 두 개 있는 경우 -> 노드에 자식이 두 개 있는 경우 왼쪽 하위 트리의 최대치를 찾거나 오른쪽 하위 트리의 최소치를 찾아서 해당 노드를 대체한다.
class BinarySearchTree {
constructor() {
this._root = null;
}
...
remove(value) {
return deleteRecursively(this._root, value);
function deleteRecursively(root, value) {
if (!root) {
return null;
} else if (value < root.value) {
root.left = deleteRecursively(root.left, value);
} else if (value > root.value) {
root.right = deleteRecursively(root.right, value);
} else {
//찾은 경우
if (!root.left && !root.right) {
//자식이 없는 경우
return null;
} else if (!root.left) {
//오른쪽 자식만 있는 경우
root = root.right;
return root;
} else if (!root.right) {
//왼쪽 자식만 있는 경우
root = root.left;
return root;
} else {
let temp = findMin(root.right);
root.value = temp.value;
root.right = deleteRecursively(this.right, temp.value);
return root;
}
}
return root;
}
function findMin(root) {
while (root.left) {
root = root.left;
}
return root;
}
}
}
이진 탐색 트리의 삽입, 검색, 삭제에 대해 알아보았다.
만약 이진 탐색 트리가 균형 트리라면 세 가지 연산 모두 시간 복잡도가 O(logN) 일 것이다.
하지만 불균형 트리(자식이 오른쪽이나 왼쪽으로 치우친 경우)는 세 가지 연산 모두 시간 복잡도가 O(n)이 된다.
즉 이진 탐색 트리의 장점을 전혀 살리지 못하는 것이다.
위의 해결 방법으로는 데이터가 삽입이 될 때 트리가 스스로 균형을 잡도록 하는 AVL 트리가 있다.
하지만 나는 아직 AVL 트리를 다루기엔 벅차다. 일주일 만에 많은 자료 구조를 공부하면서 머리가 터지기 일보직전이다.
AVL 트리에 대해선 추후에 포스팅을 해야 할 것 같다.
