Balanced tree편 Red black tree insert

레드-블랙 트리란?

 - BST 이진탐색 트리에서 파생된? 근사적 Balanced binary search tree

 - 때문에 일반 BST는 최악의 경우 트리의 깊이만큼 탐색시간이 걸리지만

 - balanced tree는 최악의 경우여도 lonN의 시간이 걸리게 된다.

 

한쪽으로 치우진 BST

레드 블랙 트리 나무위키 이미지

균형을 이루기 위한 red black tree의 특징

(1) 노드는 레드 혹은 블랙 색상 중 하나를 갖는다.

(2) 루트 노드는 블랙이다.

(3) 모든 리프 노드(또는 NIL 노드)들은 블랙이다.

(4) 레드 노드의 자식 노드들은 모두 블랙이다. (레드 노드는 연달아 나타날 수 없고, 블랙 노드만 레드 노드의 부모가 될 수 있다.)

(5) 각 노드로부터 해당 노드가 속한 하위 리프 노드까지의 단순 경로 상에는 블랙 노드 개수가 동일하다. (Black Height)

 

구현방법

1. recoloring

 - 부모가 RED 노드 일때 삼촌이 RED노드이면 recoloring을 함으로써 5번째 특성을 만족 시킬 수 있다.

절차 :

 1. 본인 노드를 z라고 하였을때 z->parent = black, z->uncle = black, z->parent->parent를 red로 바꾼다.

 2. 그리고 만일 z->parent->parent가 루트 노드일 경우 2번 특성때문에 z->parent->parent를 black으로 바꿔준다.

 

2.restructuring

삽인된 노드의 부모의 형제노드가 레드가 아닌 경우 restructuring을 진행해 주어야 한다.

총 case가 4개가 있으며 1번 케이스와 2번케이스를 이해하면 3번 케이스와 4번케이스는

총 회전 2회로 진행 할 수 있다.

 

 

레드 블랙트리 1번 케이스

 

 

레드 블랙 트리 케이스 2

3번 케이스

 

4번 케이스