种树系列一：AVL树

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

基本打算是从《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等等）取代，算是一滴时代的眼泪。