AVL树的总结

AVL树：它是高度平衡的二叉搜索树，它的左子树和右子树都是AVL树。结点拥有的平衡因子（balance）是该结点的右子树减去左子树的高度所得到的高度差,规定AVL任意结点的平衡因子只能取-1,0,1。

1、代码实现：

首先定义一个AVLTree类模板：

图1

购买和释放结点：

图2

2、实例分析：

图3：高度平衡的二叉树

如上图所示,选取数组int ar[]={16, 3, 7, 11, 9, 26, 18, 14, 15 }进行插入构造AVLTree操作。

步骤分析：

（1）先插入16，再插入3，再插入7，至此得到下图：

（2）可以看到此时这棵树已经不平衡了，所以需要对此调整。可以看到它们位于一条折线上，因此需要进行先左后右的双旋转，先以结点7为旋转轴，将结点3逆时针做左单旋转；再以结点7为旋转轴，将结点16顺时针做右单旋转，得到如下图：

（3）再插入下一个结点11，插入结点9，得到下图：

（4）可以看到此时这棵树已经不平衡了，所以需要对此调整。16、11、9三点处于一条斜线上，因此对它进行右单旋转，以11为旋转轴，将16右单旋转可得到：

（5）继续插入26，得到：

（6）可以看到此时这棵树已经不平衡了，所以需要对此调整。11、16、26三点处于一条斜线上，因此对它进行左单旋，以11为旋转轴，将7逆时针旋转，得到：

（7）然后插入18，同样得到一颗不平衡的树：

（8）因此需要对其进行调整，因为16,26,18三点处于一条折线上，因此需要对其进行右左双旋，先以18为旋转轴，将26顺时针旋转，再以18为旋转轴，将16进行逆时针旋转，可以得到下图：

（9）然后插入14、15，得到图如下：

（10）分析上图的不平衡，可以发现16,14,15三点处于一条折线上，需要进行先左后右旋转，先以15为旋转轴，将14逆时针旋转，再以15为旋转轴，将16顺时针旋转，得到下图：

（11）至此，得到了本文最开始的高度平衡的二叉树，也即AVL树。

3、实例的代码实现（向AVLTree插入结点）：

图4：插入代码1 图5：插入代码2 图6 图7 图8

4、AVL树的其它操作：

图9 图10 图11 图12