红⿊树：自平衡二叉查找树的数据结构

"红⿊树（Red–black tree）是计算机科学中的一种自平衡二叉查找树，用于实现关联数组，由鲁道夫·贝尔在1972年发明，后由利奧尼达斯·J·吉巴斯和罗伯特·塞奇威克在1978年的论文中进一步阐述。这种数据结构复杂但性能优秀，可以在O(log n)时间内完成查找、插入和删除操作。红黑树是2-3-4树的一种等价表示，其插入和删除操作可以通过颜色翻转和旋转来实现。" 红黑树是自平衡二叉查找树的一种实现，它的设计目标是在保持良好查询性能的同时，通过特定的规则来自动调整树的结构，以减缓插入和删除操作导致的不平衡。红黑树的节点有两种颜色：红色或黑色，这些颜色被用来维持树的平衡。以下是红黑树的一些关键特性： 1. **颜色规则**： - 根节点必须是黑色。 - 所有叶子节点（NIL或空节点）必须是黑色。 - 如果一个节点是红色，则其两个子节点必须是黑色。 - 对每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数量的黑色节点。 2. **性质**： - 红黑树的最大高度是log₂(2n+1)，其中n是节点总数，保证了高效的查找、插入和删除操作。 - 插入和删除操作可能导致树的不平衡，通过颜色翻转（红色节点变为黑色，黑色节点变为红色）和旋转（左旋或右旋）来恢复平衡。 3. **操作**： - **查找**：遵循二叉查找树的性质，从根节点开始，根据节点值进行比较，时间复杂度为O(log n)。 - **插入**：在红黑树中插入新节点时，可能会破坏颜色规则，需要通过旋转和重新着色来保持平衡，总体时间复杂度仍为O(log n)。 - **删除**：删除节点可能更复杂，因为需要考虑多种情况，包括删除黑色节点、红色节点、叶节点等，同样需要通过旋转和重新着色来维护平衡。 4. **2-3-4树与红黑树**： - 2-3-4树是一种内部节点可以有2、3或4个子节点的树，红黑树是其颜色编码的等价表示。在2-3-4树上进行插入和删除的转换可以直接映射到红黑树的颜色翻转和旋转操作。 - 2-3-4树更容易直观地理解平衡概念，但在实际应用中，红黑树由于其颜色规则更简洁，通常更受欢迎。 5. **应用**： - 红黑树常用于实现关联数组、哈希表、集合等数据结构，特别是在需要高效插入、删除和查询操作的场景中。 - 在函数式编程中，红黑树常用于构建持久数据结构，能够保持历史版本并支持高效的更新操作。 红黑树相比于其他平衡树，如AVL树，允许更大的不平衡度，这使得插入和旋转操作更为简便，但可能会导致稍微较差的平衡状态，从而在极端情况下影响性能。然而，红黑树的这种牺牲在大多数实际应用中并不明显，因为它依然保持了良好的平均性能。