考研专业课之统考计算机蓝宝书(23)

来源：跨考网 2009-01-07 21:06

3.2.6 平衡二叉树（AVL树）

平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过1。

左子树与右子树高度之差，这个数字称为结点的平衡因子。由平衡二叉树定义，所有结点的平衡因子只能取-1，0，1三个值之一。若二叉排序树中存在这样的结点，其平衡因子的绝对值大于1，这棵树就不是平衡二叉树
在平衡二叉树上插入或删除结点后，可能使树失去平衡，因此，需要对失去平衡的树进行平衡化调整。设a结点为失去平衡的最小子树根结点，对该子树进行平衡化调整归纳起来有以下四种情况：

如图6.3的图(a)为插入前的子树。其中，B为结点a的左子树，D、E分别为结点c的左右子树，B、D、E三棵子树的高均为h。图(a)所示的子树是平衡二叉树。

在图(a)所示的树上插入结点x，如图(b)所示。结点x插入在结点c的右子树E上，导致结点a的平衡因子绝对值大于1，以结点a为根的子树失去平衡。

【调整策略】
调整后的子树除了各结点的平衡因子绝对值不超过1，还必须是二叉排序树。由于结点c的左子树D可作为结点a的右子树，将结点a为根的子树调整为左子树是B，右子树是D，再将结点a为根的子树调整为结点c的左子树，结点c为新的根结点，如图(c)。

【平衡化调整操作判定】
沿插入路径检查三个点a、c、E，若它们处于"\"直线上的同一个方向，则要作左单旋转，即以结点c为轴逆时针旋转。

订阅收藏考研专业课之统考计算机蓝宝书

二. 右单旋转

沿插入路径检查三个点a、b、c，若它们呈"<"字形，需要进行先左后右双向旋转：
1. 首先，对结点b为根的子树，以结点c为轴，向左逆时针旋转，结点c成为该子树的新根，如图(b、e)；
2. 由于旋转后，待插入结点x相当于插入到结点b为根的子树上，这样a、c、b三点处于"/"直线上的同一个方向，则要作右单旋转，即以结点c为轴顺时针旋转，如图(c、f)。

四. 先右后左双向旋转

先右后左双向旋转和先左后右双向旋转对称，请读者自行补充整理。

在平衡的二叉排序树T上插入一个关键码为kx的新元素，递归算法可描述如下：
1. 若T为空树，则插入一个数据元素为kx的新结点作为T的根结点，树
的深度增1；
2. 若kx和T的根结点关键码相等，则不进行插入；
3. 若kx小于T的根结点关键码，而且在T的左子树中不存在与kx有相同

关键码的结点，则将新元素插入在T的左子树上，并且当插入之后的左子树深度增加1时，分别就下列情况进行处理：
① T的根结点平衡因子为-1(右子树的深度大于左子树的深度)，则将根结
点的平衡因子更改为0，T的深度不变；
② T的根结点平衡因子为0(左、右子树的深度相等)，则将根结点的平衡因
子更改为1，T的深度增加1；
② T的根结点平衡因子为1(左子树的深度大于右子树的深度)，则若T的
左子树根结点的平衡因子为1，需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；若T的左子树根结点平衡因子为-1，需进行先左后右双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，树的深度不变。

4. 若kx大于T的根结点关键码，而且在T的右子树中不存在与kx有相同
关键码的结点，则将新元素插入在T的右子树上，并且当插入之后的右子树深度增加1时，分别就不同情况处理之。其处理操作和3中所述相对称，读者可自行补充整理。

【平衡树的查找分析】
在平衡树上进行查找的过程和二叉排序树相同，因此，在查找过程中和给定值进行比较的关键码个数不超过树的深度。那么，含有n个关键码的平衡树的最大深度是多少呢？为解答这个问题，我们先分析深度为h的平衡树所具有的最少结点数。

假设以Nh表示深度为h的平衡树中含有的最少结点数。显然，N0=0，N1=1，N2=2，并且Nh=Nh-1+Nh-2+1。这个关系和斐波那契序列极为相似。利用归纳法容