AVL Tree - tenji/ks GitHub Wiki

AVL 树

AVL 树（以发明人 Adelson-Velsky 和 ​​Landis 命名）是一种自平衡二叉搜索树（Self-Balancing Binary Search Tree）。在 AVL 树中，任意节点的两个子子树的高度最多相差 1；如果在任何时候它们相差超过一，则进行重新平衡（Rebalancing）以恢复该属性。

历史

AVL 树以其两位苏联发明者 Georgy Adelson-Velsky 和 ​​Evgenii Landis 的名字命名，他们在 1962 年的论文“信息组织算法”（An algorithm for the organization of information）中发表了该树。它是被发明的最古老的自平衡二叉搜索树数据结构。

基本概念

平衡系数（Balance factor）

在二叉树中，节点 X 的平衡因子定义为以节点 X 为根的两个子树的高度差：

$BF(X) := Height(RightSubtree(X)) - Height(LeftSubtree(X))$

在 AVL 树中，平衡因子的取值范围是 -1, 0, 1，分别表示左子树比右子树高、左右子树高度相等、左子树比右子树矮。为了最大化实现查找、插入和删除操作的效率，AVL 树始终保持平衡因子绝对值不超过 1 的节点作为根节点。

avl-tree-with-balance-factor

AVL 树的特性

  1. 特性1：对于任何一颗子树的 root 根结点而言，它的左子树任何节点的 key 一定比 root 小，而右子树任何节点的 key 一定比 root 大；
  2. 特性2：对于 AVL 树而言，其中任何子树仍然是 AVL 树；
  3. 特性3：每个节点的左右子节点的高度之差的绝对值最多为 1；

AVL 树和 BST 是什么关系？

  1. AVL 本身首先是一棵 BST 二叉搜索树；
  2. AVL 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为 1。

也就是说，AVL 树，本质上是带了平衡功能的二叉搜索树。

基本操作

搜索（Searching）

遍历（Traversal）

插入（Insert）

删除（Delete）

再平衡（Rebalancing）

左左结构失衡（LL型失衡）

右右结构失衡（RR型失衡）

左右结构失衡（LR型失衡）

右左结构失衡（RL型失衡）

AVL 树再平衡最多需要多少次旋转？

AVL 的每一次插入结点操作最多只需要旋转 1 次（单旋转或双旋转），每一次删除操作最多需要 O(logn) 次旋转。

Java 实现

...

优点

  • AVL 树可以自我平衡，因此为搜索、插入和删除提供了 O(logn) 的时间复杂度；
  • AVL 树是二叉搜索树（具有平衡性），因此可以按排序顺序遍历项目；
  • 由于平衡规则比红黑树严格，AVL树一般具有相对较小的高度，因此搜索速度更快；
  • 与红黑树相比，AVL 树的理解和实现相对简单。

缺点

  • 与普通 BST 相比实现较难，与 Red Black 相比较容易实现；
  • 与红黑树相比，使用较少；
  • 由于其相当严格的平衡，AVL 树的插入和删除操作会变得复杂，因为需要执行更多的旋转。

∞、参考链接