[ Tree ] 레드-블랙 트리

레드-블랙 트리란?

레드-블랙 트리란 BTS의 일종으로, BTS의 최악의 시간복잡도 O(n)을 방지하기 위해 균형을 유지하게 하는 균형 이진 탐색트리 중 하나입니다.

FunctionSearchInsertDelete

Function	Amortized	Worst Case
Select	O(log⁡n)	O(log⁡n)
Insert	O(log⁡n)	O(log⁡n)
Delete	O(log⁡n)	O(log⁡n)

 

레드-블랙 트리의 속성

레드-블랙 트리의 노드들은 red 또는 black색을 가지며, 아래와 같은 5가지 특징을 준수하여 균형을 이룹니다.

1. 모든 노드는 red 혹은 black이다.
2. 루트 노드는 black이다.
3. 모든 리프 노드( NIL )는 black이다.
4. red 노드의 자식 노드는 항상 black이다.
5. 모든 노드에서 리프 노드들 까지 가는 경로에 존재하는 black노드의 수는 같다. ( 검색 시작 노드 제외 )

---

데이터 삽입

우선 레드-블랙 트리에서 삽입하는 노드의 색은 항상 red입니다.

 

데이터 삽입 과정 중 레드 - 블랙 트리의 속성에 위배하는 경우 Rebalancing과정을 거치게 됩니다.

Rebalancing은 색변경(Recoloring)과 회전(Rotation) 과정으로 이루어져 있으며, 케이스에 따라 두 가지 방법을 혼합하여 적용하면 레드 - 블랙 트리의 속성을 위반하지 않게 만들 수 있습니다.

 

아래에 삽입 시 발생할 수 있는 케이스에 대해 알아보고 또한 Rebalancing과정이 어떻게 이루어질 수 있는지 알아보도록 하겠습니다.

Case1. Root 삽입

맨 처음 Root에 데이터를 삽입하는 Case입니다.

 

데이터 삽입 시 들어오는 노드의 색은 항상 red로 고정되어 있기 때문에 삽입된 노드의 색상은 red입니다.

이때, 레드-블랙 트리 2번째 속성 'root는 black이다'를 위반하기 때문에 Recoloring과정을 통해 black으로 변경하여 줍니다.

---

Case2. 삽입한 노드의 부모 노드가 black인 경우

데이터 삽입 시 삽입되는 노드의 색상은 red이고, 위반하는 규칙은 존재하지 않습니다.

---

Case3. 부모 노드가 red이고, 한쪽으로 쏠린 경우

1을 삽입하게 되면 위 사진의 첫번째와 같이 red하위에 red가 존재하는 양상의 띄게 되며 그와 동시에 4번 속성을 위반하게 됩니다.

 

그럴경우 부모노드 색을 black으로 조부모 색을 red로 변경해줍니다.

그 다음 왼쪽으로 쏠림현상이 존재하므로 5를 기준으로 오른쪽으로 회전하여 2가 root에 위치하도록 합니다.

 

수정 후 모습을 보면 4번 속성을 위반하지 않고, 2번 속성도 위반하지 않는 것을 확인 할 수 있었습니다.

---

Case4. 부모노드가 red이고, 한쪽으로 몰려있으며, 오른쪽으로 꺾인 경우

3을 삽입하게 되면 오른쪽으로 꺾이게 됩니다.

이때 삽입한 노드를 기준으로 좌로 회전합니다.

 

이후 root와 삽입한 노드의 색을 바꿔주고, root를 기준으로 오른쪽으로 회전합니다.

---

Case5. 부모노드가 red이고, 삼촌노드도 red인 경우

6을 삽입하였습니다.

우선 4번 속성을 위반하기 때문에 부모와 삼촌 노드의 색을 black으로, 조상 노드의 색을 red로 변경합니다.

 

이후 2번 속성을 위반하였기 때문에 루트 노드의 색을 black으로 변경해줍니다.

 

이때 black 하위 black인 경우가 생기게 되는데, 이는 속성을 위반하는 사항이 아니므로 괜찮습니다.

---

이후 많은 다양한 상황들이 나올 수 있지만, 위 케이스들을 기반으로 비교하면 레드-블랙 트리의 속성을 지키며, 작업을 이어나갈 수 있게 됩니다.

---

레드-블랙 트리  VS AVL 트리

레드 블랙 트리를 왜 사용하는지, 그리고 AVL 트리와의 차이는 어떤 점들이 존재하는지 알아보도록 하겠습니다.

	레드-블랙 트리	AVL 트리
삽입/삭제 속도	더 빠름 (재조정이 덜 복잡함)	느림 (더 엄격한 균형 유지)
검색 속도	약간 느림 ( 완벽한 균형 x )	더 빠름 (더 균형 잡힘)
구현 난이도	상대적으로 단순	더 빠름(더 균형 잡힘)
적합한 용도	삽입/삭제가 잦은 경우	일기 성능이 중요한 경우
사용처	TreeMap, TreeSet,...	Index, Cache,...

---

Reference

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

https://www.youtube.com/watch?v=2MdsebfJOyM