[자료구조] 레드-블랙 트리(red-black tree)

* @참고: https://www.youtube.com/watch?v=2MdsebfJOyM

 

레드-블랙 트리: 자가 균형 이진 탐색 트리
숫자 등의 비교 가능한 자료를 정리하는데 쓰임.

레드-블랙 트리에서는 리프 노드들은 비어있고, 자료를 가지고 있지 않다... NIL 로 리프노드를 가진다.

내 자료는 나보다 오른쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 작거나 같고,
나보다 왼쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 크거나 같다.

장점: worst-case guarantees
삽입, 삭제 시 O(log n)만큼의 시간이 필요

연산: 색 전환(color-flipping), 회전(rotation)

레드-블랙 트리의 가장 중요한 특성: 루트 노드로부터 가장 먼 리프노드 경로까지의 거리 < 가장 가까운 리프노드 까지의 거리 * 2
-> roughly 하게 균형 잡힘!!

** 레드 노드의 자식노드는 언제나 블랙!! 레드는 연달아 나타날 수 없고, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있음.


1. 노드는 레드 또는 블랙
2. 루트 노드는 블랙
3. 리프 노드들은 블랙
4. 레드 노드의 자식노드 2은 모두 블랙
5. 어떤 노드로부터 리프 노드에 도달하는 모든 경로에서 자기자신을 제외하고 모두 같은 개수의 블랙 노드 존재


* 삽입 노드의 색: red -> 이유: 5번을 만족하기 위해