[알고리즘-이론] 레드 블랙 트리(Red-Black Tree)

---

레드-블랙 트리(Red-Black Tree)

이진 검색 트리에서 시간 복잡도는 O(log n)이 될 수도 있고 O(n)이 될 수도 있다고 하였는데 이는 트리의 높이에 따라 결정된다고 했다.

 

이러한 단점들을 극복하기 위해서 고안해 낸 것은 바로 ==균형잡힌 이진 검색 트리== 이다. 균형잡힌 이진 검색 트리란 것은 최악의 경우 에도 이진 트리의 균형이 맞게 유지되도록 하는 것을 뜻한다.

 

레드 블랙 트리는 이진 검색 트리의 모든 노드에 레드 또는 블랙의 색상을 칠하는데 다음과 같은 성질을 만족해한다.

• 1. Root Property: 루트는 블랙이다.

• 2. External Property: 모든 리프(NIL)는 블랙이다.

• 3. Internal Property: 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. (레드 노드가 연속으로 나올 수 없다.)

• 4. Depth Property: 루트 노드에서 임의의 리프노드에 이르는 경로에서 만나는 블랙의 노드의 수는 모두 같다 (모든 리프 노드에서 BlackDepth는 모두 같다)

레드 블랙 트리에서는 이진검색트리의 노드가 가진 두 개의 자식중 NIL인 것이 있으면 노드를 하나 만들고 그 것을 리프노드라고 한다. 하지만 실제 구현할 떄는 모든 NIL 리프에 대한 포인터가 하나의 노드를 할당하고 그 곳에 NIL을 준 곳으로 향하게 하면 된다.

 

레드 블랙 트리에서의 검색

 

레드 블랙 트리는 이진 검색 트리와 같지만 균형을 맞춘것 이므로 검색의 방법은 똑같다.

 

레드 블랙 트리에서의 삽입

 

레드 블랙 트리에서는 새로운 노드를 삽입할 때 먼저 이진 검색 트리의 삽입 알고리즘에 따라 삽입한 뒤 새 노드의 색상을 레드로 칠한다. 이 노드를 x라고 하자.

새 노드 x는 항상 리프 노드(블랙)에 매달리므로 아래는 레드가 오건 블랙이 오건 상관 없지만 x의 위쪽과 관련해서 문제가 생기는지 확인해야한다.

새 노드x의 부모 노드 p 가 블랙인 경우는 삽입이 완료 되지만 문제는 부모 노드p가 ==레드==인 경우 문제가 생긴다.

경우를 나눠서 생각해보자

1. p가 블랙일 때

• 레드-블랙 트리의 조건이 만족하기에 삽입이 가능

2. p가 레드일 때

• 레드가 2개 연속이므로 특성3(Internal Property)를 위반한다.
• 그런데 삽입 전에는 레드-블랙 트리였으므로 특성3에 따라 p의 부모 노드는 반드시 블랙이다.
• 마찬가지고 특성 3에 따라 x의 형제 노드도 반드시 블랙이다.