「数据结构与算法」AVL树

数据结构
留言

AVL树（得名于发明者G. M. Adelson-Velsky 和 E. M. Landis）本质上是一棵带有平衡条件的二叉搜索树。
AVL树具有以下2个性质：

  1. 左子树和右子树的深度之差的绝对值不超过1；
  2. 左子树和右子树全都是 AVL树。

其中为了度量左右子树的深度之差，我们引入平衡因子(BF)的概念。

平衡因子： 某个节点的左子树的高度减去右子树的高度得到的差值。

对于一棵 AVL树，里面的所有节点的平衡因子只能取值于-1、0、1，否则，AVL树将是不平衡的并且需要平衡调整。

1. AVL 树平衡调整

二叉树的平衡化有两大基础操作： 左旋（rotate left）和右旋（rotate right）。

  • 左旋，即是逆时针旋转，以某个节点作为旋转点，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变；

  • 右旋，即是顺时针旋转，以某个节点作为旋转点，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。

这种旋转在整个平衡化过程中可能进行一次或多次，这两种操作都是从失去平衡的最小子树根节点开始的(即离插入节点最近且平衡因子超过1的祖节点)。

造成失衡一共有 4 种情况：LL型、LR型、RL型、RR型，如下图所示。

  • LL型平衡调整：对节点C右旋即可。

  • LR型平衡调整：先对A进行一次左旋再对C进行一次右旋。

  • RL型平衡调整：先对C进行一次右旋再对A进行一次左旋。

  • RR型平衡调整：对节点A左旋即可。

2. 模拟建 AVL 树

按照整数序列 {4,5,7,2,1,3,6} 依次插入AVL树。

由于AVL树必须保证左右子树平衡(左子树和右子树的深度之差的绝对值不超过1)，

所以在插入的时候很容易出现不平衡的情况，一旦这样，就需要进行旋转以求达到平衡。

正是由于这种严格的平衡条件，导致AVL需要花大量时间在调整上，故AVL树一般适用于查询场景， 而不适用于增删频繁的场景。