AVL树研究与实现

开篇：润墨网以专业的文秘视角，为您筛选了一篇AVL树研究与实现范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：计算机最广为人知的优点之一是其能储存大量的数据，如今随着时代的发展，储存容量更是犹如日进千里一般极速扩展，大容量的硬盘、U盘早已随处可见。然而，要在巨大的数据中搜索出需要的内容却不是一件容易的事，由此，为了能减少在搜索储存数据上的开销，各种适应于不同访问搜索背景的数据结构应运而生。树，便是计算机学科中最基本的数据结构之一，提供了快速的储存和访问性能。该文探究了带有平衡条件的二叉查找树――avl树的原理，并对其使用C语言进行了实现。

关键词：数据结构；平衡二叉查找树；AVL树

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）07-1532-04

对于大量的输入数据，普通的线性数据结构访问时间太慢，例如，对于一个有N个数据的线性数据结构，假设对每个数据的访问几率大致相同，每个数据每次访问有1/N的机会被访问，由于是线性数据，因此每个数据的访问花销可以经过一定的排列，最通常的是访问第一个数据花销1个单位时间，第二个2个单位时间，第三个3各单位时间……第N个N各单位时间，于是访问一次的平均花销为（N+[N2]）/2N = （1+N）/ 2，用计算机专业的符号来说，其访问运行时间可以用O（N）来表示，即访问一次线性数据结构的花销在N这个数量级上。使用树这一数据结构可将访问花销将至logN这个数量级上，也即O（logN），这里logN是以二为底的N的对数。可以对比一下，若N=1267650600228229401496703205376，则logN=100。数字越大，则O（N）与O（logN）相差越大。

一般来说，计算机学科中使用的最基本的树为二叉查找树，下图是一颗二叉树的简单示意图：

图1 二叉树示意图

二叉查找树则是在二叉树的基础上得来。假设在一颗二叉树中，每个节点都有一个关键词值，并且关键词值都是互异且可以比较，若对于此二叉树中的每个节点，其左子树中所有节点的关键词值小于其本身关键词值，其右子树中所有关键词值大于其本身关键词值，则此二叉树为二叉查找树。

AVL树，则是最先发明的带有平衡条件的二叉查找树。

下面，就让我们来分析一下AVL树的思想和原理。

1 AVL树思想和原理

正如上所述，AVL树是一种带有平衡条件的二叉查找树。那么，这个平衡条件是什么呢？

对于二叉查找树这样的数据结构来说，由于其节点有着按顺序排列的性质，若有数据往此数据结构中插入，则可能会引起树的高度过高，使得访问数据的花销可能会比应有的要多。

例如，对于只有一个节点X的二叉查找树，若此后往树中插入的元素其关键词值皆小于X的关键词值，那么这棵树的左子树就会越来越庞大，最终访问一个比X小得多的数据可能会花费相当多的开销，而如果在插入数据到一定程度时选择X的左子树中适当的节点作为根节点，则情况会好得多。

如上所述的即是平衡条件，即使得树的深度不致过于深，让左子树和右子树的高度相差不宜过大。同时，从应用的角度来说，这个平衡条件必须容易实现，并且应该允许能够易如反掌地对数据结构进行如插入数据、删除数据这样的常见操作。

1.1 AVL树的思想与原理

对于一颗AVL树来说，其平衡条件是要求其每个节点的左子树和右子树的高度最多差一。例如，在图2中，左边的树为AVL树，右边的则不是：

据资料显示，一个AVL树的高度平均来说只有1.44log（N+2） 1.328，并且其实际上的高度只比logN多一点，这样的访问花销是比较高效的。

那么，AVL树是如何实现这个平衡条件的呢？很幸运，这个解决方法并不难。事实上，我们是可以通过足够简单的对树的修改来做到。

1.2 AVL树的旋转操作

在对一颗AVL树进行插入数据或者删除数据的操作时，我们通过一种称之为“旋转”的操作来保持树的左右子树之差。由于对像二叉查找树这样本身已经包含排列性质的数据结构的修改，一般来说只有插入数据和删除数据是常用的，所以在这作者只使用插入数据来分析AVL树的旋转操作，删除数据可以依理推知。

同时，由于插入节点后，只有那些从插入点到根节点路径上的节点的平衡性会改变，所以在对树进行操作以更新平衡时，能找到这样一个节点，它破坏了平衡性，但是可以对它进行操作使得树重新变得平衡。

现在假设这个破换平衡的节点为W。可知，根据AVL树的定义可知，此时W的左子树和右子树的高度差为二，并且这种造成不平衡的插入操作会有如下四种情况：

1）对W的左儿子的左子树进行一次插入；

2）对W的右儿子的右子树进行一次插入；

3）对W的左儿子的右子树进行一次插入；

4）对W的右儿子的左子树进行一次插入。

可以看出，1）和2）是一个镜像关系，3）和4）也是一个镜像关系，因此，从理论的角度来说实际上只有两种情况。

对于1）和2）的情形，可以使用“单旋转”来恢复平衡。

单旋转的操作示意图如下：

可以看到，在这个示意图中，节点k2扮演着W的角色，其左子树与右子树的高度差为2，并且再插入包含新数据的新节点之前，k2满足AVL树的平衡条件。于是为了恢复平衡，对k1和k2及其左右子树进行操作。在示意图中，是以k1取代k2作为根节点，将Y变成了k2的左子树，并将此时的k2作为k1的右儿子。

对于其镜像情形的操作也是一样，在此就不赘述。

而对于3）和4）的情形，则必须使用双旋转操作来保持树的平衡。例如，可以根据如下示意图来说明：

在这个情形中，对于以k1为根节点的树来说，其高度比树D多二，问题发生在k1的右子树，更准确的说，是发生在B或C，具体哪个不要紧，因为都有可能，所以此处将B和C画得一样高。

对于这种情形，可以像示意图那样改变根节点，并且将k1、k2、k3的左右子树进行交换而使树重新得到平衡。

对于其镜像情况也可以使用相同的技巧使树的平衡得到保持，在此就不赘述。

可以看出，对于这两种情况，一次旋转足以解决问题，因此，其效率能够在接受的范围之内，并且易于实现。

下面，作者使用C语言对AVl树这一数据结构进行了实现。

2 AVL树的C语言实现

作者使用C语言对AVL树的节点、获取节点所在高度函数、数据节点的插入函数、左右单旋转函数、左右双旋转函数以及以中序遍历在屏幕上显示节点信息函数等进行了实现。

2.1 AVL树节点实现

由前文分析可知，要实现的AVL树节点包含四个元素，即节点的关键词值，指向左儿子的指针以及指向右儿子的指针，此外，还需有一个记录节点高度的元素用以判断平衡状态。可以使用一个结构来表示节点，其源代码如下：

2.2 AVL树获取节点高度函数实现

获取节点的高度比较容易，只需返回节点中保存的高度信息即可，唯一要注意的是若是一颗空树，则返回-1这个高度。源代码如下：

2.3 AVL树插入元素函数实现

向AVL树中插入元素即使用一般的向二叉查找树中插入元素的操作即可，唯一要注意的是需修改节点高度信息，若平衡被破坏则使用两种旋转对树进行修改。其源代码如下：

2.4 左右单旋转函数实现

左右单旋转函数的过程可以按上文所分析的来实现，左右单旋转只是互为镜像。

右单旋转的源代码如下：

2.5 左右双旋转函数实现。

从上文中的分析可知，双旋转可以看成两次使用单旋转，因此，双旋转函数可以调用两次相对应的单旋转函数来实现。

右双旋转函数源代码如下：

2.6 中序遍历函数实现

中序遍历是一种常用的遍历树这一数据结构的方法。此顺序先访问节点中的信息，再递归访问节点左子树中节点的信息，最后递归访问右子树节点中的信息。

其源代码如下：

以上，便是作者使用C语言实现的有关AVL树的所有源代码，其他操作如删除元素等可以依原理推知。

3 总结

本文分析了AVL树的思想与原理，并根据其特点，结合C语言的特性，对AVL树和一系列的操作进行了实现。

AVL树是最早出现的数据结构之一，大大提高了访问数据的效率，也为以后数据结构的发展起着开拓性的作用。虽然如今计算机的性能越来越匪夷所思，计算速度简直无法想象，访问速度早已大有提升，但毫无疑问，使用良好的数据结构依然对提高访问速度有着举足轻重的作用。

参考文献：

[1] Robert Sedgewick.算法：C语言实现[M].北京：机械工业出版，2009.

[2] Ellis Horowitz，Sartaj Sahni，Susan Anderson-Freed.数据结构（C语言版）[M].北京：机械工业出版社，2006.

[3] Mark Allen Weiss.数据结构与算法分析[M]. 北京：人民邮电出版社，2005.

[4] Sesh Venugopal.数据结构：从应用到实现（Java版）[M]. 北京：机械工业出版社，2008.

[5] Adam Drozdek.数据结构与算法：Java语言版 [M]. 2版.北京：机械工业出版社，2006.