[자료구조] Red-Black Tree
레드블랙 트리 : B-Tree처럼 밸런스 트리 중 하나이다.
복잡한 자료구조이나, 실 사용에서 효율적이고 최악의 경우에서도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을 때, log(N)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.
레드블랙 트리는 이진검색트리의 모든 노드에 레드 또는 블랙의 색상을 칠한다. 단, 다음의 성질을 만족하도록 색을 칠해야 하는데 이를 레드블랙 특성이라 한다.
- 노드는 레드 혹은 블랙의 색을 가진다.
- 루트는 블랙이다.
- 모든 리프(NIL) 노드는 블랙이다.
- 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. (블랙의 자식은 뭐든 상관없다.)
- 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
먼저 눈에띄는 NIL이 뭐냐면 null값같은 노드이다. 원래 아무것도 없는건데 레드블랙트리에서는 특별히 null노드를 독립된 노드로 취급하고 이것을 리프노드라고 부른다. 또한 리프노드를 제외한 나머지를 내부노드라고 부른다.
1,2,3,4 번 규칙이 성립함은 바로 확인이 가능할 것이고, 5번째 규칙을 보자.
13에서 모든 리프노드로 갈 때 만나는 블랙노드의 수는 3개인 것을 확인할 수 있다. (13→8→1→NIL, 13→8→1→6→NIL, ...)
이 5번째 규칙이 시간복잡도 Log(N)이 됨을 귀납법으로 증명할 수 있다. 하지만 복잡하고 수학적이니 유튜브 영상을 참고하자. (https://www.youtube.com/watch?v=SHdYv41iCmE)
5번째 규칙 때문에 한쪽 트리의 깊이가 깊어지지 않고 밸런스 있게 트리가 구성된다.
레드블랙 트리의 삽입
X 노드를 삽입한다고 하자. X 노드를 삽입할때는 일단 레드로 색을 정하고 넣는다.
그리고 색이 안 맞을 경우 조정하는 과정을 거친다.
삽입에는 크게 4가지 케이스가 있다.
1. X가 루트일때
비어있는 레드블랙 트리에 X가 삽입된 경우이다. Root 노드는 항상 블랙이어야 하니 X를 블랙으로 바꿔주면 끝난다.
2. X의 부모가 블랙일 때
X의 부모가 블랙이고 X는 레드이다. 아무 일도 일어나지 않고 삽입 끝이다.
3. X의 부모가 레드이고 Uncle이 레드인 경우
이렇게 되면 X도 레드 부모도 레드이다. 레드블랙트리의 특징이 깨진다.
비교적 굉장히 간단하다. X를 그대로 레드로 두고 Parent와 Uncle을 블랙으로 바꾸고 GrandParent를 레드로 바꿔주면 된다. Uncle 에게 자식이 있었으면 블랙노드였을 텐데 블랙의 부모는 블랙이어도 상관없으니 문제없다.
또한 GrandParent를 블랙→레드로 바꿔줬기 때문에 5번 규칙도 어기지 않는다.
4. X의 부모가 레드이고 Uncle이 블랙인 경우
여기서는 두가지 케이스로 나뉜다.
1) X-P-G 가 Linear 할 경우
부모노드가 Right Rotation을 한번 하고 색을 규칙에 맞게 바꿔준다.
2) X-P-G 가 Triangle 할 경우
X가 Left Rataion을 한 후, Right Rotation을 또 한다. 그리고 색을 규칙에 맞게 바꿔준다.