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

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

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

一、2-3-4

1.1. 2-3-4 树介绍

2-3-4 树是一棵严格自平衡的多路查找树,又称 4阶的B树 (注:BBalance 平衡的意思)

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

  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 有两个儿子 BC,儿子 BC 要么都没有孩子,要么孩子都是满的,不然 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. )
  6. // 普通红黑树
  7. type RBTree struct {
  8. Root *RBTNode // 树根节点
  9. }
  10. // 新建一棵空树
  11. func NewRBTree() *RBTree {
  12. return &RBTree{}
  13. }
  14. // 普通红黑树节点
  15. type RBTNode struct {
  16. Value int64 // 值
  17. Times int64 // 值出现的次数
  18. Left *RBTNode // 左子树
  19. Right *RBTNode // 右子树
  20. Parent *RBTNode // 父节点
  21. Color bool // 父亲指向该节点的链接颜色
  22. }
  23. // 节点的颜色
  24. func IsRed(node *RBTNode) bool {
  25. if node == nil {
  26. return false
  27. }
  28. return node.Color == RED
  29. }
  30. // 返回节点的父亲节点
  31. func ParentOf(node *RBTNode) *RBTNode {
  32. if node == nil {
  33. return nil
  34. }
  35. return node.Parent
  36. }
  37. // 返回节点的左子节点
  38. func LeftOf(node *RBTNode) *RBTNode {
  39. if node == nil {
  40. return nil
  41. }
  42. return node.Left
  43. }
  44. // 返回节点的右子节点
  45. func RightOf(node *RBTNode) *RBTNode {
  46. if node == nil {
  47. return nil
  48. }
  49. return node.Right
  50. }
  51. // 设置节点颜色
  52. func SetColor(node *RBTNode, color bool) {
  53. if node != nil {
  54. node.Color = color
  55. }
  56. }

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

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

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

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

代码如下:

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

或者左链接进行右旋转,如图:

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

代码如下:

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

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

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

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

首先,如果是空树,那么新建根节点:

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

找到了要插入的位置,该位置是 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
  6. // 节点不能是空,不能是根节点,父亲的颜色必须为红色(如果是黑色,那么直接插入不破坏平衡,不需要调整了)
  7. for node != nil && node != tree.Root && node.Parent.Color == RED {
  8. // 父亲在祖父的左边
  9. if ParentOf(node) == LeftOf(ParentOf(ParentOf(node))) {
  10. // 叔叔节点
  11. uncle := RightOf(ParentOf(ParentOf(node)))
  12. // 图例3左边部分,叔叔是红节点,祖父变色,也就是父亲和叔叔变黑,祖父变红
  13. if IsRed(uncle) {
  14. SetColor(ParentOf(node), BLACK)
  15. SetColor(uncle, BLACK)
  16. SetColor(ParentOf(ParentOf(node)), RED)
  17. // 还要向上递归
  18. node = ParentOf(ParentOf(node))
  19. } else {
  20. // 图例4左边部分,叔叔是黑节点,并且插入的节点在父亲的右边,需要对父亲左旋
  21. if node == RightOf(ParentOf(node)) {
  22. node = ParentOf(node)
  23. tree.RotateLeft(node)
  24. }
  25. // 变色,并对祖父进行右旋
  26. SetColor(ParentOf(node), BLACK)
  27. SetColor(ParentOf(ParentOf(node)), RED)
  28. tree.RotateRight(ParentOf(ParentOf(node)))
  29. }
  30. } else {
  31. // 父亲在祖父的右边,与父亲在祖父的左边相似
  32. // 叔叔节点
  33. uncle := LeftOf(ParentOf(ParentOf(node)))
  34. // 图例3右边部分,叔叔是红节点,祖父变色,也就是父亲和叔叔变黑,祖父变红
  35. if IsRed(uncle) {
  36. SetColor(ParentOf(node), BLACK)
  37. SetColor(uncle, BLACK)
  38. SetColor(ParentOf(ParentOf(node)), RED)
  39. // 还要向上递归
  40. node = ParentOf(ParentOf(node))
  41. } else {
  42. // 图例4右边部分,叔叔是黑节点,并且插入的节点在父亲的左边,需要对父亲右旋
  43. if node == LeftOf(ParentOf(node)) {
  44. node = ParentOf(node)
  45. tree.RotateRight(node)
  46. }
  47. // 变色,并对祖父进行左旋
  48. SetColor(ParentOf(node), BLACK)
  49. SetColor(ParentOf(ParentOf(node)), RED)
  50. tree.RotateLeft(ParentOf(ParentOf(node)))
  51. }
  52. }
  53. }
  54. // 根节点永远为黑
  55. tree.Root.Color = BLACK
  56. }

可以知道,每次新插入的节点一定是红色: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. }
  6. // 变色,并对祖父进行右旋
  7. SetColor(ParentOf(node), BLACK)
  8. SetColor(ParentOf(ParentOf(node)), RED)
  9. tree.RotateRight(ParentOf(ParentOf(node)))

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

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

图例中 2122 相当于向兄弟借值,而 123 相当于向父亲的一个值合并后调整。

我们仔细分析一下:

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

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

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

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

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

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

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

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

存在删除的节点,那么进入删除操作: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. }
  10. // 删除的叶子节点找到了,删除内部节点转为删除叶子节点
  11. node.Value = s.Value
  12. node.Times = s.Times
  13. node = s // 可能存在右儿子
  14. }
  15. if node.Left == nil && node.Right == nil {
  16. // 没有子树,要删除的节点就是叶子节点。
  17. } else {
  18. // 只有一棵子树,因为红黑树的特征,该子树就只有一个节点
  19. // 找到该唯一节点
  20. replacement := node.Left
  21. if node.Left == nil {
  22. replacement = node.Right
  23. }
  24. // 替换开始,子树的唯一节点替代被删除的内部节点
  25. replacement.Parent = node.Parent
  26. if node.Parent == nil {
  27. // 要删除的节点的父亲为空,表示要删除的节点为根节点,唯一子节点成为树根
  28. tree.Root = replacement
  29. } else if node == node.Parent.Left {
  30. // 子树的唯一节点替代被删除的内部节点
  31. node.Parent.Left = replacement
  32. } else {
  33. // 子树的唯一节点替代被删除的内部节点
  34. node.Parent.Right = replacement
  35. }
  36. // delete this node
  37. node.Parent = nil
  38. node.Right = nil
  39. node.Left = nil
  40. // case 1: not enter this logic
  41. // R(del)
  42. // B B
  43. //
  44. // case 2: node's color must be black, and it's son must be red
  45. // B(del) B(del)
  46. // R O O R
  47. //
  48. // 单子树时删除的节点绝对是黑色的,而其唯一子节点必然是红色的
  49. // 现在唯一子节点替换了被删除节点,该节点要变为黑色
  50. // now son replace it's father, just change color to black
  51. replacement.Color = BLACK
  52. return
  53. }
  54. // 要删除的叶子节点没有父亲,那么它是根节点,直接置空,返回
  55. if node.Parent == nil {
  56. tree.Root = nil
  57. return
  58. }
  59. // 要删除的叶子节点,是一个黑节点,删除后会破坏平衡,需要进行调整,调整成可以删除的状态
  60. if !IsRed(node) {
  61. // 核心函数
  62. tree.fixAfterDeletion(node)
  63. }
  64. // 现在可以删除叶子节点了
  65. if node == node.Parent.Left {
  66. node.Parent.Left = nil
  67. } else if node == node.Parent.Right {
  68. node.Parent.Right = nil
  69. }
  70. node.Parent = nil
  71. }

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

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

接着继续判断,

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

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

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

  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))
  10. // 兄弟是红色的,对应图例1,那么兄弟变黑,父亲变红,然后对父亲左旋,进入图例21,22,23
  11. if IsRed(brother) {
  12. SetColor(brother, BLACK)
  13. SetColor(ParentOf(node), RED)
  14. tree.RotateLeft(ParentOf(node))
  15. brother = RightOf(ParentOf(node)) // 图例1调整后进入图例21,22,23,兄弟此时变了
  16. }
  17. // 兄弟是黑色的,对应图例21,22,23
  18. // 兄弟的左右儿子都是黑色,进入图例23,将兄弟设为红色,父亲所在的子树作为整体,当作删除的节点,继续向上递归
  19. if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
  20. SetColor(brother, RED)
  21. node = ParentOf(node)
  22. } else {
  23. // 兄弟的右儿子是黑色,进入图例22,将兄弟设为红色,兄弟的左儿子设为黑色,对兄弟右旋,进入图例21
  24. if !IsRed(RightOf(brother)) {
  25. SetColor(LeftOf(brother), BLACK)
  26. SetColor(brother, RED)
  27. tree.RotateRight(brother)
  28. brother = RightOf(ParentOf(node)) // 图例22调整后进入图例21,兄弟此时变了
  29. }
  30. // 兄弟的右儿子是红色,进入图例21,将兄弟设置为父亲的颜色,兄弟的右儿子以及父亲变黑,对父亲左旋
  31. SetColor(brother, ParentOf(node).Color)
  32. SetColor(ParentOf(node), BLACK)
  33. SetColor(RightOf(brother), BLACK)
  34. tree.RotateLeft(ParentOf(node))
  35. node = tree.Root
  36. }
  37. } else {
  38. // 要删除的节点在父亲右边,对应图例3,4
  39. // 找出兄弟
  40. brother := RightOf(ParentOf(node))
  41. // 兄弟是红色的,对应图例3,那么兄弟变黑,父亲变红,然后对父亲右旋,进入图例41,42,43
  42. if IsRed(brother) {
  43. SetColor(brother, BLACK)
  44. SetColor(ParentOf(node), RED)
  45. tree.RotateRight(ParentOf(node))
  46. brother = LeftOf(ParentOf(node)) // 图例3调整后进入图例41,42,43,兄弟此时变了
  47. }
  48. // 兄弟是黑色的,对应图例41,42,43
  49. // 兄弟的左右儿子都是黑色,进入图例43,将兄弟设为红色,父亲所在的子树作为整体,当作删除的节点,继续向上递归
  50. if !IsRed(LeftOf(brother)) && !IsRed(RightOf(brother)) {
  51. SetColor(brother, RED)
  52. node = ParentOf(node)
  53. } else {
  54. // 兄弟的左儿子是黑色,进入图例42,将兄弟设为红色,兄弟的右儿子设为黑色,对兄弟左旋,进入图例41
  55. if !IsRed(LeftOf(brother)) {
  56. SetColor(RightOf(brother), BLACK)
  57. SetColor(brother, RED)
  58. tree.RotateLeft(brother)
  59. brother = LeftOf(ParentOf(node)) // 图例42调整后进入图例41,兄弟此时变了
  60. }
  61. // 兄弟的左儿子是红色,进入图例41,将兄弟设置为父亲的颜色,兄弟的左儿子以及父亲变黑,对父亲右旋
  62. SetColor(brother, ParentOf(node).Color)
  63. SetColor(ParentOf(node), BLACK)
  64. SetColor(LeftOf(brother), BLACK)
  65. tree.RotateRight(ParentOf(node))
  66. node = tree.Root
  67. }
  68. }
  69. }
  70. // this node always black
  71. SetColor(node, BLACK)
  72. }

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

运行请看完整代码。

2.9. 完整程序

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

运行:

  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 语言基础类库中的 HashMapTreeSetTreeMap 都有使用到,C++ 语言的 STL 标准模板库中,mapset 类也有使用到。很多中间件也有使用到,比如 Nginx,但 Golang 语言标准库并没有它。