Red-Black Tree
Definition
Ø A binary search tree that every node is colored either red or black.
Ø Leaf nodes do not contain data – External nodes.
Ø Satisfy the properties.
Properties
1. The root and all external nodes are black.
2. No root-to-external-node path has two consecutive red nodes.
3. All root-to-external-node paths have the same number of black nodes.
4. Pointers from internal node to an external node are black.
5. No root-to-external-node path has two consecutive red pointers.
6. All root-to-external-node paths have the same number of black pointers.
Algorithm
1. bool IsEmpty()
Ø Same as BST
2. void Insert( int k )
Ø Inserting algorithm is same with BST
Ø But RBTREE has additional processes – Color updating
① If the added node( I will say it N ) has no parent -> root, set this black. Else, go to 2.
void change_color1( rbnode *n )
{
if ( n->parent == NULL )
n->red = false;
else
change_color2( n );
}
② If parent of N is black, do nothing. Else, go to 3.
void change_color2( rbnode *n )
{
if ( !(n->parent->red) )
return;
else
change_color3( n );
}
③ If N has uncle and the color of uncle is red, set N’s parent’s color and uncle’s color black. And set grandparent’s color red. And go to 1. Else, go to 4.
void change_color3( rbnode *n )
{
rbnode *u = uncle(n), *g;
if ( (u != NULL) && u->red ) {
n->parent->red = false;
u->red = false;
g = grandparent( n );
g->red = true;
change_color1( g );
} else
change_color4( n );
}
④ If N is right child of parent and parent is left child of grandparent, use left rotation. Else if N is left child of parent and parent is right child of grandparent, use right rotation. Then go to 5.
void change_color4( rbnode *n )
{
rbnode *g = grandparent( n );
if ( (n == n->parent->right) && (n->parent == g->left) ) {
rotate_left( n->parent, g );
n = n->left;
} else if ( (n == n->parent->left) && (n->parent == g->right) ) {
rotate_right( n->parent, g );
n = n->right;
}
change_color5( n );
}
⑤ Set parent’s color black and grandparent’s color red. If N is left child of parent, use right rotation. Else, use left rotation.
void change_color5( rbnode *n )
{
rbnode *g = grandparent( n );
n->parent->red = false;
g->red = true;
if ( n == n->parent->left )
rotate_right( n->parent, g );
else
rotate_left( n->parent, g );
}
3. void Delete( int k )
Ø It find nearest child and change two values. And save its parent to N and delete node with value k.
void delete_one_child( rbnode *iNode )
{
if ( iNode == NULL ) return;
while ( iNode->left != NULL || iNode->right != NULL )
{
if ( iNode->left != NULL ) {
rbnode *tNode = iNode->left;
while( tNode->right != NULL ) tNode = tNode->right;
int t = iNode->value;
iNode->value = tNode->value;
tNode->value = t;
delete_one_child( tNode );
return;
} else {
rbnode *tNode = iNode->right;
while( tNode->left != NULL ) tNode = tNode->left;
int t = iNode->value;
iNode->value = tNode->value;
tNode->value = t;
delete_one_child( tNode );
return;
}
}
rbnode *pNode = iNode->parent;
if ( iNode == pNode->left ) {
pNode->left = NULL;
} else {
pNode->right = NULL;
}
if ( iNode->red ) {
delete iNode;
return;
}
delete iNode;
delete_case1( pNode );
}
Ø And then start updating in some cases.
① If N is root, do nothing.
void delete_case1( rbnode *n )
{
if ( n->parent != NULL )
delete_case2( n );
}
② If sibling of N is red, execute below and go to 3
1. Set parent red.
2. Set sibling black.
3. If N is left child of parent, use left rotation.
4. Else, use right rotation.
void delete_case2( rbnode *n )
{
rbnode *s = sibling( n );
if ( s->red ) {
n->parent->red = true;
s->red = false;
if ( n == n->parent->left )
rotate_left( n->parent, n->parent->parent );
else
rotate_right( n->parent, n->parent->parent );
}
delete_case3( n );
}
③ If parent is black and sibling is black and sibling’s children is black, set sibling red and go to 1. Else, go to 4.
void delete_case3( rbnode *n )
{
rbnode *s = sibling( n );
if ( !(n->parent->red) && !(s->red) && !(s->left->red) && !(s->right->red) ) {
s->red = true;
delete_case1( n->parent );
} else
delete_case4( n );
}
④ If parent is red and sibling and its children is black, set sibling red and set parent black. Else, go to 5.
void delete_case4( rbnode *n )
{
rbnode *s = sibling( n );
if ( (n->parent->red) && !(s->red) && !(s->left->red) && !(s->right->red) ) {
s->red = true;
n->parent->red = false;
} else
delete_case5( n );
}
⑤ If sibling is black,
1. If N is left child of parent and sibling’s right child is black and sibling’s left child is red, set sibling red and sibling’s left child black. And then use right rotation.
2. Else if N is right child of parent and sibling’s left child is black and sibling’s right child is red, set sibling red and sibling’s right child black. And then use left rotation.
3. go to 6.
void delete_case5( rbnode *n )
{
rbnode *s = sibling( n );
if ( !s->red ) {
if ( (n == n->parent->left) && !(s->right->red) && (s->left->red) ) {
s->red = true;
s->left->red = false;
rotate_right( s, s->parent );
} else if ( (n == n->parent->right) && !(s->left->red) && (s->right->red) ) {
s->red = true;
s->right->red = false;
rotate_left( s, s->parent );
}
}
delete_case6( n );
}
⑥ Set sibling’s color to parent’s color. And set parent’s color black. If N is left child of parent, set sibling’s right child black and use left rotation. Else, set sibling’s left child black and use right rotation.
void delete_case6( rbnode *n )
{
rbnode *s = sibling( n );
s->red = n->parent->red;
n->parent->red = false;
if ( n == n->parent->left ) {
s->right->red = false;
rotate_left( n->parent, n->parent->parent );
} else {
s->left->red = false;
rotate_right( n->parent, n->parent->parent );
}
}
4. rbnode* Search( int k )
Ø Same as BST
5. void PrintInorder()
Ø Same as BST
'데이터구조' 카테고리의 다른 글
| [데이터구조] Binary Search Tree (BST) 정리 및 예제 (0) | 2014.02.15 |
|---|
