企业官网建设流程全解析

一、为什么需要平衡二叉树

普通二叉搜索树 BST 有致命缺陷：插入有序数据会退化成单链，从 O (logn) 退化到 O (n)，查找效率暴跌。

举例：插入 1,2,3,4,5BST 会变成一条斜链表，失去二分优势。解决方案：平衡二叉树，强制左右子树高度差不能过大，维持 O (logn) 稳定效率。

二、AVL 平衡二叉树核心特性

1. 定义

AVL 树是严格平衡二叉搜索树任意节点左右子树高度差绝对值 ≤ 1这个高度差称为平衡因子。

2. 平衡因子规则

平衡因子 = 左子树高度 - 右子树高度只能取值：-1、0、1

3. 失衡四种旋转修复

插入节点导致失衡，通过旋转恢复平衡：

1. LL 型：右单旋
2. RR 型：左单旋
3. LR 型：先左后右双旋
4. RL 型：先右后左双旋

4. AVL 优缺点

优点：高度严格平衡，查询最快缺点：插入删除旋转次数多、维护代价大，工程很少直接用

三、红黑树核心概念（面试重中之重）

1. 是什么

红黑树是弱平衡二叉搜索树不追求严格平衡，用颜色规则约束，近似平衡。C++map/set、JavaTreeMap、Linux 内核 底层都是红黑树。

2. 红黑树五大铁律（必背）

1. 每个节点红色 或 黑色
2. 根节点必须是黑色
3. 叶子节点（空节点）都是黑色
4. 红色节点的两个子节点必须都是黑色（不能红红相连）
5. 从任意节点到其所有叶子节点，经过的黑色节点数量相同

3. 核心特点

• 最长路径 ≤ 最短路径的 2 倍
• 近似平衡，不用频繁旋转
• 插入删除只有变色 + 少量旋转，维护成本低
• 查找、插入、删除稳定维持O(logn)

四、红黑树 vs AVL 树 面试对比

表格

面试一句话总结：查询多用 AVL，频繁增删用红黑树；工程实际全用红黑树。

五、为什么 STL map/set 选用红黑树

1. 增删操作远多于查询，红黑树维护成本更低
2. 不用严格高度平衡，减少旋转次数
3. 性能稳定、实现成熟、适合底层容器封装

六、面试高频问答整理

1. BST 为什么会退化？有序插入变成单链表，效率从 O (logn) 降到 O (n)。

2. AVL 和红黑树区别？AVL 严格平衡、查询快、维护贵；红黑树弱平衡、增删快、工程主流。

3. 红黑树为什么不用高度平衡？用颜色规则间接约束路径长度，减少旋转，提升增删效率。

4. 红黑树五条规则必须熟记，面试常手写口述。

七、今日总结

1. 普通 BST 会退化，引出平衡二叉树
2. AVL 严格平衡，靠平衡因子 + 旋转维护
3. 红黑树弱平衡，靠 5 条颜色规则约束
4. 红黑树是 C++ map/set 底层，面试必问
5. 记住 AVL 与红黑树选型与优缺点对比