ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据布局之红黑树 [打印本页]
作者: 曹旭辉    时间: 2025-1-13 23:36
标题: 数据布局之红黑树
注：本文为 “红黑树” 干系文章合辑。
未整理去重，如有内容异常请看原文。
Red-Black Tree / 红黑树

AWN
Feb 7, 2020

from Beenabug44 on pixabay.com .
树的搜寻 (Tree Search)，不停是电脑科学领域的重要算法，当中探究了树大概碰到的标题：树成长时大概偏重于特定一边，即不平衡 (Unbalance) 的现象。二元树是常见且广泛利用的一种树，面临如许关乎运气、大概退化成连结串列 (Linked List) 的潜藏缺点，在利用上免不了让人担心效能是否能常保顺畅。此外，在一些应用上，大概不期望如许不平衡的大概性发生，以是具有主动平衡左右数目分布效果的算法早在约 1962 年便被发表出来，称为 AVL 树 (Adelson-Velsky and Landis Tree, AVL Tree)。这种平衡成长的二元搜寻树 (Binary Search Tree, BST) 被归类称为自平衡二元搜寻树 (Self-Balancing Binary Search Tree)。
接下来，要介绍同归为自平衡二元搜寻树的红黑树 (Red-Black Tree, RBT or RB Tree) 对平衡性的要求比 AVL 树还宽松。红黑树是利用节点颜色来检视二元树每条延展的路径高度是否差不多，因此发明者订立了以下几点规则：
满意上述规则的二元树，相比一般的二元树更能保持平衡性，今后套用二元树的算法来查找资料时能更快速、方便地到达目的地，套用运算的时间复杂度为 O(log n)，这是由于红黑树保证最长路径不会超过最短路径的两倍。
由于红黑树也是二元树的一种，以是例如：新增节点、删除节点、查询节点等针对红黑树的操纵与二元树的操纵前段算法相同，只是在每次操纵完毕之后大概会让树的布局改变而大概无法满意成为红黑树的性质，进而大概不具有平衡的性质。为了在操纵后仍是一棵红黑树 (满意上述五项规则)，以下有两项基本运算可以用来帮助调整树状布局以满意红黑树的规则，这两个运算分别为变色与旋转 (左旋、右旋)。
   复习小教室：Operations on Binary Search Tree
  
    首先是变色，这个运算很容易理解，就是将当前颜色改变成另一个颜色，例如赤色改成玄色。但是很多时候用到的运算是旋转：

Left Rotation on Node P

Right Rotation on Node P
如上是以节点 P 为中心进行旋转运算。基本上维持红黑树的演算过程都是由变色与旋转依次组成。总结来说，红黑树的新增与删除操纵是先透过一般二元树的新增与删除操纵后，再从递补的节点开始向上进行红黑树性质维护。接下来，直接用例子演示走过一遍新增与删除节点的算法更能相识到变色与旋转的作用为何：
新增 (Insertion)
在新增操纵上，新插入的节点同等都为赤色，目的是盼望红黑树维持规则 5 的约束，但也大概会违反除了规则 5 以外的其他规则，以是作完二元树新增节点的操纵后，需要以新增的节点开始向上检查红黑树是否符合各项规则，修正红黑树的算法大概会有以下几种情境，因应差别情境会采取差别的修正过程：
情境一：红黑树为空，插入红节点后成为根结点，会违反规则 2，需将该节点改为玄色，即可完成红黑树维护。

Case 1: Red Node on the Empty RB Tree
情境二：在黑节点上与红节点 z 相接，不违反任何规则，无须作其他调整。

Case 2: Red Node on a Black Node
情境三：在红节点上与红节点 z 相接，会违反规则 4。从自己开始维护，若叔叔节点为赤色，则先将父节点涂黑，用以保持规则 4，但这时会违反规则 5，以是须再将祖节点与叔节点分别涂成赤色和玄色。接着再从祖节点继承往上检查维护。
如图片，可以看到最后的结果违反规则 4，该情境符合情境四所示，其父节点与自身皆为赤色，以是下一轮会再以对应的流程处理。

Case 3: Red Node on a Red Node with its Red Uncle Node
情境四：在红节点上与红节点 z 相接，会违反规则 4。从自己开始维护，若叔叔节点为玄色且自己位置在父节点右边的状态，则先以父节点进行左旋，形成情境五，再作为情况五进行下一轮的处理。

Case 4: Red Node on the Right Side of Red Node with its Black Uncle Node
情境五：在红节点上与红节点 z 相接，会违反规则 4。从自己开始维护，若叔叔节点为玄色且自己位置在父节点左边的状态，则先将父节点改为玄色，用以保持规则 4，但这时会违反规则 5，以是须再将祖节点涂成赤色，接着再以祖节点进行右旋，即能完成维护。(直觉上，节点 F 的左边路径会多一个玄色，可以透过右旋把玄色转掉)

Case 5: Red Node on the Left Side of Red Node with its Black Uncle Node
删除 (Deletion)
在删除操纵上，删除一个节点时大概也会违反规则，以是作完二元树删除节点的操纵后，视需要以递补节点开始向上检查红黑树是否符合各项规则，修正红黑树的算法大概会有以下几种情境，因应差别情境会采取差别的修正过程：
**情境一：**删除红节点，不违反任何规则，无须进行维护。

Case 1: Deletion on Red Node
情境二：删除节点为玄色需要进行维护。删除黑节点后，如果递补上来的节点为赤色时，由于黑节点被删除会违反规则 5，以是直接将递补的红节点涂黑即可。或者，如果维护点在根结点时，如果根节点为赤色，这时则违反规则 2，直接将根节点涂黑即可。

Case 2: Deletion on Black Node with Red Node Compensation
情境三：删除节点为玄色需要进行维护。删除黑节点后，如果递补上来的节点为玄色时，需要视情况补足路径上缺失的一个玄色，会以递补节点作为当前节点开始进行维护：
兄弟节点如果赤色，则将兄弟节点涂黑、父节点涂红、再以父节点为基准左旋 (由于节点 C 的左边路径会少一个玄色，直觉会是透过左旋把玄色补起来)。但是可以发现现在的红黑树还是违反规则 5，固然无法完全解决标题，但是递补节点的兄弟节点改变了，可以新情境再下一轮进行对应的修正。

Case 3: Deletion on Black Node with Black Node Compensation and Red Sibling Node
情境四：删除节点为玄色需要进行维护。删除黑节点后，如果递补上来的节点为玄色时，需要视情况补足路径上缺失的一个玄色，会以递补节点作为当前节点开始进行维护：
兄节点如果玄色，且兄节点之左节点与右节点同为玄色的时候，则将兄节点涂红。这时若父节点为赤色则结束修正后将父节点涂黑即可，但是如果父节点为玄色，则需要再从父节点开始进行修正 (由于也要照顾到父节点的兄门生树，看看是否也满意规则 5)。

Case 4: Deletion on Black Node with Black Node Compensation and Black Sibling Node with its Two Black Child Nodes
情境五：删除节点为玄色需要进行维护。删除黑节点后，如果递补上来的节点为玄色时，需要视情况补足路径上缺失的一个玄色，会以递补节点作为当前节点开始进行维护：
兄节点如果玄色，且兄节点之左节点为赤色、右节点为玄色的时候，则将兄节点涂红、兄节点之左节点涂黑，再以兄节点为基准右旋，接着再进行下次的修正 (若采用左旋会变成相同情境，以是只好右旋，才大概跳离循环)。

Case 5: Deletion on Black Node with Black Node Compensation and Black Sibling Node with its Red Left Child Node
情境六：删除节点为玄色需要进行维护。删除黑节点后，如果递补上来的节点为玄色时，需要视情况补足路径上缺失的一个玄色，会以递补节点作为当前节点开始进行维护：
兄节点如果玄色，且兄节点之右节点为赤色的时候，则将兄节点涂成与父节点相同的颜色、父节点涂黑、兄节点的右节点涂黑，再以父节点为基准左旋即可。(透过左旋与涂色操纵将右边的玄色往左调整、并将右边红点涂黑补足缺失，盼望符合规则 5 来让每条路径上玄色节点的数目同等)

Case 6: Deletion on Black Node with Black Node Compensation and Black Sibling Node with its Red Right Child Node
红黑树谨遵单单五条规则，前人总结了各种情况后，列出对应的处理方式。过后理解情境的对应处理方式固然有迹可循，但是窥探此中奥秘却也令人慑服，很难想像这项算法从无到有所付出的庞大心力与挫折！
Reference
最容易懂得红黑树

Sun_TTTT 于 2017-03-23 17:00:58 发布
介绍

红黑树是一个平衡的二叉树，但不是一个完美的平衡二叉树。固然我们盼望一个所有查找都能在~lgN次比力内结束，但是如许在动态插入中保持树的完美平衡代价太高，以是，我们稍微放松逛一下限定，盼望找到一个能在对数时间内完成查找的数据布局。这个时候，红黑树站了出来。
阅读以下需要相识普通二叉树的插入以及删除操纵。
红黑树是在普通二叉树上，对没个节点添加一个颜色属性形成的，同时整个红黑二叉树需要同时满意一下五条性质
红黑树需要满意的五条性质：
性质一：节点是赤色或者是玄色；
在树内里的节点不是赤色的就是玄色的，没有其他颜色，要不怎么叫红黑树呢，是吧。
性质二：根节点是玄色；
根节点总是玄色的，它不能为红。
性质三：每个叶节点（NIL或空节点）是玄色；
这个大概有点理解困难，可以看图：

这个图片就是一个红黑树，NIL节点是个空节点，而且是玄色的。
性质四：每个赤色节点的两个子节点都是玄色的（也就是说不存在两个连续的赤色节点）；
就是连续的两个节点不能是连续的赤色，连续的两个节点的意思就是父节点与子节点不能是连续的赤色。
性质五：从任一节点到其没个叶节点的所有路径都包含相同数目的玄色节点；
还是看图：

从根节点到每一个NIL节点的路径中，都包含了相同数目的玄色节点。
这五条性质约束了红黑树，可以通过数学证实来证实，满意这五条性质的二叉树可以将查找删除维持在对数时间内。
当我们进行插入或者删除操纵时所作的一切操纵都是为了调整树使之符合这五条性质。
下面我们先介绍两个基本操纵，旋转。
旋转的目的是将节点多的一付出让节点给另一个节点少的一支，旋转操纵在插入和删除操纵中经常会用到，以是要熟记。
下面是左旋和右旋
左旋：

右旋：

下面讲讲插入
我们先明确一下各节点的叫法

由于要满意红黑树的这五条性质，如果我们插入的是玄色节点，那就违反了性质五，需要进行大规模调整，如果我们插入的是赤色节点，那就只有在要插入节点的父节点也是赤色的时候违反性质四或者是当插入的节点是根节点时，违反性质二，以是，我们把要插入的节点的颜色变成赤色。
下面是大概碰到的插入的几种状态：
1、当插入的节点是根节点时，直接涂黑即可；
2、当要插入的节点的父节点是玄色的时候。

这个时候插入一个赤色的节点并没有对这五个性质产生破坏。以是直接插入不消在进行调整操纵。
3、如果要插入的节点的父节点是赤色且父节点是祖父节点的左支的时候。
这个要分两种情况，一种是叔叔节点为黑的情况，一种是叔叔节点为红的情况。
当叔叔为黑时，也分为两种情况，一种是要插入的节点是父节点的左支，另一种是要插入的节点是父亲的右支。
我们先看一下当要插入的节点是父节点的左支的情况：

这个时候违反了性质四，我们就需要进行调整操纵，使之符合性质四，我们可以通过对祖父节点进行右旋同时将祖父节点和父节点的颜色进行互换，如许就变成了：

颠末如许的调整可以符合性质四而且不对其他性质产生破坏。
当插入的节点是父节点的右支的时候：

当要插入的节点是父节点的右支的时候，我们可以先对父节点进行左旋，变成如下：

如果我们把原先的父节点看做是新的要插入的节点，把原先要插入的节点看做是新的父节点，那就变成了当要插入的节点在父节点的左支的情况，对，是的，就是按照当要插入的节点在父节点的左支的情况进行旋转，旋转完之后变成如下：

4、如果要插入的节点的父节点是赤色且父节点是祖父节点的右支的时候；
这个时候的情况跟情况3所表述的情况是一个镜像，将情况3的左和右互换一下就可以了。
5、如果要插入的节点的父节点是赤色而且叔叔节点也为赤色，如下：

这个时候，只需将父亲节点和叔叔节点涂黑，将祖父节点涂红。
以上就是插入的全部过程。
下面我们再讲讲删除的操纵：
首先你要相识普通二叉树的删除操纵：
1.如果删除的是叶节点，可以直接删除；
2.如果被删除的元素有一个子节点，可以将子节点直接移到被删除元素的位置；
3.如果有两个子节点，这时候就可以把被删除元素的右支的最小节点（被删除元素右支的最左边的节点）和被删除元素互换，我们把被删除元素右支的最左边的节点称之为后继节点（后继元素），然后在根据情况1或者情况2进行操纵。如图：

将被删除元素与其右支的最小元素互换，变成如下图所示：

然后再将被删除元素删除：

我们下面所称的被删除元素，皆是指已经互换之后的被删除元素。
到场颜色之后，被删除元素和后继元素互换只是值得互换，并不互换颜色，这个要注意。
下面开始讲一下红黑树删除的规则：
1.当被删除元素为红时，对五条性质没有什么影响，直接删除。
2.当被删除元素为黑且为根节点时，直接删除。
3.当被删除元素为黑，且有一个右子节点为红时，将右子节点涂黑放到被删除元素的位置，如图：
由

变成

4.当被删除元素为黑，且兄弟节点为黑，兄弟节点两个孩子也为黑，父节点为红，此时，互换兄弟节点与父节点的颜色；NIL元素是指每个叶节点都有两个空的，颜色为黑的NIL元素，需要他的时候就可以把它看成两个黑元素，不需要的时候可以忽视他。
如图：
由

变成：

5.当被删除元素为黑、而且为父节点的左支，且兄弟颜色为黑，兄弟的右支为赤色，这个时候需要互换兄弟与父亲的颜色，并把父亲涂黑、兄弟的右支涂黑，并以父节点为中心左转。如图：
由

变成：

6.当被删除元素为黑、而且为父节点的左支，且兄弟颜色为黑，兄弟的左支为赤色，这个时候需要先把兄弟与兄弟的左子节点颜色互换，进行右转，然后就变成了规则5一样了，在按照规则5进行旋转。如图：
由

先兄弟与兄弟的左子节点颜色互换，进行右转，变成：

然后在按照规则5进行旋转，变成：

7.当被删除元素为黑且为父元素的右支时，跟情况5.情况6 互为镜像。
8.被删除元素为黑且兄弟节点为黑，兄弟节点的孩子为黑，父亲为黑，这个时候需要将兄弟节点变为红，再把父亲看做那个被删除的元素（只是看做，实际上不删除），看看父亲符和哪一条删除规则，进行处理变化如图：
由：

变成：

8.当被删除的元素为黑，且为父元素的左支，兄弟节点为赤色的时候，需要互换兄弟节点与父亲结点的颜色，以父亲结点进行左旋，就变成了情况4，在按照情况四进行操纵即可，变化如下：
由：

互换兄弟节点与父亲结点的颜色，以父亲结点进行左旋 变成：

在按照情况四进行操纵，变成：

好了，删除的步骤也讲完，没有讲到的一点就是，在添加删除的时候，时候要记得更改根元素的颜色为黑。
这里并没有语言实现，只是讲了一下红黑树的插入删除步骤，你可以根据步骤自己把红黑树实现。
[点击这里]- 数据布局之红黑树插入与删除全程演示 梦醒潇湘 love 2013-01-23 11:15:08
http://blog.chinaunix.net/uid-26548237-id-3480169.html
已附本文后，照着规则一步一步的构建一个红黑树吧。
最后：
最后的最后，其实另有一种更为简单的红黑二叉树，这个简单的红黑二叉树实际上是一个 2.3 树，他只答应左节点为红节点，但是性能上肯定是不如这个红黑树。这个简单的红黑二叉树在《算法》第四版有介绍，把握完之后再看这个简单的红黑二叉树，就会觉着简单 easy。
最后的最后的最后，肯定要尝试着自己推导一下插入删除规则啊，否则经常忘，是睡一觉起来再看就有点懵逼的那种忘。
红黑树介绍

RWCC于 2022-05-28 10:30:00 发布
红黑树目录


红黑树的概念

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

红黑树的性质

思索：为什么满意上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

我们分析一下：
最短路径为全黑，最长路径就是红黑节点瓜代（由于赤色节点不能连续)，每条路径的玄色节点相同，则最长路径、刚好是最短路径的两倍。
红黑树节点的界说

  1. // 节点的颜色
  2. enum Color{RED, BLACK};
  3. // 红黑树节点的定义
  4. template<class ValueType>
  5. struct RBTreeNode
  6. {
  7.          RBTreeNode(const ValueType& data = ValueType()，Color color = RED)
  8.                  : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
  9.                  , _data(data), _color(color)
  10.          {}
  11.          
  12.          RBTreeNode<ValueType>* _pLeft; // 节点的左孩子
  13.          RBTreeNode<ValueType>* _pRight; // 节点的右孩子
  14.          RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
  15.          ValueType _data; // 节点的值域
  16.          Color _color; // 节点的颜色
  17. };
复制代码
思索：在节点的界说中，为什么要将节点的默认颜色给成赤色的？
插入赤色节点树的性质大概不会改变，而插入玄色节点每次都会违反性质4.
通过性质发现： 将节点设置为赤色在插入时对红黑树造成的影响是小的，而玄色是最大的
总结：将红黑树的节点默认颜色设置为赤色，是为尽大概减少在插入新节点对红黑树造成的影响。
红黑树布局

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，由于根节点必须为玄色，为了与根节点进行区分，将头结点给成玄色，而且让头结点的 pParent 域指向红黑树的根节点，pLeft域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点，如下：

红黑树的插入操纵

红黑树是在二叉搜刮树的根本上加上其平衡限定条件，因此红黑树的插入可分为两步：
  1. bool Insert(const T& value)
  2. {
  3.     // 1. 按照二叉搜索树的规则插入新节点
  4.     // 空树
  5.     Node*& root = GetRoot();
  6.     if (nullptr == root)
  7.     {
  8.         root = new Node(value, BLACK);
  9.         root->_parent = _head;
  10.     }
  11.     else
  12.     {
  13.         // 非空
  14.         // 按照二叉搜索树的特性找待插入节点在树中的位置
  15.         Node* cur = root;
  16.         Node* parent = _head;
  17.         while (cur)
  18.         {
  19.             parent = cur;
  20.             if (value < cur->_value)
  21.                 cur = cur->_left;
  22.             else if (value > cur->_value)
  23.                 cur = cur->_right;
  24.             else
  25.                 return false;
  26.         }
  28.         // 插入新节点
  29.         cur = new Node(value);
  30.         if (value < parent->_value)
  31.             parent->_left = cur;
  32.         else
  33.             parent->_right = cur;
  34.         cur->_parent = parent;
  36.         // 2. 检测新节点插入之后是否违反性质三：即是否存在红色节点连在一起的情况
  37.         //    因为新插入节点cur的颜色是红色的，如果cur双亲parent节点的颜色也是红色的
  38.         //    则违反了性质三
  39.         while (RED == parent->_color)
  40.         {
  41.             // 违反了性质三
  42.             Node* grandFather = parent->_parent;
  43.             // 此处grandFather一定不为空
  44.             // 因为：parent是红色的，则parent一定不是根节点，parent的双亲一定是存在的
  45.             if (parent == grandFather->_left)
  46.             {
  47.                 // 课件中给的三种情况
  48.                 Node* uncle = grandFather->_right;
  49.                 if (uncle && RED == uncle->_color)
  50.                 {
  51.                     // 情况一：叔叔节点存在且为红
  52.                     parent->_color = BLACK;
  53.                     uncle->_color = BLACK;
  54.                     grandFather->_color = RED;
  55.                     cur = grandFather;
  56.                     parent = cur->_parent;
  57.                 }
  58.                 else
  59.                 {
  60.                     // 叔叔节点为空 || 叔叔节点存在且为黑--->即情况二 或者 情况三
  61.                     // 情况三
  62.                     if (cur == parent->_right)
  63.                     {
  64.                         // 先对parent进行左单旋，然后将parent和cur交换---->变成情况二
  65.                         RotateLeft(parent);
  66.                         swap(parent, cur);
  67.                     }
  68.                     // 情况二：
  69.                     // 将祖父和双亲节点的颜色交换，然后再对祖父树进行右单旋
  70.                     grandFather->_color = RED;
  71.                     parent->_color = BLACK;
  72.                     RotateRight(grandFather);
  73.                 }
  74.             }
  75.             else
  76.             {
  77.                 // 课件总给的三种情况的反情况
  78.             }
  79.         }
  80.     }
  82.     // 需要更新_head的left和right指针域
  83.     _head->_left = MostLeft();
  84.     _head->_right = MostRight();
  85.     root->_color = BLACK;
  86.     return true;
  87. }
复制代码
情况二: cur 为红，p 为红，g 为黑，u 不存在/u 为黑

p 为 g 的左孩子，cur 为 p 的左孩子，则进行右单旋转；相反，
p 为 g 的右孩子，cur 为 p 的右孩子，则进行左单旋转
p、g 变色–p 变黑，g 变红
情况三: cur为红，p为红，g为黑，u不存在/u为黑

p 为 g 的左孩子，cur 为 p 的右孩子，则针对 p 做左单旋转；相反，
p 为 g 的右孩子，cur 为 p 的左孩子，则针对 p 做右单旋转
则转换成了情况 2

针对每种情况进行相应的处理即可。
红黑树的验证

红黑树的检测分为两步：
  1. bool IsValidRBTree()
  2. {
  3.          PNode pRoot = GetRoot();
  4.          // 空树也是红黑树
  5.          if (nullptr == pRoot)
  6.                  return true;
  7.                 
  8.          // 检测根节点是否满足情况
  9.          if (BLACK != pRoot->_color)
  10.          {
  11.                  cout << "违反红黑树性质二：根节点必须为黑色" << endl;
  12.                   return false;
  13.          }
  14.          // 获取任意一条路径中黑色节点的个数
  15.          size_t blackCount = 0;
  16.          PNode pCur = pRoot;
  17.          while (pCur)
  18.          {
  19.                  if (BLACK == pCur->_color)
  20.                          blackCount++;
  21.                         
  22.                  pCur = pCur->_pLeft;
  23.          }
  24.          // 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
  25.          size_t k = 0;
  26.          return _IsValidRBTree(pRoot, k, blackCount);
  27. }
  28. bool _IsValidRBTree(PNode pRoot, size_t k, const size_t blackCount)
  29. {
  30.          //走到null之后，判断k和black是否相等
  31.          if (nullptr == pRoot)
  32.          {
  33.                  if (k != blackCount)
  34.                  {
  35.                          cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
  36.                          return false;
  37.                  }
  38.          return true;
  39.          }
  40.          
  41.          // 统计黑色节点的个数
  42.          if (BLACK == pRoot->_color)
  43.                  k++;
  44.          // 检测当前节点与其双亲是否都为红色
  45.          PNode pParent = pRoot->_pParent;
  46.          if (pParent && RED == pParent->_color && RED == pRoot->_color)
  47.          {
  48.                  cout << "违反性质三：没有连在一起的红色节点" << endl;
  49.                  return false;
  50.          }
  51.          return _IsValidRBTree(pRoot->_pLeft, k, blackCount) &&
  52.                          _IsValidRBTree(pRoot->_pRight, k, blackCount);
  53. }
复制代码
红黑树与AVL树的比力

红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是 O (log2N)，红黑树不寻求绝对平衡，只需保证最长路径不超过最短路径的 2 倍，相对而言，低落了插入和旋转的次数，以是在经常进行增删的布局中性能比 AVL 树更优，而且红黑树实现比力简单，以是实际运用中红黑树更多。
【数据布局】史上最好理解的红黑树解说，让你彻底搞懂红黑树

小七mod已于 2023-11-04 14:49:41 修改
大家应该都学过平衡二叉树(AVLTree) ，相识到AVL树的性质，其实平衡二叉树最大的作用就是查找,AVL树的查找、插入和删除在均匀和最坏情况下都是O(logn)。AVL树的服从就是高在这个地方。如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理, 那么创建一颗平衡二叉树的资本其实不小. 这个时候就有人开始思索，而且提出了红黑树的理论，红黑树在业界应用很广泛，好比 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树布局实现的。那么红黑树到底比AVL树好在哪里？
一、 红黑树简介

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明，在当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为现在的红黑树。红黑树具有良好的服从，它可在 O(logN) 时间内完成查找、增加、删除等操纵。
二、为什么需要红黑树？

对于二叉搜刮树，如果插入的数据是随机的，那么它就是靠近平衡的二叉树，平衡的二叉树，它的操纵服从（查询，插入，删除）服从较高，时间复杂度是 O（logN）。但是大概会出现一种极度的情况，那就是插入的数据是有序的（递增或者递减），那么所有的节点都会在根节点的右侧或左侧，此时，二叉搜刮树就变为了一个链表，它的操纵服从就低落了，时间复杂度为 O (N)，以是可以认为二叉搜刮树的时间复杂度介于 O（logN）和 O (N) 之间，视情况而定。那么为了应对这种极度情况，红黑树就出现了，它是具备了某些特性的二叉搜刮树，能解决非平衡树标题，红黑树是一种靠近平衡的二叉树（说它是靠近平衡由于它并没有像 AVL 树的平衡因子的概念，它只是靠着满意红黑节点的 5 条性质来维持一种靠近平衡的布局，进而提升团体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。
三、红黑树的特性

在解说红黑树性质之前，先简单相识一下几个概念：

首先，红黑树是一个二叉搜刮树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上玄色节点相同时，最长路径刚好是最短路径的两倍）。它同时满意以下特性：

根据上面的性质，我们来判定一下下面这课树是不是红黑树

上面这棵树首先很容易就能知道是满意性质1-4条的，关键在于第5条性质，大概乍一看好像也是符合第5条的，但实际就会陷入一个误区，直接将图上的最后一层的节点看作叶子节点，如许看的话每一条从根节点到叶子结点的路径确实都颠末了3个黑节点。
但实际上，在红黑树中真正被界说为叶子结点的，是那些空节点，如下图。

如许一来，路径1有4个玄色节点（算上空节点），路径2只有3个玄色节点，如许性质5就不满意了，以是这棵树并不是一个红黑树节点。
注：下面的解说图中将省略红黑树的null节点，请自行脑补
四、红黑树的服从

4.1 红黑树服从

红黑树的查找，插入和删除操纵，时间复杂度都是O(logN)。
查找操纵时，它和普通的相对平衡的二叉搜刮树的服从相同，都是通过相同的方式来查找的，没有用到红黑树特有的特性。
但如果插入的时候是有序数据，那么红黑树的查询服从就比二叉搜刮树要高了，由于此时二叉搜刮树不是平衡树，它的时间复杂度O(N)。
插入和删除操纵时，由于红黑树的每次操纵均匀要旋转一次和变换颜色，以是它比普通的二叉搜刮树服从要低一点，不过时间复杂度仍然是O(logN)。总之，红黑树的优点就是对有序数据的查询操纵不会慢到O(logN)的时间复杂度。
4.2 红黑树和 AVL 树的比力

五、红黑树的等价变换


上面这颗红黑树，我们来将所有的赤色节点上移到和他们的父节点同一高度上，就会形成如下布局

这个布局很明显，就是一棵**四阶\ **B\ **树（一个节点最多放三个数据）\ ，如果画成如下的样子大家应该就能看的更清晰了。

由上面的等价变换我们就可以得到如下结论：
我们可以利用四阶B树与红黑树等价的性质，以红黑树转换成B树之后的节点情况来进行一个分类

六、红黑树的操纵

红黑树的基本操纵和其他树形布局一样，一般都包括查找、插入、删除等操纵。前面说到，红黑树是一种自平衡的二叉查找树，既然是二叉查找树的一种，那么查找过程和二叉查找树一样，比力简单，这里不再赘述。相对于查找操纵，红黑树的插入和删除操纵就要复杂的多。尤其是删除操纵，要处理的情况比力多，下面就来分情况解说。
6 .1 旋转操纵

在分析插入和删除操纵前，先说明一下旋转操纵，这个操纵在后续操纵中都会用得到。旋转操纵分为左旋和右旋，左旋\ 是将某个节点旋转为其右孩子的左孩子，而右旋\ 是节点旋转为其左孩子的右孩子。这话听起来有点绕，以是还是请看下图：

上图包含了左旋和右旋的示意图，这里以右旋为例进行说明，右旋节点 M 的步骤如下：

旋转操纵本身并不复杂，上面分析了右旋操纵，左旋操纵与此类似，只是右旋转的逆操纵。
6.2 插入操纵

红黑树的插入过程和二叉查找树插入过程基本类似，差别的地方在于，红黑树插入新节点后，需要进行调整，以满意红黑树的性质。
性质1规定红黑树节点的颜色要么是赤色要么是玄色，那么在插入新节点时，这个节点应该是赤色还是玄色呢？答案是赤色，原因也不难理解。如果插入的节点是玄色，那么这个节点所在路径比其他路径多出一个玄色节点，这个调整起来会比力贫困（参考红黑树的删除操纵，就知道为啥多一个或少一个玄色节点时，调整起来这么贫困了）。如果插入的节点是赤色，此时所有路径上的玄色节点数目不变，仅大概会出现两个连续的赤色节点的情况。这种情况下，通过变色和旋转进行调整即可，比之前的简单多了。以是插入的时候将节点设置为赤色，可以保证满意性质 1、2、3、5 ，只有性质4不肯定满意，需要进行干系调整。如果是添加根节点，则将节点设定为玄色。
6.2.1 插入操纵的所有情况

我们在分析红黑树各种插入情况的时候，将其等价转换为 B 树，如许我们能够更直观的进行分类，首先确定几条性质：


在上一章节红黑树的等价变换中，我们讲到了红黑树转换成B树总共有四种情况，也就是上图中叶子节点这四种情况，那么在我们进行插入操纵的时候，会将节点插入到所有的叶子节点中，总共就会有12种情况，此中四种情况满意红黑树的性质，8种情况不满意红黑树性质。
6.2.1.1 满意红黑树性质 4
有 4 种情况满意红黑树的性质 4 **：parent\ ** 为玄色节点\ 。这四种情况不需要做任何额外的处理。

6.2.1.2 不满意红黑树性质 4
有 8 种情况不满意红黑树的性质 4 **：parent\ 为赤色节点\ （ Double Red ），此中左面4种属于B树节点上溢\ 的情况（一个4阶B树节点中最多存放三个数，这四种情况原来已经有3个了，又插入了1个，变成了4个，超出了4阶B树节点的容量范围，这种情况称为上溢）。这八种情况需要进行额外的处理。

6.2.2 LL 和 RR 插入情况


如上图，插入52和60的位置分别是RR情况和LL情况。
**RR\ **情况\ ：父节点为祖父节点的右节点，插入节点为父节点的右节点
**LL\ **情况\ ：父节点为祖父节点的左节点，插入节点为父节点的左节点
这两种情况很明显，插入节点为赤色，父节点也为赤色，父节点的子节点为赤色显然违反了红黑树的性质四，我们需要对这种情况进行修复，使其重新满意红黑树性质。
判定条件：uncle 不是赤色节点。
这里的两种情况，他们的插入节点都是没有叔父节点的，以是叔父节点也不大概是赤色。
案例修复：
我们在红黑树等价转换那一章节也讲过了，红黑树等价转换成B树之后，B树节点的中间节点（父节点）都是玄色，两边的节点（子节点）都是赤色。但是上面两种情况插入后，插入位置的B树节点并不满意这个条件，以是我们对其进行修复，使其满意B树节点的条件之后，也就重新恢复了红黑树性质。
B树节点中的中间节点大小介于两个子节点之间。以上图RR情况为例，插入节点52的原父节点应该放在B树节点中间的位置，应当将其染成玄色。插入节点52的原祖父节点46，应当将其转换为插入节点原父节点的子节点，以是将其染成赤色。LL情况同理
完成染色之后，需要对原祖父节点进行单旋操纵，来进行父节点，子节点的重新分配。以上图为例：

修复之后的结果如下图：

修复步骤总结：
6.2.3 LR 和 RL 插入情况


如上图，插入48和74的位置分别是RL情况和LR情况。
RL 情况 ：父节点为祖父节点的右节点，插入节点为父节点的左节点
LR 情况 ：父节点为祖父节点的左节点，插入节点为父节点的右节点
这两种情况和上面的两种情况一样，插入节点为赤色，父节点也为赤色，父节点的子节点为赤色显然违反了红黑树的性质四，我们需要对这种情况进行修复，使其重新满意红黑树性质。
判定条件：uncle 不是赤色节点。
这两种情况的插入节点也是没有叔父节点的。
案例修复：
B树节点中的中间节点大小介于两个子节点之间。以上图RL情况为例，插入节点48大小介于原父节点和原祖父节点之间，它应该是B树节点中的中间节点，以是将插入节点48染成玄色，将原祖父节点46染成赤色来作为插入节点的子节点。LR情况同理
完成染色之后，需要进行双旋操纵，来进行父节点，子节点的重新分配。以上图为例：

修复之后的结果如下图：

修复步骤总结：
6.2.4 上溢的 LL 插入情况


如上图，插入10的位置是上溢的LL情况。
溢 LL 情况：父节点为祖父节点的左节点，插入节点为父节点的左节点。而且构成的新的B树节点已经超过了B树节点容量大小范围。
这种情况和之前非上溢的四种情况一样，插入节点为赤色，父节点也为赤色，父节点的子节点为赤色显然违反了红黑树的性质四，我们需要对这种情况进行修复，使其重新满意红黑树性质。
判定条件：uncle 是赤色节点。满意这个条件的就都是上溢的情况，上溢的修复只需要染色，不需要旋转。
案例修复：
像这种上溢的情况，就需要从溢出的 B 树节点中选出一个节点进行向上合并，选择 B 树节点中中间的树去进行向上合并，这里中间的两个节点就是原父节点 17 和原祖父节点 25，选这两个哪一个向上合并都是对的，但是我们最好选择以后方便操纵的，很显然，应该选择原祖父节点 25 来进行向上合并，由于向上合并就是和最上层的 38 和 55 来组合成新的 B 树节点，向上合并的节点肯定是一个子节点，需要与上层相连，而原祖父节点 25 本身就已经和上层连接了，相对更加方便后续的操纵。原祖父节点向上合并后，将其染成赤色。
原祖父节点 25 向上合并后，它原来左右两边的节点需要分裂成两个子树，也就是原父节点 17 和插入节点 10 形成一个子树，原叔父节点 33 形成一个子树。这两个分裂形成的树都是以后 25 的子树。左边的子树由原父节点作为中间节点，染成玄色，右边的子树由原叔父节点作为中间节点，染成玄色。
修复之后的结果如下图：

修复步骤总结：
grand 向上合并时，大概继承发生上溢。这种情况就继承递归调用修复方法就可以了。若上溢连续到根节点，只需将根节点染成玄色即可（这个意思就是说断向上上溢，不停上溢到了B树的根节点位置了，只需要将向上合并的节点变成玄色作为红黑树的根节点即可。由于从B树根节点选择出来上溢的节点，肯定就是作为整个红黑树的根节点了）。
6.2.5 上溢的 RR 插入情况


如上图，插入36的位置是上溢的RR情况。
上溢 RR 情况：父节点为祖父节点的右节点，插入节点为父节点的右节点。而且构成的新的B树节点已经超过了B树节点容量大小范围。
判定条件：uncle 是赤色节点
案例修复：
上溢 RR 情况的修复，和上溢 LL 情况基本同等，只是修复的位置差别，这里中间的两个节点就是原父节点 33 和原祖父节点 25，选择原祖父节点 25 来进行向上合并，原祖父节点向上合并后，将其染成赤色。
原祖父节点 25 向上合并后，它原来左右两边的节点需要分裂成两个子树，也就是原父节点 33 和插入节点 36 形成一个子树，原叔父节点 17 形成一个子树。这两个分裂形成的树都是以后 25 的子树。左边的子树由原叔父节点作为中间节点，染成玄色，右边的子树由原父节点作为中间节点，染成玄色。
修复之后的结果如下图：

修复步骤总结：
6.2.6 上溢的 LR 插入情况


如上图，插入20的位置是上溢的LR情况。
上溢 LR情况：父节点为祖父节点的左节点，插入节点为父节点的右节点。而且构成的新的B树节点已经超过了B树节点容量大小范围。
判定条件：uncle 是赤色节点
案例修复：
上溢 LR 情况的修复，和其他上溢情况基本同等，只是修复的位置差别，这里中间的两个节点就是原父节点 17 和原祖父节点 25，选择原祖父节点 25 来进行向上合并，原祖父节点向上合并后，将其染成赤色。
原祖父节点 25 向上合并后，它原来左右两边的节点需要分裂成两个子树，也就是原父节点 17 和插入节点 20 形成一个子树，原叔父节点 33 形成一个子树。这两个分裂形成的树都是以后 25 的子树。左边的子树由原父节点作为中间节点，染成玄色，右边的子树由原叔父节点作为中间节点，染成玄色。
修复之后的结果如下图：

修复步骤总结：
6.2.7 上溢的 RL 插入情况


如上图，插入30的位置是上溢的RL情况。
上溢 RL 情况：父节点为祖父节点的右节点，插入节点为父节点的左节点。而且构成的新的B树节点已经超过了B树节点容量大小范围。
判定条件：uncle 是赤色节点
案例修复：
上溢 RL 情况的修复，和其他上溢情况基本同等，只是修复的位置差别，这里中间的两个节点就是原父节点 33 和原祖父节点 25，选择原祖父节点 25 来进行向上合并，原祖父节点向上合并后，将其染成赤色。
原祖父节点 25 向上合并后，它原来左右两边的节点需要分裂成两个子树，也就是原父节点 33 和插入节点 30 形成一个子树，原叔父节点 17 形成一个子树。这两个分裂形成的树都是以后 25 的子树。左边的子树由原叔父节点作为中间节点，染成玄色，右边的子树由原父节点作为中间节点，染成玄色。
修复之后的结果如下图：

修复步骤总结：
6.2.8 插入情况总结

插入一共有12种情况：
6.3 删除 操纵

相较于插入操纵，红黑树的删除操纵则要更为复杂一些。B树中，最后真正被删除的元素都在叶子节点中。以是在红黑树中，被删除的节点肯定也在最后一层。

6.3.1 删除 操纵的所有情况

上面我们说删除节点肯定都在最后一层，最后一层有赤色节点和玄色节点，我们就以删除节点的颜色来区分删除操纵的所有情况。
6.3.1.1 删除赤色节点
如果删除的节点是赤色直接删除，不消作任何调整。由于删除最后一层的赤色节点，并没有影响红黑树的任何性质。

6.3.1.2 删除玄色节点
有 3 种情况：

6.3.2 删除拥有 1 个 赤色 子节点的 玄色 节点


删除拥有1个赤色子节点的玄色节点的情况，是需要我们做干系的处理的。这里删除的就是节点46和76，他们只有一个赤色子节点。
对于一个二叉树来说，删除一个度为1的节点（度指的是一个节点的子节点个数），将其删除后需要用它唯一的子节点来进行更换。而红黑树的这种情况的判定条件，就是判定要替代删除节点的子节点是不是赤色
判定条件：用以替代的子节点是赤色节点
案例修复：

删除玄色节点46和76
第一步：

将 46 与父节点的连接断开
第二步：

46 唯一的赤色子节点50作为代替 46 的节点，将其与 46 的父节点进行连接
第三步：

断开 46 与 50 的连接，将 46 删除
删除节点 76 的过程与删除节点 46 相同
第一步：

第二步：

第三步：

但是现在我们发现，80 是赤色节点，它的子节点72还是赤色节点，如许明显不符合红黑树的性质，还需要进一步修复。

将替代的子节点染成玄色即可保持红黑树性质，修复完成
修复步骤总结：
6.3.3 删除玄色叶子节点 —— 删除节点为根节点

一棵红黑树只有一个玄色根节点（也就是唯一的一个叶子节点，整个红黑树只有这一个玄色节点），可直接删除该节点，无需做其他操纵。
6.3.4 删除玄色叶子节点 —— 删除节点的兄弟节点为玄色

讲这种删除情况前先举一个例子

上面这个我们要删除节点88，该节点为玄色叶子节点，它的兄弟节点是玄色76。从B树的角度来看，如果删除88，由于四阶B树的节点中最少存有1个元素，如果不足，则会造成**下溢\ 。也就是需要从88的兄弟节点中借一个子节点出来。这就是这一节我们讨论的删除情况的焦点修复思想。
6.3.4.1 兄弟节点至少有 1 个 赤色 子节点
下面三个图分别对应着兄弟节点至少有一个赤色子节点的三种情况。删除节点为88，为玄色叶子节点，它的兄弟节点是76，为玄色。兄弟节点76都至少有一个赤色子节点，三种情况分别为76拥有一个赤色右子节点，76拥有一个赤色左子节点，76拥有两个赤色子节点。由于兄弟节点有赤色子节点，以是可以借出一个节点来进行修复。

这三种情况，玄色叶子节点被删除后，会导致B树节点下溢（好比删除88），就可以从兄弟节点中借出一个赤色子节点来进行修复。
判定条件：兄弟节点至少有 1 个赤色子节点
案例修复：
1、兄弟节点有一个右子节点：

先将88节点删除

删掉之后，从B树的角度来看就出现了下溢，这个时候就需要父节点下来，在兄弟节点的子结点中找一个，将他升上去代替。具体的实现就是要对节点进行旋转。

我们可以看出，80、76、78组成的树是一个LR的情况，先对76进行左旋转（可以将76看作父节点），如许78就上去了，再对80进行右旋转（可以将80看成祖父节点），80就下去了。

旋转完了之后，如上图。将旋转完之后的中心节点（就是78、76、80组成的树的最中心的节点，这里就是78）进行重新染色，继承删除节点的父节点80的颜色。最后再将78、76、80组成的树的左右两个节点染成玄色即可完成修复。
2、兄弟节点有一个左子节点：

先将88节点删除

删掉之后，从B树的角度来看就出现了下溢，这个时候就需要父节点下来，在兄弟节点的子结点中找一个，将他升上去代替。具体的实现就是要对节点进行旋转。

我们可以看出，80、76、72组成的树是一个LL的情况，直接对80进行右旋（将80看成是祖父节点）。

旋转完了之后，如上图。将旋转完之后的中心节点（就是76、72、80组成的树的最中心的节点，这里就是76）进行重新染色，继承删除节点的父节点80的颜色。最后再将76、72、80组成的树的左右两个节点染成玄色即可完成修复。
3、兄弟节点有两个左右子节点：

先将88节点删除

删除之后，其实可以有两种旋转可以进行修复，既可以利用LL方式进行旋转，也可以利用LR方式进行旋转。但是由于LL方式只需要旋转一次，我们就选用LL方式。

直接对80进行右旋

旋转完了之后，如上图。将旋转完之后的中心节点（就是78、72、76、80组成的树的最中心的节点，这里就是76）进行重新染色，继承删除节点的父节点80的颜色。最后再将78、72、76、80组成的树的左右两个节点染成玄色即可完成修复。
修复步骤总结：
6.3.4.2 兄弟节点没有赤色子节点
当删除节点的兄弟节点没有赤色节点可以借出的情况下，就需要父节点来向下合并进行修复，父节点向下和兄弟节点合并成新的B树节点来解决下溢。
判定条件：兄弟节点没有1个赤色子节点
案例修复：
1、父节点为赤色：

删除节点88，出现下溢

由于兄弟节点76没有可以借出的赤色节点，以是需要父节点80来向下与76合并进行修复

将兄弟节点76染成赤色，父节点80染成玄色即可完成修复
2、父节点为玄色：

删除节点88，删除之后节点88就会出现下溢

删除之后父节点80应该向下合并进行修复，但是由于父节点80为玄色，如果向下合并之后，其实就相当于80这个节点也出现了下溢。

这个时候只需要把父节点当作被删除的节点进行处理即可
修复步骤总结：
6.3.5 删除玄色叶子节点 —— 删除节点的兄弟节点为赤色


如果删除节点的兄弟节点为赤色，如许删除节点出现下溢后没办法通过兄弟节点来进行修复。这就需要先把红黑树转换为兄弟节点为玄色的情况，就可以套用上面讲的修复方法来进行修复了。
判定条件：兄弟节点是赤色
案例修复：

删除88节点之前，需要先转换成兄弟节点为玄色的情况，当前88的兄弟节点是赤色55。可以将其看作LL情况，对父节点88进行右旋转，如许55就被移动上去了，成了80的父节点。76也被移动上去了，成了80的子节点。

这种情况，删除节点88的兄弟节点就变成了玄色，而且没有赤色子节点，可以继承套用之前讲的方法来进行修复了。

删除掉88，将80染成玄色，76染成赤色，完成修复。
修复步骤总结：
七、红黑树的平衡

AVL是靠平衡因子来保持平衡的，好比平衡因子为1，那么左右子树的高度差就不能超过1，是一种强平衡。
对于红黑树而言，为何那5条性质，就能保证红黑树是平衡的？


B树比力矮，它本身就是平衡的，高度越小越平衡。
红黑树就是能保证这个树高度不会特别高，红黑树的最大高度是 2 ∗ log2(n + 1) ，依然是 O(logn) 级别，由于高度不会很大进而维持一种相对平衡的状态。相比AVL树，红黑树的平衡标准比力宽松**：没有一条路径会大于其他路径的\ **2\ **倍\ 。这是是一种弱平衡、黑高度平衡（黑高度只算玄色节点个数，红黑树的任何一条路径的玄色节点数一样，则黑高度都是一样）。
八、红黑树的均匀时间复杂度


九、 AVL 树 vs 红黑树

9.1 AVL 树


9.2 红黑树


9.3 如何选择


9.4 案例对比

10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 63, 41, 37, 24, 96组成一棵树
9.4.1 二叉搜刮树


非常不平衡
9.4.2 AVL 树


最平衡
9.4.3 红黑树


相对比力平衡
深入剖析红黑树（RB-Tree）：原理、操纵及应用

无敌岩雀已于 2024-08-31 20:05:41 修改
文章目录

红黑树作为一种自平衡的二叉搜刮树，在盘算机科学领域中占据着重要的地位。它的设计旨在在维持树的平衡性的同时，保证各种操纵的时间复杂度始终稳固在较低水平。红黑树的灵活性和高效性使得它成为浩繁编程语言和体系实现中不可或缺的数据布局之一。本文将领导读者深入探究红黑树的布局与原理。（c++实现）
一、红黑树的特点与性质


红黑树是一种特别的自平衡二叉查找树，它通过颜色和一系列性质来确保树的平衡，从而实现高效的查找、插入和删除操纵。在红黑树中，每个节点都被赋予赤色或玄色的颜色，而且这些颜色与树的五个基天性质一起工作，共同维持树的平衡。
红黑树是具有着色性质的二叉搜刮树：
这些性质共同确保了红黑树的平衡性。特别是性质5，它树确保没有一条路径会比其他路径长出两倍。这种平衡性保证了红黑树在查找、插入和删除操纵中的时间复杂度都是 O(log n)，此中n是树中节点的数目。着色法则的一个推论是，红黑树的高度最多是 2log(n+1) 。因此，查找保证是一种对数级别的操纵。

   有 n 个节点的红黑树的高度最多是 2log(n+1)，这是为什么呢？
  首先我们来我们思量一个标题，根节点为黑高为 h 的红黑树，内部节点个数至少有多少个？（黑高：从某节点出发（不含该节点）到达任意一叶节点的路径上黑节点的总数。）
内部节点上最少的情况就是总共 h 层黑节点的满树形态。若根节点黑高为 h，内部节点数最少有 2h-1 个。因此，若红黑树总高度为 h ，则根节点的黑高肯定是大于等于 h/2 的，因此内部节点数 n >= 2h/2-1，由此推出 h <= 2log(n+1) 。

红黑树同AVL树类似，也是一种自平衡的二叉搜刮树，它通过颜色和一系列性质来维护树的平衡性。与AVL树差别的是，红黑树并不寻求完全的平衡，而是答应局部的不平衡，这使得红黑树在插入或删除节点时的旋转操纵次数较少，低落了操纵的复杂性。同时，红黑树的查找、插入和删除操纵的时间复杂度也能保持在O(log n)。由于红黑树的这种特性，它在需要频仍进行插入和删除操纵的应用场景中体现得更好。
总的来说，红黑树在平衡性、操纵复杂性和性能之间找到了一个较好的平衡点，使得它在很多实际应用中成为了一个良好的选择。而AVL树固然具有严格的平衡性，但由于其操纵的复杂性以及在实际应用中的服从标题，使得它的利用范围相对较小。普通二叉搜刮树固然简单，但在数据动态变化的情况下，其性能大概会受到影响。因此，在选择利用哪种树形布局时，需要根据具体的应用场景和需求进行权衡。 深入
二、红黑树的实现


在此我们界说一个模板布局体RBTreeNode，它是红黑树中的一个节点。红黑树是一种自平衡的二叉搜刮树，此中每个节点都带有颜色属性（赤色或玄色）。Colour的罗列类型，它有两个值：RED和BLACK。这个罗列类型用于表示红黑树中节点的颜色：
  1. enum Colour { RED, BLACK };// 节点的颜色
  2. template<class K, class V>
  3. struct RBTreeNode{
  4.         RBTreeNode<K, V>* _left;                // 节点的左孩子
  5.         RBTreeNode<K, V>* _right;                // 节点的右孩子
  6.         RBTreeNode<K, V>* _parent;                // 节点的父节点
  7.         pair<K, V> _kv;                                        // 节点的键值对
  8.         Colour _col;                                        // 节点的颜色
  9.         RBTreeNode(const pair<K, V>& kv)
  10.                 :_left(nullptr)
  11.                 , _right(nullptr)
  12.                 , _parent(nullptr)
  13.                 , _kv(kv)
  14.                 , _col(RED)
  15.         {}
  16. };
复制代码
_left、_right和_parent都初始化为nullptr，表示新节点最初没有子节点或父节点。 _kv初始化为传入的键值对kv。 _col初始化为RED，表示新创建的节点默认是赤色的。
   为什么要默认是赤色呢？
  红黑树的困难在于将一个新的值插入到树中，通常把新的值作为树叶放到树中。如果插入时把该节点作为玄色，那么肯定违反性质5，由于会建立一条更长的黑节点的路径。因此，该节点必须涂成赤色。因此我们在构造函数里将其颜色初始化为赤色。
  1. template<class K,class V>
  2. class RBTree {
  3.         typedef RBTreeNode<K, V> Node;
  4. public:
  5.     //...
  6. private:
  7.         Node* _root = nullptr;
  8. };
复制代码
1、实现红黑树的插入操纵

在找到插入位置时，如果父节点是黑的，插入完成，由于插入赤色节点不会违反性质5。如果它的父节点已经是赤色的，那么我们得到连续赤色节点，这就违反性质4。在这种情况下，我们必须调整该树以确保性质4满意（且不引起性质5被破坏）。因此我们在插入时需要的基本操纵是节点颜色的改变以及树的旋转：
  1. bool Insert(const pair<K, V>& kv) ;
复制代码
  1. if (_root == nullptr) {
  2.     _root = new Node(kv);
  3.     _root->_col = BLACK;
  4.     return true;
  5. }
  6. Node* parent = nullptr;
  7. Node* cur = _root;
  8. while (cur) {
  9.     if (cur->_kv.first < kv.first) {
  10.         parent = cur;
  11.         cur = cur->_right;
  12.     }
  13.     else if (cur->_kv.first > kv.first) {
  14.         parent = cur;
  15.         cur = cur->_left;
  16.     }
  17.     else
  18.         return false;
  19. }
  21. cur = new Node(kv);
  22. if (parent->_kv.first < kv.first)
  23.     parent->_right = cur;
  24. else
  25.     parent->_left = cur;
  26. cur->_parent = parent;
复制代码

类似地，当父节点是祖父节点的右孩子时，执行相反的操纵：
我们分别给出新节点与父亲在差别方向的抽象图和相同方向的抽象图，注意对称情况：

   如果新节点是父节点的右孩子，而且父节点是其祖父节点的左孩子，则先对父亲节点进行左旋，再最祖父节点进行右旋。如果新节点是父节点的左孩子，而且父节点是其祖父节点的右孩子，则先对父亲节点进行右旋，再最祖父节点进行左旋。
  

   如果新节点是父节点的左孩子，而且父节点是其祖父节点的左孩子，则对祖父节点进行右旋；如果新节点是父节点的右孩子，而且父节点是其祖父节点的右孩子，则对祖父节点进行左旋。
  此次旋转完后，我们就结束循环，此时可以确保树仍然满意红黑树的界说。
通过执行上述步骤，我们可以确保在插入新节点后，红黑树仍然保持其平衡性质，而且能够有用地支持查找、删除等后续操纵。红黑树的插入操纵在均匀情况下的时间复杂度为O(log n)，此中n为树中节点的数目。
插入的完整代码如下：
  1. bool Insert(const pair<K, V>& kv) {    if (_root == nullptr) {        _root = new Node(kv);        _root->_col = BLACK;
  2.         return true;    }    Node* parent = nullptr;    Node* cur = _root;    while (cur) {        if (cur->_kv.first < kv.first) {            parent = cur;            cur = cur->_right;        }        else if (cur->_kv.first > kv.first) {            parent = cur;            cur = cur->_left;        }        else            return false;    }    cur = new Node(kv);    if (parent->_kv.first < kv.first)        parent->_right = cur;    else        parent->_left = cur;    cur->_parent = parent;    while (parent && parent->_col == RED) {        Node* grandparent = parent->_parent;        if (parent == grandparent->_left) {            Node* uncle = grandparent->_right;            //情况一  ：叔叔存在且为红            if (uncle && uncle->_col == RED)
  3. {                //先变色 后向上处理                parent->_col = uncle->_col = BLACK;                grandparent->_col = RED;                cur = grandparent;                parent = cur->_parent;            }            else {                //情况二：叔叔不存在 或者 存在但为玄色                //旋转+变色                if (cur == parent->_left) {                    //       g                    //    p    u                    // c                    RotateR(grandparent);                    parent->_col = BLACK;                    grandparent->_col = RED;                }                else {                    //       g                    //    p    u                    //                c                    RotateL(parent);                    RotateR(grandparent);                    cur->_col = BLACK;                    grandparent->_col = RED;                }                break;            }        }        else {            Node* uncle = grandparent->_left;            // 情况一：叔叔存在且为红            if (uncle && uncle->_col == RED)
  4. {                // 变色                parent->_col = uncle->_col = BLACK;                grandparent->_col = RED;                // 继承往上处理                cur = grandparent;                parent = cur->_parent;            }            else             {                // 情况二：叔叔不存在或者存在且为黑                // 旋转+变色                //      g                //   u     p                //            c                if (cur == parent->_right) {                    RotateL(grandparent);                    parent->_col = BLACK;                    grandparent->_col = RED;                }                else {                    //                g                    //   u     p                    //      c                    RotateR(parent);                    RotateL(grandparent);                    cur->_col = BLACK;                    grandparent->_col = RED;                }                break;            }        }    }    _root->_col = BLACK;
  5.     return true;}
复制代码
2、红黑树的验证方法

红黑树也是一种特别的二叉搜刮树，因此我们可以先获取二叉树的中序遍历序列，来判定该二叉树是否满意二叉搜刮树的性质：
  1. void _InOrder(Node* root){
  2.     if (root == nullptr)
  3.         return;
  4.     _InOrder(root->_left);
  5.     cout << root->_kv.first << endl;
  6.     _InOrder(root->_right);
  7. }
  8. void InOrder() { _InOrder(_root); }
复制代码
我们也要检测其是否满意红黑树的性质，我们需要两个函数：
a. Check 函数

Check 函数用于递归地检查红黑树的性质是否得到满意。它担当三个参数：当前节点 cur、从根节点到当前节点路径上的玄色节点数 blackNum 和从根节点到最左侧路径上的玄色节点数 refBlackNum。
  1. bool Check(Node* cur, int blackNum, int refBlackNum) {
  2.     if (cur == nullptr) {
  3.         if (refBlackNum != blackNum) {
  4.             cout << "黑色节点的数量不相等" << endl;
  5.             return false;
  6.         }
  7.         cout << "黑色节点的数量:" << blackNum << endl;
  8.         return true;
  9.     }
  10.     if (cur->_col == RED && cur->_parent->_col == RED) {
  11.         cout << cur->_kv.first << "存在连续的红色节点" << endl;
  12.         return false;
  13.     }
  14.     if (cur->_col == BLACK)
  15.         ++blackNum;
  16.     return Check(cur->_left, blackNum, refBlackNum)
  17.         && Check(cur->_right, blackNum, refBlackNum);
  18. }
复制代码
b. IsBalance 函数

IsBalance 函数用于检查整棵红黑树是否平衡。
  1. bool IsBalance(){
  2.     if (_root && _root->_col == RED)
  3.         return false;
  4.     int refBlackNum = 0;
  5.     Node* cur = _root;
  6.     while (cur){
  7.         if (cur->_col == BLACK)
  8.             refBlackNum++;
  9.         cur = cur->_left;
  10.     }
  11.     return Check(_root, 0, refBlackNum);
  12. }
复制代码
如果 Check 函数返回 true，则说明红黑树平衡，IsBalance 函数也返回 true；否则，返回 false。
本文代码置于：RBtree · 比奇堡的Zyb/每日学习 - 码云 - 开源中国 (gitee.com)
数据布局之红黑树插入与删除全程演示
梦醒潇湘 love 2013-01-23 11:15:08
分类： C/C++
弁言

现在国内图书市场上，抑或网上解说红黑树的资料层次不齐，杂乱不清，没有一个完整而同一的论述。而本人的红黑树系列四篇文章，固然从头至尾，讲的有根有据，层次清晰，然而距离读者真正做到红黑树了然于胸，则还缺点什么。
而我们知道，即便在经典的算法导论一书上，也没有把所有的插入、删除情况逐一道尽，直接导致了不少读者的迷惑，而红黑树系列第 4 篇文章：一步一图一代码，肯定要让你真正彻底明白红黑树，固然早已把所有的插入、删除情况都逐一道尽了，但也缺了点东西。
缺点什么东西呢？对了，缺的就是一个完完整整的，包含所有插入、删除情况全部过程的全程演示图，即缺一个例子，缺一个完整的图来从头至尾论述这一切。
ok，本文，即以 40 幅图来全程演示此红黑树的所有插入和删除情况。相信，肯定会对您理解红黑树有所帮助。
话不絮烦，下面，本文便以此篇文章：一步一图一代码，肯定要让你真正彻底明白红黑树为纲，从插入一个结点到最后插入全部结点，再到后来一个一个把结点全部删除的情况逐一论述。
为了有个完整同一，红黑树插入和删除情况在此合作成一篇文章。同时，由于本人的红黑树系列的四篇文章已经把红黑树的插入、删除情况都逐一细致的论述过了，因此，有关红黑树的原理，本文不再赘述，只偏重于用图来逐一全程演示结点的插入和删除情况。
有任何标题，接待指正。
一、红黑树的插入情况全程演示

通过红黑树系列的文章，我们已经知道，红黑树的所有插入情况分为以下五种：
情况 1：新结点 N 位于树的根结点，没有父结点
情况 2：新结点的父结点 P 是玄色
情况 3：父结点 P、叔叔结点 U，都为赤色
【对应于第二篇文章中的情况 1：z 的叔叔是赤色的】
情况 4：父结点 P 是赤色的，叔叔结点 U 是玄色或 NULL
【对应第二篇文章中的情况 2：z 的叔叔是玄色的，且 z 是右孩子】
情况 5：父结点 P 是赤色，而叔叔结点 U 是玄色或 NULL
要插入的结点 N 是其父结点的左孩子，而父结点 P 又是其祖父 G 的左孩子
【对应第二篇文章中情况 3：z 的叔叔是玄色的，且 z 是左孩子】
首先，各个结点插入与以上的各种插入情况，逐一对应起来，如下图所示。

以下是 20 张图，是依次插入这些结点：12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17 的全程演示图，已经把所有的 5 种插入情况，都涉及到了。
第一图：插入结点 12

第二图：插入结点 1

第三图：插入结点 9

第四图：插入结点 2

第五图：插入结点 0

第六图：插入结点 11

第七图：插入结点 7

第八图：插入结点 19

第九图：插入结点 4

第十图：插入结点 15

第十一图：插入结点 18

第十二图：插入结点 5

第十三图：插入结点 14

第十四图：插入结点 13

第十五图：插入结点 10

第十六图：插入结点 16

第十七图：插入结点 6

第十八图：插入结点 3

第十九图：插入结点 8

第二十图：插入结点 17

二、红黑树的删除情况全程演示
红黑图的所有删除情况，如下所示。
情况 1：N 是新的根
情况 2：兄弟结点 S 是赤色的
【对应于第二篇文章中情况 1：x 的兄弟结点 w 是赤色的】
情况 3：兄弟结点 S 是玄色的，却 S 的两个儿子都是玄色的。但 N 的父结点 P 是玄色
【对应于第二篇文章中情况 2：x 的兄弟结点 w 是玄色的，且兄弟结点 w 的两个儿子都是玄色的】
（这里，N 的父结点 P 为玄色）
情况 4：兄弟结点 S 是玄色的，S 的儿子也都是玄色的，但是 N 的父亲 P 是赤色
【对应于第二篇文章中情况 2：x 的兄弟结点 w 是玄色的，且 w 的两个孩子结点都是玄色的】
（这里，N 的父结点 P 为赤色）
情况 5：兄弟结点 S 为玄色，S 的左孩子为赤色，S 的右孩子是玄色，而 N 是它父结点的左儿子
// 此种情况，最后转化为下面的情况 6
【对应于第二篇文章中情况 3：x 的兄弟 w 是玄色的，w 的左孩子是赤色的，w 的右孩子是玄色】
情况 6：兄弟结点 S 是玄色的，S 的右孩子是赤色的，而 N 是它父结点的左儿子
【对应于第二篇文章中情况 4：x 的兄弟结点 w 是玄色的，且 w 的右孩子是赤色的】
各个结点的删除与以上六种情况逐一对应起来，如下图所示。

首先，插入上述结点后，形成的红黑树为：

然后，以下的 20 张图，是逐一删除 12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17 所得到的删除情况的全程演示图。
第一图：删除结点 12

第二图：删除结点 1

第三图：删除结点 9

第四图：删除结点 2

第五图：删除结点 0

第六图：删除结点 11

第七图：删除结点 7

第八图：删除结点 19

第九图：删除结点 4

第十图：删除结点 15

第十一图：删除结点 18

第十二图：删除结点 5

第十三图：删除结点 14

第十四图：删除结点 13

第十五图：删除结点 10

第十六图：删除结点 16

第十七图：删除结点 6

第十八图：删除结点 3

第十九图：删除结点 8

第二十图：删除结点 17

via:



免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4