본문 바로가기

Archived(CSE Programming)/자료구조(C++)

레드블랙 트리(Red Black Tree) (변형이진탐색트리)


레드 블랙 트리는 효율적인 탐색을 위해 BST의 height를 낮추는방식으로 고안된 트리이다.

다음의 3 가지 조건을 만족해야 한다.


  1. 루트 노드와 외부 노드는 Black 노드이다
  2. Red 노드가 연속해서 올 수 없다
  3. 루트로부터 외부 노드로 까지의 가는 경로에서 count 되는 Black 노드의 수는 같다 (최대 경로는 최소 경로의 두배 이하이다)


그리고 이러한 조건을 만족시키기 위해 삽입 시에는 Red 노드로 삽입을 고정시키는 것이 유리하다

(블랙 노드로 삽입시 조건 3을 위배시키기 쉬워서 이런 경우에는 복잡한 처리를 수행해야 하기 때문)


Red 노드로 삽입 후에는 조건 2만 체크를 하면 된다.


조건 2를 만족시키기 위해 4가지 Case가 있는데 다음과 같다.(right에 삽입되었을 경우를 합치면 총 8가지 case)

  • LLb - Red 노드가 연속해서 왼쪽 자식의 노드로 오고 조부모(g) 노드의 반대 자식 노드가 Black일 경우
  • LLr - Red 노드가 연속해서 왼쪽 자식의 노드로 오고 조부모(g) 노드의 반대 자식 노드가 Red일 경우
  • LRr - Red 노드가 왼쪽 자식의 노드, 오른쪽 자식의 노드로 오고 조부모(g) 노드의 반대 자식 노드가 Red일 경우
  • LRb - Red 노드가 왼쪽 자식의 노드, 오른쪽 자식의 노드로 오고 조부모 노드의 반대 자식 노드가 Black일 경우

각각의 경우에서 다른 자식 노드가 Red 일 경우 색깔만 다시 칠해준다(recoloring)

각각의 경우에서 다른 자식 노드가 Black 일 경우 재조정을 해준다(restructuring)




조정법

  • LLr - gu 노드를 레드로 pu 노드를 블랙, 다른 자식 노드(guR)를 블랙 처리 (처리 후에 양쪽 경로로 가는 길에 black 노드 수 같음)
  • LRr - gu 노드를 레드로 u 노드를 블랙, 다른 자식 노드(guR)를 블랙 처리 (처리 후에 양쪽 경로로 가는 길에 black 노드 수 같음)
  • LLb - pu 노드가 중간으로 가고 gu 노드를 rch로, 자식 노드를 lch로 두는 방식으로 재조정
  • LRb - u(손자) 노드가 중간으로 가고 gu 노드를 rch로, 부모 노드를 lch로 두는 방식으로 재조정


이렇게 새로 노드가 삽입되면 *ub = 1을 주고 재귀적으로 들어온 순서로 다 체크를 해주면서 루트까지간다

루트에 도달 후에는 루트 색깔을 검정색으로 변화시켜준다(혹시나 처리 과정 중에 루트 색깔이 빨강으로 변화할수 있음)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
// C program for Red-Black Tree insertion
#include<stdio.h>
#include<stdlib.h>
 
//A Red-Black tree node structure
struct node
{
    int data;     // for data part
    char color;  // for color property
 
    //links for left, right children and parent
    struct node *left, *right, *parent;
};
 
 
// Left Rotation
void LeftRotate(struct node **root,struct node *x)
{
    //y stored pointer of right child of x
    struct node *= x->right;
 
    //store y's left subtree's pointer as x's right child
    x->right = y->left;
 
    //update parent pointer of x's right
    if (x->right != NULL)
        x->right->parent = x;
 
    //update y's parent pointer
    y->parent = x->parent;
 
    // if x's parent is null make y as root of tree
    if (x->parent == NULL)
        (*root) = y;
 
    // store y at the place of x
    else if (x == x->parent->left)
        x->parent->left = y;
    else    x->parent->right = y;
 
    // make x as left child of y
    y->left = x;
 
    //update parent pointer of x
    x->parent = y;
}
 
 
// Right Rotation (Similar to LeftRotate)
void rightRotate(struct node **root,struct node *y)
{
    struct node *= y->left;
    y->left = x->right;
    if (x->right != NULL)
        x->right->parent = y;
    x->parent =y->parent;
    if (x->parent == NULL)
        (*root) = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else y->parent->right = x;
    x->right = y;
    y->parent = x;
}
 
// Utility function to fixup the Red-Black tree after standard BST insertion
void insertFixUp(struct node **root,struct node *z)
{
    // iterate until z is not the root and z's parent color is red
    while (z != *root && z->parent->color == 'R')
    {
        struct node *y;
 
        // Find uncle and store uncle in y
        if (z->parent == z->parent->parent->left)
            y = z->parent->parent->right;
        else
            y = z->parent->parent->left;
 
        // If uncle is RED, do following
        // (i)  Change color of parent and uncle as BLACK
        // (ii) Change color of grandparent as RED
        // (iii) Move z to grandparent
        if (y->color == 'R')
        {
            y->color = 'B';
            z->parent->color = 'B';
            z->parent->parent->color = 'R';
            z = z->parent->parent;
        }
 
        // Uncle is BLACK, there are four cases (LL, LR, RL and RR)
        else
        {
            // Left-Left (LL) case, do following
            // (i)  Swap color of parent and grandparent
            // (ii) Right Rotate Grandparent
            if (z->parent == z->parent->parent->left &&
                z == z->parent->left)
            {
                char ch = z->parent->color ;
                z->parent->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                rightRotate(root,z->parent->parent);
            }
 
            // Left-Right (LR) case, do following
            // (i)  Swap color of current node  and grandparent
            // (ii) Left Rotate Parent
            // (iii) Right Rotate Grand Parent
            if (z->parent == z->parent->parent->left &&
                z == z->parent->right)
            {
                char ch = z->color ;
                z->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                LeftRotate(root,z->parent);
                rightRotate(root,z->parent->parent);
            }
 
            // Right-Right (RR) case, do following
            // (i)  Swap color of parent and grandparent
            // (ii) Left Rotate Grandparent
            if (z->parent == z->parent->parent->right &&
                z == z->parent->right)
            {
                char ch = z->parent->color ;
                z->parent->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                LeftRotate(root,z->parent->parent);
            }
 
            // Right-Left (RL) case, do following
            // (i)  Swap color of current node  and grandparent
            // (ii) Right Rotate Parent
            // (iii) Left Rotate Grand Parent
            if (z->parent == z->parent->parent->right &&
                z == z->parent->left)
            {
                char ch = z->color ;
                z->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                rightRotate(root,z->parent);
                LeftRotate(root,z->parent->parent);
            }
        }
    }
    (*root)->color = 'B'//keep root always black
}
 
// Utility function to insert newly node in RedBlack tree
void insert(struct node **root, int data)
{
    // Allocate memory for new node
    struct node *= (struct node*)malloc(sizeof(struct node));
    z->data = data;
    z->left = z->right = z->parent = NULL;
 
     //if root is null make z as root
    if (*root == NULL)
    {
        z->color = 'B';
        (*root) = z;
    }
    else
    {
        struct node *= NULL;
        struct node *= (*root);
 
        // Follow standard BST insert steps to first insert the node
        while (x != NULL)
        {
            y = x;
            if (z->data < x->data)
                x = x->left;
            else
                x = x->right;
        }
        z->parent = y;
        if (z->data > y->data)
            y->right = z;
        else
            y->left = z;
        z->color = 'R';
 
        // call insertFixUp to fix reb-black tree's property if it
        // is voilated due to insertion.
        insertFixUp(root,z);
    }
}
 
// A utility function to traverse Red-Black tree in inorder fashion
void inorder(struct node *root)
{
    if (root == NULL)
        return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}
 
/* Drier program to test above function*/
int main()
{
    struct node *root = NULL;
    insert(&root,10);
    insert(&root,20);
    insert(&root,40);
    insert(&root,30);
    insert(&root,50);
    insert(&root,35);
    insert(&root,25);
    insert(&root,37);
    printf("inorder Traversal Is : ");
    inorder(root);
 
    return 0;
}
cs


구현 : https://gist.github.com/VictorGarritano/5f894be162d39e9bdd5c