首页 > 代码库 > 完整的C++实现算法导论十三章红黑树以及十四章中的顺序统计树
完整的C++实现算法导论十三章红黑树以及十四章中的顺序统计树
#include<iostream>
using namespace std;
class BRTree;
class BRTreeNode{
private:
friend class BRTree;
int key;
bool color;
int size;
BRTreeNode *left;
BRTreeNode *right;
BRTreeNode *parent;
public:
//创建一个默认构造函数
BRTreeNode():key(-1),color(0),size(0),left(NULL),right(NULL),parent(NULL){}
//创建一个拷贝构造函数
BRTreeNode(BRTreeNode *node):key(node->key),color(node->color),size(node->size),left(node->left),right(node->right),parent(node->parent){}
//创建一个含有参数的构造函数
BRTreeNode(int num,int flag,int value):key(num),color(flag),size(value),left(NULL),right(NULL),parent(NULL){}
//下面创建一个析构函数
~BRTreeNode()
{}
//下面定义一个返回结点值的函数
int getkey()
{
return key;
}
//下面定义一个返回标记的函数
bool getcolor()
{
return this->color;
}
BRTreeNode* GetLeft()
{
return this->left;
}
BRTreeNode* Getright()
{
return this->right;
}
BRTreeNode* Getparent()
{
return this->parent;
}
void inorder()
{
if(this!=NULL)
{
this->left->inorder();
cout<<"中序遍历的值是"<<this->key<<endl;
this->right->inorder();
}
}
//下面定义一个前序遍历的函数
void preorder()
{
if(this!=NULL)
{
cout<<"前序遍历的结果是"<<this->key<<endl;
this->left->preorder();
this->right->preorder();
}
}
//6
void Postorder()
{
if(this!=NULL)
{
this->left->Postorder();
this->right->Postorder();
cout<<this->key<<" ";
}
}
void make_empty()
{
if(this!=NULL)
{
this->left->make_empty();
this->right->make_empty();
delete this;
}
}
int getheight()
{
int L,R;
if(this==NULL)
{
return 0;
}
L=this->left->getheight();
R=this->right->getheight();
return 1+(L>R)?L:R;
}
};
class BRTree{
private:
BRTreeNode *root;
BRTreeNode *nil;
public:
BRTree():nil(new BRTreeNode())
{
nil->color=0;
nil->key=-1;
nil->left=nil->right=nil->parent=NULL;
root=nil;
}
//下面定义一个以清空node为根结点的树
void MakeEmpty(BRTreeNode*node)
{
if(node!=nil)
{
MakeEmpty(node->left);
MakeEmpty(node->right);
delete node;
}
}
int Getkey(BRTreeNode* node)
{
return node->getkey();
}
bool Getcolor(BRTreeNode* node)
{
return node->getcolor();
}
BRTreeNode* Getroot()
{
return root;
}
BRTreeNode* GetParent(BRTreeNode*node)
{
return node->parent;
}
int GetHeight(BRTreeNode *node)
{
int L,R;
if(node==nil)
return 0;
L=GetHeight(node->left);
R=GetHeight(node->right);
return 1+(L>R? L:R);
}
void Inorder(BRTreeNode *node)
{
if(node!=nil)
{
Inorder(node->left);
cout<<node->key<<" ";
Inorder(node->right);
}
}
void Preorder(BRTreeNode *node)
{
if(node!=nil)
{
cout<<node->key<<" ";
Preorder(node->left);
Preorder(node->right);
}
}
void Posetorder(BRTreeNode*node)
{
if(node!=nil)
{
Posetorder(node->left);
Posetorder(node->right);
cout<<node->key<<" ";
}
}
//左旋节点node
bool LeftRotate(BRTreeNode* node)
{
BRTreeNode *y;
if(node->right==nil)
{
cout<<"can't left rotate!"<<endl;
return 0;
}
y=node->right;
node->right=y->left;
if(y->left!=nil)
{
y->left->parent=node;
}
y->parent=node->parent;
if(node->parent==nil)
{
root=y;
}
else if(node->parent->left==node)
{
node->parent->left=y;
}
else
{
node->parent->right=y;
}
y->left=node;
node->parent=y;
//调整size域的大小
y->size=node->size;
node->size=node->left->size+node->right->size;
return 1;
}
//下面定义的是一个右旋函数
bool RightRotate(BRTreeNode* node)
{
if(node->left==nil)
{
cout<<"can't rightrotate!"<<endl;
return 0;
}
BRTreeNode* x;
x=node->left;
node->left=x->right;
if(x->right!=nil)
{
x->right->parent=node;
}
x->parent=node->parent;
if(node->parent==nil)
{
root=x;
}
else if(node->parent->left==node)
{
node->parent->left=x;
}
else
{
node->parent->right=x;
}
node->parent=x;
x->right=node;
x->size=node->size;
node->size=node->left->size+node->right->size;
return 1;
}
//插入一个值
void Insert(int num)
{
BRTreeNode* node=new BRTreeNode(num,1,1);
node->left=nil;
node->right=nil;
node->parent=nil;
BRTreeNode* p=root,*q=nil;
if(root==nil)
{
node->color=0;
root=node;
root->left=root->right=root->parent=nil;
root->size=1;
return ;
}
while(p!=nil)
{
if(p->key==num)
{
cout<<num<<" has exist!"<<endl;
return ;
}
else if(p->key>num)
{ p->size+=1;
q=p;
p=p->left;
}
else
{ p->size+=1;
q=p;
p=p->right;
}
}
if(q->key>num)
{
q->left=node;
node->parent=q;
}
else
{
q->right=node;
node->parent=q;
}
RBInsertAdjust(node);
}
void RBInsertAdjust(BRTreeNode* node)
{
BRTreeNode* y;
while(node->parent->color==1)
{
if(node->parent==node->parent->parent->left)
{
y=node->parent->parent->right;
if(y->color==1)
{
node->parent->color=0;
y->color=0;
y->parent->color=1;
node=node->parent->parent;
}
//此时y的颜色是黑色
else
{
//第二种情况
if(node==node->parent->right)
{
node=node->parent;
LeftRotate(node);
}
//第三种情况
node->parent->color=0;
node->parent->parent->color=1;
RightRotate(node->parent->parent);
}
}
else
{
y=node->parent->parent->left;
if(y->color==1)
{
node->parent->color=0;
y->color=0;
y->parent->color=1;
node=node->parent->parent;
}
else
{
if(node==node->parent->left)
{
node=node->parent;
RightRotate(node);
}
node->parent->color=0;
node->parent->parent->color=1;
LeftRotate(node->parent->parent);
}
}
}
root->color=0;
}
//搜索某个值
BRTreeNode* Search(int num)
{
BRTreeNode* p=root;
while(p!=nil)
{
if(p->key==num)
{
return p;
}
else if(p->key>num)
{
p=p->left;
}
else
{
p=p->right;
}
}
cout<<"there is no "<<num<<" in this tree!"<<endl;
return nil;
}
//获取以node节点为根节点的树的最小元素，并返回该最小值
int Minnum(BRTreeNode*node)
{
BRTreeNode*p=node;
while(p->left!=nil)
{
p=p->left;
}
return p->key;
}
//获取以node节点为根节点的树的最da元素，并返回该最da值
int Maxnum(BRTreeNode*node)
{
BRTreeNode*p=node;
while(p->right!=nil)
{
p=p->right;
}
return p->key;
}
//获取以node节点为根节点的树的最小元素，并返回该节点
BRTreeNode* MinNum(BRTreeNode*node)
{
BRTreeNode*p=node;
while(p->left!=nil)
{
p=p->left;
}
return p;
}
//获取以node节点为根节点的树的最大元素
BRTreeNode* MaxNum(BRTreeNode*node)
{
BRTreeNode*p=node;
while(p->right!=nil)
{
p=p->right;
}
return p;
}
BRTreeNode*InorderSuccessor(BRTreeNode*node)
{
if(node->right!=nil)
{
return MinNum(node->right);
}
else
{
BRTreeNode*p=GetParent(node);
while(p&&node==p->right)
{
node=p;
p=GetParent(node);
}
return p;
}
}
//中序遍历的前趋
BRTreeNode*InordePredecessor(BRTreeNode*node)
{
if(node->left!=nil)
{
return MaxNum(node->left);
}
else
{
BRTreeNode*p=GetParent(node);
while(p&&node==p->left)
{
node=p;
p=GetParent(node);
}
return p;
}
}
bool Delete(int num)
{
BRTreeNode*z,*y,*x;
//寻找key值为num的节点p
z=Search(num);
//如果没有该节点则返回0
if(z==nil)
{
return 0;
}
if(z->left==nil||z->right==nil)
{
y=z;
}
else
y=InorderSuccessor(z);
if(y->left!=nil)
x=y->left;
else
x=y->right;
x->parent=y->parent;
if(x->parent==nil)
root=x;
else if(y=y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
while(y!=root)
{
y->parent->size=y->parent->size-1;
y=y->parent;
}
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;
}
//下面根据统计秩来找出相应的元素，其实也就是中序排列所处的位置
~BRTree()
{
MakeEmpty(root);
delete nil;
}
BRTreeNode *os_select(BRTreeNode *startnode,int i)
{
int r=startnode->size+1;
if(r==i)
{
return startnode;
}
else if(i<r)
{
return os_select(startnode->left,i);
}
else
{
return os_select(startnode->right,i-r);
}
}
//下面定义一个给定结点的指针来找出其秩的函数
int os_rank(BRTreeNode *startnode)
{
int r=startnode->left->size+1;
BRTreeNode *y=startnode;
while(y!=root)
{
if(y==y->parent->right)
{
r+=y->parent->left->size+1;
}
y=y->parent;
}
return r;
}
};
int main()
{
BRTree tree;
int a[8]={11,2,1,7,5,8,14,15};
int i;
for(i=0;i<8;i++)
{
tree.Insert(a[i]);
}
tree.Inorder(tree.Getroot()); //输出的结果是从小到大输出，其结果是1 2 5 7 8 11 14 15；
cout<<endl;
/*tree.Insert(4); //插入一个的值是为4的；
tree.Inorder(tree.Getroot()); //中序输出插入4之后序列的结果为 1 2 4 5 7 8 11 14 15
cout<<endl;
tree.Insert(6);
tree.Inorder(tree.Getroot());
cout<<endl;
tree.Insert(3);
tree.Inorder(tree.Getroot());
cout<<endl;
cout<<tree.GetHeight(tree.Getroot());
cout<<endl;
tree.Delete(2);
tree.Inorder(tree.Getroot());
cout<<endl; */
tree.Insert(4);
tree.Inorder(tree.Getroot());
cout<<tree.os_rank(tree.Search(5))<<endl;
system("pause");
return 0;
}完整的C++实现算法导论十三章红黑树以及十四章中的顺序统计树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。