Algorithm/그밖에2
Red-Black Tree
previc
2018. 8. 7. 14:51
Red-Black Tree
특징
- 모든 node는 BLACK 또는 RED의 색을 가진다.
- root node는 항상 BLACK이다.
- leaf node도 항상 BLACK이다.
- RED가 연속되어 있을 수 없다. (부모-자식간)
- root node부터 leaf node사이의 BLACK의 개수는 동일하다.
- self-balancing BST로 일반 BST와 다르게 5번 규칙에 의해 skewed binary tree가 되지 않음이 보장된다. (삽입/삭제 O(lgN) 보장)
동작
- 색상을 RED = 0, BLACK = 1, DOUBLE-BLACK = 2로 생각하면 이해하기 편하다.
조회
- BST와 동일하게 수행
삽입
새로 삽입되는 노드는 항상 RED로 시작한다.
부모노드가 조부노드의 왼쪽 자식인 경우를 가정하고 설명(오른쪽일 경우 대칭적으로 수행)
- 부모노드가 RED인 경우
1-1. 삼촌노드가 RED인 경우
조부노드는 BLACK이므로, 조부노드의 BLACK을 삼촌과 부모노드로 내리고 조부노드를 RED로 바꾼다. 즉, 삼촌=부모=BLACK, 조부=RED
grand(B) grand(R)
/ \ / \
parent(R) uncle(R) => parent(B) uncle(B)
/ /
new_node(R) new_node(R)
조부노드가 RED가 되었으므로 조부노드를 기준으로 삽입규칙을 만족하는지 다시 확인한다.(루트에 도달할 시 BLACK으로 바꾸고 종료)
1-2. 삼촌노드가 BLACK인 경우
1-2-1. 새로 삽입한 노드가 부모노드의 오른쪽 자식인 경우
새로 삽입한 노드 기준 시계 반대방향 회전 후 parent기준 1-2-2케이스로 이동
new_node(R)
parent(R) /
/ \ -> parent(R)
left_son(B) new_node(R) /
left_son(B)
1-2-2. 새로 삽입한 노드가 부모노드의 왼쪽 자식인 경우
새로 삽입한 노드의 부모를 BLACK으로, 조부노드를 RED로 반전시키고 부모기준 시계방향 회전
grand(B)
/ parent(B)
parent(R) -> / \
/ new_node(R) grand(R)
new_node(R)
- 부모 노드가 BLACK인 경우 -> DONE
삭제
삭제가 일어나면 그 위치를 대체하는 노드는 BST에서의 삭제연산과 동일한 방법으로 찾는다.
대체할 노드는 삭제된 노드의 색으로 변경하여 삭제된 노드의 자리에 삽입한다. (엄밀히 말하면 삭제된 노드의 색을 대체할 노드의 색상에 추가한다.)
삭제된 노드가 RED인경우 -> DONE
삭제된 노드가 BLACK인경우
2-1. 대체할 노드의 기존 색이 RED인 경우 -> DONE
2-2. 대체할 노드의 기존 색이 BLACK인 경우
삭제된 노드의 색을 DOUBLE-BLACK으로 바꾸고 다음 케이스별로 처리한다.
DOUBLE-BLACK노드가 부모의 왼쪽인 경우를 가정하고 설명(오른쪽일 경우 대칭적으로 수행)
2-2-1. DOUBLE-BLACK 노드의 형제가 RED인 경우
- 부모의 색을 RED, 형제의 색을 BLACK으로 반전 후, 형제 기준 시계반대방향으로 회전한다. DOUBLE-BLACK노드 기준 2-2-2케이스로 이동
brother_node(B)
parent(B) /
/ \ -> parent(R)
new_node(BB) brother_node(R) /
new_node(BB)
2-2-2. DOUBLE-BLACK 노드의 형제가 BLACK인 경우
2-2-2-1. 형제의 양쪽 자식이 모두 BLACK인 경우
DOUBLE-BLACK노드와 형제노드의 BLACK을 부모에게 전달한다.
parent(?) parent(?+B)
/ \ / \
new_node(BB) brother_node(B) -> new_node(B) brother_node(R)
/ \ / \
left_son(B) right_son(B) left_son(B) right_son(B)
만약 부모노드의 기존 색이 RED였다면 BLACK으로 변하고 종료되지만, 기존 색이 BLACK이었다면 DOUBLE-BLACK으로 바꾸고 부모노드 기준으로 다시 DOUBLE-BLACK을 처리한다. (루트가 DOUBLE-BLACK인경우 BLACK으로 바꾸고 종료)
2-2-2-2. 형제의 왼쪽 자식이 RED, 오른쪽 자식이 BLACK인 경우
형제의 왼쪽자식과 형제노드를 각각 BLACK, RED로 반전시키고, 형제의 왼쪽자식 기준으로 우회전 한다. 2-2-2-3케이스로 이동
parent(?) parent(?)
/ \ / \
new_node(BB) brother_node(B) new_node(BB) left_son(B)
/ \ -> \
left_son(R) right_son(B) brother_node(R)
\
right_son(B)
2-2-2-3. 형제의 왼쪽자식이 BLACK, 오른쪽 자식이 RED인 경우
형제노드 기준으로 시계반대방향으로 회전한 뒤, (변경 전 기준)부모노드의 색을 형제노드에게, 부모노드와 오른쪽 자식을 BLACK으로 변경한다.
parent(?) brother_node(B) brother_node(?)
/ \ / \ / \
new_node(BB) brother_node(B) -> parent(?) right_son(R) -> parent(B) right_son(B)
/ \ / \ / \
left_son(B) right_son(R) new_node(BB) left_son(B) new_node(BB) left_son(B)