tnblog
首页
视频
资源
登录

平衡二叉树-旋转的四种情况 05

4160人阅读 2022/6/15 17:45 总访问:1432662 评论:0 收藏:0 手机
分类: Java集合

平衡二叉树-旋转的四种情况

左左、左右、右右、右左

1、左左

当根节点左子树的左子树有节点插入,导致二叉树不平衡

如将图一添加节点1变成图二的样子


1.2、我们可以根据右旋定义来使图二变成平衡二叉树
右旋∶将根节点的左侧往右拉,左子节点变成了新的父节点,并把多余的右子节点出让,给已经降级根节点当左子节点
2、左右

当根节点左子树的右子树有节点插入,导致二叉树不平衡
如将图一添加节点6变成图二的样子


变成图二的样子后,此时光一个右旋是不够的,要先左旋再右旋
2.1先将图三紫色部分左旋变成图四的样子
左旋∶就是将根节点的右侧往左拉,原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点

2.2、再将图四整体右旋得到图五
右旋∶将根节点的左侧往右拉,左子节点变成了新的父节点,并把多余的右子节点出让,给已经降级根节点当左子节点
3、右右

当根节点右子树的右子树有节点插入,导致二叉树不平衡

如将图一添加节点12变成图二的样子

3.1、将上面图二右旋得到平衡二叉树图三

4、右左

当根节点右子树的左子树有节点插入,导致二叉树不平衡

如将图一添加节点8变成图二的样子


变成图二的样子后,此时光一个右旋是不够的,要先右旋再左旋
4.1先将图三紫色部分右旋变成图四的样子

4.2再将图四整体左旋得到图五

评价
没有个性,不需要签名
排名
6
文章
6
粉丝
16
评论
8
{{item.articleTitle}}
{{item.blogName}} : {{item.content}}
ICP备案 :渝ICP备18016597号-1
网站信息:2018-2024TNBLOG.NET
技术交流:群号656732739
联系我们:contact@tnblog.net
公网安备:50010702506256
欢迎加群交流技术