2019. 4. 15. 20:30ㆍ알고리즘
레드블랙트리
이진탐색트리는 저장과 검색에 평균 O(logn)시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 잘 이루지 못한다.
균형이 많이 깨지면 O(n)에 근접한 시간이 소요될 수도 있다. 그래서 고안해낸 것이 균형잡힌 이진 검색 트리이다.
특성
레드-블랙 트리는 각각의 노드가 레드 나 블랙 인 색상 속성을 가지고 있는 이진 탐색 트리이다. 이진 탐색 트리가 가지고 있는 일반적인 조건에 다음과 같은 추가적인 조건을 만족해야 유효한(valid) 레드-블랙 트리가 된다
- 노드는 레드 혹은 블랙 중의 하나이다.
- 루트 노드는 블랙이다.
- 모든 널 포인터는 블랙이다.
- 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
- 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.
위 조건들을 만족하게 되면, 레드-블랙 트리는 가장 중요한 특성을 나타내게 된다: 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배 보다 항상 작다. 다시 말해서 레드-블랙 트리는 개략적(roughly)으로 균형이 잡혀 있다(balanced). 따라서, 삽입, 삭제, 검색시 최악의 경우(worst-case)에서의 시간복잡도가 트리의 높이(또는 깊이)에 따라 결정되기 때문에 보통의 이진 탐색 트리에 비해 효율적이라고 할 수 있다.
왜 이런 특성을 가지는지 설명하기 위해서는, 네 번째 속성에 따라서, 어떤 경로에도 레드 노드가 연이어 나타날 수 없다는 것만 알고 있어도 충분하다. 최단 경로는 모두 블랙 노드로만 구성되어 있다고 했을 때, 최장 경로는 블랙 노드와 레드 노드가 번갈아 나오는 것이 될 것이다. 다섯 번째 속성에 따라서, 모든 경로에서 블랙 노드의 수가 같다고 했기 때문에 존재하는 모든 경로에 대해 최장 경로의 거리는 최단 경로의 거리의 두배 이상이 될 수 없다.
회전
레드 블랙 트리에 새로운 값이 삽입되거나 삭제가 되었을 때 레드 블랙 트리의 특징이 깨지게 되는 경우가 존재한다.
레드블랙트리의 특징을 보존(?)시키기 위해 '회전'연산을 수행한다.
우회전, 좌회전 총 두 가지 회전 연산을 과정이 존재한다.
우회전
우회전이 되는 과정이다.
루트였던 13이 10으로 변경되고, 13이 10의 오른쪽 자식으로 들어가게 된다.
주목해서 봐야 되는 부분은 13이 10의 오른쪽 자식으로 변경되면서 13이 12의 왼쪽 자식으로 옮겨진다는 점이다.
즉, 우회전을 할 때는 왼쪽 자식(10)의 오른쪽 자식(12)이 부모 노드(13)의 왼쪽 자식으로 옮겨진다는 것을 알 수 있다.
이제 다음으로 좌회전을 시켜보자.
거꾸로 13이 루트가 되고 10이 13의 왼쪽 자식이 된다.
but, 13의 왼쪽 자식으로 12가 있었으므로 이 12는 떼어내서 10의 오른쪽 자식에 위치시키면 좌회전 끝.
즉, 좌회전을 할 때는 오른쪽 자식(13)의 왼쪽 자식(12)이 부모 노드(10)의 오른쪽 자식으로 옮겨진다는 것을 알 수 있다.
삽입
기본적으로 레드블랙트리의 삽입은 이진탐색트리의 삽입과 같다.
하지만 레드블랙트리는 삽입 이후에 추가 작업을 진행하는데 이것은 노드의 삽입 과정에서 부서졌을지도 모르는
레드블랙트리의 규칙을 다시 복구하는 작업이다.
먼저 레드블랙트리에서 노드가 삽입되면 이 노드는 빨간색이 된다. 그리고 양쪽 자식으로 NIL노드를 연결한다.
그리고 어떠한 규칙이 위반되었는지 살펴본다.
1. 모든 노드는 빨간색 아니면 검은색 --> 항상 성공
2. 루트노드는 검은색 --> 루트노드가 빨간색인 경우 다시 검은색으로 칠하기
3. 리프노드는 검은색 --> NIL를 연결하기 때문에 문제없음
4. 빨간 노드의 자식들은 모두 검은색, 하지만 검은색 노드이 자식은 빨간색일 필요 없음 --> 문제 발생(규칙 수복 필요)
5. 루트노드에서 리프노드까지 사이에 있는 검은색 노드의 수는 모두 동일 --> 삽입된 리프노드의 양쪽자식으로 NIL노드를 연결함으로써 지켜지고있다.
가장 문제가 되는 것은 4번 규칙으로, 새로 삽입된 노드의 부모역시 빨간색이었다는 것.
이 문제를 해결하기 위해서는 크게 3가지 경우로 나누어서 처리한다.
이는 부모노드가 조부 노드의 왼쪽 자식이었을 경우를 기반으로 설명하는 것이며
부모노드가 조부 노드의 오른쪽 자식이었을 경우는 이 반대로 작업을 진행하면 된다.
1. 삼촌노드가 RED 인 경우
2. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 오른쪽 자식인 경우
3. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 왼쪽 자식인 경우
1. 삼촌노드가 RED
새로 삽입된 노드는 12이며 삼촌이 RED 부모노드와 삼촌노드를 검은색으로 칠하고,
조부노드를 빨간색으로 칠한다.
이 과정에서 조부노드를 RED로 만들었기 때문에, 그 위로 다시 규칙이 위반 되는 게 없는지
루트노드에 도달할 때 까지 재귀적으로 살펴보아야 한다.
2. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 오른쪽 자식인 경우
부모노드를 왼쪽으로 회전시켜서 문제를 3번 케이스로 변경한다.
새로 삽입된 노드는 75이며 삼촌이 BLACK 부모노드(50)를 왼쪽으로 회전시켜서 문제유형을 3번으 로 넘긴다.
3. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 왼쪽 자식인 경우
부모노드를 검은색, 조부노드를 빨간색으로 칠한다. 그 다음 조부노드를 오른쪽으로 회전시킨다.
새로 삽입된 노드는 25이며 삼촌이 BLACK 부모노드를 검은색, 조부노드를 빨간색으로 칠한다. 그다 음 조부노드를 오른쪽으로 회전시킨다.
삭제
레드블랙 트리에서 노드를 삭제할 때는 기본적으로 이진검색 트리에서의 삭제 방법을 따라 노드를 삭제한 후 색상을 맞추어 준다. 이진검색트리에서 임의의 노드 d를 삭제할 때 d의 자식이 둘이면 d의 직후원소(Successor)를 d로 옮긴 뒤 삭제한다. 노드 d의 색상을 건드리지 않은 채 키만 바뀌는 것은 레드블랙특성에 영향을 미치지 않는다. 문제가 되는 것은 직후원소를 삭제한 후 주변의 레드블랙특성의 위반 여부이다. 직후원소는 왼쪽 자식을 갖지 않는다는 점을 상기하자. 따라서 d의 직후원소 노드는 최대 1개의 자식만을 가질 수 있으므로 2개의 자식을 가진 노드의 삭제 작업은 자식이 없거나 1개만을 가진 노드의 삭제 작업으로 귀결된다. 따라서 레드블랙 트리에서의 삭제 작업은 자식이 없거나 1개만을 가진 노드의 삭제에 국한해 설명해도 무방하다.
삭제하려고 하는 노드 m의 (최대 1개) 자식을 x라고 하자. 만약 자식이 없으면 x는 NIL 노드가 된다. 어떤 경우든 앞으로 설명할 알고리즘에서 구별할 필요는 없다. 그냥 x로 표시하는 것으로 충분하다. m은 자신의 부모 노드의 왼쪽 자식일 수도 있고, 오른쪽 자식일 수도 있으나 완전히 대칭적이므로 둘 중 하나만 살펴봐도 완결성이 떨어지지 않는다.
우선 간단하게 해결될 수 있는 경우를 살펴보면
1. m이 레드인 경우는 그냥 삭제하면된다.
2. m이 블랙이고 자식이 레드인 경우는 삭제후 x의 노드를 블랙으로 바꾸면된다.
까다로운 경우는 m과 x가 블랙인 경우이다. 이 경우는 m을 삭제하면 블랙 노드의 개수가 1개 모자라서 레드블랙특성 4번에 위반된다. x의 주변상황에 따라 처리 방법이 달라지는데 경우별로 나누어 살펴보도록한다. 아래의 그림은 한 예를 나타낸다.
- Case 1 : p가 레드 (s는 항상 블랙이므로) <l, r의 색상>에 따라
- Case 1-1 <블랙, 블랙>
- Case 1-2 <*, 레드>
- Case 1-3 <레드, 블랙>
- Case 2 : p가 블랙 <s, l, r의 색상>에 따라
- Case 2-1 <블랙, 블랙, 블랙>
- Case 2-2 <블랙, *, 레드>
- Case 2-3 <블렉, 레드, 블랙>
- Case 2-4 <레드, 블랙, 블랙>
Case 1-2, 2-2 와 Case 1-3, 2-3은 p의 색상이 처리 방법에 영향을 미치지 않으므로 통합하여 표시한다. 그림으로 나타내면 아래와 같다.
각 Case 별로 해결방법은 다음과 같다.
- Case 1-1
단순히 p와 s의 색상을 맞바꾼다.
- Case *-2
p를 중심으로 왼쪽으로 회전시키고, p와 s의 색상을 바꾼 다음 r의 색상을 레드에서 블랙으로 바꾼다.
- Case *-3
s를 중심으로 오른쪽으로 회전시키고 l과 s의 색상을 맞바꾼다. Case *-2로 이동한다.
- Case 2-1
단순히 s의 색상을 블랙에서 레드로 바꾼다. 이제 s를 지나가는 경로에서도 블랙 노드가 하나 모자라게 되어 p를 지나가는 경로 전체에서 블랙 노드가 하나 모자라게 된다. 이것은 원래 x에 대해서 발생했던 문제와 똑같은 문제가 p에 대해서 발생했음을 뜻한다. 재귀적으로 이 문제를 해결한다.
- Case 2-4
p를 중심으로 왼쪽으로 회전시키고 p와 s의 색상을 맞바꾼다. l과 r을 경유하는 경로와 관련해서는 문제가 없다. 다만 문제가 발생한 x의 부모 노드의 색상이 블랙에서 레드로 바뀌었다. 이것은 Case 1에 해당하므로 Case 1로 이동한다.
import java.util.Scanner;
public class RedBlackTree {
private final int RED = 0;
private final int BLACK = 1;
private class Node {
int key = -1, color = BLACK;
Node left = nil, right = nil, parent = nil;
Node(int key) {
this.key = key;
}
}
private final Node nil = new Node(-1);
private Node root = nil;
//print 함수
public void printTree(Node node) {
if (node == nil) {
return;
}
printTree(node.left);
System.out.print(((node.color==RED)?"Color: Red ":"Color: Black ")+"Key: "+node.key+" Parent: "+node.parent.key+"\n");
printTree(node.right);
}
//전의 이진트리의 Search함수와 같은역할
private Node findNode(Node findNode, Node node) {
if (root == nil) {
return null;
}
if (findNode.key < node.key) {
if (node.left != nil) {
return findNode(findNode, node.left);
}
} else if (findNode.key > node.key) {
if (node.right != nil) {
return findNode(findNode, node.right);
}
} else if (findNode.key == node.key) {
return node;
}
return null;
}
//삽입함수
private void insert(Node node) {
Node temp = root;
if (root == nil) {
root = node;
node.color = BLACK;
node.parent = nil;
} else {
node.color = RED;
while (true) {
if (node.key < temp.key) {
if (temp.left == nil) {
temp.left = node;
node.parent = temp;
break;
} else {
temp = temp.left;
}
} else if (node.key >= temp.key) {
if (temp.right == nil) {
temp.right = node;
node.parent = temp;
break;
} else {
temp = temp.right;
}
}
}
fixTree(node);
}
}
//새로 삽입 된 노드를 인수로 취한다.
private void fixTree(Node node) {
while (node.parent.color == RED) {
Node uncle = nil;
if (node.parent == node.parent.parent.left) {
uncle = node.parent.parent.right;
if (uncle != nil && uncle.color == RED) {
node.parent.color = BLACK;
uncle.color = BLACK;
node.parent.parent.color = RED;
node = node.parent.parent;
continue;
}
if (node == node.parent.right) {
//두 번 회전해야 함
node = node.parent;
rotateLeft(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
// "else if"코드가 실행되지 않은 경우에는 단일 순환 만 필요
rotateRight(node.parent.parent);
} else {
uncle = node.parent.parent.left;
if (uncle != nil && uncle.color == RED) {
node.parent.color = BLACK;
uncle.color = BLACK;
node.parent.parent.color = RED;
node = node.parent.parent;
continue;
}
if (node == node.parent.left) {
//두 번 회전해야 함
node = node.parent;
rotateRight(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
// "else if"코드가 실행되지 않은 경우에는 단일 순환 만 필요
rotateLeft(node.parent.parent);
}
}
root.color = BLACK;
}
//왼쪽회전함수
void rotateLeft(Node node) {
if (node.parent != nil) {
if (node == node.parent.left) {
node.parent.left = node.right;
} else {
node.parent.right = node.right;
}
node.right.parent = node.parent;
node.parent = node.right;
if (node.right.left != nil) {
node.right.left.parent = node;
}
node.right = node.right.left;
node.parent.left = node;
} else {
// 루트를 회전
Node right = root.right;
root.right = right.left;
right.left.parent = root;
root.parent = right;
right.left = root;
right.parent = nil;
root = right;
}
}
//오른쪽 회전함수
void rotateRight(Node node) {
if (node.parent != nil) {
if (node == node.parent.left) {
node.parent.left = node.left;
} else {
node.parent.right = node.left;
}
node.left.parent = node.parent;
node.parent = node.left;
if (node.left.right != nil) {
node.left.right.parent = node;
}
node.left = node.left.right;
node.parent.right = node;
} else {
// 루트를 회전
Node left = root.left;
root.left = root.left.right;
left.right.parent = root;
root.parent = left;
left.right = root;
left.parent = nil;
root = left;
}
}
// 전체 트리를 삭제
void deleteTree(){
root = nil;
}
//삭제 코드.
//이 함수는 이전 노드의 왼쪽과 오른쪽을 가진 새로운 노드의 연결에 대해서는 상관하지 않는다.
void transplant(Node target, Node with){
if(target.parent == nil){
root = with;
}else if(target == target.parent.left){
target.parent.left = with;
}else
target.parent.right = with;
with.parent = target.parent;
}
boolean delete(Node z){
if((z = findNode(z, root))==null)return false;
Node x;
Node y = z; //임시 주소 y
int y_original_color = y.color;
if(z.left == nil){
x = z.right;
transplant(z, z.right);
}else if(z.right == nil){
x = z.left;
transplant(z, z.left);
}else{
y = treeMinimum(z.right);
y_original_color = y.color;
x = y.right;
if(y.parent == z)
x.parent = y;
else{
transplant(y, y.right);
y.right = z.right;
y.right.parent = y;
}
transplant(z, y);
y.left = z.left;
y.left.parent = y;
y.color = z.color;
}
if(y_original_color==BLACK)
deleteFixup(x);
return true;
}
void deleteFixup(Node x){
while(x!=root && x.color == BLACK){
if(x == x.parent.left){
Node w = x.parent.right;
if(w.color == RED){
w.color = BLACK;
x.parent.color = RED;
rotateLeft(x.parent);
w = x.parent.right;
}
if(w.left.color == BLACK && w.right.color == BLACK){
w.color = RED;
x = x.parent;
continue;
}
else if(w.right.color == BLACK){
w.left.color = BLACK;
w.color = RED;
rotateRight(w);
w = x.parent.right;
}
if(w.right.color == RED){
w.color = x.parent.color;
x.parent.color = BLACK;
w.right.color = BLACK;
rotateLeft(x.parent);
x = root;
}
}else{
Node w = x.parent.left;
if(w.color == RED){
w.color = BLACK;
x.parent.color = RED;
rotateRight(x.parent);
w = x.parent.left;
}
if(w.right.color == BLACK && w.left.color == BLACK){
w.color = RED;
x = x.parent;
continue;
}
else if(w.left.color == BLACK){
w.right.color = BLACK;
w.color = RED;
rotateLeft(w);
w = x.parent.left;
}
if(w.left.color == RED){
w.color = x.parent.color;
x.parent.color = BLACK;
w.left.color = BLACK;
rotateRight(x.parent);
x = root;
}
}
}
x.color = BLACK;
}
Node treeMinimum(Node subTreeRoot){
while(subTreeRoot.left!=nil){
subTreeRoot = subTreeRoot.left;
}
return subTreeRoot;
}
public void consoleUI() {
Scanner scan = new Scanner(System.in);
while (true) {
System.out.println("\n1.- Add items\n"
+ "2.- Delete items\n"
+ "3.- Check items\n"
+ "4.- Print tree\n"
+ "5.- Delete tree\n");
int choice = scan.nextInt();
int item;
Node node;
switch (choice) {
case 1:
item = scan.nextInt();
while (item != -999) {
node = new Node(item);
insert(node);
item = scan.nextInt();
}
printTree(root);
break;
case 2:
item = scan.nextInt();
while (item != -999) {
node = new Node(item);
System.out.print("\nDeleting item " + item);
if (delete(node)) {
System.out.print(": deleted!");
} else {
System.out.print(": does not exist!");
}
item = scan.nextInt();
}
System.out.println();
printTree(root);
break;
case 3:
item = scan.nextInt();
while (item != -999) {
node = new Node(item);
System.out.println((findNode(node, root) != null) ? "found" : "not found");
item = scan.nextInt();
}
break;
case 4:
printTree(root);
break;
case 5:
deleteTree();
System.out.println("Tree deleted!");
break;
}
}
}
public static void main(String[] args) {
RedBlackTree rbt = new RedBlackTree();
rbt.consoleUI();
}
}
결과
'알고리즘' 카테고리의 다른 글
| 해시 (체이닝, 개방주소) (0) | 2019.04.29 |
|---|---|
| kd-트리 (0) | 2019.04.29 |
| B트리 (0) | 2019.04.29 |
| 이진 트리 탐색 (0) | 2019.04.07 |