红黑树(Red Black Tree)

2023-09-15 14:29 由 coffee_baby 发表于 #其他

红黑树(Red Black Tree)

红黑树（Red Black Tree）是一种自平衡二叉查找树，是一种高效的查找树，学习之前先了解一下平衡二叉树。于 1972 年由 Rudolf Bayer发明的对称二叉B 树演化而来，并以 2-3-4 树、2-3 树流行。最终在 1978 年由Leonidas J.Guibas 和 Robert Sedgewick 从对称二叉 B 树中推导出红黑树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作

建立在 BST 二叉搜索树的基础上，AVL、2-3 树、红黑树都是自平衡二叉树，红黑树每个节点增加了一个存储位，用来记录节点的颜色，RED或者BLACK 。但相比于 AVL ，高度平衡所带来的时间复杂度，红黑树对平衡的控制要宽松一些，红黑树只需要保证黑色节点平衡即可。也正因红黑树在插入和删除时不需要太多的平衡操作，也让它成为 Java 中 HashMap 底层的数据结构、Linux 的 CFS 进行调度算法、多路复用技术的 Epoll 等各类底层的数据结构实现。

实际上，在红黑树中真正被定义为叶子结点的，是那些空节点，如上图

五大性质

性质1：每个节点要么是红色，要么是黑色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL节点或null）都是黑色。
性质4：如果一个节点是红色的，则它的两个子节点都是黑色。也就是说，不能有两个连续的红色节点。
性质5：对于每个节点，从该节点到其所有后代叶子节点的简单路径上，包含相同数量的黑色节点。

红黑树保证最长路径不超过最短路径的二倍，因而近似平衡（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）

2-3树

理解红黑树之前要先了解一下2-3树，因为它们都是依靠旋转进行调衡树高的，上面讲的五条性质，就是根据2-3树演变而来的，不然没有原因，来的就有些突然。

2-3 树是一种树型数据结构，由约翰·霍普克洛夫特于 1970 年发明。它通过在个节点存放 1-2个元素来平衡树高。从而也使 2-3 树存在2 叉节点和3 叉节点

其中每个具有子节点（内部节点）的节点要么有两个子节点（2 节点）和一个数据元素，要么有三个子节点（3 节点）和两个数据元素。另外 2-3 树是 3 阶 B 树，2-3-4 树是 4 阶 B 树。

在 2-3 树中顺序插入 1、2、3、4、5、6、7，七个元素时，2-3 树的调衡处理

2-3 树的插入过程与 BST 树类似，会通过树的左右节点大小，找到自己的插入位置
一个节点可以有 1-3 个元素，但当元素个数为 3 时，则需要调衡。把三个节点的中间节点晋升上来，其余两个节点为子节点。
如果进行一次调衡后，上一层父节点达到 3 个元素，则需要 2 次调，来满足 2-3树的规则。

拆分节点

当一个节点内有 3 个元素的时候，就要发起拆分东西，拆分的过程分为;

对 3 个节点的中间节点，插入到父节点上
剩余 2 个节点创建出新的节点。
建立父节点和新创建的 2 个节点间关系

2-3树和红黑树的关系

上面这颗红黑树，我们来将所有的红色节点上移到和他们的父节点同一高度上，就会形成如下结构

这个结构很明显，就是一棵四阶B树

红黑树和 4阶B树（2-3-4树）具有等价性
黑色节点与它的红色子节点融合在一起，形成1个B树节点
红黑树的黑色节点个数与 4阶B树的节点总个数相等
在所有的B树节点中，永远是黑色节点是父节点，红色节点是子节点。黑色节点在中间，红色节点在两边。

操作

这里就不做过多讲解插入和删除的具体细节，感兴趣的可以去看看CSDN上的一篇文章，是结合2-3树进行介绍的；还有简书上一篇穷举了红黑树插入和删除的各种细节。什么情况下需要染色，什么情况下需要旋转还是很有必要知道的，这篇文章就从这里讲起

左倾染色

新增节点 1，相当于 2-3 树中在节点 2 上添加了一个节点，这个时候并不影响树高，只需要染色保持红黑树的规则即可。染色过程如图所示。

新增节点1，父亲节点和叔叔节点都是红色
把父节点染黑、叔叔节点染黑，爷爷节点染红
爷爷节点染红是临时的，这时候试想爷爷节点是根节点，不满足性质2，又会把爷爷节点染黑

右倾染色

新增节点 4，相当于 2-3 树中在节点 3 上添加了一个节点，这个时候并不影响树高，只需要染色保持红黑树的规则即可。染色过程如图所示。

1.和上面的左旋染色过程一样，只是方向变了

左旋调衡

对照 2-3 树，只有当一个节点内有 3 个节点的时候，才需要调衡。那么红黑树则是判断当前节点的叔叔节点是否为红色节点，如果不是则没法通过染色调衡，也

就是需要选择进行调衡

1 左旋一次

这种情况属于插入节点的父节点是红色，但叔叔节点是黑色或空（NIL）需要进行 染色 + 左旋 操作来修复平衡

当你把红黑树对照理解成 2-3 树，如图中第 1 步骤下的左侧小图，新增的节点 5 倒置 2-3 树不平衡
那么这个时候需要把 2-3 树中节点 4 提起来，而对应红黑树则需要先进行染色，待操作的节点 4 为黑色，两个孩子节点为红色。
最后是把节点 3 进行一次左旋操作，完成树的平衡。对应步骤 3 中的左侧小图是 2-3树调衡后的结果

2 右旋 + 左旋

当一次左旋没法调衡，需要右旋+左旋的情况，在 AVL 树中有同样的场景。本身树需要左旋操作，但整体分支树节点偏左，此时需要右旋调整树结构再左旋。可以参考平衡二叉树中的旋转

红黑树新增节点 4 以后，4→5 结构偏左，需要先进行右旋调衡树结构，再进行左旋。

其实这个时候再进行的左旋就和上面一次左旋操作一致了

右旋调衡

1 一次右旋

对照 2-3 树，只有当一个节点内有 3 个节点的时候，才需要调衡。那么红黑树则是判断当前节点的叔叔节点是否为红色节点，如果不是则没法通过染色调衡，也就是需要选择进行调衡。

当你把红黑树对照理解成 2-3 树，如图中第 1 步骤下的右侧小图，新增的节点 1 倒置 2-3 树不平衡。
那么这个时候需要把 2-3 树中节点 2 提起来，而对应红黑树则需要先进行染色，待操作的节点 2 为黑色，两个孩子节点为红色。
最后是把节点 2 进行一次右旋操作，完成树的平衡。对应步骤 3 中的右侧小图是 2-3树调衡后的结果。

2 左旋 + 右旋

当一次左旋没法调衡，需要左旋+右旋的情况，在 AVL 树中有同样的场景。本身树需要右旋操作，但整体分支树节点偏右，此时需要左旋调整树结构再右旋。

红黑树新增节点 2 以后，1↘2 结构偏右，需要先进行左旋调衡树结构，再进行右旋。其实这个时候再进行的右旋就和上面一次右旋操作一致了。

总结

红黑树相对于普通的二叉搜索树（BST）具有自平衡性，这意味着它在插入和删除操作后会自动进行调整以保持平衡。这种自平衡性赋予了红黑树在特定应用中一些重要的优势，使其更适合解决某些问题。以下是红黑树相对于普通BST的一些用途和优势：

平衡性保证：红黑树的平衡性确保了树的高度保持在较低水平，使得各种操作的平均时间复杂度为O(log n)，这包括插入、删除和查找操作。在高度平衡的情况下，红黑树能够提供可靠的性能。
插入和删除操作高效：由于红黑树能够自动调整以保持平衡，插入和删除节点的操作通常具有可接受的性能。这对于需要频繁更新数据的应用非常有用，如数据库系统。
范围查询：红黑树非常适合范围查询，因为它们具有排序性质，可以轻松找到在某一范围内的所有节点。这在数据库查询和文件系统中很有用。
多线程和并发：由于红黑树的自平衡性和性质保证，它们在多线程环境中表现出色。在并发数据结构中，红黑树通常用于实现各种同步机制，如锁、队列等。
内存分配：在某些操作系统和编程语言中，红黑树用于内存分配算法，例如Linux的slab allocator就使用了红黑树来管理内存块。
文件系统：许多文件系统使用红黑树来维护文件和目录的结构，以提供高效的文件查找和管理。
数据库系统：数据库系统中的索引通常使用红黑树来加速数据查找操作。例如，许多关系型数据库管理系统（RDBMS）使用B+树（一种变种的红黑树）来管理索引。
图算法：红黑树的结构可以用于一些图算法，如最短路径算法，以提高效率。

平衡二叉树和红黑树的区别

平衡性维护：
- 红黑树：在红黑树中，平衡性是通过节点的颜色属性来维护的，通过染色和旋转操作来确保平衡性。这使得红黑树对于插入和删除操作有一定的灵活性，可能会导致树的高度相对较高。
- AVL树：AVL树是一种更为严格的平衡二叉搜索树，它通过节点的平衡因子（左子树高度减去右子树高度）来维护平衡性。AVL树的平衡要求更为严格，插入和删除操作会更频繁地导致树的旋转操作，以维持平衡，因此树的高度相对较低，查询操作更快。
性能差异：
- 红黑树：由于其相对较宽松的平衡性要求，红黑树在插入和删除操作上比AVL树更高效，但查询操作可能会略微慢一些，因为红黑树的高度相对较高。
- AVL树：AVL树在查询操作上非常高效，因为它的高度非常平衡，但在插入和删除操作上更耗时，因为它需要频繁地进行旋转操作。
适用场景：
- 红黑树：适用于需要频繁执行插入和删除操作，而对查询性能要求较低的场景。例如，文件系统、数据库索引、内存分配算法等。
- AVL树：适用于需要快速查询操作，并且能够承受较慢的插入和删除操作的场景。例如，编译器中的符号表、排序算法、高频查询数据库等。
内存消耗：
- 红黑树：通常比AVL树具有较低的内存消耗，因为红黑树的平衡要求相对较宽松，节点不需要存储额外的平衡因子。
- AVL树：由于需要存储平衡因子，AVL树的节点可能会占用更多的内存空间。

总之，红黑树在需要高效的插入、删除和查找操作，并且需要保持平衡性的场景下非常有用。它们在计算机科学和软件工程中有广泛的应用，尤其是在需要高性能和可靠性的领域。然而，需要注意的是，红黑树并不适用于所有情况，有时其他数据结构如哈希表或AVL树可能更适合特定的需求。选择合适的数据结构应根据具体的应用场景和性能需求来决定。
本文并没有使用代码实现红黑树，JDK中TreeMap的源码实现的更为优秀，兼顾各个方面，感兴趣的可以看看😁