Ricky.L的随笔
0%

红黑树、AVL树

发表于 更新于 分类于 Disqus：

普通的二叉查找树存在什么问题？平衡二叉查找树解决了什么问题？

普通的二叉查找树最坏情况下会退化为一个链表，查找元素的时间复杂度由log_2{n}退化到n。

解决时间复杂度退化，就是要让树的高度始终保持尽可能的小，平衡二叉查找树就是让任意节点的左右子树高度都平衡（差的不多）的二叉查找树，这样查找元素的平均时间复杂度可以保持在log_2{n}，

有哪些平衡二叉查找树？

AVL树、2-3树、红黑树

为什么流行的主要是这几个树？

因为逻辑比较简单，易于实现，效率也就高。

AVL树特点

任意结点左右子树高度差小于或等于1。

由Adelson-Velskii 以及 Landis发明，故而叫AVL。

2-3树

定义：

  • 在满足二叉查找树的性质基础上，一个结点最多可以存储2个键，可以有3个孩子结点。
  • 2结点里存储1个键，可以有2个孩子结点
  • 3结点里存储2个键，可以有3个孩子结点

特点

  • 2-3树是完美平衡的，任意结点的左右子树高度相等，这可以分析所有插入的情况来证明。

自下而上生长：

  • 插入位置在2结点中，直接插入，变为3结点。
  • 插入位置在3结点中，先插入键变成4结点，再把中间的键提升到父结点中，当前结点就变成了两个2结点（不直接把键插入父结点是因为插入的键和提升到父结点的键不一定是同一个）。
    • 如果父结点本来是2结点，现在就变成了3结点。
    • 如果父结点本来是3结点，现在就变成了4结点，继续提升的过程。
    • 如果没有父结点，当前即为根结点，那么就把临时的4结点分解为3个2结点，中间的键提升为2结点作为新的根结点。

在根结点为3结点时，插入新键变为4结点，再拆分为3个2结点后，树的高度才会加1。

一颗含有n个节点的2-3树的高度在log_3{n}（全是3结点）到log_2{n}（全是2结点）之间。

每次插入后调整结点都是局部的，最坏情况下，一条路径上都是3结点，从叶结点插入新键后，会从叶结点一直调整到根结点，调整次数不会超过对数级别。

10亿个结点的2-3树高度仅在19到30之间，性能较高。

各种操作实现较为复杂。

为什么2-3树可以保持完美平衡？

这可以分析所有插入的情况来证明。

自下而上生长

  1. 插入位置在2结点中，直接插入，变为3结点

  2. 插入位置在3结点中，先插入键变成4结点，再把中间的键提升到父结点中，当前结点就变成了两个2结点（不直接把键插入父结点是因为插入的键和提升到父结点的键不一定是同一个）

  3. 如果父结点本来是2结点，现在就变成了3结点

  4. 如果父结点本来是3结点，现在就变成了4结点，继续提升的过程

  5. 如果没有父结点，当前即为根结点，那么就把临时的4结点分解为3个2结点，中间的键提升为2结点作为新的根结点

在根结点为3结点时，插入新键变为4结点，再拆分为3个2结点后，树的高度才会加1

红黑树

实现较为简单，综合性能好。

把2-3树的3结点表示为左斜的红色链接相连的两个2结点，其中一个结点是另一个结点的左子结点，其他链接为黑色链接。

红黑树既是二叉查找树也是2-3树。

等价定义（《算法》第4版 275页 3.3.2.1）：

  1. 红色链接均为左链接
  2. 没有任何一个结点同时和两条红链接相连
  3. 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同

红黑树的几条定义都是为了让红黑树满足2-3树的结构。

如果让2-3树中所有链接都为黑色，由于2-3树是完美平衡的，红黑树中红色链接代表3结点，所以红黑树中的黑色链接是完美平衡的。

再把2-3树中的3结点都分解为两个用红色链接相连的2结点，那么不会存在一个结点同时与两条红色链接相连，这一点保证了红色链接是3结点。

对红黑树插入、删除元素后，不满足红黑树的定义，都要通过旋转操作来修正。

红黑树的旋转操作修正，都是符合2-3树的修正的规则的，理解记住了2-3树的各种调整规则，就知道了红黑树各种操作的意义。

红黑树是怎么发明出来的？

它在1972年由鲁道夫·贝尔发明，被称为”对称二叉B树”，它现代的名字源于Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文。

红黑树等同于2-3-4树，是2-3-4树的二叉表现形式。

2-3-4树是B树的一种情况。

红黑树结点的颜色表明了当前结点是否属于2-3-4树中的3结点或4结点。

2-3-4树的情况讨论比较复杂， 用2-3树讨论情况较少，可以方便理解。

红黑树定义

《算法》第4版 275页 3.3.2.1 定义：

  1. 红色链接均为左链接
  2. 没有任何一个结点同时和两条红链接相连
  3. 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同

《算法导论》273页 第13章 红黑树 定义：

  1. 节点是红色或黑色
  2. 根节点是黑色
  3. 叶节点是黑色
  4. 红节点的两个子节点都是黑色
  5. 任意节点到叶节点的所有路径上的黑色节点数相同

红黑树为什么要这样定义？

红黑树的几条定义都是为了让红黑树满足2-3树的结构，红黑树是2-3树的一种表示形式，而2-3树是完美平衡的，这样红黑树也是黑色平衡的，2-3树比较难以实现，红黑树比较方便实现。

为什么要用红黑树表示2-3树？

  • 因为2-3树是完美平衡的，任意结点的子树没有高度差。
  • 2-3树的实现较为复杂，红黑树的实现较为简单。

红黑树的数据结构如何定义？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 树的结点
 */
data class Node<Key : Comparable<Key>, Value>(
        /**
         * 父结点指向本结点的链接颜色，用以标明本结点对应2-3树中的2结点还是3结点
         */
        var color: Color,
        /**
         * 关键字。用于比较来确定数据的顺序
         */
        val key: Key,
        /**
         * 关联的数据
         */
        var value: Value,
        /**
         * 左子结点
         */
        var left: Node<Key, Value>? = null,
        /**
         * 右子结点
         */
        var right: Node<Key, Value>? = null
)

/**
 * 链接颜色
 */
enum class Color {
    BLACK, RED
}

红黑树插入新元素后调整结点的操作规则是怎样的？

原则：所有操作跟2-3树能逐一对应，保证树的有序性和完美平衡性。

插入新结点先按普通的二叉查找树插入新结点那样进行插入。

普通的二叉查找树插入新元素有三种情况：

  1. 树中没有结点，插入的新结点作为根结点
  2. 树中有结点，插入的新结点一定是某个结点h的左子结点
  3. 树中有结点，插入的新结点一定是某个结点h的右子结点

在红黑树中，结点h又可以分为两种情况

  1. 结点h是2结点
  2. 结点h位于3结点中
    1. 结点h是红链接左下的结点
    2. 结点h是红链接右上的结点

插入新结点要默认新结点的颜色是红色，表示新结点到父节点的链接是红色，这样与2-3树的插入就可以对应上。

在2-3树中如果插入在2结点中，2结点变为3结点，就不再调整；如果插入的在3结点中，3结点临时变为4结点，再把4结点的中间键放入父结点中，左右两边的键分解为两个2结点与父结点相连。

处理这些情况的组合，就是所有的插入情况，针对不符合2-3树的结构的情况进行调整。

  • 结点h是2结点
    • 新结点是h的左子结点，相当于新结点和结点h组成了2-3树中的3结点，符合2-3树的结构，无需调整
    • 新结点是h的右子结点，相当于新结点和结点h组成了2-3树中的3结点，但我们规定红链接要保持左斜，以减少考虑的情况数量，所以要进行左旋转
  • 结点h位于3结点中，新结点的位置有三种情况：左、中、右
    • 结点h是红链接左下的结点
      • 新结点是h的左子结点，此时有了两条连续的红链接，连接的3个结点对应2-3树中临时的4结点，需要把中间的键放入父结点，再把两边的键拆为两个2结点分别与父结点相连，所以操作是先右旋，再变换颜色
      • 新结点是h的右子结点
    • 结点h是红链接右上的结点
      • 新结点是h的右子结点

有三种标准操作：左旋、右旋、颜色转换

为什么红黑树中红链接只能保持左斜？为什么不能有右斜的红链接？

只允许红色的左链接可以减少讨论的情景数量，进而简化代码的实现。

红黑树最坏情况下高度是多少？

有n个结点的红黑树高度最多为 $2 * log_2{n}$

由于2-3树中的3结点是由左斜红链接连接的两个结点表示的，最坏情况下最左侧路径全部都是红链接，对应2-3树中最左侧都是3结点，其他结点都是2结点。

参考《算法导论》中的证明：
红黑树相关定理及其证明

红黑树的各种操作的时间复杂度是多少？

设红黑树有n个结点，查找、插入、修改、删除操作的时间复杂度均为O(log n)

查找：

  • 最长路径长度不会超过最短路径长度的2倍，查找仍然是对数级别

插入：

  • 最坏情况下待插入的位置在叶结点，需要从根结点遍历到叶结点，同时最坏情况下遍历的路径都是红链接（路径上都是3结点），此时会从叶结点一直回溯调整结点到根结点，访问次数是2倍的树的高度，而树的高度为log_2{n}

红黑树较于AVL树有什么优点？

单次操作：

  • 单次插入数据，红黑树和AVL树平均都只需要几次旋转即可完成。
  • 单次删除元素，红黑树大多数只需要几次旋转调整，AVL树需要调整查找路径上所有结点。

大量的插入和删除操作：

  • 红黑树由于是基于2-3树，3结点的存在可以吸纳一部分不平衡性，不用做频繁的旋转调整。
  • AVL树需要始终保持平衡，在大量插入或删除元素后，AVL树的调整的次数多于红黑树。

在大量数据的统计意义上，红黑树的插入和删除次数相对于AVL树较少，适合插入和删除频繁的场景。

AVL树由于是高度平衡的，红黑树不是高度平衡，AVL树的查找次数比红黑树更少，适合对查询效率非常敏感，插入和删除不频繁的场景。

红黑树的查询跟AVL树仍然是同一个数量级，所以综合查询、插入、删除的性能，红黑树表现较好。

参考：

什么时候用AVL树？

AVL树平衡性非常好，左右子树高度差不超过1，所以查找次数少。

对于查找非常频繁，插入、修改、删除不频繁的场景，可以使用AVL树。

并发下的问题

并发情况下，由于平衡搜索树的调整可能要锁整个树。

用跳表这种性能接近于平衡树的数据结构，操作更加局部性，不会锁住太多结点，有利于并发的性能。

参考资料