二叉排序树(二叉查找树)- 数据结构和算法73

二叉排序树(二叉查找树)

让编程改变世界

Change the world by program

先给大家讲个故事吧 ~

话说有两个年轻人正在深山中行走。忽然发现远处有一只老虎正在虎视眈眈,随时都有可能冲过来,怎么办呢?

其中一个小菇凉赶紧弯腰系鞋带,另一个奇怪地问:“你系鞋带干什么?你不可能跑得比老虎还快吧?”系鞋带的小菇凉说:“我有什么必

要跑赢老虎呢?我只要跑得比你快就行了。”

呃,这真是交友不慎啊!可是大家知道故事的结局吗?

后来老虎真的跑来了,系鞋带者拼命跑,另一个人则急中生智,爬到了树上。老虎在选择爬树还是追人之间,当然是会选择后者,于是结果

大家可想而知了……

宽客网,量化投资,宽客俱乐部

爬树者改变了跑的思想,这一改变何等重要,甚至捡回了自己的一条命。

好了,这个故事告诉我们什么呢?告诉我们所谓的优势只不过是比别人多深入思考一点而已。

假设,查找的数据集是普通的顺序存储,那么插入操作就是将记录(注:我们这里说的记录就相当于元素的意思)放在表的末端,给表记录

数加一即可,删除操作可以是删除后,后边的记录向前移动。

有朋友说这样的删除操作太慢,因为数据集没有什么顺序,所以其实你也可以直接将要删除的元素与最后一个元素调换一下位置,然后把记

录数减一即可。

宽客网,量化投资,宽客俱乐部

二叉排序数(Binary Sort Tree)又称为二叉查找树,它或者是一棵空树,或者是具有下列性质的二叉树:

若它的左子树不为空,则左子树上所有结点的值均小于它的根结构的值;

若它的右子树不为空,则右子树上所有结点的值均大于它的根结构的值;

它的左、右子树也分别为二叉排序树(递归)。

宽客网,量化投资,宽客俱乐部

…… 省略,具体请看视频讲解 ……

视频下载 备用视频下载