[Algorithm Part 1] 6. Balanced Search Tree

저번 글에서 살펴본, BST는 무작위 삽입 순서일 경우에만, $\lg N$ 성능을 보여줄 뿐,

모든 삽입 순서에 대해 $\lg N$ 성능을 보장해주지 않는다.

 

이번 글에서는, 모든 삽입 순서에 대해 $\lg N$ 성능을 보장해주는 Balanced Search Tree에 대해 살펴볼 것이다.

 

Balanced Search Tree에는 대표적으로 2-3 트리와 b-트리가 있다.

---

1. 2-3 Tree

Definition

2-3 트리는 2가지 종류의 노드를 가지고 있는 트리다.

1. 2-node: 1 key, 2 children
2. 3-node: 2 key, 3 children
   1. 왼쪽 서브 트리의 모든 key는 부모 노드의 key보다 작다.
   2. 가운데 서브 트리의 모든 key는 부모 노드의 key 사이에 있다.
   3. 오른쪽 서브 트리의 모든 key는 부모 노드의 key보다 크다.

Property

1. Symmetric order: 중위 순회(inorder traversal)을 통해, 정렬 순서대로 key를 scan할 수 있다.
2. Perfect balance: 모든 leaf 노드의 깊이가 같다.

Data Structure

linked-list 기반으로 2-3 트리를 구상한다.

Operations

1. search

root 노드에서 시작해 leaf 노드로 도달할 때까지 다음 과정을 반복한다.

1. 서브 트리의 root 노드 key와 탐색 key를 비교한다. 이때 탐색 key가 있을 시, 해당 value를 반환한다.
2. 탐색 key를 포함하는 범위를 찾는다. 즉, 탐색 key를 포함하는 서브 트리를 찾는다.
3. 해당 서브 트리로 이동한다.

2. insert

search 연산으로, 삽입 위치를 찾는다.

2-node에 삽입할 시, key를 추가해 3-node로 만든다.

3-node에 삽입할 시,

1. key를 추가해 일시적으로 4-node로 만든다.
2. 가운데 key를 부모 노드로 보낸 후, 왼쪽 key와 오른쪽 key를 각각 2-node로 만든다.
3. 만약 조상 노드가 4-node가 될 경우, 1~2번을 반복한다. 
4. 만약 root 노드가 4-node가 될 시, 3개의 2-node로 나눈다. (이때, 트리의 깊이가 증가한다.)

2-3 트리가 완전 균형 트리인 이유는

root 노드가 4-node 일 때 트리 균형을 유지하는 방향으로 트리 깊이를 증가시키기 때문이다.

---

2. Red-Black BSTs.

Definition

red-black BST는 2-3 트리를 BST 방식으로 표현한 트리다. 

1. 2-node: 기본 노드와 같다.
2. 3-node: 두 개 2-node를 잇는다(=connect).
   • 2-node와 구분하기 위해 빨간색 선으로 잇는다.
   • 왼쪽으로 기울어져 있다. 즉, 큰 노드가 위에 있다.

Property

1. 빨간색 선이 연속으로 나올 수 없다. 2-3 트리는 4-node를 허용하지 않기 때문이다.
2. root 노드부터 모든 leaf 노드까지 연결된 검은색 선의 개수는 같다.
   즉, 검은색 선 기준 완전 균형 트리를 갖는다. 때문에, 완전 균형까지는 아니지만 완전 균형에 가까운 트리를 갖는다.
3. 빨간색 선은 왼쪽으로 기울어져 있다. 모든 3-node가 왼쪽으로 기울어져 있기 때문이다.
4. 2-3 트리와 red-black BST는 1-1 대응이다.

Data Structure

linked-list 기반으로 red-black BST를 구상한다.

Operations

1. search

탐색 연산은 BST와 같다. 2-node만 사용하기 때문이다.

뿐만 아니라, 삽입 연산을 제외한 모든 연산은 BST와 같다.

 

2. insert

case 1: 2-node에 삽입할 경우

1. BST 삽입 연산을 이용해, 빨간색 선 노드를 추가한다. (2-node to 3-node)
2. 오른쪽으로 기울이져 있을 경우, left rotation 연산을 사용해, 왼쪽으로 기울어지게 수정한다.

case 2: 3-node에 삽입할 경우

1. BST 삽입 연산을 이용해, 빨간색 선 노드를 추가한다. (3-node to 4-node)
2. 불균형 4-node일 경우, left rotation 혹은 right rotation 연산을 사용해, 균형 4-node로 바꾼다.
3. color flip 연산을 사용해, 4-node를 3개 2-node로 나눈다.
4. 경로를 따라가면서, red-black 트리의 성질을 유지시킨다. (by case 1, case 2)

Sub operations

1. Left rotation:오른쪽으로 기울어진 3-node를 왼쪽으로 기울어지게 수정한다.
2. Right rotation:왼쪽으로 기울어진 3-node를 오른쪽으로 기울어지게 수정한다.
3. Color flip: 자식 노드 둘 다 빨간색 선으로 연결되어 있을 경우(=4-node),
   자식 노드와의 선을 모두 검정색 선으로 바꾸고, 부모 노드와의 선을 빨간선으로 바꾼다.

---

Performance

2-3 트리의 깊이는 $\lg N$이고, red-black 트리의 깊이는 $2\lg N$보다 낮다. (빨간색 선이 연속으로 나올 수 없기 때문)

	worst case			average case
	search	insert	delete	search-hit	insert	delete
BST	N	N	N	$1.39\lg N$	$1.39\lg N$	$\sqrt N$
2-3 Tree	$c\lg N$	$c\lg N$	$c\lg N$	$c\lg N$	$c\lg N$	$c\lg N$
Red-Black Tree	$2 \lg N$	$2 \lg N$	$2 \lg N$	$1.00 \lg N$	$1.00 \lg N$	$1.00 \lg N$