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

레드 블랙 트리가 나온 이유

Red-Black tree 는 이진 검색 트리를 기반으로 한 자료구조이다.이진 검색 트리는 한쪽으로 치우쳐 질 경우 검색에서의 시간 복잡도가 O(N)으로 증가하는 문제가 있다. 이를 해결하기 위한 것이 레드-블랙 트리이다.

레드 블랙 트리의 조건

각 노드는 자료구조의 이름에서 알 수 있듯이 검은색, 빨간색으로 표기되고 다음과 같은 조건을 만족한다.

1. 루트 노드는 검은색이다.

2. 모든 리프 노드들은 검은색이다.

3. 빨간색 노드의 자식은 검은색이다. ( 빨간색 노드가 연속으로 나올 수 없다. )

4. 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수는 같다.

레드 블랙 트리의 장점

레드 블랙 트리는 리프 노드까지 경로의 노드 색을 제한함으로써 리프 노드 까지의 Depth에 대해 ReColoring과 ReStructuring을 통해 균형을 맞춰주므로 검색 시간이 O(log n)으로 효율적인 연산이 가능하다.

* ReStructuring : 새로운 노드를 삽입하거나 기존 노드를 삭제하고나서 트리의 균형을 유지하기 위해 수행되는 연산이다.
Left-Rotation과 Right-Rotation 두 가지 연산을 통해 균형이 맞춰지고 색깔의 변화는 일어나지 않는다.

Left-Rotation: 트리에서 오른쪽 자식 노드가 새로운 부모 노드가 되고, 새로운 부모의 왼쪽 자식이 기존 부모 노드가 된다.
Right-Rotation: 트리에서 왼쪽 자식 노드가 새로운 부모 노드가 되고, 새로운 부모의 오른쪽 자식이 기존 부모 노드가 된다.

* ReColoring : 레드 블랙 트리는 밑의 조건을 만족한다. 그래서 빨간색 노드가 연속으로 만들어질 경우 색을 다시 칠해서 균형을 맞춰주는 과정이 필요하다.

Case 1: 노드 X의 색깔이 레드이고, 노드 X의 부모 노드 P와 형제 노드 S가 모두 레드인 경우, P와 S의 색깔을 블랙으로 변경하고, P의 부모 노드를 새로운 노드 X로 설정된다.
Case 2: 노드 X의 색깔이 레드이고, 노드 X의 부모 노드 P의 색깔이 블랙이고, X의 형제 노드 S의 색깔이 블랙인 경우, S와 S의 자식 노드의 색깔을 레드로 변경하고, P를 새로운 노드 X로 설정된다.

레드 블랙 트리 시뮬레이션

아래의 사이트에서 시뮬레이션을 돌려볼 수 있다.

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

 

 

B트리와의 비교

B트리는 InnoDB 와 같은 데이터베이스 스토리지 엔진에서 많이 사용하는 자료 구조이다. 빠른 속도로 데이터를 찾을 수 있고 균형을 맞춰준다는 점이 같지만 사용하는 용도가 다르다.

위 시뮬레이션을 돌려보면 알 수 있듯, 레드-블랙 트리의 각 노드에 존재하는 키값은 하나이다. B트리같은 경우에는 각 노드의 키의 개수를 설정할 수 있어 더 큰 데이터를 다루는데 적합하다. 그래서 B트리는 데이터베이스와 같은 대규모 데이터를 처리하는데 사용되고, 레드-블랙 트리같은 경우에는 적은 데이터 ( 메모리, 캐시, 리눅스 커널 등 )를 다루는데 적합하다.

레드-블랙 트리를 사용한 오픈소스 예시

1. 리눅스 커널.
2. nginx - 레드-블랙트리를 사용하여 요청을 처리하고 로드 밸런싱을 수행함.
3. Redis - 레드-블랙 트리를 사용하여 정렬된 데이터 형식을 구현함.
4. C++ STL의 MAP, SET, MULTIMAP 등
5. Java Collections 라이브러리의 TreeMap, TreeSet
6. SQLite ( 내장형 데이터베이스, 주로 안드로이드와 같은 소규모 데이터베이스가 필요한 곳에서 사용된다고 알고 있음 )의 인덱싱

 

 

 

https://code-lab1.tistory.com/62