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

레드 블랙 트리는 C++ STL의 Map과 Set의 기반이 되는 알고리즘이다. 레드 블랙 트리가 형성되는 과정을 알아보겠다. 레드 블랙 트리는 자가 균형 이진 탐색 트리이며 아래의 조건들을 만족해야 한다. 1. 모든 노드는 빨간색 혹은 검은색이다. 2. 루트 노드는 검은색이다. 3. 모든 리프 노드들은 검은색이다. 4. 빨간색 노드의 자식은 검은색이다. (Double Red 금지) 5. 모든 리프 노드에서 Black Death는 같다. (루트 노드까지 가는 경로 중 거치는 검은색 노드의 수가 같다.) 추가로 삽입되는 노드는 모두 빨간색으로 설정하며 삽입 시 루트 노드부터 작은 값은 왼쪽 자식이 되고, 큰 값은 오른쪽 자식이 된다. 4번의 빨간색 노드의 자식으로 빨간색 노드가 온다면 더블 레드가 발생하는데 이를 방지하기 위해 두가지 방법이 있다. 우선 새로 삽입한 노드를 N 새로 삽입한 노드의 부모 노드를 P 새로 삽입한 노드의 조상 노드(부모 노드의 부모 노드)를 G 새로 삽입한 노...

원문링크 : 레드 블랙 트리(Red - Black Tree)