[DS] 레드블랙트리

이진탐색트리(Binary Search Tree)

- 최대 자식노드를 2개 갖는 이진트리

- 정렬된 상태로 유지되기 때문에 탐색 효율이 좋음 (중위순회시 정렬된 상태로 출력됨)

- Balanced Tree가 아니기 때문에 극단적으로 모든 노드가 자식노드를 1개씩만 갖게 되면 O(n) 성능을 보임

 

Red-Black Tree

- 이진탐색트리의 일종이지만 Balanced Tree이기 때문에 성능을 O(logN)으로 보장함

- 이진탐색트리의 일종이므로 왼쪽 서브트리의 모든 값은 오른쪽 서브트리의 모든 값보다 작아야 함(정렬됨)

- Red-Black Tree는 이진탐색트리 중에서 성능이 가장 좋다.

- 따라서 리눅스 커널의 프로세스 관리, Java 8이상 HashMap에서 해쉬 블록의 value, 함수형 프로그래밍 등에서 많이 사용되는 트리이다.

 

1) 조건

- Root Property : root노드의 색깔은 검정이다.

- External Property : 모든 leaf 노드(external 노드)는 검정이다.

- Internal Property : 빨간 노드의 자식은 검정이다. (No Double Red : 빨간 노드가 연속으로 나올 수 없다.)

- Depth Property : 모든 leaf 노드에서의 black depth는 같다.

 

cf. black depth : leaf 노드에서 root 노드로 가는 중에 만나는 블랙 노드의 개수

 

** 위와 같은 네 가지의 조건을 만족하도록 트리 구조를 유지하면 depth를 항상 logN에 바운드하게 한다.

 

2) Double Red가 발생했을 때 해결법

1) Restructuring 

- 트리 구조를 바꾸는 작업으로 Restructuring 자체는 O(1)이 소요되지만 Restructuring이 발생하려면 데이터 삽입 또는 삭제가 발생해야 하기 때문에 데이터 삽입/삭제 + Restructuring 은 O(logN)이다.

- Restructuring은 한 번만 실행되더라도 다른 서브트리에 영향을 주지 않으므로 트리 재구성이 완성된다.

 

2) Recoloring

- 한 번에 안 끝날 가능성이 있다. 즉, Recoloring을 한번 한 후의 구조에서 또 다시 Double Red가 발견될 수 있다.

- 이러한 특성은 최악의 경우 root 노드까지 전파된다.

- Recoloring 한 번자체는 O(1)이 소요되지만 root까지 전파될 경우 O(logN) 성능을 보인다.

 

** 결론: Red-Black Tree에 삽입 연산을 할 경우 Double Red가 발생할 수 있고 이를 해결하기 위해 Restructuring 또는 Recoloring을 하며 두 경우 모두 O(logN) 성능을 보인다. 따라서 Red-Black Tree에 대한 삽입 연산의 성능은 O(logN)이다.

 

 

cf. 리눅스 커널에서 사용하는 레드블랙트리

- task_struct 구조체를 노드로 해 task들을 관리함

https://ddmix.blogspot.com/2015/02/cppalgo-19-red-black-tree.html

 

 

cf. Java 8이상 버전에서의 HashMap.

- 해쉬 버킷에 충돌이 발생할 경우, HashMap은 기본적으로 Separate Chaining 방식으로 충돌을 처리하기 때문에 버킷에 여러 데이터들이 들어간다. 이때 그 개수가 8개 이상인 경우에 대해 버킷 데이터들을 Red-Black Tree로 관리한다.

 

 

https://medium.com/@harmeetkaur2793/hashmap-interenal-working-362c0ba7d854

 

 

Red-Black Tree를 사용하는 이유

- 기본적으로 Tree에서 O(logN) 성능을 보이기 위해서는 균형이 있느냐 없느냐가 매우 중요함

- 레드블랙트리는 항상 균형을 유지하기 때문에 O(logN) 을 보장함

- Double Red 발생은 트리 구조가 변경될 때 발생할 수 있으며 이를 해결하기 위한 Restructuring, Recoloring 모두 O(logN) 성능을 가짐

- 따라서 레드블랙트리는 어떠한 경우에도 O(logN)을 보장하기 때문에 성능이 좋음

 

cf. 데이터베이스 인덱스에서 Red-Black tree를 사용하지 않고 B-Tree를 사용하는 이유 :

- 레드블랙트리도 정렬을 유지하지만, B-Tree와의 가장 큰 차이점은 한 노드당 데이터의 개수이다.

- B-Tree의 경우 한 노드당 데이터를 2개 이상 넣을 수 있고 배열로 관리한다.

- 따라서 간단한 포인터연산으로 빠르게 데이터를 가져올 수 있다. (CPU를 덜 사용함)

- 이러한 특징은 범위 탐색 연산에서도 효율적이다.

- 또한 같은 양의 데이터를 Red-Black Tree에 넣는 것보다 B -ree에 넣는 것이 tree의 depth가 더 낮다.

 

 

Reference

- 레드블랙트리 시뮬레이터 https://www.cs.usfca.edu/~galles/visualization/RedBlack.html