红黑树

红黑树

一、为什么会出现红黑树

因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。

于是出现了平衡二叉树，可以看我之前写的博客：

平衡二叉树保证了在最差的情况下，二叉树依然能够保持绝对的平衡，即左右两个子树的高度差的绝对值不超过1。但是这又会带来一个问题，那就是平衡二叉树的定义过于严格，导致每次插入或者删除一个元素之后，都要去维护二叉树整体的平衡，这样产生额外的代价又太大了。二叉搜索树可能退化成链表，而平衡二叉树维护平衡的代价开销又太大了，那怎么办呢？这就要谈到“中庸之道”的智慧了。说白了就是把平衡的定义适当放宽，不那么严格，这样二叉树既不会退化成链表，维护平衡的开销也可以接受。没错，这就是我们要谈的红黑树了。

二、什么是红黑树

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须除了满足二叉搜索树的性质外，还要满足下面的性质：

每个节点要么是黑色，要么是红色。根节点是黑色。每个叶子节点是黑色。每个红色结点的两个子结点一定都是黑色。任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。

三、插入的过程

1、按照搜索树的特征进行插入

2、插入的时候有意识的碰瓷是红色不能相邻这个特征（即插入的为 红色节点）

3、随着插入的完成

插入的节点是根节点，把颜色改为黑色插入的节点的父节点是黑节点，插入完成插入接节点的父节点为红色，破坏了红色节点不能相邻的原则，需要修复

4、插入完成，结果也是一颗红黑树

四、破坏怎么修复

已知条件：新插入节点（cur）是红色。cur 的父节点（parent）是红色

推导出结论：cur 的祖父节点-- 父亲的父亲（grandpa）一定是黑色

​ 因为，如果grandpa 为红色，则parent 和 grandpa 都是红色，已经不再是红黑树了。

1、情况一

1、uncle是存在的，且颜色为红色，即为下图： grandpa + parent/uncle 代表的是两条路径，在这两条路径上，各自提供了1个黑色

修复规则：任然保证这两条路径上只有一个黑色

即：grandpa：黑 -> 红

​ parent/uncle：红 -> 黑

然后再考虑 grandpa 和它的父节点问题

cur = grandpa

parent = cur.parent

grandpa = parent.parent

按照同样的规则进行检查，直到 根 or 满足条件

修改后的样子：

2、情况2

情况2：uncle 不存在或者 uncle 存在，颜色为黑色

情况2.1、cur 是 parent 左边，并且 parent 是 grandpa 左边（两个顺边）

修复方式：

对 parent 进行右旋

parent：红 -> 黑

grandpa：黑 -> 红 所有路径只有一个黑色

---

四条路径，黑色颜色不一样多，所以 parent 之前一定右子树，并且两边子树至少有一层黑色

修复后：

情况2.2、cur 是 parent 右边，并且 parent 是 grandpa 右边（两个顺边）

修复方式：

对 parent 进行左旋

parent：红 -> 黑

grandpa：黑 -> 红

情况2.3、cur 是 parent 右边，并且 parent 是 grandpa 左边（不顺边）

修复方法：

对 parent 进行 右旋

原来的cur 视为 parent

原来的parent 视为 cur

得到如下： 然后再按照2.1处理

情况2.4、cur 是 parent 左边，并且 parent 是 grandpa 右边（不顺边）

同2.3

---

最后，把根节点同一改为 黑色

五、用途

红黑树 和 AVL 树适用范围是重叠的，都是 二叉平衡搜索树，都适合内存级别的数据查找问题

用途：

jdk/c++/linux 中都比较偏向使用红黑树

Windows 偏向使用 AVL树

Java 中使用红黑树的地方

1、TreeMap/TreeSet

2、HashMap如果发生冲突太严重，用红黑树代替链表