首页 > 代码库 > 数据结构(七)之树

数据结构(七)之树

二叉查找树查找插入和删除的时间复杂度都为O(log N)。但它有个弊端。如果输入的数据是排序数据,那么代价巨大,因为树将只由那么没有左(或右)儿子的节点组成。一种解决方法是找平衡条件:任何节点的深度不能过深。最老的一种平衡查找树,即AVL树。另外,较新的方法是放弃平衡条件,允许树有任何的深度,但是在每次操作之后要使用一个调整规则进行调整,使得后面的操作效率更高,这是自调整类结构,例如伸展树。

1. AVL树

AVL树是每个节点的左子树和右子树的高度最多差1的二叉查找树。除去可能的插入外,所有的树查找都可以以时间O(log N)执行。插入一个节点要靠旋转来修正:旋转有两种情况,一是插入发生在“外边的情况”,通过单旋转来调整。二是发生在“内部”的情形,通过“双旋转”来实现。除旋转引起的局部变化外,编程人员必须记住:树的其他部分必须知晓该变化。


对AVL树的删除多少要比插入复杂,如果删除操作相对较少,那么懒惰删除恐怕是最好的策略。

2. 伸展树

伸展树的基本想法是,当一个节点被访问后,它就要经过一系列AVL树的旋转被放到根上。另外,伸展树还不要求保留高度或平衡信息。
保证从空树开始任意连续M次对树的操作最多花费O(Mlog N)的时间。
展开思路:从底部向上沿着访问路径旋转。如果X的父节点是树根,那么我们只要旋转X和树根。这是最后的旋转。如果出现之字型,则像AVL那样双旋转。如果出现一字型,则将左边的树变换成右边树。


我们可以通过访问要删除的节点实行删除操作。将节点推到根处,然后找到左子树中最大的元素然后旋转到左子树下,此时的左子树没有右儿子,我们将可以使右子树称为右儿子从而结束删除。对于伸展树分析很困难,但编程要比AVL树简单得多,这是因为要考虑得情形少许并且没有平衡信息需要存储。

3. B树

迄今为止,我们始终假设可以把整个数据结构存储到计算机的主存中。可是,如果数据太多主存装不下,那么就意味着必须把数据结构放在磁盘上。此时,因为大O模型不再使用,所以导致规则发生了变化。
一棵M叉查找树可以有M路分支,随着分支增加,树的深度在减少。一颗完全M叉树的高度约为logMN
B树是平衡M-路树,是常用的查找树。
阶为M的B-树定义:

> 数据项存储在树叶上
> 非叶节点存储直到M-1个键,以指示搜索的方向;键i代表子树i+1中得知最小的键
> 树的根或者是一片树叶,或者其儿子数在2到M之间
> 除根外,所有非树叶节点的儿子数在[M/2]到M之间
> 所有的树叶都在相同的深度上并有[L/2]和L之间个数据项

L=5时,

4阶B-树称为2-3-4树,3阶B-树叫做2-3树。


B-树的深度最多是[logM/2N],我们执行O(log M)时间的工作量以确定选择哪个分支(使用折半查找),但是Insert和Delete运算可能需要O(M)的工作量来调整该节点该节点上的所有信息,因此,对于每个Insert和Delete,最坏情形的运行时间为O(MlogMN)=O((M/logM)logN)。不过,对于一次Find只花费O(log N)的时间。经验指出,从运行时间考虑,M的最好选择是M=3或4。
B-树实际用于数据库系统,在那里树被存储在物理的磁盘上而不是主存中。一般来说,对磁盘的访问要比任何的主存操作慢几个数量级。如果我们使用M-阶B-树,那么磁盘访问次数是O(logMN)。虽然每次磁盘访问花费O(logM)来确定分支的方向,但是执行该操作的时间一般比读存储器的区块所花费的时间少得多。

总结

我们已经看到树在操作系统、编译器设计以及查找中的应用。表达式树是更一般结构即所谓的分析树的一个小例子,分析树是编译器设计中的核心数据结构。查找树在算法设计中是非常重要的。它们几乎支持所有有用的操作。查找树的非递归实现多少要快一些,但是递归实现更讲究、更精彩,而且易于理解和除错。查找树的问题在于,其性能严重的依赖于输入,而输入则是随机的。不改变树的操作都可以使用标准二叉查找树的程序。改变树的操作必须将树恢复。在伸展树中的节点可以达到任意深度,但是在每次访问之后树又以多少有些神秘的方式被调整。任意连续M次操作花费O(M log N)的时间,它与平衡树花费的时间相同。B-树是平衡M-路树,它能很好的匹配磁盘。其特殊情形是2-3树,它是实现平衡查找树的另一种常用方法。在实践中,所有平衡树方案的运行时间都不如简单二叉查找树省时。