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

2-32-3-42-32-3-42-3-42-3
2-32-3

一、2-3 树

1.1. 2-3 树介绍

2-3John Edward Hopcroft3阶的B树BBalance

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

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

如图：

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

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

1.2. 2-3 树插入元素

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

2-3
  1. 插入元素到一个2节点，直接插入即可，这样节点变成3节点。
  2. 插入元素到一个3节点，该3节点的父亲是一个2节点，先将节点变成临时的4节点，然后向上分裂调整一次。
  3. 插入元素到一个3节点，该3节点的父亲是一个3节点，先将节点变成临时的4节点，然后向上分裂调整，此时父亲节点变为临时4节点，继续向上分裂调整。

如图（来自维基百科）：

核心在于插入3节点后，该节点变为临时4节点，然后进行分裂恢复树的特征。最坏情况为插入节点后，每一次分裂后都导致上一层变为临时4节点，直到树根节点，这样需要不断向上分裂。

临时4节点的分裂，细分有六种情况，如图：

2-3
2-3B树

1.3. 2-3 树删除元素

删除操作就复杂得多了，请耐心阅读理解。

2-32-32-3ABCBC2-3

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

情况1：删除中间节点

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

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

情况2：删除叶子节点

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

看图说话：

如果被删除的叶子节点有兄弟是3节点，那么从兄弟那里借一个值填补被删除的叶子节点，然后兄弟和父亲重新分布调整位置。下面是重新分布的具体例子：

10080

如果兄弟们都是2节点呢，那么就合并节点：将父亲和兄弟节点合并，如果父亲是2节点，那么父亲就留空了，否则父亲就从3节点变成2节点，下面是合并的两个具体例子：

806090
70

但是，如果合并后，父亲节点变空了，也就是说有中间节点留空要怎么办，那么可以继续递归处理，如图：

中间节点是空的，那么可以继续从兄弟那里借节点或者和父亲合并，直到根节点，如果到达了根节点呢，如图：

递归到了根节点后，如果存在空的根节点，我们可以直接把该空节点删除即可，这时树的高度减少一层。

2-3B树

二、 左倾红黑树

2.1. 左倾红黑树介绍

2-3

其定义为：

  1. 根节点的链接是黑色的。
  2. 红链接均为左链接。
  3. 没有任何一个结点同时和两条红链接相连
  4. 任意一个节点到达叶子节点的所有路径，经过的黑链接数量相同，也就是该树是完美黑色平衡的。比如，某一个节点，它可以到达5个叶子节点，那么这5条路径上的黑链接数量一样。
2-3

2.2. 节点旋转和颜色转换

LLRBTreeLLRBTNode
LLRBTNodeValueTimes
ColorIsRed()

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

h

代码实现如下：

h

代码实现如下：

由于左倾红黑树不允许一个节点有两个红链接，所以需要做颜色转换，如图：

代码如下：

旋转和颜色转换作为局部调整，并不影响全局。

2.3. 添加元素实现

ColorRED

接着判断其父亲是否有两个红链接（如连续的两个左红链接或者左右红色链接），或者有右红色链接，进行颜色变换或旋转操作。

主要有以下这几种情况。

插入元素到2节点，直接让节点变为3节点，不过当右插入时需要左旋使得红色链接在左边，如图：

插入元素到3节点，需要做旋转和颜色转换操作，如图：

也就是说，在一个已经是红色左链接的节点，插入一个新节点的状态变化如下：

根据上述的演示图以及旋转，颜色转换等操作，添加元素的代码为：

2.4. 添加元素算法分析

可参考论文： Left-leaning Red-Black Trees。

2log(n)n2-32-3log(n)2-32-3
AVL1.44log(n)AVLAVLlog(n)
log(n)

我们可以优化代码，使得在某一层旋转变色后，如果其父层没有连续的左红链接或者不需要变色，那么可以直接退出，不需要逐层判断是否需要旋转和变色。

AVLlog(n)
AVLAVL

在此，我们不再纠结两种平衡树哪种更好，因为代码实现中，两种平衡树都需要自底向上的递归操作，效率差别不大。。

2.5. 删除元素实现

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

我们创造两种操作，如果删除的节点在左子树中，可能需要进行红色左移，如果删除的节点在右子树中，可能需要进行红色右移。

我们介绍红色左移的步骤：

hhb，dh2-3
dehdhh2-3

红色左移可以总结为下图（被删除的节点在左子树，且进入的树根h一定为红节点）：

代码如下：

hh

红色右移的步骤类似，如图（被删除的节点在右子树，且进入的树根h一定为红节点）：

代码如下：

h

介绍完两种操作后，我们要明确一下到底是如何删除元素的。

2-32-3
树h树h树h

可以对照着大图，继续阅读下面的左倾红黑树删除元素代码：

tree.Find(value)

当根节点的左右子树都为黑节点时，那么先将根节点变为红节点，方便后面的红色左移或右移。

tree.Root = tree.Root.Delete(value)

核心的从子树中删除元素代码如下：

这段核心代码十分复杂，会用到红色左移和右移，当删除的元素小于根节点时，我们明白要在左子树中删除，如：

nowNode.Left = nowNode.Left.Delete(value)!IsRed(nowNode.Left) && !IsRed(nowNode.Left.Left)

如果删除的值不小于根节点，那么进入以下逻辑（可仔细阅读注释）：

IsRed(nowNode.Left)nowNode = RotateRight(nowNode)
value == nowNode.Value && nowNode.Right == nil
!IsRed(nowNode.Right) && !IsRed(nowNode.Right.Left)
value == nowNode.Value
minNode := nowNode.Right.FindMinValue()nowNode.Right = nowNode.Right.DeleteMin()
nowNode.FixUp()

如果不是删除内部节点，依然是从右子树继续递归：

FixUp()

删除操作很难理解，可以多多思考，红色左移和右移不断地递归都是为了确保删除叶子节点时，其是一个3节点。

2-3树

完整代码见最下面。

2.6. 删除元素算法分析

log(n)

2.7. 查找元素等实现

查找最小值，最大值，或者某个值，代码如下：

查找操作逻辑与通用的二叉查找树一样，并无区别。

2.8. 验证是否是一棵左倾红黑树

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

运行请看完整代码。

2.9. 完整程序

运行：

PS：我们的程序是递归程序，如果改写为非递归形式，效率和性能会更好，在此就不实现了，理解左倾红黑树添加和删除的总体思路即可。

三、应用场景

valuekey:value

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

最后，上述应用场景使用的红黑树都是普通红黑树，并不是本文所介绍的左倾红黑树。

左倾红黑树作为红黑树的一个变种，只是被设计为更容易理解而已，变种只能是变种，工程上使用得更多的还是普通红黑树，所以我们仍然需要学习普通的红黑树，请看下一章节。

系列文章入口

我是陈星星，欢迎阅读我亲自写的 数据结构和算法(Golang实现)，文章首发于

目录 · 数据结构和算法（Golang实现）​goa.lenggirl.com
  • 数据结构和算法(Golang实现)(1)简单入门Golang-前言
  • 数据结构和算法(Golang实现)(2)简单入门Golang-包、变量和函数
  • 数据结构和算法(Golang实现)(3)简单入门Golang-流程控制语句
  • 数据结构和算法(Golang实现)(4)简单入门Golang-结构体和方法
  • 数据结构和算法(Golang实现)(5)简单入门Golang-接口
  • 数据结构和算法(Golang实现)(6)简单入门Golang-并发、协程和信道
  • 数据结构和算法(Golang实现)(7)简单入门Golang-标准库
  • 数据结构和算法(Golang实现)(8.1)基础知识-前言
  • 数据结构和算法(Golang实现)(8.2)基础知识-分治法和递归
  • 数据结构和算法(Golang实现)(9)基础知识-算法复杂度及渐进符号
  • 数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
  • 数据结构和算法(Golang实现)(11)常见数据结构-前言
  • 数据结构和算法(Golang实现)(12)常见数据结构-链表
  • 数据结构和算法(Golang实现)(13)常见数据结构-可变长数组
  • 数据结构和算法(Golang实现)(14)常见数据结构-栈和队列
  • 数据结构和算法(Golang实现)(15)常见数据结构-列表
  • 数据结构和算法(Golang实现)(16)常见数据结构-字典
  • 数据结构和算法(Golang实现)(17)常见数据结构-树
  • 数据结构和算法(Golang实现)(18)排序算法-前言
  • 数据结构和算法(Golang实现)(19)排序算法-冒泡排序
  • 数据结构和算法(Golang实现)(20)排序算法-选择排序
  • 数据结构和算法(Golang实现)(21)排序算法-插入排序
  • 数据结构和算法(Golang实现)(22)排序算法-希尔排序
  • 数据结构和算法(Golang实现)(23)排序算法-归并排序
  • 数据结构和算法(Golang实现)(24)排序算法-优先队列及堆排序
  • 数据结构和算法(Golang实现)(25)排序算法-快速排序
  • 数据结构和算法(Golang实现)(26)查找算法-哈希表
  • 数据结构和算法(Golang实现)(27)查找算法-二叉查找树
  • 数据结构和算法(Golang实现)(28)查找算法-AVL树
  • 数据结构和算法(Golang实现)(29)查找算法-2-3树和左倾红黑树
  • 数据结构和算法(Golang实现)(30)查找算法-2-3-4树和普通红黑树