레드-블랙 트리(Red-Black Tree)의 특성(조건)
다음의 레드블랙 특성을 만족하는 이진 검색 트리를 레드-블랙 트리라고 한다.
- 모든 노드는 적색이거나 흑색이다.
- 루트는 흑색이다.
- 모든 리프(NIL)는 흑색이다.
- 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
- 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.
회전 (Rotation)
- 레드-블랙 트리의 삽입(insert), delete(삭제) 연산 과정에서 트리가 수정되기 때문에 레드-블랙 트리의 특성을 위반할 수 있다. 이런 특성을 복구해주기 위해서 트리내의 일부 노드들의 색깔과 포인터를 변경해야 한다.
- 포인터를 변경하기 위해 회전을 사용하고, 이것으로 이진 검색트리 특성을 보전한다.
-> 삽입/삭제 과정에서 노드의 추가/삭제 과정이 일어난다. 단순 이진 검색트리는 키값의 비교를 통해 단순히 해당 위치에서 노드를 추가(삭제)하면 되지만, 레드-블랙 트리는 이진 검색트리의 특성을 유지하면서 레드-블랙 트리의 특성에 맞도록 적절히 노드의 색깔과 위치를 바꾸는 과정이 필요하다. 이 과정에서, 회전을 통해 이진 검색트리의 특성을 보전하면서 트리의 구조를 수정할 수 있다.
회전은 이진 검색트리의 특성을 유지하면서 트리의 구조를 수정하는 과정이다. 좌회전 (Left-Rotation)이 일어난 후에도 이진 검색트리의 특성을 유지하는 것을 볼 수 있다.
좌회전 전 (in-order traversal (중위 순회) - 오름차순)
- 𝛼 - x - β - y - 𝛾
좌회전 후 (in-order traversal (중위 순회) - 오름차순)
- 𝛼 - x - β - y - 𝛾
과정
가정 : x 의 오른쪽 자식이 리프노드가 아님. (x -> right != T -> nil)
전체 의사코드
설명
- y = x -> right;
- x -> right = y -> left;
y를 설정, y의 왼쪽 서브트리를 x의 오른쪽 서브 트리로 옮긴다.
- if (y -> left != T -> nil)
y ->left -> parent = x;
- y -> parent = x -> parent;
y의 왼쪽 자식이 있으면 부모노드로 x를 설정,
x의 부모를 y의 부모에 연결.
- if (x -> parent == T -> nil)
T -> root = y;
x의 부모가 nil 이면 x가 루트노드 였다는 소리이므로, 루트노드를 y로 설정.
- else if (x == x -> parent -> left)
x -> parent -> left = y;
- else
x -> parent -> right = y;
x가 루트노드가 아니었다면, 왼쪽자식 이었거나 오른쪽 자식이었을 것이다. 그러므로, x가 어떤 자식이었는지 확인해서 부모노드의 자식을 y로 지정.
- y -> left = x;
- x -> parent = y;
y의 왼쪽 자식을 x로 지정, x 의 부모노드를 y로 지정.
회전이 일어나도 이진 탐색트리의 특성을 유지한다.
-> 노드의 추가/삭제 과정에서, 레드-블랙 트리의 특성을 유지하기 위해 불가피하게 트리의 구조를 수정해야한다. 하지만, 이진 탐색트리의 특성 또한 유지해야하는데, 회전을 이용하여 이진 탐색트리의 특성을 유지하면서 트리의 구조를 수정할 수 있다.
