레드 블랙트리

레드블랙 트리 규칙 4가지

1. Root Property : 루트 노드의 색깔은 검정(Black)

2. External Property : 모든  external Node 들은 검정(Balck)
   external Node : 자식이 없는 노드

3. Internal Property : 빨강(Red) 노드의 자식은 검정(Balck)
== No Double Red(빨간색 노드가 연속으로 나올수 없다.)
4. Depth Propery : 모든 리프노드에서 Black Depth는 같다.
== 리프노트에서 루프노드까지 가는 경로에서 만나는 블랙 노드의 개수는 같다.

 

위의 4가지 규칙을 지키는 이진 트리는 Red Black Tree 라고 한다. AVL Tree 보다 Blance 제약이 느슨하기 때문에 삽입 삭제 수정에 대해 높은 성능을 가진다. AVL Tree 보다 Blacne가 느슨하기 때문에 검색 속도는 AVL Tree 보다 느림.

 

레드블랙 트리에 노드를 삽입할 시 경우는 2가지로 나뉜다.

 

Case 1 : 입력 노드의 부모의 형제노드가 null 또는 블랙(Black) 노드인 경우

다음과 같이 입력 노드인 6의 부모의 형제노드가 블랙 인 경우 

 

Restructuring 을 실행한다.

 

Restructuring

현재 insert 된 노드와 부모노드 , 부모의 부모노드를 가지고 Restruction 한다.

1. 4 7 6 노드들을 오름 차순으로 정렬

2. 무조건 가운대 있는 값을 부모로 만들고 나머지 들을 자식노드

3. 올라간 가운데 있는 값을 검정(Black)으로 만들고 그 두자식을 빨강(Red)로 만든다.

Restruction의 경우에는 한번의 Restruction으로 Red Black Tree 규칙이 허용된다.

 

Case2 : Recoloring

다음처럼 입력 노드의 부모의 형제가 Red Node 인 경우

1. 현재 insert 된 노드(6)의 부모와 그 형제(2)를 검정(Black)을 하고 Grand Parent(내 부모의 부모)를 빨강으로 한다.

2. Grant Parent가 Root Node가 아니었을 시 Double Red가 발생 (이 경우 한번더 Recoloring || Restrucuring 실행)

 

input 매커니즘 예제는 다음 블로그 참조

nesoy.github.io/articles/2018-08/Algorithm-RedblackTree

RedBlack Tree에 대해