种树系列一:AVL树

作者: shad0w_walker(admin) 分类: 种树系列 发布时间: 2015-07-22 13:25 ė 6 2条评论

又要开始紧张刺激的一波数据结构和算法的学习之旅了,先从种树开始!

基本打算是从《Data Structures and Algorithm Analysis》开始看起,结合一些大牛的博客或者模板,希望这个暑假能有所收获!


 

平衡二叉树(Balanced Binary Tree),是二叉查找树的一个进化体,满足二叉查找树的性质,并且对于任意一个节点,它的左子树深度与右子树深度差值不大于1,这样就能保证对一个节点的插入、删除、查找操作能够在\(O(\log{N})\)复杂度内实现。

实现平衡二叉树的一种方式就是AVL。AVL核心的操作就是树节点的旋转,当插入或删除一个节点后,左右子树高度差大于1,不满足平衡树的性质时,就需要进行旋转。旋转分为单旋转和双旋转两种,而对应于左右子树又分为四个函数实现:

1、左左单旋(函数SingleRotateLeft)

2、右右单旋(函数SingleRotateRight)

3、左右双旋(函数DoubleRotateLR)

4、右左双旋(函数DoubleRotateRL)

关于旋转具体操作的方式,基本讲到AVL的书上都会有详细的图解,在此我就不暴露我的语言表达水平了。虽然AVL的操作很容易理解,但我实现AVL的过程确是艰难的。首先是指针,对于见到指针就头疼的我竟然用指针写了一次AVL,其次是递归函数的写法,最后是删除节点的操作,删除操作一直ACCESS_VIOLATION,写的我都快崩溃了,最后我找到了这篇博客,参考了一下他的思想,谢天谢地最后执行起来貌似终于没bug了。

给上HDOJ的几道关于AVL的题目吧

 

HDOJ2193 AVL Tree

这道题求\(n\)个节点的AVL树最大深度,根据AVL最小节点数\(f(n)\)与深度\(n\)的递推关系\(f(n)=f(n-1)+f(n-2)+1\)可以得到。

点击此处展开代码

 

HDOJ4006 The kth greater number

在插入中动态查询第k大,正好是AVL所支持的操作。但由于这道题的k是给定不变的,所以是道可以用优先队列秒杀的水题,插入保证优先队列中有小于等于k个元素,查询就是取堆顶元素。

附上我的代码,其中用类封装了AVL,写了插入和查询两个操作

点击此处展开代码

 

HDOJ5249 KPI

需要三个操作,插入、删除、查询中间值,在上题AVL类的基础上添加了删除操作,删除操作有两种,一种是把整个节点删除,另一种是把单个节点的计数值减一(frequence–),所以看上去比较累赘。但这道题保证所有数字不同,似乎不需要第二种删除,不过我还是把两种操作都写了,当做可能有相同数字来处理。还记得第一次做这道题的时候贴了Treap的模板,虽然我还不会Treap。。。模板大法好啊!

点击此处展开代码

 

最后:

AVL应该是一个比较古老也比较基础的算法了吧,它的很多操作早就被速度更快的其他算法(例如伸展树、红黑树以及上面提到的Treap等等)取代,算是一滴时代的眼泪。

 

本文出自shad0w_walker,转载时请注明出处及相应链接。

本文永久链接: https://www.sdwalker.com/archives/313.html

2条评论

  1. Natureal 2015年7月27日 16:05 回复

    Orz GKP 神犇 …

    1. shad0w_walker(admin)
      shad0w_walker(admin) 2015年7月27日 16:38 回复

      Orz 鹏巨带我啊。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回顶部