AVL 树

AVL 树是一种自平衡的二叉搜索树，这意味着树中任何节点的两个子树的高度最多相差 1。如果在任何时候这个差值大于 1，就会进行重新平衡以恢复这个特性。这棵树以其发明者 G.M. Adelson-Velsky 和 E.M. Landis 命名，他们于 1962 年引入了它。AVL 树中的每个节点都携带额外的信息（其平衡因子），该因子可以是 -1、0 或 +1。每当插入操作导致平衡因子超出这个范围时，AVL 树会通过以不同的方式（称为左-左旋转、右-右旋转、左-右旋转和右-左旋转）旋转子树来自动平衡。