레드 블랙 트리(Red-Black Tree)란 노드에 각 색을 부여하여 트리의 균형을 유지하며 탐색, 삽입, 삭제 연산의 수행 시간이 각각 O(logn)을 넘지 않는 매우 효율적인 자료구조입니다. 일반적으로 삽입이나 삭제를 수행할 때 트리의 균형을 유지하기 위해 상당히 많은 경우를 고려해야 한다는 단점이 있습니다.
그러나 좌편향 레드 블랙(Left-Leaning Red-Black; LLRB) 트리는 삽입이나 삭제 시 고려해야 하는 경우의 수가 적으며, AVL 트리, 2-3 트리, 2-3-4 트리, 일반 레드 블랙 트리보다 매우 우수한 성능을 보입니다.
LLRB 트리는 다음의 조건을 만족합니다.
- 루트와 null은 블랙
- 루트로부터 각 null까지 2개의 연속된 레드 link는 없음
- 루트로부터 각 null까지의 경로에 있는 블랙 link 수는 모두 같음
- 레드 link는 왼쪽으로 기울어져 있음
레드 블랙 트리와 AVL 트리를 비교했을 때 알고리즘 시간 복잡도는 둘 다 O(logN)에 해당합니다. 그러나 AVL 트리가 엄격하게 균형을 잡는 편이고, 레드 블랙 트리는 색으로 구분하는 경우로 인해 회전 수가 감소한다는 장점이 있습니다. 탐색이 많은 경우에는 AVL 트리가, 삽입, 삭제가 빈번한 경우에는 레드 블랙 트리가 유리합니다.
레드 블랙 트리에서의 탐색은 이진 탐색 트리의 탐색과 같습니다. 탐색하고자 하는 Key를 루트의 id와 비교하여 탐색합니다.
레드 블랙 트리 삽입과 위치 재조정 구현 코드
class Node {
int key;
int color;
Node left;
Node right;
Node parent;
Node(int key, int color, Node left, Node right, Node parent) {
this.key = key;
this.color = color;
this.left = left;
this.right = right;
this.parent = parent;
}
}
class RedBlackTree {
final int BLACK = 0;
final int RED = 1;
Node head;
public void insert(int key) {
Node checkNode = null;
if (this.head == null) {
this.head = new Node(key, BLACK, null, null, null);
} else {
Node cur = this.head;
while (true) {
Node pre = cur;
if (key < cur.key) {
cur = cur.left;
if (cur == null) {
pre.left = new Node(key, RED, null, null, pre);
checkNode = pre.left;
break;
}
} else {
cur = cur.right;
if (cur == null) {
pre.right = new Node(key, RED, null, null, pre);
checkNode = pre.right;
break;
}
}
}
reBalance(checkNode);
}
}
public void reBalance(Node node) {
while (node.parent != null && node.parent.color == RED) {
Node sibling = null;
if (node.parent == node.parent.parent.left) {
sibling = node.parent.parent.right;
} else {
sibling = node.parent.parent.left;
}
if (sibling != null && sibling.color == RED) {
node.parent.color = BLACK;
sibling.color = BLACK;
node.parent.parent.color = RED;
if (node.parent.parent == this.head) {
node.parent.parent.color = BLACK;
break;
} else {
node = node.parent.parent;
}
} else {
if (node.parent == node.parent.parent.left) {
if (node == node.parent.right) {
node = node.parent;
leftRotate(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
rightRotate(node.parent.parent);
} else if (node.parent == node.parent.parent.right) {
if (node == node.parent.left) {
node = node.parent;
rightRotate(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
leftRotate(node.parent.parent);
}
break;
}
}
}
public void leftRotate(Node node) {
if (node.parent == null) {
Node rNode = this.head.right;
this.head.right = rNode.left;
rNode.left.parent = this.head;
this.head.parent = rNode;
rNode.left = this.head;
rNode.parent = null;
this.head = rNode;
} else {
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 != null) {
node.right.left.parent = node;
}
node.right = node.right.left;
node.parent.left = node;
}
}
public void rightRotate(Node node) {
if (node.parent == null) {
Node lNode = this.head.left;
this.head.left = lNode.right;
lNode.right.parent = this.head;
this.head.parent = lNode;
lNode.right = this.head;
lNode.parent = null;
this.head = lNode;
} else {
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 != null) {
node.left.right.parent = node;
}
node.left = node.left.right;
node.parent.right = node;
}
}
}
(삭제 구현 코드는 다음 기회에…….)
LLRB 트리의 삽입과 삭제 연산을 구현하는 데 필요한 세 가지 기본 연산이 있습니다. 노드의 오른쪽 레드 link를 왼쪽으로 옮기는 rotateLeft, 노드의 왼쪽 레드 link를 오른쪽으로 옮기는 rotateRight, 노드의 두 link의 색이 같을 때 둘 다 다른 색으로 바꾸는 flipColrs입니다.
노드 삽입 후 double red가 발생했을 시 두 가지 방법으로 해결할 수 있습니다.
첫 번째는 부모 노드의 형제 노드가 red일 때입니다. 삽입한 노드의 부모와 부모의 형제 노드를 black으로 변경한 뒤 부모의 부모 노드를 red로 변경하고, 부모의 부모 노드가 root인지 double red인지에 따라 조정을 진행합니다.
두 번째는 부모 노드의 형제 노드가 black이거나 없을 때입니다. 삽입한 노드, 부모 노드, 부모의 부모 노드를 조정합니다. 조정 대상 노드를 오름차순으로 정렬한 뒤 가운데 노드를 부모 노드로 선정하고 black으로 변경합니다. 나머지 두 노드를 자식 노드로 두고 red로 변경합니다.
기본적으로 노드 삭제 시 삭제 대상 노드가 black이고 그 자리에 오는 노드가 red인 경우 해당 자리로 오는 red 노드를 black으로 변경합니다.
그러나 삭제 대상 노드가 black이고 그 자리에 오는 노드가 black인 경우도 있습니다. 이중 흑색 노드의 형제 노드가 black이고 형제의 양쪽 자식 모두 black인 경우에는 형제 노드를 red로 변경한 후 이중 흑색 노드의 black 하나를 부모 노드로 전달합니다. 부모가 root가 아닌 이중 흑색 노드가 되면 이 과정을 반복합니다.
또는 이중 흑색 노드의 형제 노드가 red인 경우에는 형제 노드를 black으로 변경하고 부모 노드를 red로 변경한 뒤 부모 노드를 기준으로 왼쪽으로 회전합니다. 이후 이중 흑색 케이스에 따라 반복합니다.
또는 이중 흑색 노드의 형제 노드가 black이고 오른쪽 자식이 red인 경우 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 변경합니다. 부모 노드를 기준으로 왼쪽으로 회전합니다.
또는 이중 흑색 노드의 형제 노드가 black이고 왼쪽 자식이 red인 경우 형제 노드를 red로, 형제 노드의 왼쪽 자식 노드를 black으로 변경합니다. 형제 노드를 기준으로 오른쪽으로 회전합니다. 앞서 설명한 과정과 동일해집니다. 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 변경하고 부모 노드를 기준으로 왼쪽으로 회전합니다.
※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.
※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.
'Java > 자료구조' 카테고리의 다른 글
| [자료구조] 이진 힙(Binary Heap) (0) | 2023.07.04 |
|---|---|
| [자료구조] 해시 테이블(Hash Table) (0) | 2023.07.02 |
| [자료구조 트리] AVL 트리 (0) | 2023.06.28 |
| [자료구조 트리] 이진 탐색 트리(Binary Search Tree) (0) | 2023.06.26 |
| [자료구조 트리] 이진 트리(Binary Tree) (0) | 2023.06.24 |