레드 블랙(Red Black) 트리란?
-
레드 블랙 트리는 이진트리이자, 균형을 갖춘 트리이다.
-
C++의 map이 레드 블랙 트리 기반이다.
규칙
- 모든 노드는 Red나 Black의 색깔을 갖는다.
- Root 노드는 항상 Black이다.
- 모든 Leaf 노드는 센티넬 노드(Sentinel Node)로서 Black이다.
- Red 노드의 자식은 모두 Black이다.
- Black 노드의 자식은 Black/Red 모두 가능
- 루트(Root)에서 Leaf로의 경로를 생각할 때, 모든 경로에 대해서 Black의 숫자는 같다.
이것을 Black Height라고 한다.
- 3번 규칙은 특정 값의 딸려있는 좌우값이 Black이라는 뜻이다. 헷갈리지 않도록 하자 !
-
역시 말 보단 그림을 통해 이해를 해보자.
-
그전에 Restructuring과 Recoloring 작업에 대해서만 알아보도록 하자.
-
두 개의 차이는 삼촌 노드의 색에 유무에 따라 달라진다.
-
자기,부모 노드가 Red일 때
삼촌이 Black이면 Restructuring
삼촌이 Red이면 Recoloring -
이것만 인지하고 예시를 통해 레드 블랙 트리를 구성해보자.
동작 과정
다음 값으로 레드 블랙 트리를 구성해 보자.
100 150 200 300 175 180 190 160
- 예제가 이해가 안된다면 레드 블랙 트리에 값을 넣으며 어떤식으로 동작하는지 시각적으로 볼 수 있는 시뮬레이터 사이트를 통해 이해해보도록 하자.
- 100이 추가되면서 루트가 검정색이 된다.
- 삽입되는 노드는 빨간색이므로 150은 루트보다 값이 크기에 우측에 위치한다.
- 200이 추가 되면서 Doble Red 현상이 발생되고 Restructuring 작업이 이뤄졌다.
- 300이 추가 되면서 또다시 Doble Red 현상이 발생되고 이 때는 Recoloring 작업이 이뤄졌다.
- 175는 단순 삽입을 하는 과정을 거친다.
- 180이 추가되면 Recoloring 작업이 이뤄진다.
-
190이 추가되면 Restructuring 작업이 이뤄진다.
-
그래서 175 180 190을 오름 차순으로 정렬 한 후 가운데 : 검정, 나머지 : 빨강 색으로 칠한다.
-
대망의 160 삽입이다.
-
Restructuring과 Recoloring 작업이 연쇄적으로 이뤄지게된다.
-
우선 Recoloring 작업이 이뤄진다.
-
175 190은 검정으로
-
180은 빨간색으로 바뀌게 된다.
-
바뀐 후 엔 180과 200이 Doble Red이므로 Restructuring 작업이 이뤄진다.
-
Why? 180의 삼촌 노드이면서 200의 형제 노드인 100이 검정이기 때문이다.
- 150 180 200을 오름 차순으로 정렬 한 후 가운데 : 검정, 나머지 : 빨강 색으로 칠한다.
-
완성된 Red Black Tree를 볼 수 있다.
-
여기까지 이해했다면 Red Black Tree를 구성하는데 Restructuring과 Recoloring 작업 과정을 이해했다 볼 수 있다.
-
매우 매우 축하한다 !
Red Black vs AVL Tree
-
AVL trees provide faster lookups than Red Black Trees because they are more strictly balanced.
-
Red Black Trees provide faster insertion and removal operations than AVL trees as fewer rotations are done due to relatively relaxed balancing.
-
AVL trees store balance factors or heights for each node, thus requires O(N) extra space whereas Red Black Tree requires only 1 bit of information per node, thus require O(1) extra space.
-
Red Black Trees are used in most of the language libraries like map, multimap, multiset in C++ whereas AVL trees are used in databases where faster retrievals are required.
추가 정리
Case 1. 조상이 루트일시
-
위 상황에서 4가 들어온다면 Recoloring 작업이 이뤄진다.
-
이 때 규칙을 따르면
1,3은 검정색으로
2는 빨간색으로 바뀌어야 하지만
그렇게 되면 루트는 검정이라는 조건에 위배되기 때문에
루트를 다시 빨 -> 검으로 색을 칠한다.
Case 2. 조상이 루트가 아닐 시
-
위 상황에서 18이 들어온다면 Recoloring 작업이 이뤄진다.
-
이 때는 조상이 루트가 아니기 때문에
11과 17은 검정색으로
15는 빨간색으로 Recoloring을 하게 된다.
