红黑树算法对应的c++实现

#include "RBTree.h" #include <string> using std::cout; using std::cin; using std::endl; using std::string; //using namespace Redblack; RBTree::RBTree(void) { cout <<"RBTree()\n"; nil = new Node(NULL, NULL, NULL, BLACK, -1); Root = nil; } RBTree::~RBTree(void) { if(nil){ delete nil; nil = NULL; } } //递归实现方法 RBTree::Node * RBTree::tree_minimum(RBTree & T,Node & z) { if(z.left == T.nil) return &z; else { return tree_minimum(T,*(z.left)); } } bool RBTree::RB_left_rotate(RBTree & T, Node & z) { Node * y = z.right; z.right = y->left; //step1 if(y->left != T.nil) //step1 y->left->p = &z; //step1 y->p = z.p; //step2 if(z.p == T.nil) { T.Root = y; }else if(z.p->left == &z) { z.p->left = y; }else //z.p->right == z { z.p->right =y; } //step2 y->left = &z; //step3 z.p = y; //step3 return true; } bool RBTree::RB_right_rotate(RBTree & T, Node & z) { Node * y = z.left; z.left = y->right; if(y->right != T.nil) y->right->p = &z; y->p = z.p; if(z.p == T.nil) { T.Root = y; }else if(z.p->left == &z) { z.p->left = y; }else //z.p->right == &z { z.p->right = y; } y->right = &z; z.p = y; return true; } /*将v迁移到u的位置， case1: u为root case2：u为右分支 \ -------> \ u v ................................ case3：u为左分支 / -------> / u v */ bool RBTree::RB_transplant(RBTree & T, Node & u, Node & v) { if(u.p == T.nil) //case1 { T.Root = &v; }else if(&u == u.p->right) //case2 { u.p->right = &v; }else //case3 { u.p->left = &v; } v.p = u.p; return true; } //bool RBTree::RB_insert_fixup(RBTree & T, Node & z) bool RBTree::RB_insert_fixup(RBTree & T, Node * z) { Node * uncle; while(z->p->color == RED) { if(z->p == z->p->p->left) //父节点处在左分支 { uncle = z->p->p->right; if(uncle->color == RED) //case1 { z->p->color = BLACK; //case1 uncle->color = BLACK; //case1 z->p->p->color = RED; //case1 z = z->p->p; //case1 }else { if( z == z->p->right ) //case2 { z = z->p; //case2 RB_left_rotate(T, *z); //case2 } z->p->color = BLACK; //case3 z->p->p->color = RED; //case3 RB_right_rotate(T, *(z->p->p)); //case3 } }else //父节点处在右分支,跟父亲处在左分支的代码基本相同，除了“左”和“右”互换 { uncle = z->p->p->left; if(uncle->color == RED) { z->p->color = BLACK; uncle->color = BLACK; z->p->p->color = RED; z = z->p->p; }else { if( z == z->p->left ) { z = z->p; RB_right_rotate(T, *z); } z->p->color = BLACK; z->p->p->color = RED; RB_left_rotate(T, *(z->p->p)); } } } T.Root->color = BLACK; return true; } /**/ bool RBTree::RB_delete_fixup(RBTree & T, Node * x) { Node *w;// w is brother of x node //to be continued while(x != T.Root && x->color == BLACK) { if(x == x->p->left)//x 是左分支 { w = x->p->right; if(w->color == RED) //case1 { w->color = BLACK; //case1 x->p->color = RED; //case1 RB_left_rotate(T,*(x->p)); //case1 w = x->p->right; //case1 }else //w->color == BLACK { if(w->left->color == BLACK && w->right->color == BLACK) //case2 { w->color = RED; //case2 x = x->p; //case2 }else if(w->right->color == BLACK) //case2 { w->left->color = BLACK; //case3 w->color = RED; //case3 RB_right_rotate(T,*(w)); //case3 w = x->p->right; //case3 }else //case4 { w->color = x->p->color; //case4 x->p->color = BLACK; //case4 w->right->color = BLACK; //case4 RB_left_rotate(T,*(x->p)); //case4 x = T.Root; //case4 } } }else ////x 是右分支，情况跟以上一样，除了“左”与“右”互换 { w = x->p->left; if(w->color == RED) //case1 { w->color = BLACK; //case1 x->p->color = RED; //case1 RB_right_rotate(T,*(x->p)); //case1 w = x->p->left; //case1 }else //w->color == BLACK { if(w->left->color == BLACK && w->right->color == BLACK) //case2 { w->color = RED; //case2 x = x->p; //case2 }else if(w->left->color == BLACK) //case2 { w->right->color = BLACK; //case3 w->color = RED; //case3 RB_left_rotate(T,*(w)); //case3 w = x->p->left; //case3 }else //case4 { w->color = x->p->color; //case4 x->p->color = BLACK; //case4 w->left->color = BLACK; //case4 RB_right_rotate(T,*(x->p)); //case4 x = T.Root; //case4 } } } } x->color = BLACK; return true; } bool RBTree::RB_insert(RBTree & T, Node & z) { Node * parent = T.nil; Node * son = T.Root; while(son != T.nil)//在二叉树中，找到插入位置 { parent = son; if(z.key > son->key) son = son->right; else son = son->left; } z.p = parent; // parent 指向被插入点的父节点 if(parent == T.nil) //如果z是目前tree中的唯一节点，则修改T.Root T.Root = & z; else if (parent->key > z.key)//插入到左分支 parent->left = & z; else parent->right = & z;//插入到右分支 z.left = T.nil; z.right = T.nil; z.color = RED; //被插入点，默认都是红色 RB_insert_fixup(T, &z);//由于可能存在两个连续的红色节点，从而破外红黑树的性质，故需要修正 return true; } RBTree::Node * RBTree::RB_delete(RBTree & T, Node & z) { //z 是要删除的节点 //y 是真正被删除的节点 //x 是真正被删除节点的右孩子 Node * y = &z; Node * x; bool y_orig_color = y->color; if(z.left == T.nil)//被删除节点左为空 { x = z.right; RB_transplant(T, z, *(z.right)); }else if(z.right == T.nil)//被删除节点右为空 { x = z.left; RB_transplant(T, z, *(z.left)); }else//被删除节点左右不为空: y迁移到z的位置，并保留z的颜色，x填充y的位置 { y = tree_minimum(T,*(z.right));//y节点的左侧最小的节点即是真正被删除的节点 y_orig_color = y->color; x = y->right;// /* case 1 z \ y \ x */ if(y->p == &z) //case1 { x->p = y; }else { //case2 /* case 2 z \ ... \ y \ x */ RB_transplant(T, *y, *(y->right));//将x填充到y的位置 y->right = z.right; //复制z的右分支到y y->right->p = y; } RB_transplant(T, z, *y);//将y迁移到z的位置，保留z的颜色和左右分支信息 //复制z的左分支到y y->left = z.left; y->left->p = y; //将y染成z的颜色 y->color = z.color; } if(y_orig_color == BLACK)//当y为黑色时，删除y会导致y附近的黑高速减少1，所以需要重新重新旋转和着色 RB_delete_fixup(T, x); return &z; } RBTree::Node * RBTree::RB_search(RBTree & T, int key) { return NULL; } RBTree::Node * RBTree::RB_next(RBTree & T) { return NULL; } RBTree::Node * RBTree::RB_next(const Node * z) { return NULL; } #include <stdlib.h> #include <time.h> int main() { bool exit = true; string temp; RBTree Tree; cout<<"Tree.nil "<<Tree.nil<<endl; cout <<"please input key of node to be inserted !!!"<<endl; srand(time(NULL)); //while(exit) for(int i=0;i<6;i++) { RBTree::Node * new_node = new RBTree::Node(); cin>> new_node->key; cout<<"key:"<<new_node->key<<endl; //new_node->key = rand()%191 +10; // 10 <= key <= 200 Tree.RB_insert(Tree, *new_node); } cout << "red black tree contructed!!!\n"; cout <<"begin to delete the root the first time\n"; RBTree::Node * tmp; tmp = Tree.RB_delete(Tree, *(Tree.Root)); cout <<