AVL树非递归算法.docx

文档介绍：AVL树非递归算法
AVL树是一种平衡的二叉搜索树,平衡因子是衡量树平衡程度的一个参数。当结点的平衡因子(本文中结点平衡因子=左子树高度-右子树高度)绝对值大于1时,我们说这个结点是不平衡的,因此需要进行旋转使之重新平衡。
结点不平衡通常是由于对AVL树进行插入或者删除结点时造成的。下面我们分别对插入和删除时的旋转和平衡因子的更新进行讨论。
一、插入
对一棵AVL树插入一个结点时,需要从根结点开始,通过比较插入结点和AVL树结点的值,确定插入的位置。这个操作和BST树的插入操作相同。如图,向一棵AVL树插入一个值为8的结点(红色连线为比较路径)。
1100
5
200
1100
1100
5
200
1100
8
1
0
1
0
1
0
0
0
0
插入前插入后
上图中插入后AVL树种各结点平衡因子的绝对值不大于1,所以不需要进行旋转,下面我们这种讨论插入的四种旋转方式和平衡因子更新。
AVL非递归插入算法描述:
1、第一步,按平衡二叉树规则插入一个结点,在插入的同时找最后一个有可能不平衡的结点。
1、左旋转
1100
h
200
h00
h
0
0
-1
0
0
1100
h
200
h+1100
h
-1
0
-2
0
0
此结点不平衡
200
0
h
0
1100
0
h
0
h+1100
0
左旋转,重新平衡
插入后,旋转前:
旋转后:
插入前:
插入一个值大于20的结点
旋转前后平衡因子变化情况:11(-2->0),20(-1->0)。
2、右旋转
8
0
h
0
1100
1
h
0
h00
0
此结点不平衡
插入前:
8
1
h
0
1100
2
h
0
h+100
0
8
0
h
0
1100
0
h
0
h+100
0
插入后,旋转前:
旋转后:
左旋转,重新平衡
插入一个值小于8的结点
旋转前后平衡因子变化情况:11(2->0),8(1->0)
3、先左后右
根据平衡因子更新情况的不同,我们把先左后右的旋转分成两类。
情况一:
此结点不平衡
插入前:
插入后,旋转前:
左旋转:
7
0
h
0
1100
1
9
0
h
0
h-1
0
h-1
0
7
-1