二叉树04：AVL树实现与优化
时隔多年又重新实现了一遍 AVL树，并且进行了深度优化，所以有些心得。 首先，我会介绍6种失衡类型和4种旋转； 然后，重点描述插入和删除的优化实现，并将给出严谨的分析和证明，解释为什么可以这么优化； 最后，我会用 AVL 树与 Java 的 TreeMap (红黑树)进行性能对比，以验证优化结果。 代码仓库：https://github.com/patricklaux/perfect-code 1. 简介 AVL 树是一种自平衡二叉查找树（Self-balancing binary search tree），得名于其两位作者的首字母1： Georgy Adelson-Velsky 和 Evgenii Landis。 相比于二叉查找树最坏情况下时间复杂度为 \( O(n) \)，AVL树查找、插入和删除的平均时间复杂度和最坏时间复杂度均为 \( O(log_2n) \)，其中 n 为树的节点数。 2. 高度与平衡因子 AVL树的平衡性质：其任意节点的左子树和右子树的高度差的绝对值小于等于1。 2.1. AVL节点 private class AvlNode<K, V> { K key; // 键 V val; // 值 byte height; // 高度 AvlNode<K, V> left; // 左孩子 AvlNode<K, V> right; //右孩子 } 2.2. 获取高度 // 空树的高度定义为 -1。 private byte height(AvlNode<K, V> node) { return (node == null) ? -1 : node.height; } 2.3. 更新高度 // 取左右子树的高度的大者再加1，即为父节点的高度 private void updateHeight(AvlNode<K, V> parent) { parent.height = (byte) (Math.max(height(parent.left), height(parent.right)) + 1); } 2.4. 平衡因子 二叉查找树的平衡因子 BF (Balance Factor) 的定义为两棵子树的高度之差。 ...