[Algorithm] Red-Black Tree ( 원리 및 insertion 설명 )

 

 

Red - Black Tree

 

Binary search tree 중 하나인 AVL Tree 이다.

 

Binary search tree   ->   왼쪽 서브트리에는 루트 보다 작은 값이 , 오른쪽 서브트리에는 루트 보다 큰 값이 들어간다.

AVL tree   ->   height가 2이상 차이나지 않는다.

 

 

Red - Black tree는 이 두 가지 특징을 모두 가진다. 

 

 

 

 

Red - Black tree의 5 가지 특징

 

 

1) 모든 노드가 red or black 이다.

2) 모든 Leaf 노드는 black 이다.

3) 만약 노드가 red 이라면 Child 노드들은 black 이다.

4) 모든 노드 -> 자식 노드 중 Leaf 노드 경로의 black의 갯수가 같다.

5) 루트는 항상 black

 

위 다섯 가지 조건을 만족하면 Red - Black tree이다.

 

 

 

Red - Black tree의 장점

 

height가 거의 일정하기 때문에 Search, Insertion , Deletion 하는 것이 빠르고 일정하다.

 

 

Search , Insertion , Deletion 의 시간 복잡도

 

O( height ) = O( lg n )

 

 

---

 

 

Insertion 정리

 

1) Tree-Insert 로 노드를 집어넣는다.

2) 새로 들어간 노드는 빨간색

3) 만약  새로 들어간 노드의 부모노드가 블랙이면 끝.

4) 아니면 만약 부모노드가 빨간색이면 recoloring만으로 해결하거나 restructure 후 recoloring을 해주는 방법이 있다.

 

 

4)에서 방법이 있다고 했는데

방법은 총 6 가지 있고 3가지만 소개 하겠다.

나머지 3 가지는 대칭이기 때문에 응용하면 된다.

 

 

Case 3가지

 

Case 1)

 

parent , sibling of parent 둘다 빨간색 ,  grand parent 검정 일 때 발동한다.

아래 왼쪽 사진과 같을 때이다.

 

 

그럴 때 아래 오른쪽과 같이 색상을 바꾼다.

끝인 것 같지만 만약

 

 

grand parent 노드의 parent가 빨간색 이면 다시 Case 지정을 통해 빨-빨을 처리해 줘야 된다. 즉 위치만 바뀌고 똑같은 문제가 발생했다고 보면 된다.

 

 

 

 

 

Case1은 그래도 root와 2-step씩 가까워진다.

계속해서 루트일 때까지 올라가므로 O( lg n) 만큼 걸린다.

 

 

Case 2)

 

부모의 오른쪽 자식이 되었을 때 이다. 그리고 sibling은 검정색일 때 ( 아래 사진 참고 )

 

 

 

Left Rotate를 해준다. 그럼 case 3로 바뀐다. (아래 사진 참고)

 

 

 

 

Case 3)

 

 

부모의 왼쪽 자식이 되었고 sibling이 검정색 노드일 때

 

 

 

 

Parent Black으로 바꾸고 Grand parent Red로 바꿈

 

 

 

 

Grand parent로 Right rotate함

 

 

 

 

 

 

 

Red-Black Tree는 이렇게 Insertion이 이루 어진다

이렇게 Insertion을 하면 Red-Black tree의 조건들이 무너지지 않고 잘 지켜진다.