AVL Tree, Red-Black Tree

Self-Balancing Binary Search Tree가 필요한 이유

출처
n = count of Node
입력에 따른 일반 이진 트리의 Worst Case.
탐색 시간복잡도 = O(n)



출처


입력마다
특정 규칙을 통한 트리의 균형을 맞추는
Self-Balancing Binary Search Tree는
탐색의 시간복잡도를 O(log n)을 보장

AVL Tree

출처

Balance Factor

각 노드의 Balance Factor(이하 BF)는
(왼쪽 Sub-Tree의 높이) - (오른쪽 Sub-Tree의 높이)


(BF == 0) : 높이 차이가 0
(BF == 1) : 왼쪽으로 1 기울어짐
(BF == -1) : 오른쪽으로 1 기울어짐

Rotate

새로운 노드 삽입 시 BF의 절댓값이 2가 되는 경우
Parent(발생노드)-Child-GrandChild의 배치를 바꾸어 해결

Case 1:

(BF == 2) Case
BF가 2가 되는 노드 발생 시 (Left-Left Case) or (Left-Right case) 발생



LL-Case :
Step 1. Child의 오른쪽 서브트리(그림 T2)를 Parent의 왼쪽 서브트리로 할당
Step 2. Parent를 Child의 오른쪽 서브트리로 할당



LR-Case :
Step 1. GrandChild의 왼쪽 서브트리(그림 T2)를 Child의 오른쪽 서브트리로 할당
Step 2. child를 GrandChild의 왼쪽 서브트리에 할당
Step 3. GrandChild의 부모(기존 Child)를 Parent로 변경
위 과정을 통해 LR-Case를 LL-Case로 변경
Step 4. LL-Case 수행


RR-Case, RL-Case 는 위의 수행과정과 동일(방향 반대)

출처

Red-Black Tree

5가지 규칙을 통해 밸런스를 유지하는 트리
1. 모든 노드의 색은 Black or Red
2. Root 노드의 색은 항상 Black
3. Red노드의 자식은 항상 Black
4. 모든 NIL(NULL Leaf)노드는 항상 Black
5. 임의의 노드에서 자손 NIL노드까지 가는 경로에는
항상 같은 Black 노드의 갯수를 보장한다


Example

임의의 노드(8)의 자손 NIL노드는 5개.
5개의 경로 모두 8을 제외한 Black Count == 2

Insertion(삽입)

삽입 규칙
1. 삽입할 노드의 초기 색은 항상 Red
2. 삽입되는 위치는 항상 Leaf(Binary Tree와 동일)
3. 부모의 색에 따라 조건 분기


3-1. 부모의 색이 == Black
종료


3-2. 부모의 색이 == Red
(Red의 자식 Red) 규칙 위반
부모의 색이 Red이면 부모의 형제 색에 따라 해결 방법 결정
Case : 부모의 형제 Color Red

70 - 80 규칙 위반
부모(70)의 형제(30)의 Color == Red
30과 70을 Black을 바꾸고 50을 Red로 바꾼다.


위 규칙을 해결하기 위한 방법.
가능한 이유는 50을 기준으로 양쪽 Black count가 1씩 증가하기 때문에
위 규칙을 위반하지 않고 해결 가능 함.
이후의 상태는
2번 규칙을 위반하기 때문에 Root를 Black으로 바꾸며 마무리.

부모가 Red이며 부모의 형제가 Red인 경우 정리

(부모)와 (부모의 형제) 색을 (조부모)의 색과 바꾸고 조부모가 Root이면 Black으로 바꾼다.

조부모가 Root가 아니라면

=> 조부모의 부모가 항상 Black이라는 보장이 없으므로
함수의 전달 인자를 삽입노드에서 조부모로 변경하여 재귀.

function insertion(삽입노드)
	if(부모 color == Red)
		if(부모의 형제 color == Red)
			부모 color = 부모의 형제 color = Black
    		조부모 color = Red
            if(조부모 == root)
            	조부모 color = black
                return
            else{
            	insertion(조부모) // 조부모의 부모 확인을 위한 재귀
            } 
        else{
        	아래에서 다룸
        }
     else{
     	return
     }