gpt4 book ai didi

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

转载 作者:qq735679552 更新时间:2022-09-28 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章平衡二叉树的左右旋以及双旋转的图文详解由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

高度平衡的搜索二叉树 。

一棵平衡树,或是空树,或是具有以下性质的二叉搜索树:左子树和右子树都是avl树,且左右子树的高度之差的绝对值不超过1。  。

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

该二叉树,根结点的右子树高度为3,左子树高度为2。结点上方的数字为平衡因子,因为右子树高度比左子树高度大1,所以根结点的平衡因子为1.

一颗平衡二叉树,如果有n个结点,其高度可保持o(log2^n),平均搜索长度也可以保持在o(log2^n) 。

平衡化旋转  。

avl树相较于普通的二叉搜索树,自主要的就是做了平衡化处理,使得二叉树变的平衡,高度降低.

在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改,当平衡因子大于1时,就需要进行平衡化处理。从发生不平衡的结点起,沿刚才回溯的路径取直接下两层的结点,如果这三个结点在一条直线上,则采用单旋转进行平衡化,如果这三个结点位于一条折线上,则采用双旋转进行平衡化.

单旋转 。

左单旋 。

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

动图演示,图片内容可以无视,看懂操作进行了 。

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

将右子树的左子树链接到父亲节点的右孩子结点,父亲节点作为ptr结点的左孩子结点便完成了旋转 。

右单旋 。

右单旋是左单旋的镜像旋转.  。

当前节点ptr,与父亲节点和当前节点的左孩子结点位于一条直线上时,使用右单旋进行平衡.

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

双旋转 。

先左后右双旋转 。

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

当在ptr的左子树的右子树中插入一个结点后,造成了ptr平衡因子为-2的不平衡,将ptr向下找到当前结点的左孩子的右孩子,先进行左单旋ptr->left = subl,然后将ptr的右子树断开指向subr,此时便完成了旋转,最后将平衡因子进行更新.

先右后左双旋转 。

先右单旋再左单旋,是先左后右的镜像旋转,这里就不做赘述了.

总结 。

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我的支持。如果你想了解更多相关内容请查看下面相关链接 。

原文链接:https://blog.csdn.net/qq_43193797/article/details/85124138 。

最后此篇关于平衡二叉树的左右旋以及双旋转的图文详解的文章就讲到这里了,如果你想了解更多关于平衡二叉树的左右旋以及双旋转的图文详解的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com