首页 > 代码库 > 红黑树
红黑树
弄了很久，学习过程中觉得很难，但学完了，其实感觉也就那样，就是情况多了些。
首先是插入，插入的时候其实也就3种情况，因为只有当插入的节点的父亲是红色的时候，此时红黑树的性质遭到破坏，需要旋转，再分1.叔父节点为红，此时只要改变颜色，但祖父节点颜色的改变可能会破坏红黑树的性质，所以要node = grandparent，继续向上，叔父为黑，这时需要旋转，所以得判断，自身的位置，也就是自己和父亲分别是左孩子还是右孩子，2.如果自身是右，父亲是左，的先把自己也旋转到左，再和自己是左，父亲也是左的情况一起处理，即再进行一次旋转，旋转其实只要是为了满足根节点到叶子节点的黑色节点数这一性质（其实是在减小树的深度），颜色的改变一是配合旋转，二是满足些别的性质，3.自身是左，而父亲是右也就是差不多的了。
另外就是删除，删除就很麻烦一些了，首先是要找到要删除节点的右孩子的最左儿子（左右儿子都存在的情况下）来替代，左儿子不存在直接用右儿子替代，右儿子不存在直接用左儿子替代，都不存在则用空节点替代，另外记录下替代节点的孩子和替代节点的父亲（如果删除节点只有一个孩子，替代节点的孩子就是替代节点），然后把孩子指向父亲，只记一个node是不行的，因为node可能为空，当替代点的颜色是黑色的话，需要另外平衡，平衡中如果替代节点的孩子是红色，直接改成黑色就OK了（因为之前只是少了个黑色节点，而红改黑除了改变黑色节点的个数外是不改变别的性质的），当替代节点孩子是黑色时，再分其兄弟节点的颜色1.兄弟节点是红色，此时改变颜色，单步旋转（因为兄弟节点所在的枝黑色节点只比另一边多一）；然后如果兄弟节点是黑色2.兄弟节点的两个孩子也是黑色或者是空，此时只需改变颜色，但父亲颜色的改变可能会破坏树的性质则node = grandparent，向上继续传，来平衡3.兄弟节点有一个红，此时又得确定位置，父亲是左孩子，而自己是右孩子黑色或空，又得先把黑色的旋转到和父亲相同的相对位置，4然后转到父亲和自己都是左孩子情况，一步旋转。父亲是右孩子的情况也一样。
自己写上面的删除和插入的时候自己都感觉晕晕的，感觉了解的还不是很彻底，改天得再写一遍。。。
#include <iostream> #include <cstdio> using namespace std; #define red 0 #define black 1 template <class T> class red_black_node { public: red_black_node* left; red_black_node* right; red_black_node* parent; T key; int color; red_black_node(T value):left(NULL),right(NULL),parent(NULL),color(red),key(value){}; red_black_node(T value,red_black_node* l,red_black_node* r,red_black_node* p): left(l),right(r),parent(p),T(value),color(red){}; }; template <class T> class red_black_tree { public: red_black_node<T>* mRoot;//根节点 public: red_black_tree(); ~red_black_tree(); void Destory(red_black_node<T>* Pnode); red_black_node<T>* RotateLeft(red_black_node<T>* p,red_black_node<T>* r); red_black_node<T>* RotateRight(red_black_node<T>* p,red_black_node<T>* r); red_black_node<T>* Insert_into(T k,red_black_node<T>* root); void Insert(T k); red_black_node<T>* Search(T k,red_black_node<T>* root); red_black_node<T>* Insert_balance(red_black_node<T>* node,red_black_node<T>* root); void Travel_it(red_black_node<T> *root); void Trave(); red_black_node<T>* Delete_Replace(T k,red_black_node<T>* root); void Delete(T k); red_black_node<T>* Delete_balance(red_black_node<T>* child,red_black_node<T>* parent,red_black_node<T>* root); }; //左旋函数，并未改变颜色 template <class T> red_black_node<T>* red_black_tree<T>::RotateLeft(red_black_node<T>* node,red_black_node<T>* root) { red_black_node<T>* tem = node->left; node->left = tem->right; tem->right = node; tem->parent = node->parent; node->parent = tem; if(node->left!=NULL) node->left->parent = node; if(tem->parent==NULL) { root = tem; } else { if(tem->key > tem->parent->key) { tem->parent->right = tem; } else { tem->parent->left = tem; } } return root; } //构造函数 template <class T> red_black_tree<T>::red_black_tree() { mRoot = NULL; } //析构函数 template <class T> red_black_tree<T>::~red_black_tree() { Destory(mRoot); } //单步右旋 template <class T> red_black_node<T>* red_black_tree<T>::RotateRight(red_black_node<T>* node,red_black_node<T>* root) { red_black_node<T>* tem = node->right; node->right = tem->left; tem->left = node; tem->parent = node->parent; node->parent = tem; if(node->right!=NULL) node->right->parent = node; if(tem->parent==NULL) { root = tem; } else { if(tem->parent->key > tem->key) { tem->parent->left = tem; //red_black_tree<T>::Travel_it(root); } else { tem->parent->right = tem; } } return root; } //销毁红黑树 template <class T> void red_black_tree<T>::Destory(red_black_node<T>* PnodeHeader) { if(PnodeHeader==NULL) return ; if(PnodeHeader->left!=NULL) Destory(PnodeHeader->left); if(PnodeHeader->right!=NULL) Destory(PnodeHeader->right); delete PnodeHeader; } template <class T> void red_black_tree<T>::Insert(T k) { mRoot = Insert_into(k,mRoot); } template <class T>//返回的是自己或者是自己的父亲 red_black_node<T>* red_black_tree<T>::Search(T k,red_black_node<T>* root) { red_black_node<T>* tem = root; if(tem==NULL)return NULL; while(true) { if(k<tem->key) { if(tem->left==NULL)return tem; else tem = tem->left; } else if(k>tem->key) { if(tem->right==NULL)return tem; else tem = tem->right; } else return tem; } } template <class T> red_black_node<T>* red_black_tree<T>::Insert_into(T k,red_black_node<T>* root) { red_black_node<T>* node; red_black_node<T>* tem = Search(k,root); //if(tem->key==k)return root;//重复直接退出 node = new red_black_node<T>(k); node->parent = tem; if(tem) { if(tem->key > k) { tem->left = node; } else { tem->right = node; } } else { root = node; } //red_black_tree<T>::Trave(); return Insert_balance(node,root); } template<class T> red_black_node<T>* red_black_tree<T>::Insert_balance(red_black_node<T>* node,red_black_node<T> *root) { red_black_node<T> *p,*gp,*uncle,*tem; while((p=node->parent)&&p->color==red) { gp = p->parent; if(p==gp->left) { uncle = gp->right; if(uncle&&uncle->color==red)//1.父亲节点和叔父节点都为红 { uncle->color = black;// p->color = black; gp->color = red; node = gp; } else { if(p->right==node)//2.叔父节点为黑，或者不存在，自己是右孩子，父亲是左孩子 { root = RotateRight(p,root); tem = p; p = node; node = tem; } p->color = black; gp->color = red; root = RotateLeft(gp,root); } } else { uncle = gp->left; if(uncle&&uncle->color==red) { uncle->color = black; p->color = black; gp->color = red; node = gp; } else { if(p->left==node) { root = RotateLeft(p,root); tem = p; p = node; node = tem; } p->color = black; gp->color = red; root = RotateRight(gp,root); } } } root->color = black; return root; } //打印函数 template <class T> void red_black_tree<T>::Travel_it(red_black_node<T> *root) { if(root==NULL)return; printf("father is:%d",root->key); if(root->color==red)printf("(red)"); else printf("(black)"); printf(" left:"); if(root->left==NULL)printf("NULL"); else { printf("%d",root->left->key); if(root->left->color==red)printf("(red)"); else printf("(black)"); } printf(" right:"); if(root->right==NULL)printf("NULL\n"); else { printf("%d",root->right->key); if(root->right->color==red)printf("(red)\n"); else printf("(black)\n"); } Travel_it(root->left); Travel_it(root->right); } template <class T> void red_black_tree<T>::Trave() { Travel_it(mRoot); } template <class T>//左右子树都不空时用右孩子的最左子树来替代，左子树为空，直接用右孩子替代，右子树为空直接用左孩子替代 red_black_node<T>* red_black_tree<T>::Delete_Replace(T k,red_black_node<T>* root) { red_black_node<T> *tem; tem = red_black_tree<T>::Search(k,mRoot); if(tem==NULL)return mRoot; if(tem->key!=k) { printf("The Key Is Wrong\r\n"); return mRoot; } red_black_node<T>* aim = tem; red_black_node<T>* replace_parent; red_black_node<T>* replace_child; int color; if(tem->left&&tem->right) { tem = tem->right; while(tem->left!=NULL) { tem = tem->left; } replace_parent = tem->parent; replace_child = tem->right; color = tem->color; if(replace_child) { replace_child->parent = replace_parent; } if(replace_parent) { if(tem->key < replace_parent->key) { replace_parent->left = replace_child; } else { replace_parent->right = replace_child; } } else//?? { root = replace_child; } //?? if (tem->parent == aim) { replace_parent = tem; } tem->parent = aim->parent; tem->left = aim->left; tem->right = aim->right; tem->color = aim->color; if(aim->parent) { if(tem->key < aim->parent->key) { tem->parent->left = tem; } else { tem->parent->right = tem; } } else { root = tem; } aim->left->parent = tem; if(aim->right) { aim->right->parent = tem; } } else { if(!tem->left) { replace_child = tem->right; } else if(!tem->right) { replace_child = tem->left; } replace_parent = tem->parent; color = tem->color; if(replace_child) { replace_child->parent = replace_parent; } if(replace_parent) { if(replace_parent->left==tem) { replace_parent->left = replace_child; } else { replace_parent->right = replace_child; } } else { root = replace_child; } } delete aim; if(color==black) { root = Delete_balance(replace_child,replace_parent,root); } return root; } template <class T> void red_black_tree<T>::Delete(T k) { mRoot = Delete_Replace(k,mRoot); } template <class T>//替代的节点是黑色时的旋转平衡 red_black_node<T>* red_black_tree<T>::Delete_balance(red_black_node<T>* child,red_black_node<T>* parent,red_black_node<T>* root) { red_black_node<T> *other, *o_left, *o_right; while((!child||child->color==black)&&child!=root) { if(parent->left==child)//是左孩子，只能是，之前用删除节点的左孩子替代 { other = parent->right; if(other->color==red) { other->color = black;//兄弟节点是红色 parent->color = red; root = RotateRight(parent,root);//旋转下即可 other = parent->right; } //x的兄弟是黑色的，且两个孩子也是黑色的 if ((!other->left || other->left->color == black) && (!other->right || other->right->color == black)) { other->color = red; child = parent; parent = child->parent; } else { if(!other->right||other->right->color==black) { if(o_left = other->left) { o_left->color = black; } other->color = black; root = RotateLeft(other,root); other = parent->right; } //x的兄弟是黑色的 other->color = parent->color; parent->color = black; if(other->right) { other->right->color = black; } root = RotateRight(parent,root); child = root; break; } } else { other = parent->left; if(other->color==red) { other->color = black; parent->color = red; root = RotateLeft(parent,root); other = parent->left; } if((!other->left||other->left->color==black)&&(!other->right||other->right->color==black)) { other->color = red; child = parent; parent = child->parent; } else { if(!other->left||other->left->color==black) { if(o_right = other->right) { o_right->color = black; } other->color = red; root = RotateRight(other,root); other = parent->left; } other->color = parent->color; parent->color = black; if(other->left) { other->left->color = black; } root = RotateLeft(parent,root); child = root; break; } } } if(child) { child->color = black; } return root; } int main() { int a[] = {15,7,10,9,4,5,8,20,1,6}; red_black_tree<int>* tree = new red_black_tree<int>(); red_black_node<int> *root = NULL; for(int i=0;i<sizeof(a)/sizeof(int);i++) { tree->Insert(a[i]); //tree->Find_parent(); // tree->Trave(); // getchar(); } tree->Trave(); printf("\n"); for(int i=0;i<sizeof(a)/sizeof(int);i++) { tree->Delete(a[i]); tree->Trave(); getchar(); } return 0; }
红黑树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。