技术宅的结界

 找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 115|回复: 0
收起左侧

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

[复制链接]

1038

主题

2307

帖子

5万

积分

用户组: 管理员

一只技术宅

UID
1
精华
216
威望
286 点
宅币
17830 个
贡献
35614 次
宅之契约
0 份
在线时间
1706 小时
注册时间
2014-1-26
发表于 2019-4-28 07:15:34 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有帐号?立即注册→加入我们

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

dragons-blood-tree.jpg.838x0_q80.jpg
(龙血树  图片来源:sunsinger/Shutterstock

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

tree.png
(图片来源: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树的时候,有个特别有意思的地方,那就是你可以在监视窗口看到整棵树的布局:

20190427224800.png

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

avlbst.png

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

20190428080850.png

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

本帖被以下淘专辑推荐:

本版积分规则

QQ|申请友链||Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号|网站地图

GMT+8, 2019-5-21 07:29 , Processed in 0.104028 second(s), 41 queries , Gzip On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表