2-3-4树和普通红黑树

某些教程不区分普通红黑树和左倾红黑树的区别，直接将左倾红黑树拿来教学，并且称其为红黑树，因为左倾红黑树与普通的红黑树相比，实现起来较为简单，容易教学。在这里，我们区分开左倾红黑树和普通红黑树。

红黑树是一种近似平衡的二叉查找树，从 2-3 树或 2-3-4 树衍生而来。通过对二叉树节点进行染色，染色为红或黑节点，来模仿 2-3 树或 2-3-4 树的3节点和4节点，从而让树的高度减小。2-3-4 树对照实现的红黑树是普通的红黑树，而 2-3 树对照实现的红黑树是一种变种，称为左倾红黑树，其更容易实现。

使用平衡树数据结构，可以提高查找元素的速度，我们在本章介绍 2-3-4 树，再用二叉树形式来实现 2-3-4 树，也就是普通的红黑树。

目前已经有更加完备的代码实现，请参考：https://github.com/hunterhug/gomap 。

一、2-3-4 树

1.1. 2-3-4 树介绍

2-3-4 树是一棵严格自平衡的多路查找树，又称 4阶的B树 (注：B 为 Balance 平衡的意思)

它不是一棵二叉树，是一棵四叉树。具有以下特征：

  1. 内部节点要么有1个数据元素和2个孩子，要么有2个数据元素和3个孩子，要么有3个数据元素和4个孩子，叶子节点没有孩子，但有1，2或3个数据元素。
  2. 所有叶子节点到根节点的长度一致。这个特征保证了完全平衡，非常完美的平衡。
  3. 每个节点的数据元素保持从小到大排序，两个数据元素之间的子树的所有值大小介于两个数据元素之间。

因为 2-3-4 树的第二个特征，它是一棵完美平衡的树，非常完美，除了叶子节点，其他的节点都没有空儿子，所以树的高度非常的小。

如图：

2-3-4树和普通红黑树 - 图1

如果一个内部节点拥有一个数据元素、两个子节点，则此节点为2节点。如果一个内部节点拥有两个数据元素、三个子节点，则此节点为3节点。如果一个内部节点拥有三个数据元素、四个子节点，则此节点为4节点。

可以说，所有平衡树的核心都在于插入和删除逻辑，我们主要分析这两个操作。

1.2. 2-3-4 树插入元素

在插入元素时，需要先找到插入的位置，使用二分查找从上自下查找树节点。

找到插入位置时，将元素插入该位置，然后进行调整，使得满足 2-3-4 树的特征。主要有三种情况：

  1. 插入元素到一个2节点或3节点，直接插入即可，这样节点变成3节点或4节点。
  2. 插入元素到一个4节点，该4节点的父亲不是一个4节点，将4节点的中间元素提到父节点，原4节点变成两个2节点，再将元素插入到其中一个2节点。
  3. 插入元素到一个4节点，该4节点的父亲是一个4节点，也是将4节点的中间元素提到父节点，原4节点变成两个2节点，再将元素插入到其中一个2节点。当中间元素提到父节点时，父节点也是4节点，可以递归向上操作。

核心在于往4节点插入元素时，需要将4节点中间元素提升，4节点变为两个2节点后，再插入元素，如图：

2-3-4树和普通红黑树 - 图2

下面演示插入元素到一个4节点：

2-3-4树和普通红黑树 - 图3

与其他二叉查找树由上而下生长不同，2-3-4 树是从下至上的生长。

2-3-4 树因为节点元素数量的增加，情况变得更复杂，下面是插入元素到一个4节点，而4节点的父节点是3节点的三种情况：

2-3-4树和普通红黑树 - 图4

其他情况可以参考 2-3树和左倾红黑树 一章，非常相似，在此不再赘述。

1.3. 2-3-4 树删除元素

删除操作就复杂得多了，请耐心阅读理解，和 2-3 树删除元素类似。

2-3-4 树的特征注定它是一棵非常完美平衡的四叉树，其所有子树也都是完美平衡，所以 2-3-4 树的某节点的儿子，要么都是空儿子，要么都不是空儿子。比如 2-3-4 树的某个节点 A 有两个儿子 B 和 C，儿子 B 和 C 要么都没有孩子，要么孩子都是满的，不然 2-3-4 树所有叶子节点到根节点的长度一致这个特征就被破坏了。

基于上面的现实，我们来分析删除的不同情况，删除中间节点和叶子节点。

情况1：删除中间节点

删除的是非叶子节点，该节点一定是有两棵，三棵或者四棵子树的，那么从子树中找到其最小后继节点，该节点是叶子节点，用该节点替换被删除的非叶子节点，然后再删除这个叶子节点，进入情况2。

如何找到最小后继节点，当有两棵子树时，那么从右子树一直往左下方找，如果有三棵子树，被删除节点在左边，那么从中子树一直往左下方找，否则从右子树一直往左下方找。如果有四棵子树，那么往被删除节点右边的子树，一直往左下方找。

情况2：删除叶子节点

删除的是叶子节点，这时叶子节点如果是4节点，直接变为3节点，如果是3节点，那么直接变为2节点即可，不影响平衡。但是，如果叶子节点是2节点，那么删除后，其父节点将会缺失一个儿子，破坏了满孩子的 2-3-4 树特征，需要进行调整后才能删除。

针对情况2，删除一个2节点的叶子节点，会导致父节点缺失一个儿子，破坏了 2-3-4 树的特征，我们可以进行调整变换，主要有两种调整：

  1. 重新分布：尝试从兄弟节点那里借值，然后重新调整节点。
  2. 合并：如果兄弟借不到值，合并节点（与父亲的元素）。

如果被删除的叶子节点有兄弟是3节点或4节点，可以向最近的兄弟借值，然后重新分布，这样叶子节点就不再是2节点了，删除元素后也不会破坏平衡。如图：

2-3-4树和普通红黑树 - 图5

与兄弟借值，兄弟必须有多余的元素可以借，借的过程中需要和父节点元素重新分布位置，确保符合元素大小排序的正确。

如果被删除的叶子节点，兄弟都是2节点，而父亲是3节点或4节点，那么将父亲的一个元素拉下来进行合并（当父节点是3节点时，父亲元素与被删除节点合并成3节点，当父节点是4节点时，被删除节点和其最近的兄弟，以及父亲的一个元素合并成一个4节点），父亲变为2节点或3节点，这时叶子节点就不再是2节点了，删除元素后也不会破坏平衡。如图：

2-3-4树和普通红黑树 - 图6

有一种最特殊的情况，也就是被删除的叶子节点，兄弟都是2节点，父亲也是2节点，这种情况没法向兄弟借，也没法和父亲合并，与父亲合并后父亲就变空了。幸运的是，这种特殊情况只会发生在根节点是其父节点的情况，如图：

2-3-4树和普通红黑树 - 图7

因为 2-3-4 树的性质，除了根节点，其他节点不可能出现其本身和儿子都是2节点。

2-3-4 树的实现将会放在 B树 章节，我们将会实现其二叉树形式的普通红黑树结构。

二、 普通红黑树

2.1. 普通红黑树介绍

普通红黑树可以由 2-3-4 树的二叉树形式来实现。

其定义为：

  1. 根节点的链接是黑色的。
  2. 每个红色节点都必须有两个黑色子节点。
  3. 任意一个节点到达叶子节点的所有路径，经过的黑链接数量相同，也就是该树是完美黑色平衡的。比如，某一个节点，它可以到达5个叶子节点，那么这5条路径上的黑链接数量一样。

普通红黑树与其变种：左倾红黑树的区别是，它允许右倾的红色节点，不再限制左倾，但仍然不能有连续的两个左倾红色链接。

每一棵 2-3-4 树可以对应多棵普通红黑树，如图：

2-3-4树和普通红黑树 - 图8

区别：2-3 树与左倾红黑树则是一一对应，而 2-3-4 树可以对应多棵普通红黑树，是因为它允许了红链接右倾。

2.2. 结构定义和节点旋转

首先，我们要定义树的结构 RBTree ，以及表示普通红黑树的节点 RBTNode：

  1. // 定义颜色
  2. const (
  3.     RED   = true
  4.     BLACK = false
  5. )
  7. // 普通红黑树
  8. type RBTree struct {
  9.     Root *RBTNode // 树根节点
  10. }
  12. // 新建一棵空树
  13. func NewRBTree() *RBTree {
  14.     return &RBTree{}
  15. }
  17. // 普通红黑树节点
  18. type RBTNode struct {
  19.     Value  int64    // 值
  20.     Times  int64    // 值出现的次数
  21.     Left   *RBTNode // 左子树
  22.     Right  *RBTNode // 右子树
  23.     Parent *RBTNode // 父节点
  24.     Color  bool     // 父亲指向该节点的链接颜色
  25. }
  27. // 节点的颜色
  28. func IsRed(node *RBTNode) bool {
  29.     if node == nil {
  30.         return false
  31.     }
  32.     return node.Color == RED
  33. }
  35. // 返回节点的父亲节点
  36. func ParentOf(node *RBTNode) *RBTNode {
  37.     if node == nil {
  38.         return nil
  39.     }
  41.     return node.Parent
  42. }
  44. // 返回节点的左子节点
  45. func LeftOf(node *RBTNode) *RBTNode {
  46.     if node == nil {
  47.         return nil
  48.     }
  50.     return node.Left
  51. }
  53. // 返回节点的右子节点
  54. func RightOf(node *RBTNode) *RBTNode {
  55.     if node == nil {
  56.         return nil
  57.     }
  59.     return node.Right
  60. }
  62. // 设置节点颜色
  63. func SetColor(node *RBTNode, color bool) {
  64.     if node != nil {
  65.         node.Color = color
  66.     }
  67. }

在节点 RBTNode 中，我们存储的元素字段为 Value，由于可能有重复的元素插入，所以多了一个 Times 字段，表示该元素出现几次。

当然，红黑树中的红黑颜色使用 Color 定义，表示父亲指向该节点的链接颜色。我们还多创建了几个辅助函数。

在元素添加和实现的过程中，需要做调整操作，有两种旋转操作，对某节点的右链接进行左旋转，如图：

2-3-4树和普通红黑树 - 图9

代码如下：

  1. // 对某节点左旋转
  2. func (tree *RBTree) RotateLeft(h *RBTNode) {
  3.     if h != nil {
  5.         // 看图理解
  6.         x := h.Right
  7.         h.Right = x.Left
  9.         if x.Left != nil {
  10.             x.Left.Parent = h
  11.         }
  13.         x.Parent = h.Parent
  14.         if h.Parent == nil {
  15.             tree.Root = x
  16.         } else if h.Parent.Left == h {
  17.             h.Parent.Left = x
  18.         } else {
  19.             h.Parent.Right = x
  20.         }
  21.         x.Left = h
  22.         h.Parent = x
  23.     }
  24. }

或者左链接进行右旋转，如图：

2-3-4树和普通红黑树 - 图10

代码如下：

  1. // 对某节点右旋转
  2. func (tree *RBTree) RotateRight(h *RBTNode) {
  3.     if h != nil {
  5.         // 看图理解
  6.         x := h.Left
  7.         h.Left = x.Right
  9.         if x.Right != nil {
  10.             x.Right.Parent = h
  11.         }
  13.         x.Parent = h.Parent
  14.         if h.Parent == nil {
  15.             tree.Root = x
  16.         } else if h.Parent.Right == h {
  17.             h.Parent.Right = x
  18.         } else {
  19.             h.Parent.Left = x
  20.         }
  21.         x.Right = h
  22.         h.Parent = x
  23.     }
  24. }

旋转作为局部调整，并不影响全局。

可以继续查看下面的内容。

2.3. 添加元素实现

每次添加元素节点时，都将该节点 Color 字段，也就是父亲指向它的链接设置为 RED 红色。

总结情况如下：

2-3-4树和普通红黑树 - 图11

情况1：空树，那么插入节点直接变为根节点。

情况2：父节点是黑节点，直接插入即可，不破坏红黑树特征。

情况3：父节点是红节点，叔叔节点也是红节点，这时对应 2-3-4 树的4节点，插入后变成了5节点，破坏了平衡，直接将祖父节点变色即可，然后向上递归处理，相当于 2-3-4 树的4节点提升，如图：

2-3-4树和普通红黑树 - 图12

情况4：父节点是红节点，没有叔叔或者叔叔是黑节点，插入后出现了两个连续的红链接，需要进行旋转调整，如图：

2-3-4树和普通红黑树 - 图13

如果是顺方向连续红链接，旋转一次即可，否则需要左右旋转或者右左旋转，旋转两次。

这次我们使用非递归的形式，效率会更高（可及时跳出循环），代码实现如下：

  1. // 普通红黑树添加元素
  2. func (tree *RBTree) Add(value int64) {
  3.     // 根节点为空
  4.     if tree.Root == nil {
  5.         // 根节点都是黑色
  6.         tree.Root = &RBTNode{
  7.             Value: value,
  8.             Color: BLACK,
  9.         }
  10.         return
  11.     }
  13.     // 辅助变量 t，表示新元素要插入到该子树，t是该子树的根节点
  14.     t := tree.Root
  16.     // 插入元素后，插入元素的父亲节点
  17.     var parent *RBTNode
  19.     // 辅助变量，为了知道元素最后要插到左边还是右边
  20.     var cmp int64 = 0
  22.     for {
  23.         parent = t
  25.         cmp = value - t.Value
  26.         if cmp < 0 {
  27.             // 比当前节点小，往左子树插入
  28.             t = t.Left
  29.         } else if cmp > 0 {
  30.             // 比当前节点节点大，往右子树插入
  31.             t = t.Right
  32.         } else {
  33.             // 已经存在值了，更新出现的次数
  34.             t.Times = t.Times + 1
  35.             return
  36.         }
  38.         // 终于找到要插入的位置了
  39.         if t == nil {
  40.             break // 这时叶子节点是 parent，要插入到 parent 的下面，跳到外层去
  41.         }
  42.     }
  44.     // 新节点，它要插入到 parent下面
  45.     newNode := &RBTNode{
  46.         Value:  value,
  47.         Parent: parent,
  48.     }
  49.     if cmp < 0 {
  50.         // 知道要从左边插进去
  51.         parent.Left = newNode
  52.     } else {
  53.         // 知道要从右边插进去
  54.         parent.Right = newNode
  55.     }
  57.     // 插入新节点后，可能破坏了红黑树特征，需要修复，核心函数
  58.     tree.fixAfterInsertion(newNode)
  59. }
  61. // 调整新插入的节点，自底而上
  62. // 可以看图理解
  63. func (tree *RBTree) fixAfterInsertion(node *RBTNode) {
  64.     // 插入的新节点一定要是红色
  65.     node.Color = RED
  67.     // 节点不能是空，不能是根节点，父亲的颜色必须为红色（如果是黑色，那么直接插入不破坏平衡，不需要调整了）
  68.     for node != nil && node != tree.Root && node.Parent.Color == RED {
  69.         // 父亲在祖父的左边
  70.         if ParentOf(node) == LeftOf(ParentOf(ParentOf(node))) {
  71.             // 叔叔节点
  72.             uncle := RightOf(ParentOf(ParentOf(node)))
  74.             // 图例3左边部分，叔叔是红节点，祖父变色，也就是父亲和叔叔变黑，祖父变红
  75.             if IsRed(uncle) {
  76.                 SetColor(ParentOf(node), BLACK)
  77.                 SetColor(uncle, BLACK)
  78.                 SetColor(ParentOf(ParentOf(node)), RED)
  79.                 // 还要向上递归
  80.                 node = ParentOf(ParentOf(node))
  81.             } else {
  82.                 // 图例4左边部分，叔叔是黑节点，并且插入的节点在父亲的右边，需要对父亲左旋
  83.                 if node == RightOf(ParentOf(node)) {
  84.                     node = ParentOf(node)
  85.                     tree.RotateLeft(node)
  86.                 }
  88.                 // 变色，并对祖父进行右旋
  89.                 SetColor(ParentOf(node), BLACK)
  90.                 SetColor(ParentOf(ParentOf(node)), RED)
  91.                 tree.RotateRight(ParentOf(ParentOf(node)))
  92.             }
  93.         } else {
  94.             // 父亲在祖父的右边，与父亲在祖父的左边相似
  95.             // 叔叔节点
  96.             uncle := LeftOf(ParentOf(ParentOf(node)))
  98.             // 图例3右边部分，叔叔是红节点，祖父变色，也就是父亲和叔叔变黑，祖父变红
  99.             if IsRed(uncle) {
  100.                 SetColor(ParentOf(node), BLACK)
  101.                 SetColor(uncle, BLACK)
  102.                 SetColor(ParentOf(ParentOf(node)), RED)
  103.                 // 还要向上递归
  104.                 node = ParentOf(ParentOf(node))
  105.             } else {
  106.                 // 图例4右边部分，叔叔是黑节点，并且插入的节点在父亲的左边，需要对父亲右旋
  107.                 if node == LeftOf(ParentOf(node)) {
  108.                     node = ParentOf(node)
  109.                     tree.RotateRight(node)
  110.                 }
  112.                 // 变色，并对祖父进行左旋
  113.                 SetColor(ParentOf(node), BLACK)
  114.                 SetColor(ParentOf(ParentOf(node)), RED)
  115.                 tree.RotateLeft(ParentOf(ParentOf(node)))
  116.             }
  117.         }
  118.     }
  120.     // 根节点永远为黑
  121.     tree.Root.Color = BLACK
  122. }

首先，如果是空树，那么新建根节点：

  1.     // 根节点为空
  2.     if tree.Root == nil {
  3.         // 根节点都是黑色
  4.         tree.Root = &RBTNode{
  5.             Value: value,
  6.             Color: BLACK,
  7.         }
  8.         return
  9.     }

否则，需要找到叶子节点，方便新节点插进去：

  1.     // 辅助变量 t，表示新元素要插入到该子树，t是该子树的根节点
  2.     t := tree.Root
  4.     // 插入元素后，插入元素的父亲节点
  5.     var parent *RBTNode
  7.     // 辅助变量，为了知道元素最后要插到左边还是右边
  8.     var cmp int64 = 0
  10.     for {
  11.         parent = t
  13.         cmp = value - t.Value
  14.         if cmp < 0 {
  15.             // 比当前节点小，往左子树插入
  16.             t = t.Left
  17.         } else if cmp > 0 {
  18.             // 比当前节点节点大，往右子树插入
  19.             t = t.Right
  20.         } else {
  21.             // 已经存在值了，更新出现的次数
  22.             t.Times = t.Times + 1
  23.             return
  24.         }
  26.         // 终于找到要插入的位置了
  27.         if t == nil {
  28.             break // 这时叶子节点是 parent，要插入到 parent 的下面，跳到外层去
  29.         }
  30.     }

找到了要插入的位置，该位置是 parent，将新元素插入：

  1.     // 新节点，它要插入到 parent下面
  2.     newNode := &RBTNode{
  3.         Value:  value,
  4.         Parent: parent,
  5.     }
  6.     if cmp < 0 {
  7.         // 知道要从左边插进去
  8.         parent.Left = newNode
  9.     } else {
  10.         // 知道要从右边插进去
  11.         parent.Right = newNode
  12.     }

插入节点后，就需要进行调整操作了，这是核心：tree.fixAfterInsertion(newNode)。

参照图例对比一下，就可以理解调整操作的逻辑了：

  1. // 调整新插入的节点，自底而上
  2. // 可以看图理解
  3. func (tree *RBTree) fixAfterInsertion(node *RBTNode) {
  4.     // 插入的新节点一定要是红色
  5.     node.Color = RED
  7.     // 节点不能是空，不能是根节点，父亲的颜色必须为红色（如果是黑色，那么直接插入不破坏平衡，不需要调整了）
  8.     for node != nil && node != tree.Root && node.Parent.Color == RED {
  9.         // 父亲在祖父的左边
  10.         if ParentOf(node) == LeftOf(ParentOf(ParentOf(node))) {
  11.             // 叔叔节点
  12.             uncle := RightOf(ParentOf(ParentOf(node)))
  14.             // 图例3左边部分，叔叔是红节点，祖父变色，也就是父亲和叔叔变黑，祖父变红
  15.             if IsRed(uncle) {
  16.                 SetColor(ParentOf(node), BLACK)
  17.                 SetColor(uncle, BLACK)
  18.                 SetColor(ParentOf(ParentOf(node)), RED)
  19.                 // 还要向上递归
  20.                 node = ParentOf(ParentOf(node))
  21.             } else {
  22.                 // 图例4左边部分，叔叔是黑节点，并且插入的节点在父亲的右边，需要对父亲左旋
  23.                 if node == RightOf(ParentOf(node)) {
  24.                     node = ParentOf(node)
  25.                     tree.RotateLeft(node)
  26.                 }
  28.                 // 变色，并对祖父进行右旋
  29.                 SetColor(ParentOf(node), BLACK)
  30.                 SetColor(ParentOf(ParentOf(node)), RED)
  31.                 tree.RotateRight(ParentOf(ParentOf(node)))
  32.             }
  33.         } else {
  34.             // 父亲在祖父的右边，与父亲在祖父的左边相似
  35.             // 叔叔节点
  36.             uncle := LeftOf(ParentOf(ParentOf(node)))
  38.             // 图例3右边部分，叔叔是红节点，祖父变色，也就是父亲和叔叔变黑，祖父变红
  39.             if IsRed(uncle) {
  40.                 SetColor(ParentOf(node), BLACK)
  41.                 SetColor(uncle, BLACK)
  42.                 SetColor(ParentOf(ParentOf(node)), RED)
  43.                 // 还要向上递归
  44.                 node = ParentOf(ParentOf(node))
  45.             } else {
  46.                 // 图例4右边部分，叔叔是黑节点，并且插入的节点在父亲的左边，需要对父亲右旋
  47.                 if node == LeftOf(ParentOf(node)) {
  48.                     node = ParentOf(node)
  49.                     tree.RotateRight(node)
  50.                 }
  52.                 // 变色，并对祖父进行左旋
  53.                 SetColor(ParentOf(node), BLACK)
  54.                 SetColor(ParentOf(ParentOf(node)), RED)
  55.                 tree.RotateLeft(ParentOf(ParentOf(node)))
  56.             }
  57.         }
  58.     }
  60.     // 根节点永远为黑
  61.     tree.Root.Color = BLACK
  62. }

可以知道，每次新插入的节点一定是红色：node.Color = RED。

接着判断：node != nil && node != tree.Root && node.Parent.Color == RED，发现节点非空，且非根节点，并且其父亲是红色，那么插入新元素到父亲下面就连续两个红链接了，需要调整，否则不需要调整。

调整时要区分父亲是在祖父的左边：ParentOf(node) == LeftOf(ParentOf(ParentOf(node))) 还是在右边，接着判断叔叔节点uncle := RightOf(ParentOf(ParentOf(node))) 的颜色。

如果叔叔是红色，对应图例3，如图：

2-3-4树和普通红黑树 - 图14

叔叔是红节点，那么祖父变色，也就是父亲和叔叔变黑，祖父变红，然后继续往上递归：

  1.     // 图例3右边部分，叔叔是红节点，祖父变色，也就是父亲和叔叔变黑，祖父变红
  2.     if IsRed(uncle) {
  3.         SetColor(ParentOf(node), BLACK)
  4.         SetColor(uncle, BLACK)
  5.         SetColor(ParentOf(ParentOf(node)), RED)
  6.         // 还要向上递归
  7.         node = ParentOf(ParentOf(node))
  8.     }

如果叔叔不是红色，对应图例4，如图：

2-3-4树和普通红黑树 - 图15

在图例4左边部分，父亲在祖父左边，叔叔是黑节点，如果插入的节点在父亲的右边，需要对父亲左旋，接着对祖父变色即可：

  1.     // 图例4左边部分，叔叔是黑节点，并且插入的节点在父亲的右边，需要对父亲左旋
  2.     if node == RightOf(ParentOf(node)) {
  3.         node = ParentOf(node)
  4.         tree.RotateLeft(node)
  5.     }
  7.     // 变色，并对祖父进行右旋
  8.     SetColor(ParentOf(node), BLACK)
  9.     SetColor(ParentOf(ParentOf(node)), RED)
  10.     tree.RotateRight(ParentOf(ParentOf(node)))

在图例4右边部分，父亲在祖父右边，叔叔是黑节点，如果插入的节点在父亲的左边，需要对父亲右旋，接着对祖父变色即可：

  1.     // 图例4右边部分，叔叔是黑节点，并且插入的节点在父亲的左边，需要对父亲右旋
  2.     if node == LeftOf(ParentOf(node)) {
  3.         node = ParentOf(node)
  4.         tree.RotateRight(node)
  5.     }
  7.     // 变色，并对祖父进行左旋
  8.     SetColor(ParentOf(node), BLACK)
  9.     SetColor(ParentOf(ParentOf(node)), RED)
  10.     tree.RotateLeft(ParentOf(ParentOf(node)))

最后，调整完后，根节点永远为黑：

  1.     // 根节点永远为黑
  2.     tree.Root.Color = BLACK

2.4. 添加元素算法分析

当父亲是红节点，叔叔为空或是黑节点时，不需要向上递归，插入最多旋转两次就恢复了平衡。而如果父亲和叔叔都是红节点，那么祖父变色之后可能需要一直递归向上处理，直到根节点，但是只要中途出现了旋转，仍然是旋转两次就不需要继续向上递归，树就平衡了。

最坏情况的红黑树高度为 2log(n)（证明略），查找到插入的位置最坏情况查找 2log(n) 次，然后进行调整，最坏情况递归到根节点，递归 2log(n) 次（构造最坏情况的树很难），去掉常数，添加元素的平均时间复杂度仍然为 log(n)，而旋转最多不超过两次。

2.5. 删除元素实现

删除操作就复杂得多了。对照一下 2-3-4 树。

  1. 情况1：如果删除的是非叶子节点，找到其最小后驱节点，也就是在其右子树中一直向左找，找到的该叶子节点替换被删除的节点，然后删除该叶子节点，变成情况2。
  2. 情况2：如果删除的是叶子节点，如果它是红节点，也就是父亲指向它的链接为红色，那么直接删除即可。否则，我们需要进行调整，使它变为红节点，再删除。

针对情况2，如果删除的叶子节点是红节点，那它对应 2-3-4 树的3节点或4节点，直接删除即可，删除后变为了2节点或3节点。否则，它是一个2节点，删除后破坏了平衡，要么向兄弟借值，要么和父亲的一个元素合并。

删除的叶子节点是黑色的，才需要向兄弟借值，或与父亲合并，有以下几种情况：

删除的叶子节点在父亲的左边：

2-3-4树和普通红黑树 - 图16

图例中 21， 22 相当于向兄弟借值，而 1 和 23 相当于向父亲的一个值合并后调整。

我们仔细分析一下：

图例 1，当删除的叶子节点在父亲左边，而兄弟是红色节点，我们可以知道 父亲 和 兄弟的儿子们 绝对都是黑节点，将兄弟变黑，父亲变红，然后对父亲右链接左旋。如图：

2-3-4树和普通红黑树 - 图17

这时调整后变为了图例 23，这种情况实际上是在 2-3-4 树中和父亲的值合并，只不过将父亲的值转了一个方向，可能变为图例 21，22，23。

图例 23，当删除的叶子节点在父亲左边，兄弟节点是黑色，兄弟的儿子们也都是黑色，相当于 2-3-4 树和兄弟借不到值了，需要将兄弟变为红色，然后将父亲作为一个整体来删除，向上递归处理（相当于拉了父亲的一个值和兄弟合并）。如图：

2-3-4树和普通红黑树 - 图18

图例 21 和 21 就简单了，相当 2-3-4 树与兄弟借值。

图例 21，当删除的叶子节点在父亲左边，且兄弟是黑色，而兄弟的右儿子是红色，那么兄弟设置成父亲的颜色，兄弟的右儿子和父亲变黑，接着对父亲进行左旋，旋转后可以直接删除元素。如图：

2-3-4树和普通红黑树 - 图19

图例 22，当删除的叶子节点在父亲左边，且兄弟是黑色，而兄弟的右儿子是黑色，左儿子是红色，将兄弟设置为红色，兄弟的左儿子设置为黑色，对兄弟进行右旋，变为图例 21。如图：

2-3-4树和普通红黑树 - 图20

当然，删除的叶子节点可以在父亲的右边（与上述的图反方向）：

2-3-4树和普通红黑树 - 图21

类似于删除的叶子节点在父亲的左边，在此不再分析。

上面的图例，我们其实可以将其画出 2-3-4 树的形式，会更容易理解，在此就不画出了。

这次我们使用非递归的形式，效率会更高（可及时跳出循环），代码实现如下：

  1. // 普通红黑树删除元素
  2. func (tree *RBTree) Delete(value int64) {
  3.     // 查找元素是否存在，不存在则退出
  4.     p := tree.Find(value)
  5.     if p == nil {
  6.         return
  7.     }
  9.     // 删除该节点
  10.     tree.delete(p)
  11. }
  13. // 删除节点核心函数
  14. // 找最小后驱节点来补位，删除内部节点转为删除叶子节点
  15. func (tree *RBTree) delete(node *RBTNode) {
  16.     // 如果左右子树都存在，那么从右子树的左边一直找一直找，就找能到最小后驱节点
  17.     if node.Left != nil && node.Right != nil {
  18.         s := node.Right
  19.         for s.Left != nil {
  20.             s = s.Left
  21.         }
  23.         // 删除的叶子节点找到了，删除内部节点转为删除叶子节点
  24.         node.Value = s.Value
  25.         node.Times = s.Times
  26.         node = s // 可能存在右儿子
  27.     }
  29.     if node.Left == nil && node.Right == nil {
  30.         // 没有子树，要删除的节点就是叶子节点。
  31.     } else {
  32.         // 只有一棵子树，因为红黑树的特征，该子树就只有一个节点
  33.         // 找到该唯一节点
  34.         replacement := node.Left
  35.         if node.Left == nil {
  36.             replacement = node.Right
  37.         }
  39.         // 替换开始，子树的唯一节点替代被删除的内部节点
  40.         replacement.Parent = node.Parent
  41.         if node.Parent == nil {
  42.             // 要删除的节点的父亲为空，表示要删除的节点为根节点，唯一子节点成为树根
  43.             tree.Root = replacement
  44.         } else if node == node.Parent.Left {
  45.             // 子树的唯一节点替代被删除的内部节点
  46.             node.Parent.Left = replacement
  47.         } else {
  48.             // 子树的唯一节点替代被删除的内部节点
  49.             node.Parent.Right = replacement
  50.         }
  52.         // delete this node
  53.         node.Parent = nil
  54.         node.Right = nil
  55.         node.Left = nil
  57.         //  case 1: not enter this logic
  58.         //      R(del)
  59.         //    B   B
  60.         //
  61.         //  case 2: node's color must be black, and it's son must be red
  62.         //    B(del)     B(del)
  63.         //  R  O       O   R
  64.         //
  65.         // 单子树时删除的节点绝对是黑色的，而其唯一子节点必然是红色的
  66.         // 现在唯一子节点替换了被删除节点，该节点要变为黑色
  67.         // now son replace it's father, just change color to black
  68.         replacement.Color = BLACK
  69.         return
  70.     }
  72.     // 要删除的叶子节点没有父亲，那么它是根节点，直接置空，返回
  73.     if node.Parent == nil {
  74.         tree.Root = nil
  75.         return
  76.     }
  78.     // 要删除的叶子节点，是一个黑节点，删除后会破坏平衡，需要进行调整，调整成可以删除的状态
  79.     if !IsRed(node) {
  80.         // 核心函数
  81.         tree.fixAfterDeletion(node)
  82.     }
  84.     // 现在可以删除叶子节点了
  85.     if node == node.Parent.Left {
  86.         node.Parent.Left = nil
  87.     } else if node == node.Parent.Right {
  88.         node.Parent.Right = nil
  89.     }
  91.     node.Parent = nil
  93. }
  95. // 调整删除的叶子节点，自底向上
  96. // 可以看图理解
  97. func (tree *RBTree) fixAfterDeletion(node *RBTNode) {
  98.     // 如果不是递归到根节点，且节点是黑节点，那么继续递归
  99.     for tree.Root != node && !IsRed(node) {
  100.         // 要删除的节点在父亲左边，对应图例1，2
  101.         if node == LeftOf(ParentOf(node)) {
  102.             // 找出兄弟
  103.             brother := RightOf(ParentOf(node))
  105.             // 兄弟是红色的，对应图例1，那么兄弟变黑，父亲变红，然后对父亲左旋，进入图例21,22,23
  106.             if IsRed(brother) {
  107.                 SetColor(brother, BLACK)
  108.                 SetColor(ParentOf(node), RED)
  109.                 tree.RotateLeft(ParentOf(node))
  110.                 brother = RightOf(ParentOf(node)) // 图例1调整后进入图例21,22,23，兄弟此时变了
  111.             }
  113.             // 兄弟是黑色的，对应图例21，22，23
  114.             // 兄弟的左右儿子都是黑色，进入图例23，将兄弟设为红色，父亲所在的子树作为整体，当作删除的节点，继续向上递归
  115.             if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
  116.                 SetColor(brother, RED)
  117.                 node = ParentOf(node)
  118.             } else {
  119.                 // 兄弟的右儿子是黑色，进入图例22，将兄弟设为红色，兄弟的左儿子设为黑色，对兄弟右旋，进入图例21
  120.                 if !IsRed(RightOf(brother)) {
  121.                     SetColor(LeftOf(brother), BLACK)
  122.                     SetColor(brother, RED)
  123.                     tree.RotateRight(brother)
  124.                     brother = RightOf(ParentOf(node)) // 图例22调整后进入图例21，兄弟此时变了
  125.                 }
  127.                 // 兄弟的右儿子是红色，进入图例21，将兄弟设置为父亲的颜色，兄弟的右儿子以及父亲变黑，对父亲左旋
  128.                 SetColor(brother, ParentOf(node).Color)
  129.                 SetColor(ParentOf(node), BLACK)
  130.                 SetColor(RightOf(brother), BLACK)
  131.                 tree.RotateLeft(ParentOf(node))
  133.                 node = tree.Root
  134.             }
  135.         } else {
  136.             // 要删除的节点在父亲右边，对应图例3，4
  137.             // 找出兄弟
  138.             brother := RightOf(ParentOf(node))
  140.             // 兄弟是红色的，对应图例3，那么兄弟变黑，父亲变红，然后对父亲右旋，进入图例41,42,43
  141.             if IsRed(brother) {
  142.                 SetColor(brother, BLACK)
  143.                 SetColor(ParentOf(node), RED)
  144.                 tree.RotateRight(ParentOf(node))
  145.                 brother = LeftOf(ParentOf(node)) // 图例3调整后进入图例41,42,43，兄弟此时变了
  146.             }
  148.             // 兄弟是黑色的，对应图例41，42，43
  149.             // 兄弟的左右儿子都是黑色，进入图例43，将兄弟设为红色，父亲所在的子树作为整体，当作删除的节点，继续向上递归
  150.             if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
  151.                 SetColor(brother, RED)
  152.                 node = ParentOf(node)
  153.             } else {
  154.                 // 兄弟的左儿子是黑色，进入图例42，将兄弟设为红色，兄弟的右儿子设为黑色，对兄弟左旋，进入图例41
  155.                 if !IsRed(LeftOf(brother)) {
  156.                     SetColor(RightOf(brother), BLACK)
  157.                     SetColor(brother, RED)
  158.                     tree.RotateLeft(brother)
  159.                     brother = LeftOf(ParentOf(node)) // 图例42调整后进入图例41，兄弟此时变了
  160.                 }
  162.                 // 兄弟的左儿子是红色，进入图例41，将兄弟设置为父亲的颜色，兄弟的左儿子以及父亲变黑，对父亲右旋
  163.                 SetColor(brother, ParentOf(node).Color)
  164.                 SetColor(ParentOf(node), BLACK)
  165.                 SetColor(LeftOf(brother), BLACK)
  166.                 tree.RotateRight(ParentOf(node))
  168.                 node = tree.Root
  169.             }
  170.         }
  171.     }
  173.     // this node always black
  174.     SetColor(node, BLACK)
  175. }

首先需要查找删除的值是否存在，不存在则不必要调用删除操作了：

  1. // 普通红黑树删除元素
  2. func (tree *RBTree) Delete(value int64) {
  3.     // 查找元素是否存在，不存在则退出
  4.     p := tree.Find(value)
  5.     if p == nil {
  6.         return
  7.     }
  9.     // 删除该节点
  10.     tree.delete(p)
  11. }

存在删除的节点，那么进入删除操作：tree.delete(p)。

删除操作无非就是找最小后驱节点来补位，删除内部节点转为删除叶子节点，然后针对叶子节点的链接是不是黑色，是的话那么需要调整：

  1. // 删除节点核心函数
  2. // 找最小后驱节点来补位，删除内部节点转为删除叶子节点
  3. func (tree *RBTree) delete(node *RBTNode) {
  4.     // 如果左右子树都存在，那么从右子树的左边一直找一直找，就找能到最小后驱节点
  5.     if node.Left != nil && node.Right != nil {
  6.         s := node.Right
  7.         for s.Left != nil {
  8.             s = s.Left
  9.         }
  11.         // 删除的叶子节点找到了，删除内部节点转为删除叶子节点
  12.         node.Value = s.Value
  13.         node.Times = s.Times
  14.         node = s // 可能存在右儿子
  15.     }
  17.     if node.Left == nil && node.Right == nil {
  18.         // 没有子树，要删除的节点就是叶子节点。
  19.     } else {
  20.         // 只有一棵子树，因为红黑树的特征，该子树就只有一个节点
  21.         // 找到该唯一节点
  22.         replacement := node.Left
  23.         if node.Left == nil {
  24.             replacement = node.Right
  25.         }
  27.         // 替换开始，子树的唯一节点替代被删除的内部节点
  28.         replacement.Parent = node.Parent
  29.         if node.Parent == nil {
  30.             // 要删除的节点的父亲为空，表示要删除的节点为根节点，唯一子节点成为树根
  31.             tree.Root = replacement
  32.         } else if node == node.Parent.Left {
  33.             // 子树的唯一节点替代被删除的内部节点
  34.             node.Parent.Left = replacement
  35.         } else {
  36.             // 子树的唯一节点替代被删除的内部节点
  37.             node.Parent.Right = replacement
  38.         }
  40.         // delete this node
  41.         node.Parent = nil
  42.         node.Right = nil
  43.         node.Left = nil
  45.         //  case 1: not enter this logic
  46.         //      R(del)
  47.         //    B   B
  48.         //
  49.         //  case 2: node's color must be black, and it's son must be red
  50.         //    B(del)     B(del)
  51.         //  R  O       O   R
  52.         //
  53.         // 单子树时删除的节点绝对是黑色的，而其唯一子节点必然是红色的
  54.         // 现在唯一子节点替换了被删除节点，该节点要变为黑色
  55.         // now son replace it's father, just change color to black
  56.         replacement.Color = BLACK
  57.         return
  58.     }
  60.     // 要删除的叶子节点没有父亲，那么它是根节点，直接置空，返回
  61.     if node.Parent == nil {
  62.         tree.Root = nil
  63.         return
  64.     }
  66.     // 要删除的叶子节点，是一个黑节点，删除后会破坏平衡，需要进行调整，调整成可以删除的状态
  67.     if !IsRed(node) {
  68.         // 核心函数
  69.         tree.fixAfterDeletion(node)
  70.     }
  72.     // 现在可以删除叶子节点了
  73.     if node == node.Parent.Left {
  74.         node.Parent.Left = nil
  75.     } else if node == node.Parent.Right {
  76.         node.Parent.Right = nil
  77.     }
  79.     node.Parent = nil
  81. }

当删除的节点有两棵子树，那么它是内部节点，找到其最小后驱节点来替换它，也就是其右子树一直往左边找，该最小后驱节点可能是叶子结点，也可能有一个右儿子：

  1.     // 如果左右子树都存在，那么从右子树的左边一直找一直找，就找能到最小后驱节点
  2.     if node.Left != nil && node.Right != nil {
  3.         s := node.Right
  4.         for s.Left != nil {
  5.             s = s.Left
  6.         }
  8.         // 删除的叶子节点找到了，删除内部节点转为删除叶子节点
  9.         node.Value = s.Value
  10.         node.Times = s.Times
  11.         node = s
  12.     }

接着继续判断，

如果没有子树，那么删除的节点就是叶子节点了：

  1.     if node.Left == nil && node.Right == nil {
  2.         // 没有子树，要删除的节点就是叶子节点。
  3.     }

否则如果只有一棵子树，那么根据红黑树的特征，该子树只有一个节点：

  1.     } else {
  2.         // 只有一棵子树，因为红黑树的特征，该子树就只有一个节点
  3.         // 找到该唯一节点
  4.         replacement := node.Left
  5.         if node.Left == nil {
  6.             replacement = node.Right
  7.         }
  9.         // 替换开始，子树的唯一节点替代被删除的内部节点
  10.         replacement.Parent = node.Parent
  11.         if node.Parent == nil {
  12.             // 要删除的节点的父亲为空，表示要删除的节点为根节点，唯一子节点成为树根
  13.             tree.Root = replacement
  14.         } else if node == node.Parent.Left {
  15.             // 子树的唯一节点替代被删除的内部节点
  16.             node.Parent.Left = replacement
  17.         } else {
  18.             // 子树的唯一节点替代被删除的内部节点
  19.             node.Parent.Right = replacement
  20.         }
  22.         // delete this node
  23.         node.Parent = nil
  24.         node.Right = nil
  25.         node.Left = nil
  27.         //  case 1: not enter this logic
  28.         //      R(del)
  29.         //    B   B
  30.         //
  31.         //  case 2: node's color must be black, and it's son must be red
  32.         //    B(del)     B(del)
  33.         //  R  O       O   R
  34.         //
  35.         // 单子树时删除的节点绝对是黑色的，而其唯一子节点必然是红色的
  36.         // 现在唯一子节点替换了被删除节点，该节点要变为黑色
  37.         // now son replace it's father, just change color to black
  38.         replacement.Color = BLACK
  39.         return
  40.     }

删除叶子节点，如何删除呢，首先如果它是根节点，那么树就空了：

  1.     // 要删除的叶子节点没有父亲，那么它是根节点，直接置空，返回
  2.     if node.Parent == nil {
  3.         tree.Root = nil
  4.         return
  5.     }

否则需要判断该叶子节点是不是红节点，如果不是红节点，不能直接删除，需要调整：

  1.     // 要删除的叶子节点，是一个黑节点，删除后会破坏平衡，需要进行调整，调整成可以删除的状态
  2.     if !IsRed(node) {
  3.         // 核心函数
  4.         tree.fixAfterDeletion(node)
  5.     }

最后，就可以删除叶子节点了：

  1.     // 现在可以删除叶子节点了
  2.     if node == node.Parent.Left {
  3.         node.Parent.Left = nil
  4.     } else if node == node.Parent.Right {
  5.         node.Parent.Right = nil
  6.     }
  7.     node.Parent = nil

核心删除调整函数 fixAfterDeletion 非常重要，可以看图理解：

  1. // 调整删除的叶子节点，自底向上
  2. // 可以看图理解
  3. func (tree *RBTree) fixAfterDeletion(node *RBTNode) {
  4.     // 如果不是递归到根节点，且节点是黑节点，那么继续递归
  5.     for tree.Root != node && !IsRed(node) {
  6.         // 要删除的节点在父亲左边，对应图例1，2
  7.         if node == LeftOf(ParentOf(node)) {
  8.             // 找出兄弟
  9.             brother := RightOf(ParentOf(node))
  11.             // 兄弟是红色的，对应图例1，那么兄弟变黑，父亲变红，然后对父亲左旋，进入图例21,22,23
  12.             if IsRed(brother) {
  13.                 SetColor(brother, BLACK)
  14.                 SetColor(ParentOf(node), RED)
  15.                 tree.RotateLeft(ParentOf(node))
  16.                 brother = RightOf(ParentOf(node)) // 图例1调整后进入图例21,22,23，兄弟此时变了
  17.             }
  19.             // 兄弟是黑色的，对应图例21，22，23
  20.             // 兄弟的左右儿子都是黑色，进入图例23，将兄弟设为红色，父亲所在的子树作为整体，当作删除的节点，继续向上递归
  21.             if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
  22.                 SetColor(brother, RED)
  23.                 node = ParentOf(node)
  24.             } else {
  25.                 // 兄弟的右儿子是黑色，进入图例22，将兄弟设为红色，兄弟的左儿子设为黑色，对兄弟右旋，进入图例21
  26.                 if !IsRed(RightOf(brother)) {
  27.                     SetColor(LeftOf(brother), BLACK)
  28.                     SetColor(brother, RED)
  29.                     tree.RotateRight(brother)
  30.                     brother = RightOf(ParentOf(node)) // 图例22调整后进入图例21，兄弟此时变了
  31.                 }
  33.                 // 兄弟的右儿子是红色，进入图例21，将兄弟设置为父亲的颜色，兄弟的右儿子以及父亲变黑，对父亲左旋
  34.                 SetColor(brother, ParentOf(node).Color)
  35.                 SetColor(ParentOf(node), BLACK)
  36.                 SetColor(RightOf(brother), BLACK)
  37.                 tree.RotateLeft(ParentOf(node))
  39.                 node = tree.Root
  40.             }
  41.         } else {
  42.             // 要删除的节点在父亲右边，对应图例3，4
  43.             // 找出兄弟
  44.             brother := RightOf(ParentOf(node))
  46.             // 兄弟是红色的，对应图例3，那么兄弟变黑，父亲变红，然后对父亲右旋，进入图例41,42,43
  47.             if IsRed(brother) {
  48.                 SetColor(brother, BLACK)
  49.                 SetColor(ParentOf(node), RED)
  50.                 tree.RotateRight(ParentOf(node))
  51.                 brother = LeftOf(ParentOf(node)) // 图例3调整后进入图例41,42,43，兄弟此时变了
  52.             }
  54.             // 兄弟是黑色的，对应图例41，42，43
  55.             // 兄弟的左右儿子都是黑色，进入图例43，将兄弟设为红色，父亲所在的子树作为整体，当作删除的节点，继续向上递归
  56.             if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
  57.                 SetColor(brother, RED)
  58.                 node = ParentOf(node)
  59.             } else {
  60.                 // 兄弟的左儿子是黑色，进入图例42，将兄弟设为红色，兄弟的右儿子设为黑色，对兄弟左旋，进入图例41
  61.                 if !IsRed(LeftOf(brother)) {
  62.                     SetColor(RightOf(brother), BLACK)
  63.                     SetColor(brother, RED)
  64.                     tree.RotateLeft(brother)
  65.                     brother = LeftOf(ParentOf(node)) // 图例42调整后进入图例41，兄弟此时变了
  66.                 }
  68.                 // 兄弟的左儿子是红色，进入图例41，将兄弟设置为父亲的颜色，兄弟的左儿子以及父亲变黑，对父亲右旋
  69.                 SetColor(brother, ParentOf(node).Color)
  70.                 SetColor(ParentOf(node), BLACK)
  71.                 SetColor(LeftOf(brother), BLACK)
  72.                 tree.RotateRight(ParentOf(node))
  74.                 node = tree.Root
  75.             }
  76.         }
  77.     }
  79.     // this node always black
  80.     SetColor(node, BLACK)
  81. }

只有符合 tree.Root != node && !IsRed(node) 才能继续进入递归。

要删除的节点在父亲左边：node == LeftOf(ParentOf(node))，对应图例1，2:

2-3-4树和普通红黑树 - 图22

否则对应图例3，4：

2-3-4树和普通红黑树 - 图23

可以参考图理解代码，代码注释很清晰地对照了示例图。

2.6. 删除元素算法分析

删除元素比左倾红黑树的情况还要多，但是平均时间复杂度仍然是 log(n)，出现在和兄弟借不到值的情况下向上递归。和 AVL树 区别是，普通红黑树删除元素最多旋转三次，参考 1图例-22图例-21图例 的状态转变，最多旋转三次，而 AVL树 可能旋转很多次，甚至自底向上一直旋转到根节点。

2.7. 查找元素等实现

略。与左倾红黑树，AVL树都一样。

2.8. 验证是否是一棵普通红黑树

如何确保我们的代码实现的就是一棵普通红黑树呢，可以进行验证：

  1. // 验证是不是棵红黑树
  2. func (tree *RBTree) IsRBTree() bool {
  3.     if tree == nil || tree.Root == nil {
  4.         return true
  5.     }
  7.     // 判断树是否是一棵二分查找树
  8.     if !tree.Root.IsBST() {
  9.         return false
  10.     }
  12.     // 判断树是否遵循2-3-4树，也就是不能有连续的两个红链接
  13.     if !tree.Root.Is234() {
  14.         return false
  15.     }
  17.     // 判断树是否平衡，也就是任意一个节点到叶子节点，经过的黑色链接数量相同
  18.     // 先计算根节点到最左边叶子节点的黑链接数量
  19.     blackNum := 0
  20.     x := tree.Root
  21.     for x != nil {
  22.         if !IsRed(x) { // 是黑色链接
  23.             blackNum = blackNum + 1
  24.         }
  25.         x = x.Left
  26.     }
  28.     if !tree.Root.IsBalanced(blackNum) {
  29.         return false
  30.     }
  31.     return true
  32. }
  34. // 节点所在的子树是否是一棵二分查找树
  35. func (node *RBTNode) IsBST() bool {
  36.     if node == nil {
  37.         return true
  38.     }
  40.     // 左子树非空，那么根节点必须大于左儿子节点
  41.     if node.Left != nil {
  42.         if node.Value > node.Left.Value {
  43.         } else {
  44.             fmt.Printf("father:%#v,lchild:%#v,rchild:%#v\n", node, node.Left, node.Right)
  45.             return false
  46.         }
  47.     }
  49.     // 右子树非空，那么根节点必须小于右儿子节点
  50.     if node.Right != nil {
  51.         if node.Value < node.Right.Value {
  52.         } else {
  53.             fmt.Printf("father:%#v,lchild:%#v,rchild:%#v\n", node, node.Left, node.Right)
  54.             return false
  55.         }
  56.     }
  58.     // 左子树也要判断是否是平衡查找树
  59.     if !node.Left.IsBST() {
  60.         return false
  61.     }
  63.     // 右子树也要判断是否是平衡查找树
  64.     if !node.Right.IsBST() {
  65.         return false
  66.     }
  68.     return true
  69. }
  71. // 节点所在的子树是否遵循2-3-4树
  72. func (node *RBTNode) Is234() bool {
  73.     if node == nil {
  74.         return true
  75.     }
  77.     // 不允许连续两个左红链接
  78.     if IsRed(node) && IsRed(node.Left) {
  79.         fmt.Printf("father:%#v,lchild:%#v\n", node, node.Left)
  80.         return false
  81.     }
  83.     if IsRed(node) && IsRed(node.Right) {
  84.         fmt.Printf("father:%#v,rchild:%#v\n", node, node.Right)
  85.         return false
  86.     }
  88.     // 左子树也要判断是否遵循2-3-4树
  89.     if !node.Left.Is234() {
  90.         return false
  91.     }
  93.     // 右子树也要判断是否是遵循2-3-4树
  94.     if !node.Right.Is234() {
  95.         return false
  96.     }
  98.     return true
  99. }
  101. // 节点所在的子树是否平衡，是否有 blackNum 个黑链接
  102. func (node *RBTNode) IsBalanced(blackNum int) bool {
  103.     if node == nil {
  104.         return blackNum == 0
  105.     }
  107.     if !IsRed(node) {
  108.         blackNum = blackNum - 1
  109.     }
  111.     if !node.Left.IsBalanced(blackNum) {
  112.         fmt.Println("node.Left to leaf black link is not ", blackNum)
  113.         return false
  114.     }
  116.     if !node.Right.IsBalanced(blackNum) {
  117.         fmt.Println("node.Right to leaf black link is not ", blackNum)
  118.         return false
  119.     }
  121.     return true
  122. }

运行请看完整代码。

2.9. 完整程序

  1. package main
  3. import "fmt"
  5. // 普通红黑树实现，参考 Java TreeMap，更强壮。
  6. // red-black tree
  8. // 定义颜色
  9. const (
  10.     RED   = true
  11.     BLACK = false
  12. )
  14. // 普通红黑树
  15. type RBTree struct {
  16.     Root *RBTNode // 树根节点
  17. }
  19. // 新建一棵空树
  20. func NewRBTree() *RBTree {
  21.     return &RBTree{}
  22. }
  24. // 普通红黑树节点
  25. type RBTNode struct {
  26.     Value  int64    // 值
  27.     Times  int64    // 值出现的次数
  28.     Left   *RBTNode // 左子树
  29.     Right  *RBTNode // 右子树
  30.     Parent *RBTNode // 父节点
  31.     Color  bool     // 父亲指向该节点的链接颜色
  32. }
  34. // 节点的颜色
  35. func IsRed(node *RBTNode) bool {
  36.     if node == nil {
  37.         return false
  38.     }
  39.     return node.Color == RED
  40. }
  42. // 返回节点的父亲节点
  43. func ParentOf(node *RBTNode) *RBTNode {
  44.     if node == nil {
  45.         return nil
  46.     }
  48.     return node.Parent
  49. }
  51. // 返回节点的左子节点
  52. func LeftOf(node *RBTNode) *RBTNode {
  53.     if node == nil {
  54.         return nil
  55.     }
  57.     return node.Left
  58. }
  60. // 返回节点的右子节点
  61. func RightOf(node *RBTNode) *RBTNode {
  62.     if node == nil {
  63.         return nil
  64.     }
  66.     return node.Right
  67. }
  69. // 设置节点颜色
  70. func SetColor(node *RBTNode, color bool) {
  71.     if node != nil {
  72.         node.Color = color
  73.     }
  74. }
  76. // 对某节点左旋转
  77. func (tree *RBTree) RotateLeft(h *RBTNode) {
  78.     if h != nil {
  80.         // 看图理解
  81.         x := h.Right
  82.         h.Right = x.Left
  84.         if x.Left != nil {
  85.             x.Left.Parent = h
  86.         }
  88.         x.Parent = h.Parent
  89.         if h.Parent == nil {
  90.             tree.Root = x
  91.         } else if h.Parent.Left == h {
  92.             h.Parent.Left = x
  93.         } else {
  94.             h.Parent.Right = x
  95.         }
  96.         x.Left = h
  97.         h.Parent = x
  98.     }
  99. }
  101. // 对某节点右旋转
  102. func (tree *RBTree) RotateRight(h *RBTNode) {
  103.     if h != nil {
  105.         // 看图理解
  106.         x := h.Left
  107.         h.Left = x.Right
  109.         if x.Right != nil {
  110.             x.Right.Parent = h
  111.         }
  113.         x.Parent = h.Parent
  114.         if h.Parent == nil {
  115.             tree.Root = x
  116.         } else if h.Parent.Right == h {
  117.             h.Parent.Right = x
  118.         } else {
  119.             h.Parent.Left = x
  120.         }
  121.         x.Right = h
  122.         h.Parent = x
  123.     }
  124. }
  126. // 普通红黑树添加元素
  127. func (tree *RBTree) Add(value int64) {
  128.     // 根节点为空
  129.     if tree.Root == nil {
  130.         // 根节点都是黑色
  131.         tree.Root = &RBTNode{
  132.             Value: value,
  133.             Color: BLACK,
  134.         }
  135.         return
  136.     }
  138.     // 辅助变量 t，表示新元素要插入到该子树，t是该子树的根节点
  139.     t := tree.Root
  141.     // 插入元素后，插入元素的父亲节点
  142.     var parent *RBTNode
  144.     // 辅助变量，为了知道元素最后要插到左边还是右边
  145.     var cmp int64 = 0
  147.     for {
  148.         parent = t
  150.         cmp = value - t.Value
  151.         if cmp < 0 {
  152.             // 比当前节点小，往左子树插入
  153.             t = t.Left
  154.         } else if cmp > 0 {
  155.             // 比当前节点节点大，往右子树插入
  156.             t = t.Right
  157.         } else {
  158.             // 已经存在值了，更新出现的次数
  159.             t.Times = t.Times + 1
  160.             return
  161.         }
  163.         // 终于找到要插入的位置了
  164.         if t == nil {
  165.             break // 这时叶子节点是 parent，要插入到 parent 的下面，跳到外层去
  166.         }
  167.     }
  169.     // 新节点，它要插入到 parent下面
  170.     newNode := &RBTNode{
  171.         Value:  value,
  172.         Parent: parent,
  173.     }
  174.     if cmp < 0 {
  175.         // 知道要从左边插进去
  176.         parent.Left = newNode
  177.     } else {
  178.         // 知道要从右边插进去
  179.         parent.Right = newNode
  180.     }
  182.     // 插入新节点后，可能破坏了红黑树特征，需要修复，核心函数
  183.     tree.fixAfterInsertion(newNode)
  184. }
  186. // 调整新插入的节点，自底而上
  187. // 可以看图理解
  188. func (tree *RBTree) fixAfterInsertion(node *RBTNode) {
  189.     // 插入的新节点一定要是红色
  190.     node.Color = RED
  192.     // 节点不能是空，不能是根节点，父亲的颜色必须为红色（如果是黑色，那么直接插入不破坏平衡，不需要调整了）
  193.     for node != nil && node != tree.Root && node.Parent.Color == RED {
  194.         // 父亲在祖父的左边
  195.         if ParentOf(node) == LeftOf(ParentOf(ParentOf(node))) {
  196.             // 叔叔节点
  197.             uncle := RightOf(ParentOf(ParentOf(node)))
  199.             // 图例3左边部分，叔叔是红节点，祖父变色，也就是父亲和叔叔变黑，祖父变红
  200.             if IsRed(uncle) {
  201.                 SetColor(ParentOf(node), BLACK)
  202.                 SetColor(uncle, BLACK)
  203.                 SetColor(ParentOf(ParentOf(node)), RED)
  204.                 // 还要向上递归
  205.                 node = ParentOf(ParentOf(node))
  206.             } else {
  207.                 // 图例4左边部分，叔叔是黑节点，并且插入的节点在父亲的右边，需要对父亲左旋
  208.                 if node == RightOf(ParentOf(node)) {
  209.                     node = ParentOf(node)
  210.                     tree.RotateLeft(node)
  211.                 }
  213.                 // 变色，并对祖父进行右旋
  214.                 SetColor(ParentOf(node), BLACK)
  215.                 SetColor(ParentOf(ParentOf(node)), RED)
  216.                 tree.RotateRight(ParentOf(ParentOf(node)))
  217.             }
  218.         } else {
  219.             // 父亲在祖父的右边，与父亲在祖父的左边相似
  220.             // 叔叔节点
  221.             uncle := LeftOf(ParentOf(ParentOf(node)))
  223.             // 图例3右边部分，叔叔是红节点，祖父变色，也就是父亲和叔叔变黑，祖父变红
  224.             if IsRed(uncle) {
  225.                 SetColor(ParentOf(node), BLACK)
  226.                 SetColor(uncle, BLACK)
  227.                 SetColor(ParentOf(ParentOf(node)), RED)
  228.                 // 还要向上递归
  229.                 node = ParentOf(ParentOf(node))
  230.             } else {
  231.                 // 图例4右边部分，叔叔是黑节点，并且插入的节点在父亲的左边，需要对父亲右旋
  232.                 if node == LeftOf(ParentOf(node)) {
  233.                     node = ParentOf(node)
  234.                     tree.RotateRight(node)
  235.                 }
  237.                 // 变色，并对祖父进行左旋
  238.                 SetColor(ParentOf(node), BLACK)
  239.                 SetColor(ParentOf(ParentOf(node)), RED)
  240.                 tree.RotateLeft(ParentOf(ParentOf(node)))
  241.             }
  242.         }
  243.     }
  245.     // 根节点永远为黑
  246.     tree.Root.Color = BLACK
  247. }
  249. // 普通红黑树删除元素
  250. func (tree *RBTree) Delete(value int64) {
  251.     // 查找元素是否存在，不存在则退出
  252.     p := tree.Find(value)
  253.     if p == nil {
  254.         return
  255.     }
  257.     // 删除该节点
  258.     tree.delete(p)
  259. }
  261. // 删除节点核心函数
  262. // 找最小后驱节点来补位，删除内部节点转为删除叶子节点
  263. func (tree *RBTree) delete(node *RBTNode) {
  264.     // 如果左右子树都存在，那么从右子树的左边一直找一直找，就找能到最小后驱节点
  265.     if node.Left != nil && node.Right != nil {
  266.         s := node.Right
  267.         for s.Left != nil {
  268.             s = s.Left
  269.         }
  271.         // 删除的叶子节点找到了，删除内部节点转为删除叶子节点
  272.         node.Value = s.Value
  273.         node.Times = s.Times
  274.         node = s // 可能存在右儿子
  275.     }
  277.     if node.Left == nil && node.Right == nil {
  278.         // 没有子树，要删除的节点就是叶子节点。
  279.     } else {
  280.         // 只有一棵子树，因为红黑树的特征，该子树就只有一个节点
  281.         // 找到该唯一节点
  282.         replacement := node.Left
  283.         if node.Left == nil {
  284.             replacement = node.Right
  285.         }
  287.         // 替换开始，子树的唯一节点替代被删除的内部节点
  288.         replacement.Parent = node.Parent
  289.         if node.Parent == nil {
  290.             // 要删除的节点的父亲为空，表示要删除的节点为根节点，唯一子节点成为树根
  291.             tree.Root = replacement
  292.         } else if node == node.Parent.Left {
  293.             // 子树的唯一节点替代被删除的内部节点
  294.             node.Parent.Left = replacement
  295.         } else {
  296.             // 子树的唯一节点替代被删除的内部节点
  297.             node.Parent.Right = replacement
  298.         }
  300.         // delete this node
  301.         node.Parent = nil
  302.         node.Right = nil
  303.         node.Left = nil
  305.         //  case 1: not enter this logic
  306.         //      R(del)
  307.         //    B   B
  308.         //
  309.         //  case 2: node's color must be black, and it's son must be red
  310.         //    B(del)     B(del)
  311.         //  R  O       O   R
  312.         //
  313.         // 单子树时删除的节点绝对是黑色的，而其唯一子节点必然是红色的
  314.         // 现在唯一子节点替换了被删除节点，该节点要变为黑色
  315.         // now son replace it's father, just change color to black
  316.         replacement.Color = BLACK
  317.         return
  318.     }
  320.     // 要删除的叶子节点没有父亲，那么它是根节点，直接置空，返回
  321.     if node.Parent == nil {
  322.         tree.Root = nil
  323.         return
  324.     }
  326.     // 要删除的叶子节点，是一个黑节点，删除后会破坏平衡，需要进行调整，调整成可以删除的状态
  327.     if !IsRed(node) {
  328.         // 核心函数
  329.         tree.fixAfterDeletion(node)
  330.     }
  332.     // 现在可以删除叶子节点了
  333.     if node == node.Parent.Left {
  334.         node.Parent.Left = nil
  335.     } else if node == node.Parent.Right {
  336.         node.Parent.Right = nil
  337.     }
  339.     node.Parent = nil
  341. }
  343. // 调整删除的叶子节点，自底向上
  344. // 可以看图理解
  345. func (tree *RBTree) fixAfterDeletion(node *RBTNode) {
  346.     // 如果不是递归到根节点，且节点是黑节点，那么继续递归
  347.     for tree.Root != node && !IsRed(node) {
  348.         // 要删除的节点在父亲左边，对应图例1，2
  349.         if node == LeftOf(ParentOf(node)) {
  350.             // 找出兄弟
  351.             brother := RightOf(ParentOf(node))
  353.             // 兄弟是红色的，对应图例1，那么兄弟变黑，父亲变红，然后对父亲左旋，进入图例21,22,23
  354.             if IsRed(brother) {
  355.                 SetColor(brother, BLACK)
  356.                 SetColor(ParentOf(node), RED)
  357.                 tree.RotateLeft(ParentOf(node))
  358.                 brother = RightOf(ParentOf(node)) // 图例1调整后进入图例21,22,23，兄弟此时变了
  359.             }
  361.             // 兄弟是黑色的，对应图例21，22，23
  362.             // 兄弟的左右儿子都是黑色，进入图例23，将兄弟设为红色，父亲所在的子树作为整体，当作删除的节点，继续向上递归
  363.             if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
  364.                 SetColor(brother, RED)
  365.                 node = ParentOf(node)
  366.             } else {
  367.                 // 兄弟的右儿子是黑色，进入图例22，将兄弟设为红色，兄弟的左儿子设为黑色，对兄弟右旋，进入图例21
  368.                 if !IsRed(RightOf(brother)) {
  369.                     SetColor(LeftOf(brother), BLACK)
  370.                     SetColor(brother, RED)
  371.                     tree.RotateRight(brother)
  372.                     brother = RightOf(ParentOf(node)) // 图例22调整后进入图例21，兄弟此时变了
  373.                 }
  375.                 // 兄弟的右儿子是红色，进入图例21，将兄弟设置为父亲的颜色，兄弟的右儿子以及父亲变黑，对父亲左旋
  376.                 SetColor(brother, ParentOf(node).Color)
  377.                 SetColor(ParentOf(node), BLACK)
  378.                 SetColor(RightOf(brother), BLACK)
  379.                 tree.RotateLeft(ParentOf(node))
  381.                 node = tree.Root
  382.             }
  383.         } else {
  384.             // 要删除的节点在父亲右边，对应图例3，4
  385.             // 找出兄弟
  386.             brother := RightOf(ParentOf(node))
  388.             // 兄弟是红色的，对应图例3，那么兄弟变黑，父亲变红，然后对父亲右旋，进入图例41,42,43
  389.             if IsRed(brother) {
  390.                 SetColor(brother, BLACK)
  391.                 SetColor(ParentOf(node), RED)
  392.                 tree.RotateRight(ParentOf(node))
  393.                 brother = LeftOf(ParentOf(node)) // 图例3调整后进入图例41,42,43，兄弟此时变了
  394.             }
  396.             // 兄弟是黑色的，对应图例41，42，43
  397.             // 兄弟的左右儿子都是黑色，进入图例43，将兄弟设为红色，父亲所在的子树作为整体，当作删除的节点，继续向上递归
  398.             if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
  399.                 SetColor(brother, RED)
  400.                 node = ParentOf(node)
  401.             } else {
  402.                 // 兄弟的左儿子是黑色，进入图例42，将兄弟设为红色，兄弟的右儿子设为黑色，对兄弟左旋，进入图例41
  403.                 if !IsRed(LeftOf(brother)) {
  404.                     SetColor(RightOf(brother), BLACK)
  405.                     SetColor(brother, RED)
  406.                     tree.RotateLeft(brother)
  407.                     brother = LeftOf(ParentOf(node)) // 图例42调整后进入图例41，兄弟此时变了
  408.                 }
  410.                 // 兄弟的左儿子是红色，进入图例41，将兄弟设置为父亲的颜色，兄弟的左儿子以及父亲变黑，对父亲右旋
  411.                 SetColor(brother, ParentOf(node).Color)
  412.                 SetColor(ParentOf(node), BLACK)
  413.                 SetColor(LeftOf(brother), BLACK)
  414.                 tree.RotateRight(ParentOf(node))
  416.                 node = tree.Root
  417.             }
  418.         }
  419.     }
  421.     // this node always black
  422.     SetColor(node, BLACK)
  423. }
  425. // 找出最小值的节点
  426. func (tree *RBTree) FindMinValue() *RBTNode {
  427.     if tree.Root == nil {
  428.         // 如果是空树，返回空
  429.         return nil
  430.     }
  432.     return tree.Root.FindMinValue()
  433. }
  435. func (node *RBTNode) FindMinValue() *RBTNode {
  436.     // 左子树为空，表面已经是最左的节点了，该值就是最小值
  437.     if node.Left == nil {
  438.         return node
  439.     }
  441.     // 一直左子树递归
  442.     return node.Left.FindMinValue()
  443. }
  445. // 找出最大值的节点
  446. func (tree *RBTree) FindMaxValue() *RBTNode {
  447.     if tree.Root == nil {
  448.         // 如果是空树，返回空
  449.         return nil
  450.     }
  452.     return tree.Root.FindMaxValue()
  453. }
  455. func (node *RBTNode) FindMaxValue() *RBTNode {
  456.     // 右子树为空，表面已经是最右的节点了，该值就是最大值
  457.     if node.Right == nil {
  458.         return node
  459.     }
  461.     // 一直右子树递归
  462.     return node.Right.FindMaxValue()
  463. }
  465. // 查找指定节点
  466. func (tree *RBTree) Find(value int64) *RBTNode {
  467.     if tree.Root == nil {
  468.         // 如果是空树，返回空
  469.         return nil
  470.     }
  472.     return tree.Root.Find(value)
  473. }
  475. func (node *RBTNode) Find(value int64) *RBTNode {
  476.     if value == node.Value {
  477.         // 如果该节点刚刚等于该值，那么返回该节点
  478.         return node
  479.     } else if value < node.Value {
  480.         // 如果查找的值小于节点值，从节点的左子树开始找
  481.         if node.Left == nil {
  482.             // 左子树为空，表示找不到该值了，返回nil
  483.             return nil
  484.         }
  485.         return node.Left.Find(value)
  486.     } else {
  487.         // 如果查找的值大于节点值，从节点的右子树开始找
  488.         if node.Right == nil {
  489.             // 右子树为空，表示找不到该值了，返回nil
  490.             return nil
  491.         }
  492.         return node.Right.Find(value)
  493.     }
  494. }
  496. // 中序遍历
  497. func (tree *RBTree) MidOrder() {
  498.     tree.Root.MidOrder()
  499. }
  501. func (node *RBTNode) MidOrder() {
  502.     if node == nil {
  503.         return
  504.     }
  506.     // 先打印左子树
  507.     node.Left.MidOrder()
  509.     // 按照次数打印根节点
  510.     for i := 0; i <= int(node.Times); i++ {
  511.         fmt.Println(node.Value)
  512.     }
  514.     // 打印右子树
  515.     node.Right.MidOrder()
  516. }
  518. // 验证是不是棵红黑树
  519. func (tree *RBTree) IsRBTree() bool {
  520.     if tree == nil || tree.Root == nil {
  521.         return true
  522.     }
  524.     // 判断树是否是一棵二分查找树
  525.     if !tree.Root.IsBST() {
  526.         return false
  527.     }
  529.     // 判断树是否遵循2-3-4树，也就是不能有连续的两个红链接
  530.     if !tree.Root.Is234() {
  531.         return false
  532.     }
  534.     // 判断树是否平衡，也就是任意一个节点到叶子节点，经过的黑色链接数量相同
  535.     // 先计算根节点到最左边叶子节点的黑链接数量
  536.     blackNum := 0
  537.     x := tree.Root
  538.     for x != nil {
  539.         if !IsRed(x) { // 是黑色链接
  540.             blackNum = blackNum + 1
  541.         }
  542.         x = x.Left
  543.     }
  545.     if !tree.Root.IsBalanced(blackNum) {
  546.         return false
  547.     }
  548.     return true
  549. }
  551. // 节点所在的子树是否是一棵二分查找树
  552. func (node *RBTNode) IsBST() bool {
  553.     if node == nil {
  554.         return true
  555.     }
  557.     // 左子树非空，那么根节点必须大于左儿子节点
  558.     if node.Left != nil {
  559.         if node.Value > node.Left.Value {
  560.         } else {
  561.             fmt.Printf("father:%#v,lchild:%#v,rchild:%#v\n", node, node.Left, node.Right)
  562.             return false
  563.         }
  564.     }
  566.     // 右子树非空，那么根节点必须小于右儿子节点
  567.     if node.Right != nil {
  568.         if node.Value < node.Right.Value {
  569.         } else {
  570.             fmt.Printf("father:%#v,lchild:%#v,rchild:%#v\n", node, node.Left, node.Right)
  571.             return false
  572.         }
  573.     }
  575.     // 左子树也要判断是否是平衡查找树
  576.     if !node.Left.IsBST() {
  577.         return false
  578.     }
  580.     // 右子树也要判断是否是平衡查找树
  581.     if !node.Right.IsBST() {
  582.         return false
  583.     }
  585.     return true
  586. }
  588. // 节点所在的子树是否遵循2-3-4树
  589. func (node *RBTNode) Is234() bool {
  590.     if node == nil {
  591.         return true
  592.     }
  594.     // 不允许连续两个左红链接
  595.     if IsRed(node) && IsRed(node.Left) {
  596.         fmt.Printf("father:%#v,lchild:%#v\n", node, node.Left)
  597.         return false
  598.     }
  600.     if IsRed(node) && IsRed(node.Right) {
  601.         fmt.Printf("father:%#v,rchild:%#v\n", node, node.Right)
  602.         return false
  603.     }
  605.     // 左子树也要判断是否遵循2-3-4树
  606.     if !node.Left.Is234() {
  607.         return false
  608.     }
  610.     // 右子树也要判断是否是遵循2-3-4树
  611.     if !node.Right.Is234() {
  612.         return false
  613.     }
  615.     return true
  616. }
  618. // 节点所在的子树是否平衡，是否有 blackNum 个黑链接
  619. func (node *RBTNode) IsBalanced(blackNum int) bool {
  620.     if node == nil {
  621.         return blackNum == 0
  622.     }
  624.     if !IsRed(node) {
  625.         blackNum = blackNum - 1
  626.     }
  628.     if !node.Left.IsBalanced(blackNum) {
  629.         fmt.Println("node.Left to leaf black link is not ", blackNum)
  630.         return false
  631.     }
  633.     if !node.Right.IsBalanced(blackNum) {
  634.         fmt.Println("node.Right to leaf black link is not ", blackNum)
  635.         return false
  636.     }
  638.     return true
  639. }
  641. func main() {
  642.     tree := NewRBTree()
  643.     values := []int64{2, 3, 7, 10, 10, 10, 10, 23, 9, 102, 109, 111, 112, 113}
  644.     for _, v := range values {
  645.         tree.Add(v)
  646.     }
  648.     // 找到最大值或最小值的节点
  649.     fmt.Println("find min value:", tree.FindMinValue())
  650.     fmt.Println("find max value:", tree.FindMaxValue())
  652.     // 查找不存在的99
  653.     node := tree.Find(99)
  654.     if node != nil {
  655.         fmt.Println("find it 99!")
  656.     } else {
  657.         fmt.Println("not find it 99!")
  658.     }
  660.     // 查找存在的9
  661.     node = tree.Find(9)
  662.     if node != nil {
  663.         fmt.Println("find it 9!")
  664.     } else {
  665.         fmt.Println("not find it 9!")
  666.     }
  668.     tree.MidOrder()
  670.     // 删除存在的9后，再查找9
  671.     tree.Delete(9)
  672.     tree.Delete(10)
  673.     tree.Delete(2)
  674.     tree.Delete(3)
  675.     tree.Add(4)
  676.     tree.Add(3)
  677.     tree.Add(10)
  678.     tree.Delete(111)
  679.     node = tree.Find(9)
  680.     if node != nil {
  681.         fmt.Println("find it 9!")
  682.     } else {
  683.         fmt.Println("not find it 9!")
  684.     }
  686.     if tree.IsRBTree() {
  687.         fmt.Println("is a rb tree")
  688.     } else {
  689.         fmt.Println("is not rb tree")
  690.     }
  692.     tree.Delete(3)
  693.     tree.Delete(4)
  694.     tree.Delete(7)
  695.     tree.Delete(10)
  696.     tree.Delete(23)
  697.     tree.Delete(102)
  698.     tree.Delete(109)
  699.     tree.Delete(112)
  700.     tree.Delete(112)
  701.     tree.MidOrder()
  702. }

运行：

  1. find min value: &{2 0 <nil> <nil> 0xc000092060 false}
  2. find max value: &{113 0 <nil> <nil> 0xc0000921e0 true}
  3. not find it 99!
  4. find it 9!
  5. 2
  6. 3
  7. 7
  8. 9
  9. 10
  10. 10
  11. 10
  12. 10
  13. 23
  14. 102
  15. 109
  16. 111
  17. 112
  18. 113
  19. not find it 9!
  20. is a rb tree

红黑树，无论是左偏还是普通的红黑树，理解都可以直接理解2-3或2-3-4树，添加操作比较简单，删除则是向兄弟借值或和父亲合并，然后如果父亲空了，把父亲的子树当成删除的一个整体，继续递归向上，至于二叉化的调整实现，则是将3或4节点画成红链接，可以多画下图就理解了。

三、应用场景

红黑树可以用来作为字典 Map 的基础数据结构，可以存储键值对，然后通过一个键，可以快速找到键对应的值，相比哈希表查找，不需要占用额外的空间。我们以上的代码实现只有 value，没有 key:value，可以简单改造实现字典。

Java 语言基础类库中的 HashMap，TreeSet，TreeMap 都有使用到，C++ 语言的 STL 标准模板库中，map 和 set 类也有使用到。很多中间件也有使用到，比如 Nginx，但 Golang 语言标准库并没有它。

附录

代码下载：https://github.com/hunterhug/goa.c/blob/master/code/rbt/main.go 。