Binary Search Tree
다음의 조건을 만족시키는 Binary Tree를 Binary Search Tree로 정의한다.
- 각 노드에는 key값이 저장되어 있다.
- 모든 노드에 대해, key값은 left subtree의 모든 key값보다 크다.
- 모든 노드에 대해, key값은 right subtree의 모든 key값보다 작다.
+) Binary Search Tree에서 in-order traversal을 하면, 오름차순으로 정렬된 key list를 얻을 수 있다.
+) Binary Search Tree의 높이를 h라고 할 때, 탐색 연산은 O(h)만큼의 시간을 소요하기 때문에, 높이를 최소한으로 줄이는 것이 중요하다.(as balanced as possible)
+) Binary Search Tree에서 삽입, 삭제 연산에도 탐색 연산이 수행된다. 따라서 탐색 연산의 복잡도를 최소한으로 하는 것이 중요하다.
Balanced Binary Search Tree
- 트리의 모든 높이에서 좌우 서브트리의 높이 차이가 일정 범위 내로 유지되도록 설계된 데이터 구조를 Balanced Binary Search Tree라고 정의한다.
- 노드의 수가 N일때, 높이는 약 logN이 되므로, 탐색 연산의 시간복잡도는 O(logN)이다.
- 대표적인 예시로는 AVL Tree, Red-Black Tree가 있다.
Red-Black Tree
다음의 조건을 만족시키는 Binary Search Tree를 Red-Black Tree로 정의한다.
- Root Property: 루트 노드는 black이다.
- External Property: 모든 leaf노드는 black이다.
- Internal Property: red의 자식노드는 black이다.
- Black Depth Property: 모든 leaf노드에 대해, black depth는 동일하다.
(Black Depth: root로 가는 경로중에 마주치는 black노드의 수)
Red-Black Tree는 Balanced Binary Search Tree로, 높이는 logN이다.
Red-Black Tree Insertion
Red-Black Tree의 삽입 연산의 순서는 다음과 같다. (삽입하고자 하는 노드를 z key값을 k라고 하자.)
- find(k)를 통해 z가 위치해야할 곳을 찾는다.
- z를 찾은 위치에 삽입한다. (v는 red)
- z의 부모 노드가 red인 경우, Internal Property를 어기기 때문에, Restructuring 혹은 Recoloring을 진행한다.
Restructuring
z의 uncle node가 black인 경우, restructuring을 진행한다.
- z의 parent, grandparent node를 binary search tree형태로 만들어준다.
- root를 black으로, 두 자식을 red로 설정한다.
- 해당 과정은 O(1) time이 소요된다.
Recoloring
z의 uncle node가 red인 경우, restructuring을 진행한다.
- z의 parent, uncle을 black으로 수정하고, grandparent를 red로 수정한다.
- 해당 과정은 O(1) time이 소요된다.
- 이렇게 recoloring한 결과 다시 double red가 발생하면, 해당 노드에 대해 다시 restructuring이나 recoloring을 진행한다.
- 만약 grandparent가 root인 경우, Root Property에 의해 root를 다시 black으로 설정해준다.
Recoloring이 계속 반복되어 root까지 올라가면 O(1)을 약 logN번 반복하게 된다. 따라서 삽입 연산에서 double red를 해소하는 과정은 최악의 경우 O(logN) time이 소요된다.
