자료구조 - BST
Tree
Tree 자료구조는 Node로 이루어짐.
꼭대기는 Root.
Root Node에서 아래의 Node들로 내려가면서 이어지는 자료구조.
각각의 Node들은 Child node들을 가짐.
다른 Child node들로 이어지는 branch를 가진 Node를 Parent라고 함.
Parent에서 branch로 이어진 Node들은 당연히 Child.
Children이 없는, Tree의 맨 마지막에 있는 Node들을 Leaf.
Children은 그들이 Root가 되는 Subtree를 가짐.
Binary Search Tree
Binary Search Tree는 한 Node 당 두 개의 Children만 가질 수 있음.
또한, Binary Search Tree는 정렬되어있음.
모든 Left subtree들이 Parent Node보다 같거나 작음.
모든 Right subtree들은 Parent Node보다 크거나 같음.
이진 탐색의 원리로 인해, 대부분의 검색이 트리의 절반정도를 스킵한다.
그래서 삽입, 삭제, 검색이 트리에 저장된 아이템의 평균적으로 O(logN)의 속도를 보임.
Key로 아이템을 순차적으로 찾거나 Unsorted array의 O(n)보다는 빠르지만
Hash table의 O(1)보다는 느림.
좌우가 얼추 갯수가 비슷하면 balanced, 그렇지 못하면 unbalanced.
좌우의 갯수가 완전히 같으면 perfect, 한쪽으로만 완전히 치우쳐저있으면 degenerate.
degenerate은 linked list와 다름없음. 그러면 효율성이 떨어지기 때문에
스스로 균형을 맞추는 red-black tree나 AVL tree도 있음.
노드의 삽입이나 삭제는 재귀 알고리즘을 활용함.
/* Binary Search Tree */
class Node {
constructor(data, left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
}
class BST {
constructor() {
this.root = null;
}
add(data) {
const node = this.root;
if(node === null) {
this.root = new Node(data);
return;
} else {
//use recursive function to figure out where to put this node in the tree.
const searchTree = function(node) {
if(data < node.data) {
if(node.left === null) {
node.left = new Node(data);
return;
} else if(node.left !== null) {
return searchTree(node.left);
}
} else if(data > node.data) {
if(node.right === null) {
node.right = new Node(data);
return;
} else if(node.right !== null) {
return searchTree(node.right);
}
} else {
// equal -> not going to add the data to the tree.
return null;
}
};
// 위에까지는 searchTree function의 정의
// initially call the searchTree function with this return statement.
return searchTree(node);
}
}
findMin() {
let current = this.root;
while(current.left !== null) {
current = current.left;
}
return current.data;
}
findMax() {
let current = this.root;
while(current.right !== null) {
current = current.right;
}
return current.data;
}
find(data) {
let current = this.root;
while(current.data !== data) {
if(data < current.data) {
current = current.left;
} else {
current = current.right;
}
if(current === null) {
return null;
}
}
return current;
}
isPresent(data) {
let current = this.root;
while(current) {
if(data === current.data) {
return true;
}
if(data < current.data) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
remove(data) {
const removeNode = function(node, data) {
if(node == null) {
return null;
}
if(data == node.data) {
if(node.left == null && node.right == null) {
// 노드가 양쪽의 자식이 모두 없으면
return null;
}
if(node.left == null) { // 노드가 왼쪽 자식이 없는 경우
return node.right;
}
if(node.right == null) { // 노드가 오른쪽 자식이 없는 경우
return node.left;
}
// if(node.left && node.right)
let tempNode = node.right;
// 자식이 둘일 경우, right child로 한 번 간 상태에서
// 그 놈의 subtree 중 가장 작은 data를 가진 node를 찾으면 됨.
while(tempNode.left !== null) {
tempNode = tempNode.left;
// 그 node가 삭제된 node를 대신해서 들어간다.
}
node.data = tempNode.data;
node.right = removeNode(node.right, tempNode.data);
// 삭제한 node 대신 들어간 node의 원래 자리에 있는 원본을 지워줘야됨.
// -> right subtree쪽으로 한 칸 가서 그 node의 data를 removeNode.
return node;
} else if(data < node.data) {
// 만약 이번에 순회하는 노드가 타겟 데이터를 가진 노드가 아니라면
// 타겟 방향으로 한 칸 더 가서 재귀호출
node.left = removeNode(node.left, data);
return node;
// 즉, 타겟 데이터를 가진 노드가 아니면 건드리면 안되니까
// 타겟 방향으로 한 칸 건너가서 재귀호출 해주고(traverse를 진행해야되니까)
// 자기는 그냥 자기자신을 return한다.
} else {
// (data > node.data)
node.right = removeNode(node.right, data);
return node;
}
};
// 위에까지는 함수의 정의
// 여기서 처음 호출
this.root = removeNode(this.root, data);
}
isBalanced() {
return (this.findMinHeight() >= this.findMaxHeight() - 1);
}
findMinHeight(node = this.root) {
// 양쪽 자식을 모두 가져야 높이 1로 인정.
// 1. 재귀 호출을 left부터 쭉 타고 들어가서, null까지 도달
// 2. 그러면 null부터, -1을 return하면서 재귀호출을 하나하나씩 풀어가는 것.
if(node == null) {
return -1;
}
let left = this.findMinHeight(node.left);
let right = this.findMinHeight(node.right);
if(left < right) {
return left + 1;
} else {
return right + 1;
}
}
findMaxHeight(node = this.root) {
if(node == null) {
return -1;
}
let left = this.findMaxHeight(node.left);
let right = this.findMaxHeight(node.right);
if(left > right) {
return left + 1;
} else {
return right + 1;
}
}
inOrder() {
if(this.root == null) {
return null;
} else {
// root 노드가 존재하는 경우.
const result = new Array();
// 함수 정의
function traverseInOrder(node) {
// if node.left exists, call traverseInOrder recursively.
node.left && traverseInOrder(node.left);
result.push(node.data);
node.right && traverseInOrder(node.right);
}
// 함수 호출
traverseInOrder(this.root);
return result;
}
}
preOrder() {
if(this.root == null) {
return null;
} else {
const result = new Array();
function traversePreOrder(node) {
// if node.left exists, call traverseInOrder recursively.
result.push(node.data);
node.left && traversePreOrder(node.left);
node.right && traversePreOrder(node.right);
}
traversePreOrder(this.root);
return result;
}
}
postOrder() {
if(this.root == null) {
return null;
} else {
const result = new Array();
function traversePostOrder(node) {
// if node.left exists, call traverseInOrder recursively.
node.left && traversePostOrder(node.left);
node.right && traversePostOrder(node.right);
result.push(node.data);
}
traversePostOrder(this.root);
return result;
}
}
levelOrder() {
let result = [];
let Q = [];
if(this.root != null) {
Q.push(this.root);
while(Q.length > 0) {
let node = Q.shift();
result.push(node.data);
if(node.left != null) {
Q.push(node.left);
}
if(node.right != null) {
Q.push(node.right);
}
}
return result;
} else {
return null;
}
}
};
const bst = new BST();
bst.add(9);
bst.add(4);
bst.add(17);
bst.add(3);
bst.add(6);
bst.add(22);
bst.add(5);
bst.add(7);
bst.add(20);
console.log(bst.findMinHeight());
console.log(bst.findMaxHeight());
console.log(bst.isBalanced());
bst.add(10);
console.log(bst.findMinHeight());
console.log(bst.findMaxHeight());
console.log(bst.isBalanced());
console.log('inOreder: ' + bst.inOrder());
console.log('preOreder: ' + bst.preOrder());
console.log('postOreder: ' + bst.postOrder());
console.log('levelOreder: ' + bst.levelOrder());
BFS & DFS
Depth first search는 branch by branch로 트리를 탐색하고
Breadth first search는 level by level로 트리를 탐색한다.
in-order depth first search는 left node -> root node -> right node 순으로 검색을 해나간다.
이 순서로 탐색을 완료하고나면, 트리의 모든 값들이 순서대로(오름차순) 출력된다.
pre-order dfs는 root node -> left node -> right node 순으로 검색.
post-order dfs는 left node -> right node -> root node 순으로 검색.
Breadth first search는 Queue 자료구조를 사용한다.
Root node부터 시작해서 트리의 레벨별로 순회를 하기 때문에, Level order search라고도 한다.
BST는 아주 많은 양의 정렬된 데이터를 가지고 작업할 때 매우 효과적이다.
재귀에 익숙하지 않아서 이해하는 데에 역대급으로 오래 걸렸다.
다른 BST 코드를 막 찾아보면서, 최대한 재귀가 없는 코드를 찾아보려고 했는데
애초에 그럴 수가 없는 코드였다는 생각이 들고나서부터 이 코드 이해하는데만 이틀이 걸린 듯.
이해하고나서 보니, 코드를 제대로 읽지 않아서 이해가 안됐다는 걸 알게 됐다.
처음부터 집중해서 코드를 읽었으면 쉽게 이해했을텐데..
if문을 제대로 보지 않아서 생각이 꼬였다.
어우. 지긋지긋해.
얘로 어떻게 문제를 풀지 앞이 캄캄하다 증말로.