平衡二叉树：AVL与红黑树终极对比

一、为什么需要平衡二叉树普通二叉搜索树 BST 有致命缺陷插入有序数据会退化成单链从 O (logn) 退化到 O (n)查找效率暴跌。举例插入 1,2,3,4,5BST 会变成一条斜链表失去二分优势。解决方案平衡二叉树强制左右子树高度差不能过大维持 O (logn) 稳定效率。二、AVL 平衡二叉树核心特性1. 定义AVL 树是严格平衡二叉搜索树任意节点左右子树高度差绝对值 ≤ 1这个高度差称为平衡因子。2. 平衡因子规则平衡因子 左子树高度 - 右子树高度只能取值-1、0、13. 失衡四种旋转修复插入节点导致失衡通过旋转恢复平衡LL 型右单旋RR 型左单旋LR 型先左后右双旋RL 型先右后左双旋4. AVL 优缺点优点高度严格平衡查询最快缺点插入删除旋转次数多、维护代价大工程很少直接用三、红黑树核心概念面试重中之重1. 是什么红黑树是弱平衡二叉搜索树不追求严格平衡用颜色规则约束近似平衡。Cmap/set、JavaTreeMap、Linux 内核 底层都是红黑树。2. 红黑树五大铁律必背每个节点红色 或 黑色根节点必须是黑色叶子节点空节点都是黑色红色节点的两个子节点必须都是黑色不能红红相连从任意节点到其所有叶子节点经过的黑色节点数量相同3. 核心特点最长路径 ≤ 最短路径的 2 倍近似平衡不用频繁旋转插入删除只有变色 少量旋转维护成本低查找、插入、删除稳定维持O(logn)四、红黑树 vs AVL 树 面试对比表格对比项AVL 树红黑树平衡程度严格平衡弱平衡平衡约束高度差≤1颜色五条规则维护代价旋转多、开销大变色 少量旋转、开销小查询性能略快稍慢一点插入删除慢更快工程应用几乎不用map/set、内核、数据库广泛用面试一句话总结查询多用 AVL频繁增删用红黑树工程实际全用红黑树。五、为什么 STL map/set 选用红黑树增删操作远多于查询红黑树维护成本更低不用严格高度平衡减少旋转次数性能稳定、实现成熟、适合底层容器封装六、面试高频问答整理BST 为什么会退化有序插入变成单链表效率从 O (logn) 降到 O (n)。AVL 和红黑树区别AVL 严格平衡、查询快、维护贵红黑树弱平衡、增删快、工程主流。红黑树为什么不用高度平衡用颜色规则间接约束路径长度减少旋转提升增删效率。红黑树五条规则必须熟记面试常手写口述。七、今日总结普通 BST 会退化引出平衡二叉树AVL 严格平衡靠平衡因子 旋转维护红黑树弱平衡靠 5 条颜色规则约束红黑树是 C map/set 底层面试必问记住 AVL 与红黑树选型与优缺点对比