AnthonyZero's Bolg

数据结构-红黑树(元素插入小结)

发表于 | 分类于

介绍

红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。

它的综合性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。比如在 Java 集合框架中，很多部分(HashMap, TreeMap, TreeSet 等)都有红黑树的应用，这些集合均提供了很好的性能。

rbtree.png

红黑树与AVL树不同，严格来说不是平衡二叉树没要求每个节点的左右节点的高度差值不超过1，红黑树是保持”黑平衡”的二叉树。

性质

首先红黑树是二叉搜索树，所以它满足二叉搜索树性质，除此之外红黑树还有下面5个性质：

  1. 节点是红色或黑色
  2. 根节点是黑色
  3. 每个叶子节点都是NIL，并且是黑色的
  4. 每个红色节点的两个子节点都是黑色(从根到每个叶子所有路径上不能有两个连续的红色节点)
  5. 从任意一节点到它的每个叶子节点的所有简单路径上都包含相同数目的黑色节点

2-3-4 树

说到红黑树，就不得不提 2-3-4 树，因为，红黑树可以说就是它的一种特殊实现，对它有所了解，非常有助于理解红黑树。保持平衡，无非是为了降低树的高度，如果把二叉查找树一般化，允许一个结点保存多个值，变成多叉树，也可认为是降低了高度。

确切地说，标准二叉查找树中的结点称为2-结点（一个值两个子结点），现在引入3-结点（两个值三个子结点）和4-结点（三个值四个子结点），这样就能得到一颗 2-3-4 树（也称为 2-4 树）。
rbtree2.png

2-3-4 树是 4 阶 B 树，所有数据按排序顺序保存，所有叶子结点都在相同的深度。对于大多数编程语言，直接实现 2-3-4 树比较困难，而红黑树的实现相对要简单容易，这也是红黑树应用广泛的一部分原因
rbtree3.png

红黑树是二叉树，所有的结点都是2-结点，所以为了能够表示3-结点和4-结点，为结点引入了颜色属性：

  • 黑色，表示普通结点
  • 红色，表示可与父结点合并看作多值结点

如上图所示，如果把红黑树的红色结点和其父结点放平，它的结构就和左边的 2-3-4 树一样。

通过引入了2-3-4树，再来看红黑树的性质4,5就能很好理解了。

  1. 红色表示可与父结点合并，不可能连续一条路上存在两个红色节点所以性质4就说了红色节点左右必须是黑色节点
  2. 把红黑树看成一个2-3-4树，因为它是绝对平衡的，从给定结点到其任何后代 NIL 结点的每条路径，经过的层数高度相同，每经过一层不论是2节点还是3节点或者4节点都有一个黑色代表。

树旋转

树旋转是二叉树中调整子树的一种操作，常用于调整树的局部平衡性，它包含两种方式，左旋转和右旋转。跟上文AVL树左右旋转一样的操作。
rbtree.gif rbtree2.gif

红黑树的旋转其实就是为了确保和其结构相同的 2-3-4 树的一一对应关系，同时保证红黑树的有序性和平衡性。

红黑树的平衡插入

对于2-4 树的插入逻辑是这样的（在 2-4 树中，待插入结点都认为可以插入到一个多值结点中）：

  • 如果是 2-结点，直接插入变成 3-结点
  • 如果是 3-结点，直接插入变成 4-结点
  • 如果是 4-结点，首先进行分裂，变成 2-结点，再插入

对照2-4树，红黑树插入的结点都是红色的，红黑树的插入主要分两步：

  • 首先和二叉查找树的插入一样，查找、插入
  • 然后调整结构，保证满足红黑树状态:对树进行相关的旋转操作;对结点进行重新着色

假设待插入结点为 N，P 是 N 的父结点，G 是 N 的祖父结点，U 是 N 的叔叔结点（即父结点的兄弟结点），那么红黑树有以下几种插入情况：

  1. N 是根结点，即红黑树的第一个结点
  2. N 的父结点（P）为黑色
  3. P 是红色的（不是根结点），它的兄弟结点 U 也是红色的
  4. P 为红色，而 U 为黑色，或者NIL(也是黑色)

情况1

当前待插入节点N位于根,它没有父节点与子节点,这时候只需要把它重新设置为黑色即可,无需其他调整. 相当于建立一个根结点为黑色的标准 2-结点

情况2

父节点P是黑色
rbtree4.png
这时候如果P是黑色的，那么插入一个节点就是一个 2-结点->3-结点->4-结点转换的过程，不会打破平衡，直接插入即可。如上图10插入9和20两个元素。

父节点是黑色，不管父亲有没有兄弟节点，待插入节点红色不管值是该放在左边还是右边都可以跟父亲融合形成3节点，无需任何操作

情况3

父节点P是红色，存在它的兄弟节点U是红色的
6.png
如果P与U都为红色,我们可以将它们两个重新绘制为黑色,然后将G绘制为红色(保持性质5),最后再从G开始继续向上进行调整.比如继续插入元素2

情况4

父节点P是红色，存在它的兄弟节点U是黑色或者NIL（黑色）

分别有以下四种可能：

  • P 是 G 的左孩子，若 N 是 P 的左孩子，那么将祖父结点 G 右旋转 即可
  • P 是 G 的左孩子，若 N 是 P 的右孩子，那么 P 先左旋转，然后再将祖父结点 G 右旋转
    如下图2是9的左孩子，3（待插节点）是2的右孩子，（2的兄弟是NIL黑色）

相反的：

  • P 是 G 的右孩子，若 N 是 P 的右孩子，那么将祖父结点 G 左旋转 即可
  • P 是 G 的右孩子，若 N 是 P 的左孩子，那么 P 先右旋转，然后再将祖父结点 G 左旋转

5.png

总结

这里引入2-3-4树并总结了红黑树的元素插入情况：红黑树比较复杂，单纯的分析性质和旋转，意义不大，而 2-3-4 树就不一样了，它的插入和删除简单多了，而红黑树的旋转和变色最终也是为了和同构的 2-3-4 树保持一致。

红黑树可视化