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

8.11 平衡二叉树——红黑树

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

红黑树的特性

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

红黑树的恢复平衡操作

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

变色

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

父节点 P 变黑

叔叔节点 U 变黑

祖父节点 G 变红

作用：将冲突上移到祖父节点，可能需要进一步调整。

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

可能需要旋转来修复树的结构，但如果变色足以恢复平衡，优先使用变色减少旋转次数。

示例

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

此时，按照变色规则：

P 变黑
U 变黑
G 变红

变色后树的结构变为：

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

左旋

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

示例

初始状态：

左旋 P，使 N 上移：

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

右旋

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

示例

初始状态：

右旋 P，使 N 上移：

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

左旋：将右子树调整为平衡状态，减少右倾现象。

右旋：将左子树调整为平衡状态，减少左倾现象。

旋转后通常需要以保

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

工科女嵌入式开发秋招逆袭指南文章被收录于专栏

作者简介：仅用几个月时间0基础天坑急转嵌入式开发，逆袭成功拿下华为、vivo、小米等15个offer，面试经验100+，收藏20+面经，分享求职历程与学习心得。专栏内容：这是一份覆盖嵌入式求职过程中99%问题指南，详细讲解了嵌入式开发的学习路径、项目经验分享、简历优化技巧、面试心得及实习经验，从技术面，HR面，AI面，主管面，谈薪一站式服务，助你突破技术瓶颈、打破信息差，争取更多大厂offer。