我们知道引入树是为了提高数据存储,读取的效率。可是有的二叉树并不能提高效率,例如下面的这个树。
![](https://img-blog.csdnimg.cn/c1dc8ba52b704f898b8cfad20c9232a4.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6IuP56a-5ZGA,size_20,color_FFFFFF,t_70,g_se,x_16)
这是一种极端的情况,实际上它已经和链表一样了,现在对它进行查询,时间复杂度已经成为了O(n)。而我们为了避免这种情况的出现,就引入了平衡二叉树。
平衡二叉树是在有序二叉树的基础上保证左右子树的高度差不超过1。
那我们如何把一个不平衡的有序二叉树变成平衡的有序二叉树呢?答案当然就是:旋转。
而旋转又分为4种:LL,LR,RL,RR。
那如何判断是哪种旋转类型呢?
- 找到不平衡的节点;
- 找到因为它的插入而造成树不平衡的节点;
- 让不平衡的节点向造成不平衡的节点走两步,怎么走的就是什么类型。
下面咱们就来分别讨论这四种旋转方式。
LL型旋转
![](https://img-blog.csdnimg.cn/76e57b806e914f86889633dceb83d778.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6IuP56a-5ZGA,size_20,color_FFFFFF,t_70,g_se,x_16)
- 将不平衡节点(A)的左子节点(B)提升为新的根节点;
- 将原来的不平衡节点(A)降为B的右子节点;
- 将剩下的各子树按照大小关系连接。
例子
![](https://img-blog.csdnimg.cn/827cde4b94f24fdcb16457852087a7a7.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6IuP56a-5ZGA,size_20,color_FFFFFF,t_70,g_se,x_16)
RR型旋转
RR型旋转和LL型旋转类似。
![](https://img-blog.csdnimg.cn/33556efb7c9a48bd986cdb11a436a4f6.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6IuP56a-5ZGA,size_20,color_FFFFFF,t_70,g_se,x_16)
- 将不平衡节点(A)的右子节点(B)提升为新的根节点;
- 将原来的不平衡节点(A)降为B的左子节点;
- 将剩下的各子树按照大小关系连接。
例子
![](https://img-blog.csdnimg.cn/bc206342bd8a4c5f8883284a51dc143a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6IuP56a-5ZGA,size_20,color_FFFFFF,t_70,g_se,x_16)
LR型旋转
![](https://img-blog.csdnimg.cn/1fc53e30414743488ce1a3f4b96d36d0.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6IuP56a-5ZGA,size_20,color_FFFFFF,t_70,g_se,x_16)
- 将B的右子节点提升为新的根节点;
- 将原来的根节点降为现在根节点(C)的右子节点;
- 将各子树按照大小关系连接。
例子
![](https://img-blog.csdnimg.cn/dbdf6e3bf2374ced9dc453f12b81f7ab.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6IuP56a-5ZGA,size_20,color_FFFFFF,t_70,g_se,x_16)
RL型旋转
RL型旋转和LR型旋转类似。
![](https://img-blog.csdnimg.cn/41919d2d095e4a78b18ee127a160cc51.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6IuP56a-5ZGA,size_20,color_FFFFFF,t_70,g_se,x_16)
- 将B的左子节点提升为新的根节点;
- 将原来的根节点降为现在根节点(C)的左子节点;
- 将各子树按照大小关系连接。
例子
![](https://img-blog.csdnimg.cn/34e7c1de9d2247e680611efc411bced3.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6IuP56a-5ZGA,size_20,color_FFFFFF,t_70,g_se,x_16)
最后来一个综合的练习吧。
将列{25,27,30,12,11,18,14,20,15}构建成一个平衡有序二叉树。
![](https://img-blog.csdnimg.cn/a0565163d59d4e8b93401e7e5570a324.gif)
![](https://img-blog.csdnimg.cn/91850e7bef3a46a580ddc8bc0057eada.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6IuP56a-5ZGA,size_20,color_FFFFFF,t_70,g_se,x_16)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)