레드블랙 트리의 특성
레드블랙 트리는 루트에서 리프까지의 경로에 나타나는 노드의 색깔을 제한함으로써 그러한 경로 중 어떠한 것도 다른 것보다 두 배 이 상 길지 않음을 보장하게 되는데, 이로써 트리는 근사적으로 균형을 이룬 트리가 된다.
트리는 각 노드의 color, key, left, right, p 등의 필드를 가진다.
한 노드의 자식 또는 부모가 존재하지 않으면 그에 대응되는 노드의 포인터 필드는 NIL값으로 채워진다.
이런 NIL들은 이진 검색 트리의 리프 노드들에 대한 포인터들로 간주하고, 키를 가지는 정상적인 노드들은 트리의 내부 노드로 간주할 것이다.
sentinel(경계 노드)
경계 노드 T.nil은 트리의 다른 보통의 노드와 마찬가지로 동일한 필드를 가진다.
이 노드의 color 필드는 흑색이지만, p, left, right, key 등의 필드 값은 의미를 갖지 않는다. 모든 nil을 가리키는 포인터는 경계 노드 T.nil을 가리키도록 변경된다.
경계 노드를 이용함으로써 노드 x의 nil 자식을 x의 정상적인 자식 노드와 동일하게 다룰 수 있게 된다.
트리 내 각각의 nil을 위해서 개별적인 경계 노드를 사용할 수도 있지만 이렇게 하면 저장 공간이 낭비된다. 대신 하나의 경계 노드 T.nil을 두어서 모든 NIL, 즉 모든 리프와 루트의 부모를 표현하게 된다.
경계 노드의 필드 p, left, right, key 등은 프로시저의 수행 과정에서 값이 채워질 수도 있으나 이는 의미를 갖지 않는다.
레드블랙 트리에서 관심 대상은 키값을 가지는 내부 노드다. 따라서 리프 노드를 생략하여 레드블랙 트리를 그린다!
회전 (Rotation)
-
RB tree의 insert와 delete 연산 과정에서 O(logn) 시간에 수행된다. 이 과정에서 트리가 수정되기 때문에 레드블랙 트리의 특성을 위반할 수 있다. 이런 특성을 복구해주기 위해서 트리 내의 일부 노드들의 색깔과 포인터를 변경해야 한다.
-
포인터를 변경하기 위해 회전을 사용하는데, 이것은 이진 탐색 트리의 특성을 보전해준다.
회전의 종류에는 좌회전, 우회전 이 있다.
가정: 노드 x에 대해서 좌회전 적용 시 오른쪽 자식 y는 T.nil이 아니며 x는 오른쪽 자식이 T.nil이 아닌 모든 노드에 해당한다. 좌회전은 x와 y를 연결하는 링크를 중심축으로 하여 적용된다. (x->right != t->nil)
그 결과 y는 서브 트리의 새로운 루트가 되며, x는 y의 왼쪽 자식이 되고 y의 왼쪽 자식은 x의 오른쪽 자식이 된다.
left_rorate 슈도코드
작성한 코드
// 좌회전
void left_rotation(rbtree *t, node_t *x) {
node_t *y = x->right; // y는 현재 x의 오른쪽 자식 노드
x->right = y->left; // y의 왼쪽 서브 트리를 먼저 떼서 x의 오른쪽 자식에 붙여줌
if (y->left != t->nil) // 왼쪽 자식 노드가 있으니까
y->left->parent = x; // 그 자식의 부모를 x로 변경
y->parent = x->parent; // x의 부모를 y로 연결 (좌회전시킴)
// x의 위치 잡아주는 조건문 -> 원래 x자리에 y를 넣어주기 위해서
if (x->parent == t->nil) // x의 부모가 nil이라면 (루트면)
t->root = y; // 트리의 루트를 y로 변경
else if (x == x->parent->left) // x가 왼쪽 자식이라면
x->parent->left = y; // x의 부모의 왼쪽자식을 y로 변경
else // x가 오른쪽 자식이라면
x->parent->right = y; // x의 부모의 오른쪽을 y로 변경
y->left = x; // y의 왼쪽자식 x로
x->parent = y; // x의 부모를 y로
return;
}
// 우회전
void right_rotation(rbtree *t, node_t *x) {
node_t *y = x->left; // y는 현재 x의 왼쪽 자식 노드
x->left = y->right; // y의 오른쪽 서브트리를 먼저 떼서 x의 왼쪽 자식에 붙여줌
if (y->right != t->nil)
y->right->parent = x;
y->parent = x->parent; // x의 부모를 y로 연결 (우회전시킴)
// x의 위치 잡아주는 조건문 -> 원래 x자리에 y를 넣어주기 위해서
if (x->parent == t->nil) // x가 루트일 때
t->root = y;
else if (x == x->parent->left) // x가 왼쪽 자식일 때
x->parent->left = y;
else // x가 오른쪽 자식일 때
x->parent->right = y;
y->right = x; // y 위치 고정된 후 y의 오른쪽 자식 x로 변경
x->parent = y;
return;
}회전은 이진 탐색 트리의 특성을 유지하면서 트리의 구조를 수정하는 과정이다.
rotation이 일어난 후에도 이진 탐색 트리의 특성을 유지하는 것을 볼 수 있다.
좌회전(left-rotation) 예시
- before left-rotate
𝛼 - x - β - y - 𝛾
- after left-rotate
𝛼 - x - β - y - 𝛾
