（嵌入式八股）第8章 数据结构(二)（后续数据结构相关会持续补充在这里）

8.11 平衡二叉树——红黑树

红黑树是一种 自平衡二叉搜索树（BST），在插入和删除时通过 旋转（左旋、右旋） 和 变色 操作保持平衡。相比 AVL 树，红黑树牺牲部分平衡性，减少旋转次数，以提高插入/删除的性能，使其在实际应用中更高效。

红黑树的特性

红黑树遵循五大特性，用颜色属性来维持平衡：

红黑树的恢复平衡操作

当红黑树的特性被破坏时，需要通过以下 3 种操作来恢复平衡：

变色

规则1：父节点（P）和叔叔节点（U）均为红色时：

规则2：插入节点的叔叔节点（U）是黑色或不存在时：

示例

• 假设插入一个新节点后，出现了如下的红红冲突：

此时，按照变色规则：

• P 变黑
• U 变黑
• G 变红

变色后树的结构变为：

如果此时G 的父节点也是红色，则问题上移，可能需要继续调整。

左旋

• 作用：用于调整树的平衡，通常在插入或删除节点后，当右子树过高或出现特定红黑冲突时使用。
• 旋转规则：
• 将当前节点 (P) 变为其右子节点 (N) 的左子节点。
• N 的左子树变成 P 的右子树（如果存在）。
• N 取代 P 成为父节点。

示例

初始状态：

左旋 P，使 N 上移：

右旋

• 作用：用于调整树的平衡，通常在左子树过高或出现特定红黑冲突时使用。
• 旋转规则：
• 将当前节点 (P) 变为其左子节点 (N) 的右子节点。
• N 的右子树变成 P 的左子树（如果存在）。
• N 取代 P 成为父节点。

示例

初始状态：

右旋 P，使 N 上移：

效果：调整结构，降低左子树的高度，可能需要进一步变色处理。