您好,欢迎来到站长目录(28sn.com)!


平衡二叉树插入操作的详细过程图解

来源:网络整理 浏览:308次 时间:2020-09-21
二叉搜索树/二叉排序树/二叉查找树
  • 是二叉树、任意结点的左子树的值均小于根节点的值,右子树均大于根节点的值
  • 没有键值相等平衡二叉树(AVL树)
  • 定义
    • 左右字数的高度差的绝对值不超过1,并且两子树都是平衡二叉树
    • 没有键值相等
    • 高度差,又名平衡因子,范围为[-1,0,1],在此规定==平衡因子 bf = 右子树的高度-左子树的高度==
  • 插入操作
    1. 当有新的结点插入之前,该树一定是一个平衡二叉树
    2. 按照普通搜索树的方式插入结点cur
    3. 插入之后,调整cur的 parent.bf:插入到左边 bf --;插入到右边 bf++;
    4. bf变为3种值:
      (1)0:插入结束
      (2)-1/1:调整 bf 的过程向上蔓延
      (3 )-2/2:进行修复,
    5. 对失衡的情况进行修复
    6. 插入完成之后,该树依然是一个平衡二叉树
  • 具体步骤
    • 通过查找,找到key的合适的位置并将key插入(如果已经存在,则放弃查找)
    • 设置并修改平衡因子

      • 设置新插入的结点 cur 的平衡因子,新插入的结点的平衡因子是 0(未调整的),因为一定插入在叶子结点
      • 修改 cur 的父节点 parent 的平衡因子 bf
        • 如果cur是parent的左子树,parent.bf -= 1
        • 如果cur是parent的右子树,parent.bf += 1
      • 修改parent.bf 之后,parent.bf 的取值范围为 [-2,-1,0,1,2]
      • 具体情况如下表:
        在这里插入图片描述

      • 对表格的进一步说明(此处的bf一律指parent.bf):
        • 当bf修改之前是 -1或者 1 ,修改之后变为 0 时,即在父节点的子树高度较小的那一边插入了新结点,使得父结点的左右子树一样高,说明本次插入对整棵树的高度是没有影响的,即其他结点的平衡因子不会改变,因此插入结束
        • 举个栗子:在这里插入图片描述
        • 当bf修改之前是 0 ,修改之后是 -1 或 1 时,即插入之后导致父结点的左右子树高度差1,说明这棵子树的所有父结点的左右子树的高度都有变化,因此其他结点的平衡因子会发生改变,需继续向上调整
        • 举个栗子:在这里插入图片描述
        • 当bf修改之前是 -1或 1,修改之后是 -2 或 2时,即插入之后父结点的左右子树高度差2,已经失衡,需要将当前 parent 进行调整,使之再次保证平衡,进而参考上表做出下一步操作
        • 举个栗子:在这里插入图片描述
    • 失去平衡的调整方法:
      • 解决失衡的方法口诀
        • 左左失衡,parent右旋;
        • 左右失衡,cur左旋,parent右旋;
        • 右右失衡,parent左旋;
        • 右左失衡,cur右旋,parent左旋;
      • 解析:parent为当前失衡的结点,cur为parent的孩子(新结点所在的子树的根节点)
      • eg:在这里插入图片描述
      • 四种失衡状态:
        在这里插入图片描述在这里插入图片描述
      • 很明显:如果从根节点到新插入的结点是一路向左,即左左失衡;如果中途向右了,即左右失衡;如果一路向右,即为右右失衡;如果中途向左了,即右左失衡;
      • 根据不同的失衡,口诀中有不同的解决方法,接下来我们一起来验证一下吧:
        • ”左左失衡,parent右旋“:
        • 在这里插入图片描述
      • “左右失衡,cur左旋,parent右旋”:
      • 在这里插入图片描述
      • “右右失衡,parent左旋”:
      • 在这里插入图片描述
        • “右左失衡,cur右旋,parent左旋”:
        • 在这里插入图片描述
    • 调整之后,该树还是一个平衡二叉树

推荐站点

  • 我爱发烧音乐我爱发烧音乐

    我爱发烧音乐囊括了从流行音乐到古典音乐多个类型的音乐作品,专栏推荐最新的音乐,提供音乐排名榜单!可供免费线上收听音乐,歌曲流畅,音效极佳! 网站提供的钢琴以及二胡专栏,可供收听者,陶冶情操,改善心情,是难得的轻音乐典藏!

    www.520fs.com
  • 世纪音乐网世纪音乐网

    世纪音乐网是专业的在线音乐试听MP3下载网站。歌曲总计30余万首,收录了网上最新歌曲和流行音乐,DJ舞曲,非主流音乐,经典老歌,劲舞团歌曲,搞笑歌曲,儿童歌曲,英文歌曲等。是您上网听歌的最佳网站。

    www.ssjj.com
  • 怒江大峡谷网怒江大峡谷网

    怒江大峡谷网内容包括:新闻、要闻、怒江报、视频、文化、民俗、人文、音乐、政务、公告、政策等地方信息。

    www.nujiang.cn
  • 杭州网杭州网

      杭州网是杭州地区唯一的新闻门户网站,由中共杭州市委宣传部、杭州日报报业集团和杭州广播电视集团共同组建的杭州网络传媒有限公司运营。

    www.hangzhou.com.cn
  • 深圳在线深圳在线

      深圳在线 www.szol.net是深圳本地最大、最早的地方生活资讯网站之一,网站名“深圳在线www.szol.net”由南方报业传媒集团编辑委员会总编辑、南方日报社总编辑、南方都市报总编辑、南方书画院名誉院长王春芙亲笔题名,深圳在线www.szol.net团队与深圳热线www.szonline.net、奥一网www.oeeee.com都源于全国最早成立于1996年的知名网络公司——深圳万用网。

    www.szol.net

鄂公网安备 42062502000001号