立即登录 马上注册
首页 › 开发帮助文档 › 编程语言 › 平衡二叉树的左右旋以及双旋转的图文详解 ...

赞

评论

收藏

[Java] 平衡二叉树的左右旋以及双旋转的图文详解

编程语言 编程语言 发布于：2021-10-05 22:12 | 阅读数：438 | 评论：0

今天小编就为大家分享一篇关于平衡二叉树的左右旋以及双旋转的图文详解，小编觉得内容挺不错的，现在分享给大家，具有很好的参考价值，需要的朋友一起跟随小编来看看吧
高度平衡的搜索二叉树
一棵平衡树，或是空树，或是具有以下性质的二叉搜索树：左子树和右子树都是avl树，且左右子树的高度之差的绝对值不超过1。
DSC0000.png

该二叉树，根结点的右子树高度为3，左子树高度为2。结点上方的数字为平衡因子，因为右子树高度比左子树高度大1，所以根结点的平衡因子为1。
一颗平衡二叉树，如果有n个结点，其高度可保持o(log2^n),平均搜索长度也可以保持在o(log2^n)
平衡化旋转
avl树相较于普通的二叉搜索树，自主要的就是做了平衡化处理，使得二叉树变的平衡，高度降低。
在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改，当平衡因子大于1时，就需要进行平衡化处理。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点，如果这三个结点在一条直线上，则采用单旋转进行平衡化，如果这三个结点位于一条折线上，则采用双旋转进行平衡化。
单旋转
左单旋
DSC0001.jpg

动图演示，图片内容可以无视，看懂操作进行了
DSC0002.jpg

将右子树的左子树链接到父亲节点的右孩子结点，父亲节点作为ptr结点的左孩子结点便完成了旋转
右单旋
右单旋是左单旋的镜像旋转.
当前节点ptr，与父亲节点和当前节点的左孩子结点位于一条直线上时，使用右单旋进行平衡。
DSC0003.jpg

双旋转
先左后右双旋转
DSC0004.jpg

当在ptr的左子树的右子树中插入一个结点后，造成了ptr平衡因子为-2的不平衡，将ptr向下找到当前结点的左孩子的右孩子，先进行左单旋ptr->left = subl，然后将ptr的右子树断开指向subr，此时便完成了旋转，最后将平衡因子进行更新。
先右后左双旋转
先右单旋再左单旋，是先左后右的镜像旋转，这里就不做赘述了。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对CodeAE代码之家的支持。如果你想了解更多相关内容请查看下面相关链接
原文链接：https://blog.csdn.net/qq_43193797/article/details/85124138

关注下面的标签，发现更多相似文章
免责声明：

1. 本站所有资源来自网络搜集或用户上传，仅作为参考不担保其准确性！

2. 本站内容仅供学习和交流使用，版权归原作者所有！© 查看更多

3. 如有内容侵害到您，请联系我们尽快删除，邮箱：kf@codeae.com

分享到： QQ好友和群QQ好友和群 QQ空间QQ空间

举报

返回列表
相关帖子
avatar
3416 经验
3415 文档
OPNE在线字典
  • 手机版| 免责声明|
2021-2024  版权所有：CodeAE代码之家   
粤ICP备2023096576号-2