平衡二叉树

前言

在计算机科学中, AVL 树是最早被发明的自平衡二叉查找树. 在 AVL 树中, 任一节点对应的两棵子树的最大高度差为 1, 因此它也被称为高度平衡树. 查找, 插入和删除在平均和最坏情况下的时间复杂度都是 O(logn). 增加和删除元素的操作则可能需要借由一次或多次树旋转, 以实现树的重新平衡. AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 Evgenii Landis, 他们在 1962 年的论文 An algorithm for the organization of information 中公开了这一数据结构.

为什么要有平衡二叉树

二叉搜索树的查找效率取决于树的高度, 因此保持树的高度最小, 即可保证树的查找效率. 如果二叉树的形态类似于一个链表, 那么它的时间复杂度将退化成 O(n). 下面这个例子, 查找 6 得需要 6 次.

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

二叉搜索树的查找效率取决于树的高度, 因此保持树的高度最小, 即可保证树的查找效率. 下面这个例子查找 6 的次数只有 3 次. 因此可以看出当节点数目一定, 保持树的左右两端保持平衡, 树的查找效率最高.

    3
   / \
  2   5
 /   / \
1   4   6

AVL 的定义

定义

• 可以是空树
• 假如不是空树, 任何一个结点的左子树与右子树都是平衡二叉树, 并且高度之差的绝对值不超过 1.

下面这棵树中, 2 -> 4 -> 7 -> 8 这个子树右边都没东西, 显然不平衡, 故不是二叉平衡树.

        1
       / \
      2   3
     /   / \
    4   5   6
   /
  7
 /
8

下面这棵树中, 左边是 1 -> 2 -> 4 -> 6 , 右边只是 1 -> 3,高度差的绝对值大于了 1, 故不是二叉平衡树.

      1
     / \
    2   3
   / \
  4   5
 /
6

平衡因子

某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子(BF,Balance Factor). 平衡二叉树中不存在平衡因子大于 1 的节点. 在一棵平衡二叉树中, 节点的平衡因子只能取 0, 1 或者 -1, 分别对应着左右子树等高, 左子树比较高, 右子树比较高.