红黑树的创建、插入和删除等源代码 (二)
parent->parent->lchild;
if ( y->color == RED )
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if ( z == z->parent->lchild )
{
z = z->parent;
RightRotate( z );
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
LeftRotate( z->parent->parent );
}
} //endif right
// root->color = BLACK; // 位置是否正确？？？
} // endwhile
root->color = BLACK;
}
void RB_Tree::RB_Insert( TreeNode *z )
{
TreeNode *y = Nil;
TreeNode *x = root;
while ( x != Nil )
{
y = x;
if ( z->key < x->key )
{
x = x->lchild;
}
else
{
x = x->rchild;
}
}
z->parent = y;
if ( y == Nil )
{
root = z; // root.key = z.key
}
else if ( z->key < y->key )
{
y->lchild = z; //
}
else
{
y->rchild = z; //
}
z->lchild = Nil;
z->rchild = Nil;
z->color = RED;
RB_InsertFixUp( z );
}
void RB_Tree::RB_Create( int a[], int length )
{
for ( int i = 0; i != length; ++i )
{
TreeNode *p = new TreeNode( a[ i ] );
RB_Insert( p );
}
}
TreeNode* RB_Tree::TreeMinimun( TreeNode *x ) // 经过些函数x变了吗。。。
{
if ( x == Nil )
{
cout << "ERROR" << endl;
return Nil;
}
while ( x->lchild != Nil )
{
x = x->lchild;
}
return x;
}
TreeNode* RB_Tree::TreeMaxmun( TreeNode *x )
{
if ( x == Nil )
{
cout << "ERROR" << endl;
return Nil;
}
while ( x->rchild != Nil )
{
x = x->rchild;
}
return x;
}
TreeNode* RB_Tree::TreeSuccessor( TreeNode *x )
{
if ( x == Nil )
{
cout << "ERROR!" << endl;
return Nil;
}
if ( x->rchild != Nil )
{
x = x->rchild;
while ( x->lchild != Nil )
{
x = x->lchild;
}
return x;
}
while ( x == x->
parent->rchild )
{
x = x->parent;
}
x = x->parent;
return x;
}
TreeNode* RB_Tree::TreePredecessor( TreeNode *x )
{
if ( x == Nil )
{
cout << "ERROR" << endl;
return Nil;
}
if ( x->lchild != Nil )
{
x = x->lchild;
while ( x->rchild != Nil )
{
x = x->rchild;
}
return x;
}
while ( x == x->parent->lchild )
{
x = x->parent;
}
x = x->parent;
return x;
}
TreeNode* RB_Tree::TreeSearch( int k )
{
TreeNode *p = root;
while ( p != Nil && p->key != k )
{
if ( k < p->key )
{
p = p->lchild;
}
else
{
p = p->rchild;
}
}
if ( p->key == k )
{
return p;
}
else
{
return Nil;
}
}
void RB_Tree::RB_DeleteFixUp( TreeNode *x )
{
while ( x != root && x->color == BLACK )
{
if ( x == x->parent->lchild )
{
TreeNode *w = x->parent->rchild;
if ( w->color == RED ) // case 1
{
x->parent->color = RED;
w->color = BLACK;
LeftRotate( x->parent );
w = x->parent->rchild;
}
// case 2, 3, 4
if ( w->lchild->color == BLACK && w->rchild->color == BLACK ) // case 2
{
w->color = RED;
x = x->parent;
}
else // case 3, 4
{
if ( w->lchild->color == RED && w->rchild->color == BLACK ) // case 3
{
w->color = RED;
w->lchild->color = BLACK;
RightRotate( w );
w = x->parent->rchild;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->rchild->color = BLACK;
LeftRotate( x->parent );
x = root;
}
}
else
{
TreeNode *w = x->parent->lchild;
if ( w->color == RED ) // case 1
{
w->color = BLACK;
x->parent->color = RED;
RightRotate( x->parent );
w = x->parent->lchild;
}
//case 2, 3, 4
i