0xAA55 发表于 2019-4-28 07:15:34

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

查找树,是一种用一个标签(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 发表于 2019-7-30 23:35:26

2009年还在用WIN7!!!
页: [1]
查看完整版本: 【数据结构】AVL二分查找树