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

数据结构(七)之树

二叉查找树查找插入和删除的时间复杂度都为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树,它是实现平衡查找树的还有一种经常用法。

在实践中,全部平衡树方案的执行时间都不如简单二叉查找树省时。

数据结构(七)之树