Red-Black Tree (레드-블랙 트리, RBT)
레드-블랙 트리는 이진 탐색 트리(Binary Search Tree)를 기반으로 하는 트리 형태의 자료구조로, 자가 균형 이진 탐색 트리라고도 부릅니다.
레드-블랙 트리는 다음 조건들을 만족하게 됩니다.
- 모든 노드는 빨간색 또는 검정색이다.
- 루트 노드는 검정색이다.
- 모든 리프 노드는 검정색이다.
- 빨간색 노드의 자식은 모두 검정색이다
No Double Red (빨간색 노드는 연속으로 나올 수 없다)
- 모든 리프 노드에서 Black Depth는 같다
리프 노드에서 루트 노드까지 가는 경로에서 만나는 검정색 노드의 개수는 같다.Black-Height
Red-Black Tree 특징
레드-블랙 트리는 기본적으로 이진 탐색 트리를 기반으로 하기 때문에 이진 탐색 트리의 특징을 모두 가지고 있습니다.
그리고 위 조건들을 모두 만족하게 될 경우 루트 노드로부터 가장 멀리 있는 리프 노드까지의 거리가, 가장 가까운 곳에 있는 리프 노트까지의 거리의 두배보다 항상 작습니다.
즉 최대 경로와 최소 경로의 비율이 2보다 크지 않은 것인데 이러한 상태를 balanced 한 상태라고 말합니다.
삽입 (Insertion)
레드-블랙 트리에서 새로운 노드를 삽입할 때에는 항상 빨간색으로 삽입합니다. 왜냐하면 앞서 설명했던 Black-Height의 변경을 최소화 하기 위해서입니다.
그러나 이렇게 빨간색으로 새로운 노드를 삽입하게 되면 이때의 레드-블랙 트리는 우리가 알고 있는 조건 중 빨간색 노드의 자식은 모두 검정색이라는 조건(즉 빨간색 노드가 두 번 연속될 수 없다는 No Double Red 조건)을 만족하지 못하게 됩니다.
이러한 문제점을 해결하기 위해서는 2가지 방법을 사용하는데,
새로 삽입할 노드를 N, 부모 노드를 P, 조상 노드를 G, 삼촌 노드(부모의 형제)를 U라고 했을 때
삼촌 노드가 검정색일 경우에는 Restructuring, 삼촌 노드가 빨간색일 경우에는 Recoloring을 실행합니다.
위 예시의 경우 삼촌 노드가 검정색입니다. 그러므로 Restructuring 을 실행합니다.
- 삼촌 노드를 제외한 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬
- 중간 값 3을 부모 노드로, 나머지 값을 자식 노드로 설정
- 새로운 부모 노드를 검정색, 나머지를 빨간색으로 설정
Recoloring의 경우에는
- 새로운 노드(N)의 부모(P)와 삼촌(U)를 검정색으로 바꾸고 조상 노드(G)를 빨간색으로 설정
- 그러나 블랙-레드 트리는 루트 노드가 검정색이어야 하는 조건이 있으므로 다시 루트 노드를 검정색으로 설정
- 검정색 노드는 2번이 나와도 상관 없으므로 해당 상태가 Recoloring이 완료된 상태
삭제 (Removal)
레드-블랙 트리는 삭제하려는 대상이 어떤 색인지에 따라 2가지 방법이 있습니다. 첫 번째, 타겟 노드의 색이 빨간색일 경우는 그대로 삭제 합니다.
왜냐하면 타켓 노드의 색이 빨간색 이라는 것은 부모 노드의 색이 검정색이기 때문에 빨간색이 사라지더라도 Double Red 현상이 발생하지 않고, Black-Height에도 아무런 영향을 끼치지 않기 때문입니다.
그러나 타겟 노드 색상이 검정색일 경우, 해당 노드를 삭제학 되면 Black-Height에 균형이 깨지게 됩니다.
이럴 경우 타켓 노드의 조카 노드가 검정색일 경우 타켓 노드의 부모 노드(A)를 기준으로 rotation을 통해 해결합니다.
rotation 후에 target 방향의 Black-Height는 2가 되었기 때문에 target 노드를 삭제하더라도 나머지 Black-Height와의 균형이 맞춰집니다.
조카 노드의 색이 빨간색일 경우 부모 노드(A) 기준으로 회전을 하면 Double Red 현상이 발생합니다. 이럴 때에는 앞서 데이터 삽입에서 처럼 삼촌 노드의 색상을 확인한 뒤 재조정을 해주는데, 지금의 경우 삼촌 노드(D)의 색상이 빨간색이기 때문에 부모 노드와 삼촌 노드는 모두 검정색으로, 기존에 있던 Red를 위로 올려주면서 해결할 수 있습니다.
