CS/자료구조

AVL Tree

AVL Tree - AVL Tree는 left subtree와 right subtree의 높이차가 1 이하인 BST이다. - AVL Tree는 balance가 타이트하게 유지되기 때문에 Red-Black Tree보다 height가 더 낮다. 따라서 탐색이 더 빠르다. - AVL Tree가 insert, delete 연산에 대해서는 성능이 밀린다는 통념이 있다. - 하지만 잘만 구현한다면 AVL Tree가 수행 시간이 더 짧다는 실험 결과가 있다. 그러나 그 사실을 아는 사람이 많지 않고 CLRS에서 AVL Tree를 다루지 않기 때문에 RB Tree가 더 자주 사용된다. 많은 프로그래밍 언어의 라이브러리에서 RB Tree가 사용된다. AVL Tree Class public class AVLTree { c..

Tree rotation

[ 출처 : https://en.wikipedia.org/wiki/Tree_rotation ] - left subtree가 더 무거울 때 right rotation을 해준다. - right subtree가 더 무거울 때 left rotation을 해준다. Example : rotate left 1에서 imbalance가 발생했다고 해보자. 또, imbalance의 원인이 3 혹은 3의 subtree에 있다고 해보자. 1을 기준으로 left rotation을 해준다. (즉, 1-2-3 덩어리를 왼쪽으로 한 칸 민다) imbalance가 해소되었다. Example : rotate right-left 1에서 imbalance가 발생했다고 해보자. 또, imbalance의 원인이 2 혹은 2의 subtree에 ..

Balanced BST

BST에 1, 2, 3, 4, 5, 6, 7 을 넣는다고 생각해보자. 1, 2, 3, 4, 5, 6, 7 순서로 값을 추가하면 4, 2, 6, 1, 3, 5, 7 순서로 값을 추가하면 전자의 경우 linked list와 별반 차이가 없다. 후자의 경우 탐색에 $O(\log{n})$의 시간이 소요되지만, 전자의 경우 탐색에 $O(n)$의 시간이 소요된다. 따라서 unbalanced BST보다는 rotation 개념을 이용해 balance를 맞춘 balanced BST가 자주 사용된다. Balanced tree의 예로 AVL tree, red-black tree, splay tree 등이 있다.

Binary Search Tree (BST)

Binary Search Tree - 각 node에 대해 (left subtree) < node < (right subtree) 의 성질을 만족하는 tree - in order traversal을 기준으로 정렬된 상태 Example Node class class Node{ E data; Node left, right; public Node(E obj) { data = obj; left = right = null; } } 필요하다면 parent pointer 도 만들어 줄 수 있다. BST class initialization public class BST{ ... Node root; int currentSize; public BinarySearchTree() { root = null; currentSiz..