vlambda博客
学习文章列表

搞定红黑树(C++实现)

来源：http://a.nxw.so/1wSOqU




红黑树的概念


红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是红色或黑色。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。如下图：

搞定红黑树(C++实现)


红黑树的性质


  1. 每个结点不是红色就是黑色

  2. 根节点是黑色的

  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的

  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点

  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)


上面的4点性质用自己的话可以总结为：(性质5不用记)


  • 结点不是红色就是黑色

  • 没有连续的红色结点

  • 每条路径上的黑色结点的数量是一样的


AVL树是通过高度来控制平衡的，是严格平衡的。那如果新插入结点很多那么旋转也是要付出代价的。红黑树通过颜色来控制平衡，但不是严格的平衡，它近似平衡。红黑树也可以达到AVL树的效率。它最长路径不超过最短路径的2倍。


那为什么红黑树的最长路径不超过最短路径的2倍呢？


通过上面的性质，假设我们把红黑树的黑色结点单独抽出来，从跟到叶子黑结点个数为N个

搞定红黑树(C++实现)

那它最短路径就是长度为N
那它最长的路径可能是一黑一红

搞定红黑树(C++实现)

那它的长度为2N，所以它的最长路径不超过最短路径的2倍，则其他路径的长度就在N-2N之间。那么红黑树增删查改的效率就在logN-2logN之间，和AVL树的logN差不多了。


红黑树的结点定义


红黑树的结点定义还是跟AVL树一样，定义成三叉链结构和KV模型，不同的则是红黑树用枚举加入了颜色。

enum Color{ RED, BLACK};template<class K, class V>struct RBTreeNode{ RBTreeNode<K, V> _left;//结点的左孩子 RBTreeNode<K, V> _right;//结点的右孩子 RBTreeNode<K, V> _parent;//结点的双亲 pair<K, V>_kv; Color _color;//该结点的颜色 RBTreeNode(const pair<K,V>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) ,_color(RED) {}};


红黑树的插入


那么我们插入结点时选择插入黑结点还是红结点呢？


当然是选择插入红结点了。选择插入黑结点那麻烦就大了，那1条路径上就多了1个黑结点，破坏了性质4，代价很大。插入红结点，如果它的父亲结点是黑色则不用调整，拍拍屁股走人，它的父亲是红色那我们在进行后序的处理。


总结一下：

  • 插入黑色结点一定破坏性质4，调整起来会很麻烦

  • 插入红结点不一定破坏红黑树的性质，它的父亲结点是红色才进行调整，比插入黑结点调整起来方便。


插入的逻辑：


  • 找到插入结点的位置

  • 插入结点

  • 检测新结点插入后是否破坏了红黑的性质，如果破坏则需要进行处理


因为新插入结点的颜色是红色，若它的父亲结点是黑色不用调整，是红色的话需要对红黑树分情况来讨论。


红黑树调整主要看叔叔结点


下面我们根据叔叔结点的情况来具体看一下。

情况一


以下用p来代表parent结点，c代表cur为新增结点,g代表grandparent结点，u代表uncle结点。
我们还是跟AVL树一样画具象图：

叔叔结点存在且为红

搞定红黑树(C++实现)

为什么把g变成红色呢？如果g不变成红色，那此时子树上就多了1个黑结点了。
只要我们画出具象图，那面试时手撕红黑树也完全不怂。

当然还有很多种情况，那就给出抽象图：

搞定红黑树(C++实现)

这种情况下cur在p的左边还是右边都不影响。

情况二

叔叔结点存在且为黑，新增结点是p的左边

搞定红黑树(C++实现)

这是由情况一变来的，如果u存在那cur一定是黑的，不是新郑结点，这样才满足红黑树的性质。

新增结点是p的右边

搞定红黑树(C++实现)

情况三

叔叔结点不存在

新增结点在parent的左边

搞定红黑树(C++实现)

新增结点在parent的右边

搞定红黑树(C++实现)

总结一下：

以上的情况都是父亲结点在祖先结点的左边，在祖先结点的右边也是相同的处理方法

  • 叔叔结点存在且为红，把父亲结点和叔叔结点变黑，祖先变红继续向上处理直到祖先是根节点

  • 叔叔存在为黑，祖孙三代在一条直线上进行单旋，不在则进行双旋

  • 叔叔不存在，祖孙三代在一条直线上进行单旋，不在则进行双旋


所以2,3的逻辑可以合在一起，分为新增结点在父亲结点的左边还是右边处理。


下面再来简单的说说父亲结点在祖先结点的右边


叔叔存在且为红

搞定红黑树(C++实现)

此时，cur在p的左边还是右边没有影响。


叔叔存在且为黑


新增结点在父亲结点的右边

搞定红黑树(C++实现)

新增结点在父亲结点的左边

搞定红黑树(C++实现)

叔叔不存在

总结一下：

  • 叔叔存在且为红,u,p变黑，g变红继续向上调，直到g为根结点，最后把g变黑

  • 叔叔存在且为黑，祖孙3带在一条直线上单旋，折线要双旋

  • 叔叔不存在，祖孙3带在一条直线上单旋，折线要双旋

代码如下：

 pair<Node*, bool> insert(const pair<K, V>& kv) { //1.树为空 if (_root == nullptr) { _root = new Node(kv); _root->_color = BLACK;//根结点为黑色 return make_pair(_root, true); } //树不为空 Node* cur = _root; Node* parent = nullptr; while (cur) { //新结点key大于当前结点往右边 if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } //新结点key小于当前结点往左边 else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return make_pair(cur, false); } } cur = new Node(kv); Node* newnode = cur; newnode->_color = RED; if (parent->_kv.first < kv.first) { parent->_right = newnode; newnode->_parent = parent; } else { parent->_left = newnode; newnode->_parent = parent; }
 //开始调整颜色 //父亲存在且为红 while (parent && parent->_color == RED) { Node* grandParent = parent->_parent;  //parent是grandParent左孩子 if (grandParent->_left == parent) { Node* uncle = grandParent->_right; //叔叔存在且为红色,父亲和叔叔都调为黑色 //祖先调为红色，如果不调那每条路径的黑结点变了 if (uncle && uncle->_color == RED) { parent->_color = BLACK; uncle->_color = BLACK; grandParent->_color = RED; //继续往上调 cur = grandParent; parent = cur->_parent; } else//叔叔不存在或叔叔存在且为黑 { if (parent->_left == cur) { //右单旋 RotateR(grandParent); parent->_color = BLACK; grandParent->_color = RED; } else //parent->_right == cur { RotateL(parent); RotateR(grandParent); grandParent->_color = RED; cur->_color = BLACK; } break; } } else //parent是grandParent左孩子 { Node* uncle = grandParent->_left; if (uncle && uncle->_color == RED) { uncle->_color = BLACK; parent->_color = BLACK; grandParent->_color = RED; cur = grandParent; parent = cur->_parent; } else { if (parent->_right == cur) { RotateL(grandParent); parent->_color = BLACK; grandParent->_color = RED; } else { RotateR(parent); RotateL(grandParent); cur->_color = BLACK; grandParent->_color = RED; } break; }  } } _root->_color = BLACK; return make_pair(newnode, true); } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* parentParent = parent->_parent; //先旋转 parent->_right = subRL; subR->_left = parent;
 parent->_parent = subR; //在改父亲结点 if (subRL) subRL->_parent = parent; if (_root == parent) { _root = subR; _root->_parent = nullptr; }
 else { //subR旋转后可能是左右子树2种情况 if (parentParent->_left == parent) parentParent->_left = subR; else parentParent->_right = subR; subR->_parent = parentParent; } } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* parentParent = parent->_parent;//记录parent的父亲结点 //subLR做parent->_left parent->_left = subLR; subL->_right = parent; //同时更新动的2个节点的parent //注意subLR还可能是空结点 if (subLR) subLR->_parent = parent; parent->_parent = subL; //parent可能是单独的树，或者子树,分情况 if (_root == parent) { _root = subL; _root->_parent = nullptr; }
 else { //还有可能parent是子树，可能是左子树 if (parentParent->_left == parent) parentParent->_left = subL; else //也可能是右子树 parentParent->_right = subL; //调整subL的父亲结点 subL->_parent = parentParent; } }


红黑树的查找


查找跟AVL树的逻辑是一样的，这里就不做多的讲解了。

 Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first > key) { cur = cur->_left; } else if (cur->_kv.first < key) { cur = cur->_right; } else { return cur; } }
 return nullptr; }


红黑树的验证


先检查有没有连续的红结点，还有红结点的父亲结点是不是黑色。这就保证了没有连续的红结点。还有路径也要算。我们找1条路径作为参考，例如最左路径，只要有1条路径和它的黑结点数量不同就不是红黑树。

bool _CheckBlance(Node* root,int blackNum, int count) { if (root == nullptr) { if (count != blackNum) { cout << "黑色节点的数量不相等" << endl; return false; }
 return true; }
 if (root->_color == RED && root->_parent->_color == RED) { cout << "存在连续的红色节点" << endl; return false; }
 if (root->_color == BLACK) { count++; }
 return _CheckBlance(root->_left, blackNum, count) && _CheckBlance(root->_right, blackNum, count); }
 bool CheckBlance(){ if (_root == nullptr) { return true; }
 if (_root->_color == RED) { cout << "根节点是红色的" << endl; return false; }
 // 找最左路径做黑色节点数量参考值 int blackNum = 0; Node* left = _root; while (left) { if (left->_color == BLACK) { blackNum++; }
 left = left->_left; }
 int count = 0; return _CheckBlance(_root, blackNum, count); }

我们来测试一下：



没有问题，我也是调试了好长时间。一定要用好调试。


红黑树的和AVL树的简单比较


红黑树的删除也是了解，红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log2)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。


简单分享快乐学习，如有错误请多包涵！


PS：如果没有你的关注，那我所做的将毫无意义！欢迎分享，点赞，在看。

推荐阅读

[5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档 [5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档
【安全资讯】未能修补Log4j或将被采取法律行动 【安全资讯】未能修补Log4j或将被采取法律行动

相关文章