数据结构与算法—我来带你征服恐惧已久的AVL树(二叉平衡树) AVL树概念 前面学习二叉查找树和二叉树的各种遍历，但是其查找效率不稳定(斜树)，而二叉平衡树的用途更多。查找相比稳定很多。(欢迎数据结构专栏)AVL树是带有平衡条件的二叉查找树。这个平衡条件必须要。而且要保证它的深度是O(logN).AVL的条件是左右树的高度差（）不大于1；并且它的每个子树也都是平衡二叉树。对于平衡二叉树的最小个数，;;;(求法可以类比斐波那契！) 难点：AVL是一颗二叉排序树，用什么样的规则或者规律让它能够在复杂度不太高的情况下实现动态平衡呢？
不平衡概况 
如果简单的以单节点看，大致有上面情形，并且他们的最后结果也是有的有所相近。只是：上下会变动。该在左面的还在左面，改在右面的还在右面。
这只是针对在底部，对于可能出现的平衡要首先搞清楚：
所以针对四种不平衡，可能出现在底部，也可能出现在头，也可能出现在某个中间节点导致不平衡。而我们只需要研究其首次不平衡点，解决之后整棵树即继续平衡。当然，在实际解决肯定会带上的思想解决问题。 四种平衡旋转方式 RR平衡旋转(左单旋转) 
出现这种情况的原因是节点的右侧的右侧较深这时候点需要。再细看过程。再左旋的过程中，节点下沉，上浮.而其中的右侧依然不变。它上浮左侧所以需要指向(毕竟一棵树)。但是这样原来左侧节点空缺。而我们需要仍然让整个树完整并且满足二叉排序树的规则。而刚好本来oldroot右侧指向newroot变成oldroot被newroot左侧指向。所以，刚好这个位置在oldroot的右侧。在newroot的左侧。.所以我们将H插入在这个位置。其中H可能为NULL。不过不影响操作！
而左旋的代码可以表示为：代码语言：javascript复制 LL平衡旋转(右单旋转) 而右旋和左旋相反，但是思路相同，根据上述进行替换即可！
代码：代码语言：javascript复制 RL平衡旋转(先右后左双旋转) 产生不平衡的条件原因是：，使得.这个与我们前面看到的左旋右旋不同的是因为它的结构不能直接变一下就可以完成。因为对于右左结构，中间的最大，两侧的最小。但是下面的比上面大()所以如果平衡的话，那么应该在中间，而应该。原来的root在左侧。所以节点的变化浮动比较大，而且需要妥善处理各个子节点的移动使其满足二叉排序树的性质！期间考虑树高度变化即可！ 这种双旋转其实也很简单。不要被外表唬住。基于前面的单旋转，双旋转有具体。 思路1：两次旋转RR,LL
根据上图所圈的，先对底部使得底部的大小关系变化，使其在满足二叉平衡树的条件下还满足RR结构的二叉树。所以只需要对,再对ROOT进行左旋即可。 思路2：直接分析 根据初始和结果的状态，然后分析各个节点变化顺序。手动操作这些节点即可！首先根据三个节点变化。R.L肯定要在最顶层。左右分别指向ROOT和R。那么这其中发生变化(原来分别是R,L和R)暂时为空。而刚好根据左右大小关系可以补上。这样思考整棵树也可以完成平衡，但是要考虑树的高度变化。
代码为：(注释部分为方案1)代码语言：javascript复制 LR平衡旋转(先左后右单旋转) 根据上述RL修改即可
代码语言：javascript复制 java代码实现 首先对于节点多个属性。用于计算高度(平衡因子)插入是递归插入。递归一个来回的过程，去的过程进行插入。回的过程进行高度更新。和检查是否平衡。不要写全局递归计算高度，效率太低下。事实上高度变化只和插入和平衡有关，仔细考虑即不会有疏漏！ github地址：https://github.com/javasmall/oj-problem-java/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/src/%E4%BA%8C%E5%8F%89%E6%A0%91/AvlTree.java bigsai的github地址(javasmall) 总结 测试情况：
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/81542.html
