企业官网建设流程全解析

核心重点：BST缺陷与平衡树由来、AVL树定义与平衡因子、四大旋转原理、红黑树五大核心特性、变色与旋转机制、AVL与红黑树区别、TreeMap/TreeSet底层原理、高频面试问答全集

一、前置铺垫：为什么需要平衡二叉树？

我们回顾普通二叉搜索树（BST）的核心问题：BST 的形态完全依赖数据插入顺序，若插入有序递增/递减数据，树会变成一条单边链。

举例：依次插入 1,2,3,4,5，BST 会退化为全部右子树的链表结构。

• 正常平衡BST：查找、增删时间复杂度O(logn)

• 退化链式BST：查找、增删时间复杂度O(n)

为了强制维持树的平衡、保证操作效率稳定在O(logn)，平衡二叉树应运而生。主流平衡二叉树分为两类：AVL树（高度平衡）、红黑树（弱平衡）。

二、AVL平衡二叉树（严格平衡树）

AVL树是最早的自平衡二叉搜索树，是严格高度平衡的BST，所有平衡规则、旋转机制都是后续红黑树的基础，面试必学前置知识。

2.1 AVL树严格定义（面试必背）

AVL树 = 合法二叉搜索树 + 严格高度平衡，满足两个条件：

1. 整体是合法BST，满足左小右大有序规则；

2. 任意节点的左右子树高度差绝对值不