AVL树非递归算法

AVL 树非递归算法

AVL 树是一种平衡的二叉搜索树，平衡因子是衡量树平衡程度的一个参数。当结点的平衡因子（本文中结点 平衡因子=左子树高度-右子树高度）绝对值大于1时，我们说这个结点是不平衡的，因此需要进行旋转使之重新平衡。

结点不平衡通常是由于对AVL 树进行插入或者删除结点时造成的。下面我们分别对插入和删除时的旋转和平衡因子的更新进行讨论。

一、插入

对一棵AVL 树插入一个结点时，需要从根结点开始，通过比较插入结点和AVL 树结点的值，确定插入的位置。这个操作和BST 树的插入操作相同。如图，向一棵AVL 树插入一个值为8的结点（红色连线为比较路径）。

插入前 插入后

上图中插入后AVL 树种各结点平衡因子的绝对值不大于1，所以不需要进行旋转，下面我们这种讨论插入的四种旋转方式和平衡因子更新。

AVL 非递归插入算法描述：

1、第一步，按平衡二叉树规则插入一个结点，在插入的同时找最后一个有可能不平衡的结点。

1、左旋转

插入一个值大于20的结点

旋转前后平衡因子变化情况：11(-2->0)，20(-1->0)。

2、右旋转

左旋转，重新平衡

左旋转，重新平衡

插入一个值小于8的结点

旋转前后平衡因子变化情况：11(2->0)，8(1->0) 3、先左后右

根据平衡因子更新情况的不同，我们把先左后右的旋转分成两类。情况一：

第一类情况：插入的结点大于9

平衡因子更新情况：9(1->0)，7(0->1)，11(1->0)

情况二：

左旋转:

左旋转:

第二类情况：插入的结点小于9