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

来源:岁月联盟 编辑:猪蛋儿 时间:2012-11-13

红黑树的定义:

一棵二叉查找树如果满足下面的红黑性质,则为一棵红黑树:

1)每个节点或是红的,或是黑的。

2)根节点是黑的。

3)每个叶节点(NIL)是黑节点。

4)如果一个节点是红的,则它的两个儿子都是黑的。

5)对每个节点,从该节点到其子孙节点的所有路径上包含相同节点数目的黑节点。

 


C++代码实现:

BRTreeNode.h


[cpp]
<SPAN style="FONT-SIZE: 14px">#ifndef BRTREENODE_H_INCLUDED 
#define BRTREENODE_H_INCLUDED  
#include<iostream>  
using namespace std; 
class BRTree; 
class BRTreeNode 

private: 
    friend class BRTree; 
    int key; 
    bool color; 
    BRTreeNode* left; 
    BRTreeNode* right; 
    BRTreeNode* parent; 
public: 
    BRTreeNode():key(-1),color(0),left(NULL),right(NULL),parent(NULL){} 
    BRTreeNode(BRTreeNode* node):key(node->key),color(node->color),left(node->left),right(node->right),parent(node->parent) 
    {} 
    BRTreeNode(int num,bool flag):key(num),color(flag),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<<" "; 
            this->right->Inorder(); 
        } 
    } 
    void Preorder() 
    { 
        if(this!=NULL) 
        { 
            cout<<this->key<<" "; 
            this->left->Preorder(); 
            this->right->Preorder(); 
        } 
    } 
    void Postorder() 
    { 
        if(this!=NULL) 
        { 
            this->left->Postorder(); 
            this->right->Postorder(); 
            cout<<this->key<<" "; 
        } 
    } 
 
    void MakeEmpty() 
    { 
        if(this!=NULL) 
        { 
            this->left->MakeEmpty(); 
            this->right->MakeEmpty(); 
            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); 
    } 
}; 
 
 
#endif // BRTREENODE_H_INCLUDED  
</SPAN> 

#ifndef BRTREENODE_H_INCLUDED
#define BRTREENODE_H_INCLUDED
#include<iostream>
using namespace std;
class BRTree;
class BRTreeNode
{
private:
 friend class BRTree;
 int key;
 bool color;
 BRTreeNode* left;
 BRTreeNode* right;
 BRTreeNode* parent;
public:
 BRTreeNode():key(-1),color(0),left(NULL),right(NULL),parent(NULL){}
 BRTreeNode(BRTreeNode* node):key(node->key),color(node->color),left(node->left),right(node->right),parent(node->parent)
 {}
 BRTreeNode(int num,bool flag):key(num),color(flag),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<<" ";
   this->right->Inorder();
  }
 }
 void Preorder()
 {
  if(this!=NULL)
  {
   cout<<this->key<<" ";
   this->left->Preorder();
   this->right->Preorder();
  }
 }
 void Postorder()
 {
  if(this!=NULL)
  {
   this->left->Postorder();
   this->right->Postorder();
   cout<<this->key<<" ";
  }
 }

 void MakeEmpty()
 {
  if(this!=NULL)
  {
   this->left->MakeEmpty();
   this->right->MakeEmpty();
   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);
 }
};


#endif // BRTREENODE_H_INCLUDED

BRTree.h


[cpp]
<SPAN style="FONT-SIZE: 14px">#ifndef BRTREE_H_INCLUDED 
#define BRTREE_H_INCLUDED  
#define maxSize 30  
#define maxWidth 30  
#include"BRTreeNode.h"  
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; 
    } 
    ~BRTree() 
    { 
        MakeEmpty(root); 
        delete 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); 
    } 
    int GetBlackHeight(BRTreeNode* node) 
    { 
        int L,R; 
        if(node==nil) return 0; 
        L=GetHeight(node->left); 
        R=GetHeight(node->right); 
        if(node->Getcolor()) return(L>R? L:R); 
        else 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<<" "; 
        } 
    } 
    //层次法打印树  
void DispTree(BRTreeNode*BT) 

    BRTreeNode stack[maxSize],p; 
    int level[maxSize][2],top,n,i,width=4; 
    if(BT!=NULL) 
    { 
        cout<<"Display a tree by hollow means."<<endl; 
        top=1; 
        stack[top]=BT;//push root point to stack.  
        level[top][0]=width; 
        while(top>0) 
        { 
            p=stack[top]; 
            n=level[top][0]; 
            for(i=1;i<=n;i++) 
                cout<<" "; 
            //输出信息  
            if(p.key==0) 
            { 
                cout<<")"; 
            } 
            else{ 
            if(p.key==-1) cout<<"Nil"; 
            else if(p.left&&p.right) cout<<"("<<p.key; 
            else cout<<p.key; 
            if(p.Getcolor()) cout<<"R,"; 
            else cout<<"B,"; 
            } 
            for(i=n+1;i<maxWidth;i+=2) 
                cout<<"--"; 
            cout<<endl; 
            top--; 
            if(p.right!=NULL) 
            { 
                //插入一个括号节点,key值为0  
                top++; 
                BRTreeNode* tmp=new BRTreeNode(); 
                tmp->key=0; 
                stack[top]=tmp; 
                level[top][0]=n+width; 
                level[top][1]=2; 
                top++; 
                stack[top]=p.right; 
                level[top][0]=n+width; 
                level[top][1]=2; 
 
            } 
            if(p.left!=NULL) 
            { 
                top++; 
                stack[top]=p.left; 
                level[top][0]=n+width; 
                level[top][1]=1; 
            } 
        } 
    } 

    //左旋节点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; 
        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; 
        return 1; 
    } 
    void Insert(int num) 
    { 
        BRTreeNode* node=new BRTreeNode(num,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; 
            return ; 
        } 
        while(p!=nil) 
        { 
            if(p->key==num) 
            { 
                cout<<num<<"  has exist!"<<endl; 
                return ; 
            } 
            else if(p->key>num) 
            { 
                q=p; 
                p=p->left; 
            } 
            else 
            { 
                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; 
        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  
</SPAN> 

#ifndef BRTREE_H_INCLUDED
#define BRTREE_H_INCLUDED
#define maxSize 30
#define maxWidth 30
#include"BRTreeNode.h"
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;
 }
 ~BRTree()
 {
  MakeEmpty(root);
  delete 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);
 }
    int GetBlackHeight(BRTreeNode* node)
 {
  int L,R;
  if(node==nil) return 0;
  L=GetHeight(node->left);
  R=GetHeight(node->right);
  if(node->Getcolor()) return(L>R? L:R);
  else 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<<" ";
  }
 }
 //层次法打印树
void DispTree(BRTreeNode*BT)
{
    BRTreeNode stack[maxSize],p;
    int level[maxSize][2],top,n,i,width=4;
    if(BT!=NULL)
    {
        cout<<"Display a tree by hollow means."<<endl;
        top=1;
        stack[top]=BT;//push root point to stack.
        level[top][0]=width;
        while(top>0)
        {
            p=stack[top];
            n=level[top][0];
            for(i=1;i<=n;i++)
                cout<<" ";
            //输出信息
            if(p.key==0)
            {
                cout<<")";
            }
            else{
            if(p.key==-1) cout<<"Nil";
            else if(p.left&&p.right) cout<<"("<<p.key;
            else cout<<p.key;
            if(p.Getcolor()) cout<<"R,";
            else cout<<"B,";
            }
            for(i=n+1;i<maxWidth;i+=2)
                cout<<"--";
            cout<<endl;
            top--;
            if(p.right!=NULL)
            {
                //插入一个括号节点,key值为0
                top++;
                BRTreeNode* tmp=new BRTreeNode();
                tmp->key=0;
                stack[top]=tmp;
                level[top][0]=n+width;
                level[top][1]=2;
                top++;
                stack[top]=p.right;
                level[top][0]=n+width;
                level[top][1]=2;

            }
            if(p.left!=NULL)
            {
                top++;
                stack[top]=p.left;
                level[top][0]=n+width;
                level[top][1]=1;
            }
        }
    }
}
 //左旋节点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;
  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;
  return 1;
 }
 void Insert(int num)
 {
  BRTreeNode* node=new BRTreeNode(num,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;
   return ;
  }
  while(p!=nil)
  {
   if(p->key==num)
   {
    cout<<num<<"  has exist!"<<endl;
    return ;
   }
   else if(p->key>num)
   {
    q=p;
    p=p->left;
   }
   else
   {
    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;
  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]
<SPAN style="FONT-SIZE: 14px">#include <iostream> 
#include"BRTree.h"  
#include "BRTreeNode.h"  
using namespace std; 
 
int main() 

    BRTree tree; 
    cout<<"Insert 9 numbers:"<<endl; 
    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:"<<endl; 
    tree.Delete(11); 
    tree.DispTree(tree.Getroot()); 
    cout << "blackHeight:" <<tree.GetBlackHeight(tree.Getroot())<<endl; 
 
    return 0; 
}</SPAN> 

#include <iostream>
#include"BRTree.h"
#include "BRTreeNode.h"
using namespace std;

int main()
{
    BRTree tree;
    cout<<"Insert 9 numbers:"<<endl;
    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:"<<endl;
    tree.Delete(11);
    tree.DispTree(tree.Getroot());
    cout << "blackHeight:" <<tree.GetBlackHeight(tree.Getroot())<<endl;

    return 0;
}

 

运行结果:

 


 

/
/