算法导论-透辟了解平衡二叉树（AVL树）

算法导论-透彻了解平衡二叉树（AVL树）
一.平衡二叉树 简介
形态匀称的二叉排序树称为平衡二叉树 (Balanced binary tree) ，其每个结点的左子树和右子树的高度最多差1,严格定义是：
一棵空树是平衡二叉树；若 T 是一棵非空二叉树，其左、右子树为 TL 和 TR ，令 hl 和 hr 分别为左、右子树的深度。当且仅当
1)TL 、 TR 都是平衡二叉树； 
2)｜ hl － hr ｜≤ 1；

当然,二叉排序树有的性质它都有,复习一下:
1)二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。
2)二叉排序树中，各结点关键字是惟一的。
3)按中序遍历该树所得到的中序序列是一个递增有序序列。
看下面的例子:

二.树的旋转
当我们在对AVL树进行插入和删除等操作时，对树做了修改，那么可能会违AVL树的性质。


为了保持AVL树的性质，我们可以通过对树进行旋转，即修改树中相应结点指针结构，以达到对AVL树进行插入、删除结点等操作时，AVL树依然能保持它特有的性质
Adelson-Velskii 和 Landis 提出了一个动态地保持二叉排序树平衡的方法，其基本思想是：
　　在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。    

上面所说的的调整就是旋转。
假设按二叉排序树进行插入的时候需要平衡的节点是a，则不平衡可能出现四种情况：
1）对a的左儿子的左子树进行一次插入。
2）对a的左儿子的右子树进行一次插入。
3）对a的右儿子的左子树进行一次插入。
4）对a的右儿子的右子树进行一次插入。

其中1和4关于a对称，2和3也关于a对称。
1和4的情况（即左左或右右）只需对树进行一次单旋转就可以完成调整，2和3的情况（即左右或右左）需要进行双旋状才能完成。

下面用图来说明。

1)单旋转

右右型为例。如下图，在k1的右儿子的右子树进行一次插入，k1为失衡结点。

解决方法：k1右儿子k2为轴向左旋转，其中Y不为空的话需要将Y连接到k1的右子树。

 
例：
 
算法导论中的代码：
LEFT-ROTATE(T,x)
1 y = x.right  // set y
2 x.right = y. left  // turn y’s left subtree into x’s right subtree
3 if y.left!= T.nil
4 y. left.p = x
5 y.p = x.p  // link x’s parent to y
6 if x.p == T.nil
7 T.root = y
8 elseif x == x.p. left
9 x.p.left = y
10 else x.p.right = y
11 y.left = x  // put x on y’s left
12 x.p = y

2）双旋转
右左型为例。1为失衡节点，直接左转肯定不能解决问题。
做法：k3左子树绕k2右旋转，树变成了右右型，绕k2进行左旋转一次就可以了。


例：
 

三.AVL树的插入
插入分两步：
1）按照二叉排序树的插入方法将新结点插入树种位置。
2）看情况对树进行旋转。

四.AVL树的删除
1）按照二叉排序树的删除方法将对应结点删除。
2）看情况对树进行旋转。

二叉排序树的插入和删除方法见：
算法导论-二叉排序树

举一例说明，设一组记录的关键字按以下次序进行插入： 4 、 5 、 7 ， 2 、 1 、 3 、 6 ，其生成及调整成二叉平衡树的过程示于图（括号内的数字是节点平衡因子）。
 

参考文章：

算法导论（第三版）

数据结构与算法分析

http://blog.csdn.net/sagadean/article/details/7081625

http://www.cnblogs.com/fornever/archive/2011/11/15/2249492.html

查看更多 下一篇