专栏首页老沙课堂据结构与算法(十) AVL树

据结构与算法(十) AVL树

平衡二叉树来源

二叉搜索树的复杂度分析

和高度有关

O(h) = O(logn)

最坏复杂度是从小到大添加节点 (和链表差不多)

O(h) = O(n)

如何二叉搜索树退化成链表??

让添加删除搜索的复杂度维持在logn

平衡(Balance)

当节点固定时,左右字数高度就越接近,这颗二叉树就越平衡

理想平衡

最理想的平衡,例如 完全二叉树,满二叉树

如何改进二叉搜索树

因为无法改变添加删除顺序(用户操作决定),所以在每次操作之后,让二叉树达到平衡状态。

•用最少的调整次数达到适度的平衡既可。

平衡二叉搜索树(Balanced Binary Search Tree)

简称BBST

常见的平衡二叉搜索树有

•AVL树•红黑树•C++ STL(map set)•Java中的TreeMap、TreeSet、HashMap、HashSet•Linux 的进程调度•Ngix的timer

一般称他们为:自平衡的二叉搜索树(Self-Balance Binary Search Tree)

AVL树

介绍:

最早发明的自平衡二叉树之一

取名为G.M.Adelson-Velsky和E.M.Landis(来自苏联的科学家) 两个人的名字称呼

平衡因子:某节点的左右子树高度差

特点:

•每个节点的左右高度差不超过1•搜索、添加、删除的时间复杂度为O(logn)

LL- 右旋转(单旋)

•注意维护T3、2、3的 parent的属性•以及更新2、3的高度

LL右旋转.gif

RR-左旋转

•注意维护T3、3、4的 parent的属性•以及更新3、4的高度

RR-左旋转

LR-RR左旋转,LL右旋转(双旋)

•首先对 LR的进行中的2 进行 RR左旋转

•对旋转后对3进行LL右旋转参考上方LL右旋转

RL-LL右旋转,RR左旋转(双旋)

•参考上方LR-RR左旋转,LL右旋转(双旋)。方法即是LR的对称

删除导致失衡

•只可能导致父节点或者祖先节点(只有一个)失衡(原因是因为 失衡因子= 子节点相减)

LL\RR\LR\RL情况:

•极端情况 所有的祖先节点都会失衡 共(logn)次调整

解决方式:

在删除后进行平衡操作

删除

让父节点恢复失衡后,可能导致更高节点的祖先接点失衡(最多需要log(n)次调整)

添加:

添加会导致所有祖先节点都失衡

处理:只要让最低失衡节点回复平衡,整棵树就恢复平衡(O(n))

解决方式:

添加后进行平衡操作

时间复杂度

搜索:平均时间复杂度O(logn)

添加:平均时间复杂度O(logn) O(1)次旋转

删除:平均时间复杂度O(logn) O(logn)次旋转

private void rebalance(Node<E> grand) {
  Node<E> parent = ((AVLNode<E>)grand).tallChild();
  Node<E> node = ((AVLNode<E>)parent).tallChild();
  if (parent.isLeftChild() ) { //L
    if (node.isLeftChild()) {//LL
      rotateRight(grand);
    }else { //LR
      rotateLeft(parent);
      rotateRight(grand);
    }
  }else {//R
    if (node.isLeftChild()) { //RL
      rotateRight(parent);
      rotateLeft(grand);
    }else {//RR
      rotateLeft(grand);
    }
  }
}

private void rotateLeft(Node<E> grand) {
  Node<E> parent = grand.right;
  Node<E> child = parent.left;
  grand.right = child;
  parent.left = grand;

  afterRotate(grand, parent, child);
}

private void rotateRight(Node<E> grand) {

  Node<E> parent = grand.left;
  Node<E> child = parent.right;

  grand.left = child;
  parent.right = grand;
  afterRotate(grand, parent, child);

}
// 旋转后更新操作
private void afterRotate(Node<E> grand,Node<E> parent, Node<E> child) {
  parent.parent = grand.parent;

  if (grand.isLeftChild()) {
    grand.parent.left = parent;    
  }else if (grand.isRightChild()){
    grand.parent.right = parent;
  }else {
    root = parent;
  }
  if (child != null) {
    child.parent = grand;
  }
  grand.parent = parent;

  updateHeight(grand);
  updateHeight(parent);
}

本文分享自微信公众号 - 老沙课堂(gh_f73a6b772d4f),作者:沙睿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • RunLoop详解

    线程刚创建的时候没有Ru nLoop对象,RunLoop会在第一次获取它的时候创建

    老沙
  • 浅入深出Copy和mutableCopy

    由Tagged Pointed 可以知道a b 为Tagged Pointer 对象 想深入了解的的可以看一下我的上一篇文章

    老沙
  • 数据结构与算法(九)二叉搜索树的删除操作

    •前驱节点:中序遍历时的前一个节点•如果左子树存在,从该节点的左子节点的最右的节点。•如果左子树 == null && 父节点!= null 父节点为父节点遍历...

    老沙
  • 平衡二叉树 AVL树结构详解 [Java实现]

    https://blog.csdn.net/zhang6622056/article/details/82698859

    纯洁的微笑
  • 平衡二叉树 AVL树结构详解 [Java实现]--源码部分

    https://blog.csdn.net/zhang6622056/article/details/82698859

    纯洁的微笑
  • 在myeclipse安装beyond插件

    myeclipse自带的比较工具感觉是有一些看不清晰,也不是太方便处理,然后就找了个比较插件了。

    @坤的
  • 深入理解红黑树

    前面的文章已经介绍过二叉搜索树,AVL树,以及2-3Tree,今天我们再来学习一下二叉搜索树里面的大佬,它就是红黑树。红黑树(英语:Red–black tree...

    我是攻城师
  • psacct

    psacct或ACCT都是在系统上监控用户活动的开源应用程序。 这些应用程序在后台运行,并跟踪系统上的每个用户活动以及正在使用的资源。

    胡齐
  • 英方软件挂牌,云灾备市场容量或将大爆发|新三板

    成立于 2011 年 8 月 12 日的上海英方软件股份有限公司,于 2015 年 8 月 26 日完成股。2016 年 7 月 7 日成功登陆新三板。 200...

    人称T客
  • HBase框架基础(一)

    HBase的基础框架,将分成几个章节对HBase进行描述,不当之处还望大家批评指正。下面是了解HBase基础架构的第一部分。

    大数据和云计算技术

扫码关注云+社区

领取腾讯云代金券