java数据结构与算法之平衡二叉树AVL树的设计与实现Word文档格式.docx
《java数据结构与算法之平衡二叉树AVL树的设计与实现Word文档格式.docx》由会员分享，可在线阅读，更多相关《java数据结构与算法之平衡二叉树AVL树的设计与实现Word文档格式.docx（16页珍藏版）》请在冰点文库上搜索。
③在结点X的右孩子结点的左子树中插入元素
④在结点X的右孩子结点的右子树中插入元素
以上4种情况，其中第①情况和第④情况是对称的，可以通过单旋转来解决，而第②种情况和第③情况是对称的，需要双旋转来解决。
在分析这四种情况前，我们先看看AVL的结点该如何设计的，其声明如下：
packagecom.zejian.structures.Tree.AVLTree;
/**
*Createdbyzejianon2016/12/25.
*Blog:
[原文地址,请尊重原创]
*平衡二叉搜索树（AVL树）节点
*/
publicclassAVLNode<
TextendsComparable>
{
publicAVLNode<
T>
left;
//左结点
right;
//右结点
publicTdata;
publicintheight;
//当前结点的高度
publicAVLNode（Tdata）{
this（null,null,data）;
}
publicAVLNode（AVLNode<
left,AVLNode<
right,Tdata）{
this（left,right,data,0）;
right,Tdata,intheight）{
this.left=left;
this.right=right;
this.data=data;
this.height=height;
}
可以看出，为了满足平衡二叉树的特性，需要在原来的二叉搜索树（BST）的结点中添加一个height的字段表示高度，方便我们计算，这里强调一下，高度和深度一组相反的概念，高度是指当前结点到叶子结点的最长路径，如所有叶子结点的高度都为0，而深度则是指从根结点到当前结点的最大路径，如根结点的深度为0。
这里约定空结点（空子树）的高度为-1，叶子结点的高度为0，非叶子节点的高度则根据其子树的高度而计算获取，如下图：
ok~，了解上述的内容，下面就来分析4种可能失衡的情景。
平衡二叉树的单旋转算法与实现
左左单旋转（LL）情景①分析
从下图可以看出，结点X并不能满足AVL树的性质，因为它的左子树比右子树深2层，这种情况就是典型的LL情景，此时需要通过右向旋转来修复失衡的树，如图1，X经过右旋转后变成图2，W变为根结点，X变为W的右子树，同时W的右子树变为X的左子树，树又重新回到平衡，各个结点的子树高度差都已在正常范围。
一般情况下，我们把X结点称为失衡点，修复一棵被破坏的AVL树时，找到失衡点是很重要的并把通过一次旋转即可修复平衡的操作叫做单旋转，从图3和图4可知，在原始AVL树插入7结点后，结点9变为失衡点，树再满足AVL性质，因此需要对9结点进行左左单旋转（即向右旋转）后，得到图4，我们发现此时并没有操作树的根结点（6），实际上这是因为正常情况下，不必从树的根结点进行旋转，而是从插入结点处开始，向上遍历树，并更新和修复在这个路径上的每个结点的平衡及其平衡信息（高度）即可。
其代码实现如下，比较简单：
*左左单旋转（LL旋转）w变为x的根结点,x变为w的右子树
*@paramx
*@return
privateAVLNode<
singleRotateLeft（AVLNode<
x）{
//把w结点旋转为根结点
AVLNode<
w=x.left;
//同时w的右子树变为x的左子树
x.left=w.right;
//x变为w的右子树
w.right=x;
//重新计算x/w的高度
x.height=Math.max（height（x.left）,height（x.right））+1;
w.height=Math.max（height（w.left）,x.height）+1;
returnw;
//返回新的根结点
右右单旋转（RR）情景④分析
接着再来看看右右单旋转（RR）的情景，如下图，可以发现与左左单旋转的情况恰好是一种镜像关系，同样结点X并不能满足AVL树的性质，在这样的情景下，需要对X结点进行左旋转来修复树的平衡，如图1经左旋转后变了图2，此时X变为了根结点，W变为X的左孩子，X的左子树变为W的右子树，而树又重新恢复了平衡。
如图3和图4的实例情景，原始的AVL树在12处插入结点18后，结点10就变成了失衡点，因为10的左子树和右子树的高度相差2，显然不符合AVL树性质，需要对结点10进行右右单旋转修复（向左旋转），然后得到图4，此时树重新回到了平衡，这便是右右单旋转（RR）的修复情景。
代码实现如下：
*右右单旋转（RR旋转）x变为w的根结点,w变为x的左子树
singleRotateRight（AVLNode<
w）{
x=w.right;
w.right=x.left;
x.left=w;
x.height=Math.max（height（x.left）,w.height）+1;
w.height=Math.max（height（w.left）,height（w.right））+1;
//返回新的根结点
returnx;
平衡二叉树的双旋转算法与实现
前面两种情景都已分析完，它们都是基于单旋转的算法，但这种算法存在一个问题，那就是对情景②③无法生效，根本问题在于子树Y太深了，如下图所示：
显然经过一次单旋转的修复后无论是X或者W作为根结点都无法符合AVL树的性质，此时就需要用双旋转算法来实现了。
由于子树Y是在插入某个结点后导致X结点的左右子树失去平衡，那么就说明子树Y肯定是非空的，因此为了易于理解，我们可以把子树Y看作一个根结点和两棵子树，如下图所示：
ok~，明白了单旋转对于情景②③的窘境，下面我们就通过双旋转算法来解开这个窘境。
左右双旋转（LR）情景②分析
为了重新平衡，通过上述的分析显然不能把X根结点，而X与W间的旋转也解决不了问题，那唯一的旋转就是把Y作为新根。
这样的话，X、W就不得不成为Y的孩子结点，其中W作为Y的左孩子结点，而X成为Y的右孩子结点。
这里我们以下图为例来分析，为了达到以上结果，需要W、Y进行单旋转（图1），这里我们可把WY组成的子树看成前面的右右旋转情景，然后进行左向旋转，得到图2，W变为Y的左子树同时Y的左子树B变成W的右子树，其他不变，到此第一次旋转完成，进行第二次旋转，以X结点向右进行旋转（同样可看作左左情景），由图2得到图3，X变成Y的右孩子结点并且Y的右子树C变成X的左子树，第二次旋转完成，树也重新恢复到平衡。
在左右双旋转实例图123中，在原AVL树种插入结点7后，结点8变成了失衡点，此时需要把6结点变为根结点才能重新恢复平衡。
因此先进行左向旋转再进行右向旋转，最后树恢复平衡。
算法代码实现如下：
*左右旋转（LR旋转）x（根）wy结点把y变成根结点
doubleRotateWithLeft（AVLNode<
//w先进行RR旋转
x.left=singleRotateRight（x.left）;
//再进行x的LL旋转
returnsingleRotateLeft（x）;
右左双旋转（RL）情景③分析
对于右左双旋转（RL）情景和左右双旋转（LR）情景是一对镜像，旋转的原理上一样的，这里就不废话了，给出下图协助理解即可（已很清晰了）：
实现代码如下：
*右左旋转（RL旋转）
*@paramw
doubleRotateWithRight（AVLNode<
//先进行LL旋转
w.right=singleRotateLeft（w.right）;
//再进行RR旋转
returnsingleRotateRight（w）;
好~，到此4种情况都已分析完毕，接着我们就利用这种四种情况来重写AVL树的插入操作过程。
平衡二叉树插入操作的实现
实际上，有了上述四种情况后，编写插入操作的编码细节并不会太困难，这里我们给出主要思路和代码实现即可（很清晰的注释），与BST（二叉查找树）的插入实现原理一样，使用递归算法，根据值大小查找到插入位置，然后进行插入操作，插入完成后，我们需要进行平衡判断，评估子树是否需要进行平衡修复，需要则利用上述的四种情景套入代码即可，最后要记得重新计算插入结点路径上的高度。
*插入方法
*@paramdata
*/
@Override
publicvoidinsert（Tdata）{
if（data==null）{
thrownewRuntimeException（"
datacan\'
tnotbenull"
）;
this.root=insert（data,root）;
insert（Tdata,AVLNode<
p）{
//说明已没有孩子结点,可以创建新结点插入了.
if（p==ull）{
p=newAVLNode<
（data）;
}elseif（pareTo（p.data）<
0）{//向左子树寻找插入位置
p.left=insert（data,p.left）;
//插入后计算子树的高度,等于2则需要重新恢复平衡,由于是左边插入,左子树的高度肯定大于等于右子树的高度
if（height（p.left）-height（p.right）==2）{
//判断data是插入点的左孩子还是右孩子
if（pareTo（p.left.data）<
0）{
//进行LL旋转
p=singleRotateLeft（p）;
}else{
//进行左右旋转
p=doubleRotateWithLeft（p）;
}elseif（pareTo（p.data）>
0）{//向右子树寻找插入位置
p.right=insert（data,p.right）;
if（height（p.right）-height（p.left）==2）{
if（pareTo（p.right.data）<
//进行右左旋转
p=doubleRotateWithRight（p）;
p=singleRotateRight（p）;
else
;
//ifexistdonothing
//重新计算各个结点的高度
p.height=Math.max（height（p.left）,height（p.right））+1;
returnp;
//返回根结点
平衡二叉树删除操作的实现
关于平衡二叉树的删除，我们这里给出一种递归的实现方案，和二叉查找树中删除方法的实现类似，但是在移除结点后需要进行平衡检测，以便判断是否需要进行平衡修复，主要明白的是，这种实现方式在删除时效率并不高，不过我们并不打算过多讨论它，更复杂的删除操作过程将放在红黑树中进行讨论。
下面给出实现代码：
*删除方法
*@paramdata
publicvoidmove（Tdata）{
this.root=remove（data,root）;
*删除操作
*@paramp
remove（Tdata,AVLNode<
if（p==null）
returnnull;
intresult=pareTo（p.data）;
//从左子树查找需要删除的元素
if（result<
p.left=remove（data,p.left）;
//检测是否平衡
currentNode=p.right;
//判断需要那种旋转
if（height（currentNode.left）>
height（currentNode.right））{
//LL
}else{
//LR
//从右子树查找需要删除的元素
elseif（result>
p.right=remove（data,p.right）;
currentNode=p.left;
if（height（currentNode.right）>
height（currentNode.left））{
//RR
//RL
//已找到需要删除的元素,并且要删除的结点拥有两个子节点
elseif（p.right!
=null&
&
p.left!
=null）{
//寻找替换结点
p.data=findMin（p.right）.data;
//移除用于替换的结点
p.right=remove（p.data,p.right）;
else{
//只有一个孩子结点或者只是叶子结点的情况
p=（p.left!
=null）?
p.left:
p.right;
//更新高度值
if（p!
=null）
平衡二叉树的最少结点数和最多结点数问题
关于最少结点数和最多结点数的问题，为了方便理解和简单化问题，这里我们假设AVL树的高度是h，N（h）表示高度为h的AVL树的结点数。
对于求解高度为h的AVL树的最少结点数，则应该尽可能用最少结点数来填充该树，现在假设左子树填充到的高度为h-1，根据AVL树的特性，右子树的高度只能填充到h-2，因此高度为h的AVL树的最小结点数为：
N（h）=N（h-1）+N（h-2）+1
其中：
N（h-1）代表高度为h-1的左子树的最小结点数
N（h-2）代表高度为h-2的右子树的最小结点数
1代表当前结点（根）。
求解上述递归公式可得（计算过程涉及线性代数的知识点，这里就不详细分析求解过程，毕竟我们主要求时间复杂度相关问题）其中n是AVL树的节点数：
N（h）=O（1.618h）=>
h=1.44logn≈O（logn）
通过上述的递推公式，我们也可以发现最少结点数的求解公式恰好符合斐波那契数列的规律（F（n）=F（n-1）+F（n-2）），因此求解最少结点数也就变得容易多了。
接着，我们采用同样的方法计算最大结点数，为了得到最大结点数，则左右子树的高必须相等，即都填充到h-1，由于结点都充满了，那么该树不仅是AVL树而且还是一个完全二叉树了，则会有如下公式：
N（h）=N（h-1）+N（h-1）+1=2N（h-1）+1
最终求解该递归公式得：
N（h）=O（2h）=>
h=logn≈O（logn）
因此在两种情况下，AVL树的性质可以确保带有n个结点的AVL树的高度为O（logn）。
这也意味着AVL树的操作在时间复杂度上近乎于O（logn），也就不可能出现BST（二叉查找树）的最糟糕情况O（n）。
升级会员 