红黑树

什么是红黑树

红黑树（Red-Black Tree）是一种 自平衡二叉搜索树，其主要特点是通过在每个节点上增加一个颜色属性（红或黑），在插入和删除操作后，通过一系列规则保持树的近似平衡。红黑树确保在最坏情况下的时间复杂度为 O(log n)，从而保证了高效的查找、插入和删除操作。

性质

红黑树是通过强制如下规则来保持平衡的：

• 节点是红色或黑色：每个节点都被标记为红色或黑色。
• 根节点是黑色：树的根节点总是黑色的。
• 叶节点（空节点）都是黑色：在红黑树的定义中，所有的叶节点（空节点）都被认为是黑色。实际存储时，这些叶节点是 NULL 指针。
• 红色节点不能有红色子节点（红色节点的子节点必须是黑色）：这意味着不会有连续的红色节点。这个性质保证了树的相对平衡性。
• 从任意节点到其所有叶子节点的路径上，黑色节点的数量相同：这保证了树不会过度倾斜，提供了一种近似平衡的状态。

这些性质保证了红黑树的最大高度为 2log(n)，因此可以在最坏情况下仍然保持 O(log n) 的性能。

红黑树的操作

在红黑树中，最常见的操作有 插入、删除 和 查找，其中插入和删除操作后需要重新调整树的结构，以保证红黑树的性质不被破坏。

插入

插入一个新节点后，红黑树可能会因为违反其性质而不再平衡，因此需要调整。插入的节点通常是红色的，调整的步骤包括：

1. 重新着色：更改某些节点的颜色。
2. 旋转：旋转是调整红黑树的一个关键操作，用来恢复树的平衡。有两种旋转：
   • 左旋：把一个节点的右子树转换成它的左子树。
   • 右旋：把一个节点的左子树转换成它的右子树。

删除

删除操作比插入操作复杂一些，删除节点可能会导致树的性质被破坏，因此需要进行更多的修复。修复的方式包括：

1. 重新着色：调整某些节点的颜色。
2. 旋转：使用左旋或右旋操作恢复树的平衡。

删除后的调整步骤取决于删除的节点是否是红色或黑色，以及它的子节点情况。

查找

查找操作与普通的二叉搜索树相同，红黑树的性质不会影响查找操作。由于红黑树是平衡的，查找操作的时间复杂度为 O(log n)。

红黑树的旋转

旋转是红黑树中调整平衡的核心操作，分为左旋和右旋：

• 左旋：以某个节点为支点，将其右子节点移到该节点的位置，右子节点的左子树变成原节点的右子树。
• 右旋：以某个节点为支点，将其左子节点移到该节点的位置，左子节点的右子树变成原节点的左子树。

通过这些旋转操作，可以调整节点的位置以保持红黑树的平衡。

优势

• 平衡性：红黑树通过控制红色和黑色节点的比例，确保树的高度接近 O(log n)，从而保证插入、删除和查找操作的效率。
• 最坏情况下的性能保证：相比其他树结构，红黑树在最坏情况下仍然保持 O(log n) 的时间复杂度，这是它的主要优势。
• 自动调整：红黑树通过插入和删除后的自动调整，始终保持平衡状态，而无需额外的操作。