一、AVL 平衡二叉树平衡二叉搜索树1. 核心基础规则二叉搜索树特性左子树所有节点 当前节点 右子树所有节点查找时间复杂度 (O(logn))平衡约束任意节点左右子树高度差平衡因子绝对值 ≤ 1高度差大于 1 则树失衡需要旋转调整平衡。失衡分类4 种失衡场景LL / LR / RR / RL对应 4 套旋转修复方案。2. 四种失衡旋转图解说明1LL失衡根源当前节点的左孩子的左子树插入节点左子树高度远超右子树。修复以左孩子为支点整体右旋一次即可恢复平衡。 示例根 5左子 33 的左子 1高度差为 2右旋后 3 升为根5 变为 3 的右孩子。2LR失衡根源当前节点的左孩子的右子树插入节点。 修复分两步对左孩子做左旋转化为 LL 结构对根节点做右旋完成平衡。 图示案例根 5 → 左子 3 → 3 的右子 4先左旋 3 和 4再右旋 5 与新根 4最终 4 为根3、5 分属左右子树。3RR失衡根源当前节点的右孩子的右子树插入节点。 修复以右孩子为支点整体左旋一次。 示例根 3右子 88 的右子 10左旋后 8 升为根3 变为 8 的左孩子。4RL失衡根源当前节点的右孩子的左子树插入节点。 修复分两步对右孩子做右旋转化为 RR 结构对根节点做左旋恢复平衡。 图示案例根 3 → 右子 8 → 8 的左子 5先右旋 8 和 5再左旋 3 与新根 5最终 5 为根3、8 分属左右子树。二、2-3-4 树1. 节点类型定义所有节点关键字有序存储节点关键字数量决定类型二节点仅 1 个 key2 个子分支结构[left, key, right]三节点2 个 key3 个子分支结构[left, key1, mid, key2, right]四节点3 个 key4 个子分支结构[left, k1, m1, k2, m2, k3, right]2. 核心特性多路平衡所有叶子节点处于同一层天然平衡插入元素时节点满 3 个 key 会向上分裂保证层数均匀和红黑树完全等价2-3-4 树可以无损映射成红黑树红黑树也能还原为 2-3-4 树。3. 2-3-4 树 ↔ 红黑树映射规则二节点对应黑色节点无子红色节点三节点一个黑父节点 一个红色子节点两个 key 拆分小 key 红、大 key 黑四节点一个黑色父节点 两个红色子节点三个 key 拆分两侧 key 为红中间 key 为黑。三、红黑树1. 五大核心约束根节点永远是黑色所有叶子节点空 null 节点都是黑色红色节点的两个子节点必须是黑色不能出现连续红节点从任意节点出发到其所有叶子节点的路径上黑色节点数量完全相等黑高统一每条路径不存在两个连续红色节点。2. 平衡边界特性最短路径全黑色节点最长路径红黑交替结论任意一条路径长度不会超过其他路径的 2 倍查找稳定 \(O(logn)\)。3. 底层本质红黑树是 2-3-4 树的二叉树实现通过变色 旋转模拟 2-3-4 树的节点分裂、合并逻辑解决 AVL 树频繁旋转的性能损耗广泛用于TreeMap、HashMap、数据库索引。四、M 阶 B 树1. 阶数定义M 阶 B 树单个节点最多存放M-1个有序 key-value最多分出M个子分支。二节点1 个 key2 分支三节点2 个 key3 分支四节点3 个 key4 分支五节点4 个 key5 分支。2. 完整特性节点内所有 key 从小到大有序排列非叶子节点 key 充当分割线左子树 key 右子树所有叶子节点处于同一层天然平衡所有节点同时存储key value索引和数据共存多用于文件系统索引内外存查询场景。3. 结构示例5 阶 B 树根节点存放20、62、130三个 key分出 4 个子节点分支左分支7、11、19中左分支29、40、48、53中右分支75、99右分支176五、B 树1. 和 B 树核心区别非叶子节点只存 key不存储 value仅做索引导航所有真实 value 数据只存在叶子节点全部叶子节点通过双向链表串联形成有序链表支持范围查询、全表遍历非叶子节点 key 会冗余出现在叶子节点保证范围检索连续。2. 核心优势非叶子节点无数据一页磁盘能存放更多索引 key树高度更低磁盘 IO 更少叶子有序链表between、like、order by范围查询效率极高等值查询、范围查询性能稳定是关系型数据库聚簇索引标准结构。3. 结构示例顶层根节点62中层非叶子节点20、40/99、176仅 key无 value底层叶子链表[7,11,19] → [20,29] → [40,48,53] → [62,75] → [99,130] → [176]每个节点携带完整 value指针串联。六、树结构对比总结表树结构平衡规则核心用途优缺点AVL 平衡二叉树左右子树高度差≤1严格平衡内存高频查找查询最快插入删除旋转次数多开销大红黑树黑高统一无连续红节点近似平衡TreeMap、JDK8 HashMap插入删除旋转少综合性能均衡2-3-4 树所有叶子同层多路平衡红黑树理论原型直观易懂多路节点拆分M 阶 B 树多路平衡节点存 keyvalue文件系统索引索引数据同节点范围查询弱B 树非叶子仅存 key叶子有序链表MySQL 数据库索引磁盘 IO 少范围查询极强数据库标配