算法导论-红黑树C++实现 - c++编程基础

y->parent->right=x;
if(y!=z)
{
z->key=y->key;
}
if(y->color==0)
{
RBTreeFixup(x);
}
return 1;
}
void RBTreeFixup(BRTreeNode* x)
{
BRTreeNode*w;
while(x!=root&&x->color==0)
{
if(x==x->parent->left)
{
w=x->parent->right;
if(w->color==1)
{
w->color=0;
x->parent->color=1;
LeftRotate(x->parent);
w=x->parent->right;
}
if(w->left->color==0&&w->right->color==0)
{
w->color=1;
x=x->parent;
}
else
{
if(w->right->color==0)
{
w->color=1;
RightRotate(w);
w=x->parent->right;
}
w->color=x->parent->color;
x->parent->color=0;
w->right->color=0;
LeftRotate(x->parent);
x=root;
}
}
else
{
w=x->parent->left;
if(w->color==1)
{
w->color=0;
x->parent->color=1;
RightRotate(x->parent);
w=x->parent->left;
}
if(w->right->color==0&&w->left->color==0)
{
w->color=1;
x=x->parent;
}
else
{
if(w->left->color==0)
{
w->color=1;
LeftRotate(w);
w=x->parent->left;
}
w->color=x->parent->color;
x->parent->color=0;
w->left->color=0;
RightRotate(x->parent);
x=root;
}
}
}
x->color=0;
}
};

#endif // BRTREE_H_INCLUDED

测试程序

[cpp]
#include
#include"BRTree.h"
#include "BRTreeNode.h"
using namespace std;

int main()
{
BRTree tree;
cout<<"Insert 9 numbers:"< int a[9]={8,11,17,15,6,1,22,25,27};
int i;
for(i=0;i<9;i++)
{
tree.Insert(a[i]);
}
tree.DispTree(tree.Getroot());
cout<<"Delete 11:"< tree.Delete(11);
tree.DispTree(tree.Getroot());
cout << "blackHeight:" <
return 0;
}

#include
#include"BRTree.h"
#include "BRTreeNode.h"
using namespace std;

int main()
{
BRTree tree;
cout<<"Insert 9 numbers:"< int a[9]={8,11,17,15,6,1,22,25,27};
int i;
for(i=0;i<9;i++)
{
tree.Insert(a[i]);
}
tree.DispTree(tree.Getroot());
cout<<"Delete 11:"< tree.Delete(11);
tree.DispTree(tree.Getroot());
cout << "blackHeight:" <

return 0;
}

运行结果：

算法导论-红黑树C++实现 (八)