小蚂蚁学习数据结构(34)——平衡二叉树的概念
小蚂蚁学习数据结构(34)——平衡二叉树的概念
嗜学如命的小蚂蚁 发表于2年前
小蚂蚁学习数据结构(34)——平衡二叉树的概念
  • 发表于 2年前
  • 阅读 196
  • 收藏 6
  • 点赞 1
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

摘要: 平衡二叉树的概念

平衡二叉树的作用

    由于二叉排序树的结构可能不平衡,导致对树的运算的时间复杂度增加。

    调整二叉排序树的结构,使其始终成为平衡的状态——平衡二叉树。

平衡二叉树的定义

    若一个二叉树中每个结点的左右子树的高度至多相差1,则称此树为平衡树

平衡因子

    二叉树中的每个结点的左子树高度减去右子树高度。

    平衡树中的每个结点的平衡因子只能是:1、0、-1

平衡二叉树的构造思路

    在构造平衡二叉树的过程中,每当插入一个结点时,首先检查是否因为插入而破坏了树的平衡性,若是,则找出其中最小不平衡子树,在保持排序树特性的前提下,调整最小不平衡子树中个结点之间的链接关系,以达到新的平衡。

最小不平衡子树

    以离插入结点最近,且平衡因子绝对值大于1的结点作为根的子树。

需要对最小不平衡树进行调整

调整方法四种方式:

    1,单向右旋平衡处理:

        在左子树根节点的左子树上插入结点,可以进行一次向右的顺时针旋转操作。

    2,单向左旋平衡处理:

        在右子树根节点的右子树上插入结点,可以进行一次向左的逆时针旋转操作。

    3,双向旋转(先左后右)

        在左子树的右子树上插入结点,先进行一次左的逆时针旋转,再进行一次向右的顺时针旋转。

    4,双向旋转(先右后左)

        在右子树的左子树上插入结点,先进行一次右的顺时针旋转,再进行一次向左的逆时针旋转。


    学PHP的小蚂蚁 博客 http://my.oschina.net/woshixiaomayi/blog



标签: 数据结构
共有 人打赏支持
粉丝 132
博文 161
码字总数 100864
×
嗜学如命的小蚂蚁
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: