最新消息:我们是一群和平年代充满浮躁与抱怨的程序猿,心中充满抱负却无处撒野,明明是一匹野马,却找不到草原。

刨根问底之树结构_二叉树

技术经验 goomoon 951浏览 0评论

以前上学的时候一直觉得树结构没有实际用处,也没有好好学,只是做了简单了解,可是往往不积跬步无以至千里,工作中往往很多大的架构设计和实现都是有着最初的简单而来,所以在此沉淀一下近几年所见所知,再一个也对很多认为树结构无用论初级点的码农(其实归根到底还是不清楚树的实际用途)普及下树结构在实际生产中的用途。

下面看一个例子:

一:场景

1:现状

前几天我的一个大学同学负责的网站出现了严重的性能瓶颈,由于业务是写入和读取都是密集型,如果做缓存,时间间隔也只能在30s左右,否则就会引起客户纠纷,所以同学也就没有做缓存,通过测试发现慢就慢在数据读取上面,总共需要10s,天啊…原来首页的加载关联到了4张表,而且表数据中最多的在10w条以上,可以想象4张巨大表的关联,然后就是排序+范围查找等等相关的条件,让同学抓狂。

2:我个人的提供解决方案

① 读取问题

既然不能做缓存,那没办法,我们需要自己维护一套”内存数据库“,数据如何组织就靠我们的算法功底了,比如哈希适合单key(等于性)的查找,树结构适合多key查找(”范围查找“),lucene适合字符串的查找,我们在添加和更新的时候同时维护自己的内存数据库,最终杜绝表关联,老同学,还是先应急,把常用的表灌倒内存,如果真想项目好的话,改架构吧…

② 添加问题

或许你的Add操作还没有达到瓶颈这一步,如果真的达到了那就看情况来进行”表切分“,”数据库切分“吧,让用户的Add或者Update操作分流,虽然做起来很复杂,但是没办法,总比用户纠纷强吧,可对…

二:二叉查找树

正式切入主题,从上面的说明我们知道了二叉树非常适合于范围查找,关于树的基本定义,这里我就默认大家都知道,我就直接从查找树说起了。

1:定义

查找树的定义非常简单,一句话就是左孩子比父节点小,右孩子比父节点大,还有一个特性就是”中序遍历“可以让结点有序。

6179835620150704234021083

2:树节点

为了具有通用性,我们定义成泛型模板,在每个结点中增加一个”数据附加域”。

 

3:添加

根据查找树的性质我们可以很简单的写出Add的代码,一个一个的比呗,最终形成的效果图如下

6179835620150704235224067

这里存在一个“重复节点”的问题,比如说我在最后的树中再插入一个元素为15的结点,那么此时该怎么办,一般情况下,我们最好不要在树中再追加一个重复结点,而是在“重复节点”的附加域中进行”+1“操作。

 

4:范围查找

这个才是我们使用二叉树的最终目的,既然是范围查找,我们就知道了一个”min“和”max“,其实实现起来也很简单,

第一步:我们要在树中找到min元素,当然min元素可能不存在,但是我们可以找到min的上界,耗费时间为O(logn)。

第二步:从min开始我们中序遍历寻找max的下界。耗费时间为m。m也就是匹配到的个数。

最后时间复杂度为M+logN,要知道普通的查找需要O(N)的时间,比如在21亿的数据规模下,匹配的元素可能有30个,那么最后的结果也就是秒杀和几个小时甚至几天的巨大差异,后面我会做实验说明。

 

5:删除

对于树来说,删除是最复杂的,主要考虑两种情况。

<1>单孩子的情况

这个比较简单,如果删除的节点有左孩子那就把左孩子顶上去,如果有右孩子就把右孩子顶上去,然后打完收工。

6179835620150705000657095

<2>左右都有孩子的情况。

首先可以这么想象,如果我们要删除一个数组的元素,那么我们在删除后会将其后面的一个元素顶到被删除的位置,如图

6179835620150705000823093

那么二叉树操作同样也是一样,我们根据”中序遍历“找到要删除结点的后一个结点,然后顶上去就行了,原理跟”数组”一样一样的。

6179835620150705000935080

同样这里也有一个注意的地方,在Add操作时,我们将重复元素的值追加到了“附加域”,那么在删除的时候,就可以先判断是

不是要“-1”操作而不是真正的删除节点,其实这里也就是“懒删除”,很有意思。

=================>>>>>>下面代码只是伪代码,具体实现可以自己研究写哦<<<<<<====================

这样一个普通的二叉树就构建好了,接下来就可以写实现代码进行测试了。

具体代码如下:

经过测试:

617983562015070517045306

可以看到,构建500万的树节点,需要17秒的时间,但是查询起来花了3毫秒,同样用另外一种构建一个HashMap的结构,然后从Map里取值,所花的时间节点图如下:

6179835620150705170954028

 

经过测试,这个普通二叉树比Map结构着实快上不少,从数量级来说还不是非常明显,为什么说不是非常明显,这是因为普通的查找树的时间复杂度不是严格的log(N),在最坏的情况下会出现“链表”的形式,复杂度退化到O(N)

不过总会有解决办法的,下一篇我们继续聊如何旋转,保持最坏复杂度在O(logN)。

==============================================>>>>>>>>>

文章部分内容摘自 http://www.cnblogs.com/huangxincheng/archive/2012/07/21/2602375.html

 

转载请注明:刘召考的博客 » 刨根问底之树结构_二叉树