数据结构之「红黑树」

红黑树

红黑树（Red–black tree）是一种自平衡二叉查找树。红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。
红黑树的特性：
1.节点要么是红色要么就是黑色，不能没有颜色。
2.根节点是黑色的。
3.所有叶子节点都是黑色的。
4.每个红色节点必须有两个黑色的子节点。
5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

红黑树

从根节点到叶子节点的最长路径不会超过最短路径的 2 倍，所以它对查找、删除和新增的最差时间复杂度为 O(log n)，且叶子上没有数据存储。

红黑树的实现

在 AVL树 插入中，插入后导致不平衡，我们使用旋转来保证它的平衡性。在红黑树中，我们使用 重新着色 和 旋转 来进行平衡。
首先，我们尝试重新着色，如果重新着色满足不了红黑树的特性，那么我们就进行旋转。

插入算法主要有两种情况，取决于叔叔节点的颜色。如果叔叔节点是红色的，就进行重新着色。如果叔叔节点是黑色的，就要进行旋转和（或）重新着色操作。

左旋和右旋请先参考《数据结构之「AVL树」》。

新添加的节点设置为红色。如果设为黑色，就会导致根到叶子节点的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过重新着色和树旋转来调整。

假如新插入的节点为 x：
1.按标准的二叉搜索树插入节点颜色为红色的新节点。

2.假如 x 就是根节点，那么改变 x 节点颜色为黑色。

3.如果新节点的父节点是黑色的，直接返回。

4.如果父节点和叔叔节点都是红色的，需要改变父节点和叔叔节点的颜色为黑色，并设置祖父节点为红色，如果祖父节点为根节点，设置祖父节点颜色为黑色。

5.如果父节点是红色而叔叔节点是黑色或缺少，新节点是父节点的左子节点，而父节点又是其父节点的左子节点。这种情况就需要对祖父节点进行一次右旋，然后在切换父节点和祖父节点的颜色，就满足红黑树的性质了。

6.如果父节点是红色，而叔叔节点是黑色或缺少，并且新节点是其父节点的右子节点而父节点又是其父节点的左子节点。需要先对当前节点节点进行左旋，变成 情形5，然后按 情形5 的步骤操作来。

总结

与 AVL树 相比，AVL树 更加平衡，但它可能在插入和删除期间引
起更多旋转。因此，如果频繁的插入和删除操作，那么应该首选红黑树。如果插入和删除频率较低且搜索是更频繁的操作，那么AVL树应优先于红黑树。

红黑树牺牲了部分平衡性以换取插入/删除操作时做少量的旋转操作，整体来说性能要优于AVL树。

在 JDK 中，都是用红黑树来做 TreeSet 和 TreeMap 的数据结构存储，在 JDK1.8之后都是用红黑树来存储哈希冲突大于等于八个节点的数据结构，所以红黑树还是一种比较常用的数据结构。

PS:
清山绿水始于尘，博学多识贵于勤。
我有酒，你有故事吗？
公众号：「清尘闲聊」。
欢迎一起谈天说地，聊代码。