文档章节

AVL树-scala实现

venps
 venps
发布于 2016/02/14 14:39
字数 2307
阅读 2995
收藏 59
点赞 7
评论 8

二叉查找树已经能够很好的应用到应用程序中,但它们在最坏的情况下性能还是很糟糕。考虑到如图所示这种情况:AVL2 查找操作的性能完全等同于线性。而AVL树的查找操作,能够保证无论怎么构造它,运行时间一直对数级别的。一起来学习一下AVL树吧。

什么是AVL

AVL(Adelson-Velsky 和 Landis)树,是带有平衡条件的二叉查找树,这个平衡条件必须要容易保持,并且它保证树的深度是O(LogN).

一颗AVL树是其每个节点的左右子树节点高度最多差1的二叉查找树。

AVL1

平衡条件

我门上面说,一颗AVL树是其每个节点的左右子树节点高度最多差1的二叉查找树。 左右子树的高度最多差1便是AVL树的平衡条件。

当进行插入操作时,我们需要更新通往根节点的所有节点的平衡信息。而插入操作隐含困难的原因在于,可能会破坏AVL树的特性(例如,考虑将6插入到图1的AVL树中将会破坏节点为8的平衡条件)。如果发生这种情形,那么就要考虑在插入完成之后重新回复节点的平衡信息。事实上,总可以通过对树进行简单的修正得到,我们称其为旋转(ratation).

在插入以后,只有那些从插入点到根节点的平衡条件可能变化,因为只有这些节点的字数可能发生变化。当我们沿着这条路路径行进到根节点,可以发现一个节点它的新平衡破坏了AVL树的特性。我们需要在这个节点重新平衡这棵树。

我们把必须重新平衡的节点叫做α。因为平衡条件是高度最多相差1,那么出现不平衡就是α点的高度相差为2。容易看出这种不平衡可能出现在下面这四种情况下:

  1. 对α的左儿子的左子树进行一次插入
  2. 对α的左儿子的右子树进行一次插入
  3. 对α的右儿子的左子树进行一次插入
  4. 对α的右儿子的右子树进行一次插入

1和4,2和3 是关于α点的镜像对称。因此理论上讲只有两种情况,当然编程上还是四种情况。

第一种情况是插入发生在外边的情况(即左-左的情况或者右-右的情况),该情况是通过对树的一次单旋转来完成操作。

第二种情况是插入发生在内部的情形(即左-右的情况或者右-左的情况),该情况通过稍微复杂点的双旋转操作来处理。

单旋转

下图显示了单旋转如何调整情形1。旋转前的图在左边,旋转后的图在右边。 AVL3

让我们来分析具体的做法。节点K2不满足平衡条件, 因为它的左子树比右子树深两层(图中的虚线表示树的各层).

为使树恢复平衡,我们把节点X向上移一层,并把Z像下移一层,为此我们重新安排节点以形成一颗等价的树。如上图的右边部分。抽象的形容就是,把把树想象成一棵柔软灵活的树,抓住子节点K1,闭上眼睛使劲的摇动它,这样由于重力的作用,K1就变成了新的根。二叉树的性质告诉我们,在原树中K2>K1,这样在新树中,K2变成了K1的右儿子,Y变成了K2的左子树,而X、Z依然是K1的左子树和K2的右子树。

AVL4

让我们演示一个更长的例子,假设从初始的空的AVL树开始依次插入3、2、1,然后再依次插入4-7.

在插入关键字1的时候第一个问题就出现了,AVL性质在根处被破坏,我们在根和其左儿子之间施加单旋转操作来修正问题。下图是旋转之前和之后的两棵树。

AVL5

图中虚线连接的两个节点,它们是旋转的主体。下面我们插入关键字4这没有问题,在我们插入关键字5的时候,问题又出现了,平衡条件在关键字3处被破坏,而通过单旋转再次将问题修复。

AVL6

接下来插入6,平衡条件在根节点处被打破,因此我们在根处,在2、4之间施加一次单旋转操作。

AVL7

我们插入最后的关键字7,它导致另外的旋转。

AVL8

双旋转

单旋转对情形2、3无效愿因在于子树Y太深。单旋转没有降低它的深度。

AVL9

对于子树Y我们可以假设他有一个根和两棵子树(对应上图的K2、B、C)。

为了平衡期间,我们不能再把K3当成根了,而如上图所示K3和K1之间旋转又解决不了问题,唯一的选择是把K2当成根,这迫K1成为K2的左子树,K3成为K1的右子树,而K2的左子树成为K1的右子树,K2的右子树成为K3的左子树。容易看出最后得到的树满足AVL树的特征。

我们继续在前面例子的基础上以倒序插入10-16,接着插入8,再插入9.插入16很容易这并不破坏树的平衡,插入15会引起节点7处的高度不平衡,这属于情形3,需要通过右-左双旋转来解决。如图:

AVL10

下面我们来插入14,它也需要一个双旋转。此时修复树的旋转还是右-左双旋转

add14

如果现在插入13那么在根处就会出现不平衡,由于13不在4-7之间,我们知道只要一次单旋转就行.

add13

插入12也需要一次双旋转

add12

插入11、10都需要进行单旋转,接着我们插入8不需要进行旋转,这样就建成了一颗近乎理想的平衡树

add8

最后我们插入9,在节点10发生不平衡,这里满足情形2,对左儿子的右子树进行一次,需要一次双旋转。

after

总结

现在让我们对上面的讨论做出总结,除几种情形外,编程的细节是相当简单的。为将节点X插入AVL树T中,我们递归的将X插入到T的子树中。如果子树的高度不变,那么插入完成;如果出现高度不平衡,那么找到不平衡点,做适当的单旋转或者双旋转,更新这些高度,从而完成插入。

scala实现

sealed trait AVLTree[+A] extends Serializable {
  def balance: Int

  def depth: Int

  def contains[B >: A](x: B)(implicit ordering: Ordering[B]): Boolean

  def insert[B >: A](x: B)(implicit ordering: Ordering[B]): AVLTree[B]


  def rebalance[B >: A]: AVLTree[B]

}

/**
 * 叶子节点
 */
case object Leaf extends AVLTree[Nothing] {

  override val balance: Int = -1
  override val depth: Int = 0

  override def contains[B >: Nothing](x: B)(implicit ordering: Ordering[B]): Boolean = false



  override def insert[B >: Nothing](x: B)(implicit ordering: Ordering[B]): AVLTree[B] = {
    Node(x, Leaf, Leaf)
  }


  override def rebalance[B >: Nothing]: AVLTree[B] = this

}

case class Node[A](value: A, left: AVLTree[A], right: AVLTree[A]) extends AVLTree[A] {
  override def balance: Int = right.depth - left.depth

  override def depth: Int = math.max(left.depth, right.depth)

  override def contains[B >: A](x: B)(implicit ordering: Ordering[B]): Boolean = ???

  override def insert[B >: A](x: B)(implicit ordering: Ordering[B]): AVLTree[B] = {
    val cmp = ordering.compare(x,value)
    if (cmp < 0){
      Node(value, left.insert(x),right).rebalance
    } else if (cmp > 0){
      Node(value, left, right.insert(x)).rebalance
    } else {
      this
    }
  }

  override def rebalance[B >: A]  = {
    if (-2 == balance){
      if (1 == left.balance){
        doubleRightRotation
      } else {
        rightRotation
      }
    } else if(2 == balance) {
      if (-1 == right.balance){
        doubleLeftRotation
      }else {
        leftRotation
      }
    } else {
      this
    }
  }


  /*
   *   5
   *    \                                  6
   *     6       ---- 左单旋转 --->        /  \
   *      \                              5   7
   *       7
   *
   *   在节点5 发生不平衡 5的右节点成为新的根节点
   */
  private def leftRotation[B >: A] = {
    if (Leaf != right) {
      val r = right.asInstanceOf[Node[A]]
      Node(r.value, Node(value, left, r.left), r.right)
    } else {
      sys.error("should not happen.")
    }
  }


  /*
   *           7
   *          /                                6
   *         6    ---- 右单旋转 --->           /  \
   *        /                                5   7
   *       5
   *
   *    在节点7 发生不平衡 7的左节点成为新的根节点
   */
  private def rightRotation[B >: A] = {
    if (Leaf != left) {
      val l = left.asInstanceOf[Node[A]]
      Node(l.value, l.left, Node(value, l.right, right))
    } else {
      sys.error("should not happen.")
    }

  }

  /*
   *     左双旋转
   *
   *     5                           5
   *       \                          \                     6
   *        7    ----step1 --->        6    ---step2--->   / \
   *       /                            \                 5   7
   *      6                              7
   *
   *  在节点5处不平衡
   *  step1 : 节点5的右节点 做一次 右旋转
   *  step2 : 左旋转
   *
   */
  private def doubleLeftRotation[B >: A] = {
    if (Leaf != right) {
      val r = right.asInstanceOf[Node[A]]
      val rightRotated = r.rightRotation
      Node(rightRotated.value, Node(value, left, rightRotated.left), rightRotated.right)
    } else {
      sys.error("should not happen.")
    }
  }

  /*
  *   右双旋转
  *
  *     7                            7
  *    /                            /                   6
  *   5       ----step1 --->       6    ---step2--->   / \
  *    \                          /                   5   7
  *     6                        5
  *
  *  在节点7处不平衡
  *  step1 : 节点7的左节点 做一次 左旋转
  *  step2 : 右旋转
  *
  */
  private def doubleRightRotation[B >: A] = {
    if (Leaf != left) {
      val l: Node[A] = left.asInstanceOf[Node[A]]
      val leftRotated = l.leftRotation
      Node(leftRotated.value, leftRotated.left, Node(value, leftRotated.right, right))
    } else sys.error("Should not happen.")
  }

}

参考资料

《数据结构与算法分析java语言描述》 AVL tree (维基百科)

© 著作权归作者所有

共有 人打赏支持
venps
粉丝 7
博文 2
码字总数 3885
作品 0
朝阳
高级程序员
加载中

评论(8)

venps
venps

引用来自“Neo”的评论

不是说查找多用AVL,写入较多就用RB吗?
查询密集型,AVL性能优于RB,因为AVL是更严格的平衡。但通常使用RB,能获得更好的性能
Neo
Neo
不是说查找多用AVL,写入较多就用RB吗?
邹海彬
邹海彬
avl维持平衡,可能需要经过多次旋转,但是rbtree只需要最多经过3次旋转——我听说的
young7
young7

引用来自“行意天下”的评论

实际中怎么用?

引用来自“venps”的评论

AVL是高度平衡的二叉树,维护这种高度平衡的代价相对较大,一般是用追求局部而不是非常严格整体平衡的红黑树来替代。红黑树的应用比较多,比如 java中的TreeMap和TreeSet。
很多资料都说avl代价比较大,因此用rb,但是我找了很久也没有找到精确分析avl在旋转时候究竟怎么代价大的,反倒是觉得rb比avl难多了
二的基本算合格
二的基本算合格
写这个要赞一下~
Jordan
Jordan
好东西
venps
venps

引用来自“行意天下”的评论

实际中怎么用?
AVL是高度平衡的二叉树,维护这种高度平衡的代价相对较大,一般是用追求局部而不是非常严格整体平衡的红黑树来替代。红黑树的应用比较多,比如 java中的TreeMap和TreeSet。
行意天下
行意天下
实际中怎么用?
会X86汇编的帮我看看为什么debug和release结果时间相差那么多

下面输出是我实现的avl树和三叉搜索树的字符串搜索性能比较结果,avl cmp times为avl树的字符比较次数,tst cmp times为三叉搜索树的字符比较次数。从结果来看release与debug都一样的比较次数...

cut
2012/11/10
455
7
花时间分别实现了AVL,SBT,Treap,RBT,还是有些收获的

发现AVL(平衡二叉树)和SBT(据说是国内某天才少年创造的宽度平衡二叉树),在数学上和树的构成上是完全等价的,SBT完全可以说是AVL的变种,创新之处在于使用统计(宽度)代替了高度,因此可...

刘地
2012/10/12
503
4
一文读懂 AVL 树

背景 AVL 树是一棵平衡的二叉查找树,于 1962 年,G. M. Adelson-Velsky 和 E. M. Landis 在他们的论文《An algorithm for the organization of information》中发表。 所谓的平衡之意,就是...

超级数学建模
01/02
0
0
JDK TreeMap Red-Black Tree

介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas 和 Robert Sedgewi...

zuoer
2011/12/18
0
0
java集合框架(四):TreeMap

TreeMap的数据结构与HashMap、LinkedHashMap不同,其整个结构就是一颗红黑树,所以我们要研究TreeMap就得先从红黑树开始。对于红黑树的算法,我在本文章不详细展开,有兴趣的同学可以点击这里...

chenzanjin
2017/11/07
0
1
数据结构与算法之10(AVL自平衡二叉树与RB红黑树)

本节继续总结二叉树的变种,上节里的哈夫曼树是一种独特的二叉树,用于编解码会比较有效。这里的两种树都是BST二叉搜索树的加强版。 》BST二叉搜索树的弱点 我们之前也提到了,当插入序列是有...

kkae8643150
2017/12/01
0
0
二叉树-你可能需要知道这些

一直以来,我都很少使用也避免使用到树和图,总觉得它们神秘而又复杂,但是树在一些运算和查找中也不可避免的要使用到,那么今天我们就鼓起勇气来学习下树,争取在被问到和使用时不再那么怂。...

24K男
2017/10/10
0
0
学习数据结构 二叉查找树(binary search tree)

为学习 LLVM 的 ImmutableSet,其底层的实现选择为 AVL 树(平衡二叉搜索树),我不很熟悉该树,虽然大致知道但毕竟不精,因此还是先学习学习二叉搜索树吧。 二叉搜索树或叫做二叉查找树,可...

刘军兴
2012/03/16
0
2
MIT Introduction to Algorithms 学习笔记(七)

Lecture 6: Balanced Binary Search Trees AVL树 定义: AVL树是自平衡二叉查找树, 每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1. 平衡(Balance):平衡最坏的情况是每个节点高度差...

hyaicc
2016/01/04
21
0
学习 LLVM(20) ImutAVLTree 和 ImutAVLFactory

ImmutableSet 比较复杂,前面我们先了解了二叉查找树(binary search tree), AVL tree 才能理解其实现机制。这里先从其底层实现的 AVL 树节点,AVL 树操作工厂类开始,它们分别是 ImutAVLTre...

刘军兴
2012/03/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Laravel5.5 MySQL配置、读写分离及操作

Laravel 让连接不同数据库以及对数据库进行增删改查操作: 参考:http://laravelacademy.org/post/854.html 配置读写分离 应用的数据库配置位于 config/database.php(但是数据库用户及密码等...

MichaelShu
8分钟前
0
0
Linux 查看用户

存储帐号的文件:/etc/passwd 存储密码的文件:/etc/shadow 查看当前系统所有用户 grep bash /etc/passwd root修改普通用户的密码 sudo passwd user_name 然后连续两次输入新的用户密码即可...

yeahlife
15分钟前
0
0
Webpack使用nodemon实时打包编译

业务场景: 1.编写一个npm组件包并且link到了项目文件中 2.需要不断的修改并run build编译npm包并且在项目run dev 查看效果 3.问题: 每次改完npm包都要手动run build编译十分的麻烦且低效,可不...

JamesView
26分钟前
0
0
电脑炸了,浪费我好几天时间,还是简要记下来吧

我的小本本一直在兢兢业业的干活,然而前几天说炸就炸了...... 爆炸现场: 软件: windows10 pro + EIS11+ 360卫士 BIOS:N1DET98W 2.24 硬件: Xeon E3 1505-V5 nv-M3000M thinkpadP70:20E...

Oh_really
30分钟前
0
0
Git之branch和checkout

1.branch是查看、创建、删除分支 #>git branch --helpNAME git-branch - List, create, or delete branchesSYNOPSIS git branch [--color[=<when>] | --no-color] [......

汉斯-冯-拉特
32分钟前
0
0
Mybatis拦截器之数据权限过滤与分页集成

需求场景 最近项目有个数据权限的业务需求,要求大致为每个单位只能查看本级单位及下属单位的数据,例如:一个集团军下属十二个旅,那么军级用户可以看到所有数据,而每个旅则只能看到本旅部...

佛系程序猿灬
41分钟前
9
0
SpringCloud 微服务 (十六) 服务追踪 Zipkin

问题 在服务中,有一个接口,该A接口中又调用了其他服务的B、C、D接口,出现一个请求耗时大的问题,这时候并不知道该B、C、D接口中哪个接口造成的耗时量,然后比如确定C服务接口出现的耗时量大,但...

___大侠
今天
0
0
Java面试基础篇——第八篇:抽象类与接口的区别

1.抽象类 抽象类:如果一个类中包含有抽象方法,或这个类使用abstract关键字修饰,则称这个类是抽象类。 抽象方法是什么呢?抽象方法就是指用abstract关键字修饰的方法。 需要注意的是:抽象...

developlee的潇洒人生
今天
2
0
jsoup 相关资料

1.jsoup 2.Jsoup概述 3.jsoup入门 4.jsoup Java HTML Parser 1.11.3 API

IT追寻者
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部