java数据结构与算法之平衡二叉树(AVL树)的设计与实现分析.pdf

《java数据结构与算法之平衡二叉树(AVL树)的设计与实现分析.pdf》由会员分享，可在线阅读，更多相关《java数据结构与算法之平衡二叉树(AVL树)的设计与实现分析.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、java 数据结构与算法之平衡二叉树(AVL 树)的设计与实现 普通二叉查找树的问题 在开篇，我们提到过,普通二叉树（二叉查找树）在操作的时间复杂度上不一定遵循 O(n）,也有可能是 O(n)，这是为什么呢？在上一篇中,我们明明插入都按照一定规则比较的呀，其实那是因为我们在上篇测试时执行了随机插入的操作,如果此时利用上篇实现的二叉搜索树将一段已排序好的数据一个个插入后,就会发现如下情况了：从图中我们可以发现,把已排序的 1-9 数据进行正序和倒序插入后，树的结构已变成单向左子树或者右子树了，如果我们在往里插入已排序的数据，那么单向左子树或者右子树越来越长，此时已跟单链表没有什么区别了，因此对此

2、结构的操作时间复杂度自然就由 O（n）变成 O(n）了,这也就是普通二叉查找树不是严格意义上 O(n)的原因.那么该如何解决这个问题呢？事实上一种解决的办法就是要有一个称为平衡的附加结构条件即：任何结点的深度不得过深，而这种数据结构就是我们本篇要分析的平衡二叉树（AVL）,它本身也是一种二叉查找树，只不过不会出现前面我们分析的情形罢了，接下来我们就来分析一下这棵平衡二叉树。平衡二叉树的定义 通过上面的分析，我们明白的普通二叉查找树的不足，也知道了如何去解决这个缺点，即构建树时要求任何结点的深度不得过深（子树高度相差不超过 1），而最终这棵树就是平衡二叉树（Balanced Binary Tre

3、e），它是 G.M。Adelson-Velsky 和 E.M.Landis 在 1962 年在论文中发表的，因此又叫 AVL 树。这里我们还需要明确一个概念,AVL 树只是实现平衡二叉树的一种方法,它还有很多的其他实现方法如红黑树、替罪羊树、Treap、伸展树等，后面我们还会分析其他树的实现。ok，接着来了解一下 AVL 树的特性：一棵 AVL 树是其每个结点的左子树和右子树的高度最多相差 1 的二叉查找树（空树的高度为-1)，这个差值也称为平衡因子（其取值可以是 1，0，-1，平衡因子是某个结点左右子树层数的差值,有的书上定义是左边减去右边，有的书上定义是右边减去左边,这样可能会有正负的区别

4、,但是这个并不影响我们对平衡二叉树的讨论).如下图 图（1)显然就是一棵平衡二叉树，它每个结点的左子树和右子树的高度最多相差 1，同时也是一棵二叉查找树，而图二虽然也是一棵二叉查找树,但是它每个结点的左子树和右子树的高度相差却到达了 2,因此不是平衡二叉树。理解了平衡二叉树的概念后,我们在思考一下，那些操作可能引起平衡发生变化呢？显然只有那些引起结点数量变化的操作才可能导致平衡被改变,也就是删除和插入操作了，如下图，我们把 6 插入到图 a 后,结构变成了图 b，这时原本的平衡二叉树就失去平衡了。显然图 b 已失去平衡，如果发生这样的情况，我们就必须考虑插入元素后恢复二叉树的平衡性质,实际上也

5、总是可以通过对树进行简单的修复来让其重新恢复到平衡，而这样的简单操作我们就称之为旋转，当然旋转也有单旋转和双旋转之分，下面我们将会一一分析，这里有点需要明白的是，无论是插入还是删除，只有那些从插入或者删除点到根结点的路径上的结点的平衡才有可能被改变，因为只有这些结点的子树才可能发生变化，所以最终也只需针对这些点进行平衡修复操作即可。平衡二叉树的设计与实现 ok，有了旋转的概念后，我们接着了解如何通过旋转来修复一棵失衡的二叉树,这里假设结点 X 是失衡点，它必须重新恢复平衡，由于任意结点的孩子结点最多有两个，而且导致失衡的必要条件是 X 结点的两棵子树高度差为 2(大于 1）,因此一般只有以下

6、4 种情况可能导致 X 点失去平衡：在结点 X 的左孩子结点的左子树中插入元素 在结点 X 的左孩子结点的右子树中插入元素 在结点 X 的右孩子结点的左子树中插入元素 在结点 X 的右孩子结点的右子树中插入元素 以上 4 种情况,其中第情况和第情况是对称的,可以通过单旋转来解决，而第种情况和第情况是对称的，需要双旋转来解决。在分析这四种情况前，我们先看看 AVL 的结点该如何设计的,其声明如下：package com。zejian.structures。Tree.AVLTree；/*Created by zejian on 2016/12/25。Blog:http：/blog。csdn。net

7、/javazejian 原文地址，请尊重原创 *平衡二叉搜索树(AVL 树)节点 */public class AVLNodeT extends Comparable public AVLNode right；/右结点 public T data；public int height;/当前结点的高度 public AVLNode（T data）this（null,null，data）;public AVLNode（AVLNode left，AVLNode right,T data）this（left,right，data，0）;public AVLNode（AVLNode left,AVLNo

8、de right，T data，int height)this.left=left；this.right=right;this。data=data;this。height=height;可以看出,为了满足平衡二叉树的特性，需要在原来的二叉搜索树(BST)的结点中添加一个height 的字段表示高度，方便我们计算,这里强调一下，高度和深度一组相反的概念,高度是指当前结点到叶子结点的最长路径，如所有叶子结点的高度都为 0，而深度则是指从根结点到当前结点的最大路径,如根结点的深度为 0。这里约定空结点（空子树)的高度为-1，叶子结点的高度为 0，非叶子节点的高度则根据其子树的高度而计算获取,如下图：

9、ok，了解上述的内容,下面就来分析 4 种可能失衡的情景.平衡二叉树的单旋转算法与实现 左左单旋转(LL)情景分析 从下图可以看出,结点 X 并不能满足 AVL 树的性质,因为它的左子树比右子树深 2 层，这种情况就是典型的 LL 情景，此时需要通过右向旋转来修复失衡的树，如图 1，X 经过右旋转后变成图 2，W 变为根结点，X 变为 W 的右子树，同时 W 的右子树变为 X 的左子树，树又重新回到平衡,各个结点的子树高度差都已在正常范围。一般情况下，我们把 X 结点称为失衡点，修复一棵被破坏的 AVL 树时，找到失衡点是很重要的并把通过一次旋转即可修复平衡的操作叫做单旋转，从图 3 和图 4

10、 可知，在原始 AVL 树插入 7 结点后，结点 9 变为失衡点，树再满足 AVL 性质,因此需要对 9 结点进行左左单旋转(即向右旋转)后，得到图 4,我们发现此时并没有操作树的根结点(6)，实际上这是因为正常情况下，不必从树的根结点进行旋转，而是从插入结点处开始,向上遍历树，并更新和修复在这个路径上的每个结点的平衡及其平衡信息(高度)即可。其代码实现如下，比较简单：/*左左单旋转（LL 旋转)w 变为 x 的根结点,x 变为 w 的右子树 param x *return /private AVLNodeT singleRotateLeft（AVLNodeT x)/把 w 结点旋转为根结点

11、AVLNode w）AVLNode x=w.right；w。right=x。left;x.left=w;/重新计算 x/w 的高度 x。height=Math.max（height(x.left）,w.height)+1;w。height=Math。max(height（w.left),height(w。right）)+1;/返回新的根结点 return x;平衡二叉树的双旋转算法与实现 前面两种情景都已分析完，它们都是基于单旋转的算法，但这种算法存在一个问题,那就是对情景无法生效，根本问题在于子树 Y 太深了，如下图所示：显然经过一次单旋转的修复后无论是 X 或者 W 作为根结点都无法符合

12、AVL 树的性质，此时就需要用双旋转算法来实现了。由于子树 Y 是在插入某个结点后导致 X 结点的左右子树失去平衡，那么就说明子树 Y 肯定是非空的，因此为了易于理解，我们可以把子树 Y 看作一个根结点和两棵子树，如下图所示:ok，明白了单旋转对于情景的窘境,下面我们就通过双旋转算法来解开这个窘境。左右双旋转(LR）情景分析 为了重新平衡，通过上述的分析显然不能把 X 根结点，而 X 与 W 间的旋转也解决不了问题,那唯一的旋转就是把 Y 作为新根。这样的话，X、W 就不得不成为 Y 的孩子结点，其中W 作为 Y 的左孩子结点，而 X 成为 Y 的右孩子结点。这里我们以下图为例来分析，为了达到

13、以上结果,需要 W、Y 进行单旋转（图 1），这里我们可把 WY 组成的子树看成前面的右右旋转情景，然后进行左向旋转，得到图 2，W 变为 Y 的左子树同时 Y 的左子树 B 变成 W 的右子树,其他不变，到此第一次旋转完成，进行第二次旋转,以 X 结点向右进行旋转(同样可看作左左情景）,由图 2 得到图 3，X 变成 Y 的右孩子结点并且 Y 的右子树 C 变成 X 的左子树，第二次旋转完成，树也重新恢复到平衡。在左右双旋转实例图 123 中，在原 AVL 树种插入结点 7 后，结点 8 变成了失衡点,此时需要把 6 结点变为根结点才能重新恢复平衡。因此先进行左向旋转再进行右向旋转，最后树恢

14、复平衡.算法代码实现如下：/*左右旋转(LR 旋转)x(根）w y 结点 把 y 变成根结点 return /private AVLNode doubleRotateWithLeft（AVLNodeT x）/w 先进行 RR 旋转 x。left=singleRotateRight(x。left)；/再进行 x 的 LL 旋转 return singleRotateLeft（x）；右左双旋转（RL)情景分析 对于右左双旋转（RL）情景和左右双旋转(LR）情景是一对镜像，旋转的原理上一样的，这里就不废话了,给出下图协助理解即可（已很清晰了）：实现代码如下：/*右左旋转（RL 旋转）param w

15、*return /private AVLNodeT doubleRotateWithRight（AVLNodeT w）/先进行 LL 旋转 w.right=singleRotateLeft(w.right);/再进行 RR 旋转 return singleRotateRight(w）；好,到此 4 种情况都已分析完毕，接着我们就利用这种四种情况来重写 AVL 树的插入操作过程。平衡二叉树插入操作的实现 实际上,有了上述四种情况后,编写插入操作的编码细节并不会太困难,这里我们给出主要思路和代码实现即可（很清晰的注释）,与 BST(二叉查找树）的插入实现原理一样，使用递归算法，根据值大小查找到插入

16、位置，然后进行插入操作，插入完成后，我们需要进行平衡判断,评估子树是否需要进行平衡修复，需要则利用上述的四种情景套入代码即可，最后要记得重新计算插入结点路径上的高度。代码实现如下：/*插入方法 param data/Override public void insert(T data）if(data=null）throw new RuntimeException(”data cant not be null”）；this。root=insert(data,root）;private AVLNodeT insert(T data，AVLNodeT p）/说明已没有孩子结点,可以创建新结点插入了.

17、if(p=nwww。sm136。comull)p=new AVLNodeT（data)；else if(data。compareTo（p。data)0）/向左子树寻找插入位置 p.left=insert（data,p.left）;/插入后计算子树的高度,等于 2 则需要重新恢复平衡，由于是左边插入，左子树的高度肯定大于等于右子树的高度 if(height(p。left)-height（p。right)=2）/判断 data 是插入点的左孩子还是右孩子 if(pareTo（p.left.data)remove(T data,AVLNodeT p)if（p=null)return null;int

18、 result=pareTo(p。data)；/从左子树查找需要删除的元素 if（resulth=1。44lognO(logn)通过上述的递推公式，我们也可以发现最少结点数的求解公式恰好符合斐波那契数列的规律（F(n）=F(n1）+F(n2)），因此求解最少结点数也就变得容易多了。接着，我们采用同样的方法计算最大结点数,为了得到最大结点数，则左右子树的高必须相等，即都填充到h-1，由于结点都充满了，那么该树不仅是 AVL 树而且还是一个完全二叉树了,则会有如下公式:N(h）=N（h-1）+N(h-1)+1=2N(h-1)+1 最终求解该递归公式得:N（h）=O(2h）=h=lognO(logn)因此在两种情况下，AVL 树的性质可以确保带有 n 个结点的 AVL 树的高度为 O(logn）。这也意味着 AVL 树的操作在时间复杂度上近乎于 O（logn)，也就不可能出现 BST（二叉查找树）的最糟糕情况 O（n）.