【数据结构】AVL二分查找树

0xAA55

查找树，是一种用一个标签（key）来代表一个数据，然后使用这个标签来检索它对应的特定数据的一种数据结构。


（龙血树  图片来源：sunsinger/Shutterstock）

顺着树根上去，然后根据标签来判断该往哪个分叉走，再在下一个分叉通过标签判断该往哪一个分叉走。这就是查找树。


（图片来源：https://yourbasic.org/algorithms/binary-search-tree/）

二分查找树（Binary Search Tree），则是一种利用二分法来加快数据查找的查找树。原理上来说，我们可以把二分查找树的查找过程，理解成猜数字的过程。

我心里想一个数，从零到4294967295之间。你猜我想的是哪个数，我告诉你大了还是小了。

想必大家小时候应该都玩过这个游戏。

使用二分查找树的时候，查找数据所需的最大次数和标签的长度对应，如果你的标签是一个32位整数（比如之前所说的从零到4294967295之间这个范围。或者对于有符号整数而言是从-2147483648到2147483647的范围之间），你的查找次数最多就只需要32次。这远比数组一个个遍历判断效率多了（如果不考虑CPU缓存的话），因为你的查找次数等于这个数组的长度，时间复杂度是O(n)。

虽然对于数据的查找而言，二分查找树的优化效果已经十分明显了。但我们所说的二分查找树依然可以继续优化，那就是保证它的平衡性。

而AVL二分查找树，则是一帮名字缩写叫“AVL”的几个毛子（Adelson, Velski & Landis）在上个世纪六十年代就搞出来的一种自平衡树，而且被一直沿用至今。它的树根的两个树杈重量基本相同，这样可以保证查找速度快而且稳定。

AVL在每个节点上记录自己的层数，并递归记录子节点的层数。然后可以通过比对子节点的层数差，来判断树是否平衡。然后对不平衡的情况下的树，进行旋转操作，也就是按照不同的顺序来交换节点，从而使其对称。

除了AVL树，还有红黑树。红黑树的查找速度比AVL树慢一些，然后插入和删除的速度比AVL树快一些。这是一个微小的差异。

AVL二分查找树的实现已经基本相同，但不同的人有不同的代码书写风格，并且对于查找数据的过程中使用的标签，和它对应的数据，都需要在代码层面上定义它们的类型。于是就有了不同的AVL树的代码实现。

考虑到查询的速度以及对应平台的存储能力等，我认为标签应该被定义为size_t类型，或者ssize_t类型，或者ptrdiff_t类型等。只要和处理器平台的指针长度挂钩即可。

至于对应数据的存储方式，其实有很多种，比如在给每个节点分配内存的时候，多分配一些，然后存储到节点数据的后面。C语言可以这样做。这样每个节点在包含了查找树的必须内容（自己的标签和左、右两个分叉）的同时，直接带了自己的数据。又比如，每个节点再来一个void *指针，存储一个新分配的内存用于存储对应数据。此时要注意，在删除节点的同时，你也要对这些数据进行恰当的释放方式来释放。

请在GitHub上查看我编写的AVL二分查找树的实现：
https://github.com/0xAA55/avlbst

另外，VB6也可以使用AVL二分查找树。VB6玩AVL树的时候，有个特别有意思的地方，那就是你可以在监视窗口看到整棵树的布局：



有人说“AVL树太难了！”但其实这就是一个用来查找或者存储数据的一个东西，理解成“字典”或者“数据库”就行。
我用VB6实现的这个二分查找树也就只有这么几个方法，使用起来应该算是比较直观的：



此外，对于认为VB6无法不通过API来使用指针从而无法不通过API来使用链表的人们：请了解一下VB6的“类”这个概念。



请在GitHib上查看VB6版的AVL二分查找树的实现：
https://github.com/0xAA55/avlbst_vb6

Golden Blonde

2009年还在用WIN7！！！