Java 数据结构 - 红黑树：为什么工程中使用的平衡二叉查找树都是红黑树？

数据结构与算法目录(https://www.cnblogs.com/binarylei/p/10115867.html)

1. 平衡二叉查找树

平衡二叉树：二叉树中任意一个节点的左右子树的高度相差不能大于 1。

从这个定义来看，完全二叉树、满二叉树其实都是平衡二叉树。常用的平衡二叉查找树的实现有两种：

• AVL 树：最先被发明的平衡二叉查找树，它严格符合我刚讲到的平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树。

• 红黑树(Red-Black Tree)：它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。红黑树是一种不严格的平衡二叉树。

平衡二叉查找树中 "平衡" 的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。所以，只要树的高度不比 logn 大很多，查找的效率就不会降低很多，都是可以接收的。

2. 红黑树

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

• 性质1：节点是红色或黑色。
• 性质2：根节点是黑色。
• 性质3：每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
• 性质4：每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 性质5：从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树每次插入的节点颜色预设为红色，插入后，有可能会导致以上性质不满足，然后进行结点调整。红黑树之所以定义上述严格的特性，目的就是为了确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接*衡的二叉树。

• (01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
  
  (02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接*衡的二叉树。

2.1 时间复杂度

我们知道二叉查找树的时间复杂度是 O(height)，和树的高度息息相关，如果是平衡二叉树则是 O(logn)，如果退化为链表则为 O(n)。所以分析红黑树的时间复杂度，关键是分析红黑树的高度。

我们首先只考虑黑色结点，分析出所有黑色结点的高度。

• 性质 3 规定，每个叶子节点都是黑色的空节点红黑树。也就是说，非叶子结点都有两个子结点。
• 性质 5 中规定，从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。也就是说，所有的黑色高度都相同。
• 如果只考虑黑色结点，所有的非叶子结点都有两个子结点，且高度相同。此时相当于一棵满二叉树的高度，黑色结点的高度为 logn。
• 此时，我们将红色结点加上。性质 4 规定，不能有两个连续的红色结点。也就说即便最坏的情况，红色结点和黑色结点的高度一样。此时，红黑树的高度也不会大于 2logn。
• 所以，由于红黑树的高度最大为 2logn，因此其时间复杂度为 O(logn)。

2.2 实现自己的红黑树

...

---

每天用心记录一点点。内容也许不重要，但习惯很重要！