`

【查找结构6】动态查找树比较

阅读更多

我们这个专题介绍的动态查找树主要有: 二叉查找树(BST),平衡二叉查找树(AVL),红黑树(RBT),B~/B+树(B-tree)。这四种树都具备下面几个优势:

(1) 都是动态结构。在删除,插入操作的时候,都不需要彻底重建原始的索引树。最多就是执行一定量的旋转,变色操作来有限的改变树的形态。而这些操作所付出的代价都远远小于重建一棵树。这一优势在《查找结构专题(1):静态查找结构概论 》中讲到过。

(2) 查找的时间复杂度大体维持在O(log(N))数量级上。可能有些结构在最差的情况下效率将会下降很快,比如BST。这个会在下面的对比中详细阐述。

 

 

下面我们开始概括性描述这四种树,并相互比较一下优劣。

 

1. 二叉查找树  (Binary Search Tree)   详细见《查找结构专题(2):二叉查找树 [BST]

 

    很显然,二叉查找树的发现完全是因为静态查找结构在动态插入,删除结点所表现出来的无能为力(需要付出极大的代价)。

 

   BST 的操作代价分析:

    (1) 查找代价: 任何一个数据的查找过程都需要从根结点出发,沿某一个路径朝叶子结点前进。因此查找中数据比较次数与树的形态密切相关。

         当树中每个结点左右子树高度大致相同时,树高为logN。则平均查找长度与logN成正比,查找的平均时间复杂度在O(logN)数量级上。

         当先后插入的关键字有序时,BST退化成单支树结构。此时树高n。平均查找长度为(n+1)/2,查找的平均时间复杂度在O(N)数量级上。

 

    (2) 插入代价: 新结点插入到树的叶子上,完全不需要改变树中原有结点的组织结构。插入一个结点的代价与查找一个不存在的数据的代价完全相同。

 

    (3) 删除代价: 当删除一个结点P,首先需要定位到这个结点P,这个过程需要一个查找的代价。然后稍微改变一下树的形态。如果被删除结点的左、右子树只有一个存在,则改变形态的代价仅为O(1)。如果被删除结点的左、右子树均存在,只需要将当P的左孩子的右孩子的右孩子的...的右叶子结点与P互换,在改变一些左右子树即可。因此删除操作的时间复杂度最大不会超过O(logN)。

 

    BST效率总结 查找最好时间复杂度O(logN),最坏时间复杂度O(N)。

                            插入删除操作算法简单,时间复杂度与查找差不多

 

 

 

2. 平衡二叉查找树 ( Balanced Binary Search Tree ) 详细见《查找结构专题(3):平衡二叉查找树 [AVL]

 

    二叉查找树在最差情况下竟然和顺序查找效率相当,这是无法仍受的。事实也证明,当存储数据足够大的时候,树的结构对某些关键字的查找效率影响很大。当然,造成这种情况的主要原因就是BST不够平衡(左右子树高度差太大)。

 

    既然如此,那么我们就需要通过一定的算法,将不平衡树改变成平衡树。因此,AVL树就诞生了。

 

    AVL 的操作代价分析:

    (1) 查找代价: AVL是严格平衡的BST(平衡因子不超过1)。那么查找过程与BST一样,只是AVL不会出现最差情况的BST(单支树)。因此查找效率最好,最坏情况都是O(logN)数量级的。

 

    (2) 插入代价: AVL必须要保证严格平衡(|bf|<=1),那么每一次插入数据使得AVL中某些结点的平衡因子超过1就必须进行旋转操作。事实上,AVL的每一次插入结点操作最多只需要旋转1次(单旋转或双旋转)。因此,总体上插入操作的代价仍然在O(logN)级别上(插入结点需要首先查找插入的位置)。

 

    (3) 删除代价:AVL删除结点的算法可以参见BST的删除结点,但是删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。因此删除的代价稍微要大一些。每一次删除操作最多需要O(logN)次旋转。因此,删除操作的时间复杂度为O(logN)+O(logN)=O(2logN)

 

    AVL 效率总结 查找的时间复杂度维持在O(logN),不会出现最差情况

                            AVL树在执行每个插入操作时最多需要1次旋转,其时间复杂度在O(logN)左右。

                            AVL树在执行删除时代价稍大,执行每个删除操作的时间复杂度需要O(2logN)。

 

 

 

 

3. 红黑树 (Red-Black Tree ) 详细见《查找结构专题(4):红黑树 [RBT]

 

    二叉平衡树的严格平衡策略以牺牲建立查找结构(插入,删除操作)的代价,换来了稳定的O(logN) 的查找时间复杂度。但是这样做是否值得呢?

 

    能不能找一种折中策略,即不牺牲太大的建立查找结构的代价,也能保证稳定高效的查找效率呢? 答案就是:红黑树。

 

    RBT 的操作代价分析:

     (1) 查找代价:由于红黑树的性质(最长路径长度不超过最短路径长度的2倍),可以说明红黑树虽然不像AVL一样是严格平衡的,但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右,但在最差情况下(最长路径是最短路径的2倍少1),比AVL要略逊色一点。

 

    (2) 插入代价:RBT插入结点时,需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转,这一点和AVL的插入操作一样。虽然变色操作需要O(logN),但是变色操作十分简单,代价很小。

 

    (3) 删除代价:RBT的删除操作代价要比AVL要好的多,删除一个结点最多只需要3次旋转操作。

 

    RBT 效率总结 : 查找 效率最好情况下时间复杂度为O(logN),但在最坏情况下比AVL要差一些,但也远远好于BST。

                           插入和删除操作改变树的平衡性的概率要远远小于AVL(RBT不是高度平衡的)。因此需要的旋转操作的可能性要小,而且一旦需要旋转,插入一个结点最多只需要旋转2次,删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN),但是实际上,这种操作由于简单所需要的代价很小。

 

 

 

 

4. B~树/B+树 (B-Tree ) 详细见《查找结构专题(5):B~树/B+树

 

     对于在内存中的查找结构而言,红黑树的效率已经非常好了(实际上很多实际应用还对RBT进行了优化)。但是如果是数据量非常大的查找呢?将这些数据全部放入内存组织成RBT结构显然是不实际的。实际上,像OS中的文件目录存储,数据库中的文件索引结构的存储.... 都不可能在内存中建立查找结构。必须在磁盘中建立好这个结构。那么在这个背景下,RBT还是一种好的选择吗?

 

     在磁盘中组织查找结构,从任何一个结点指向其他结点都有可能读取一次磁盘数据,再将数据写入内存进行比较。大家都知道,频繁的磁盘IO操作,效率是很低下的(机械运动比电子运动要慢不知道多少)。显而易见,所有的二叉树的查找结构在磁盘中都是低效的。因此,B树很好的解决了这一个问题。

 

    B-Tree的操作代价分析:

    (1) 查找代价: B-Tree作为一个平衡多路查找树(m-叉)。B树的查找分成两种:一种是从一个结点查找另一结点的地址的时候,需要定位磁盘地址(查找地址),查找代价极高。另一种是将结点中的有序关键字序列放入内存,进行优化查找(可以用折半),相比查找代价极低。而B树的高度很小,因此在这一背景下,B树比任何二叉结构查找树的效率都要高很多。而且B+树作为B树的变种,其查找效率更高。

 

    (2)插入代价: B-Tree的插入会发生结点的分裂操作。当插入操作引起了s个节点的分裂时,磁盘访问的次数为h(读取搜索路径上的节点)+2s(回写两个分裂出的新节点)+1(回写新的根节点或插入后没有导致分裂的节点)。因此,所需要的磁盘访问次数是h+2s+1,最多可达到3h+1。因此插入的代价是很大的。

 

    (3)删除代价:B-Tree的删除会发生结点合并操作。最坏情况下磁盘访问次数是3h=(找到包含被删除元素需要h次
读访问)+(获取第2至h层的最相邻兄弟需要h-1次读访问)+(在第3至h层的合并需要h-2次写
访问)+(对修改过的根节点和第2层的两个节点进行3次写访问)

 

   B-Tree效率总结: 由于考虑磁盘储存结构,B树的查找、删除、插入的代价都远远要小于任何二叉结构树(读写磁盘次数的降低)。

 

 

 

 

动态查找树结构的对比:

 

(1) 平衡二叉树和红黑树  [AVL  PK  RBT]

 

      AVL 和RBT 都是二叉查找树的优化。其性能要远远好于二叉查找树。他们之间都有自己的优势,其应用上也有不同。

 

      结构对比: AVL的结构高度平衡,RBT的结构基本平衡。平衡度AVL > RBT.

 

      查找对比: AVL 查找时间复杂度最好,最坏情况都是O(logN)。

                      RBT 查找时间复杂度最好为O(logN),最坏情况下比AVL略差。

 

      插入删除对比:  1. AVL的插入和删除结点很容易造成树结构的不平衡,而RBT的平衡度要求较低。因此在大量数据插入的情况下,RBT需要通过旋转变色操作来重新达到平衡的频度要小于AVL。

                             2. 如果需要平衡处理时,RBT比AVL多一种变色操作,而且变色的时间复杂度在O(logN)数量级上。但是由于操作简单,所以在实践中这种变色仍然是非常快速的。

                             3. 当插入一个结点都引起了树的不平衡,AVL和RBT都最多需要2次旋转操作。但删除一个结点引起不平衡后,AVL最多需要logN 次旋转操作,而RBT最多只需要3次。因此两者插入一个结点的代价差不多,但删除一个结点的代价RBT要低一些。

                             4. AVL和RBT的插入删除代价主要还是消耗在查找待操作的结点上。因此时间复杂度基本上都是与O(logN) 成正比的。

 

        总体评价:大量数据实践证明,RBT的总体统计性能要好于平衡二叉树。

 

 

(2) B~树和B+树    [ B~Tree   PK  B+Tree]

 

      B+树是B~树的一种变体,在磁盘查找结构中,B+树更适合文件系统的磁盘存储结构。

 

      结构对比: B~树是平衡多路查找树,所有结点中都包含了待查关键字的有效信息(比如文件磁盘指针)。每个结点若有n个关键字,则有n+1个指向其他结点的指针。

                     B+树严格意义上说已经不是树,它的叶子结点之间也有指针链接。B+树的非终结点中并不含有关键字的信息,需要查找的关键字的全部信息都包含在叶子结点上。非终结点中只作为叶子结点关键字的索引而存在。

 

      查找对比:1. 在相同数量的待查数据下,B+树查找过程中需要调用的磁盘IO操作要少于普通B~树。由于B树所在的磁盘存储背景下,因此B+树的查找性能要好于B~树。

                     2. B+树的查找效率更加稳定,因为所有叶子结点都处于同一层中,而且查找所有关键字都必须走完从根结点到叶子结点的全部历程。因此同一颗B+树中,任何关键字的查找比较次数都是一样的。而B树就不一定了,可能查找到某一个非终结点就结束了。

 

      插入删除对比:  B+树与B~树在插入删除操作中的效率是差不多的。

 

      总体评价:在应用背景下,特别是文件结构存储中。B+树的应用要更多,其效率也要比B~树好。

 

 

 

 

字符串查找结构

 

这次专题所讲的BST、AVL、BRT、B~Tree等可以胜任对任何关键字数据进行查找。但对字符串的查找(字符串匹配)结构,有专门的结构和算法。详见:《KMP算法 》,《Trie Tree

 

分享到:
评论
1 楼 lixia0417 2010-11-08  
RBT 的操作代价分析:

     (1) 查找代价:由于红黑树的性质(最长路径长度不超过最短路径长度的2倍),可以说明红黑树虽然不像AVL一样是严格平衡的,但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右,但在最差情况下(最长路径是最短路径的2倍少1),比AVL要略逊色一点。

相关推荐

    数据结构动态查找表

    2. 树结构:例如二叉查找树(Binary Search Tree)、平衡树(AVL树、红黑树等),它们通过特定的规则保证了查找效率,通常可以在O(log n)的时间复杂度内完成查找。 3. 散列表(Hash Table):散列表通过哈希函数将...

    数据结构_动态查找表

    - 查找操作:编写查找函数,根据数据结构的特性进行查找,例如链表中顺序遍历,二叉搜索树中利用比较规则进行查找,哈希表中通过哈希函数定位。 - 删除操作:设计删除函数,考虑如何安全地从表中移除元素,并可能...

    数据结构课程设计--动态查找表 二叉排序树

    在数据结构的学习中,动态查找表是一个至关重要的概念,它允许我们在数据集合中高效地进行插入、删除和查找操作。本课程设计的重点是利用二叉排序树(Binary Search Tree,BST)来实现动态查找表。二叉排序树是一种...

    综合查找算法(顺序查找、折半查找、二叉排序树、哈希表)-数据结构课程设计

    二叉排序树可以方便地进行插入、删除和查找操作,适用于动态变化的数据集。 **哈希表**是一种利用哈希函数将键映射到数组索引的数据结构。查找、插入和删除操作通常在平均情况下达到O(1)的时间复杂度,但最坏情况下...

    数据结构——查找

    6. **静态树表和分块查找** - 静态树表是利用树形结构实现查找,如二叉排序树,可以提高查找效率。 - 分块查找结合了索引和顺序查找,通过索引来快速定位到数据块,然后在块内进行顺序查找,提高了查找速度。 7. ...

    采用二叉链式结构做存储结构的二叉排序树建立和查找算法

    二叉排序树,又称二叉查找树或二叉搜索树,是一种特殊的二叉树数据结构,它具有以下特性:对于树中的每个节点,其左子树中的所有节点的值都小于该节点的值,而右子树中的所有节点的值都大于该节点的值。这种性质使得...

    数据结构课程实验动态查找表代码

    数据结构 报告 动态查找表用二叉平衡树结构的实验

    数据结构实验报告-查找-B-树基本操作的实现2017.docx

    B-树是一种自平衡的多路查找树,广泛应用于数据库和文件系统中,以高效地处理大量数据。 **B-树的定义** B-树是一种m阶的树,具有以下特性: 1. 每个节点最多有m个子节点。 2. 如果根节点不是叶节点,那么它至少有...

    最优二叉查找树 动态规划法.cpp.rar

    最优二叉查找树(Optimal Binary Search Tree, OBST)是一种高效的检索数据结构,它根据键值分布的不同,自适应地调整树的形态以达到最小化查找时间的目的。在计算机科学中,动态规划(Dynamic Programming, DP)是...

    数据结构7.1查找技术概述

    综合上述内容,查找技术涉及关键码的定义和使用、查找的含义及结果、静态与动态查找的区别、查找结构的分类及其对应的查找技术,以及如何通过平均查找长度来衡量查找算法的性能。掌握这些知识点是深入理解数据结构中...

    数据结构——二叉查找树(BST)静态查找表.zip

    二叉查找树(Binary Search Tree,BST),也称为二叉排序树,是计算机科学中用于组织数据的一种数据结构。它是一种特殊的二叉树,每个节点包含一个键(key)、一个关联的值、一个指向左子树的引用以及一个指向右子树...

    数据结构实验之二叉排序树

    动态查找是指在数据结构中搜索特定值的过程,对于二叉排序树,这个过程通常从根节点开始,如果目标值小于当前节点,则在左子树中继续查找;如果目标值大于当前节点,则在右子树中查找,直到找到目标值或遍历完所有...

    AVL树数据结构平衡二叉查找树

    在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者...

    3种查找算法——数据结构实验

    它先通过一个索引表(通常是哈希表或二叉查找树)找到目标值可能存在的位置,然后在该位置附近进行精确查找。索引查找可以显著减少实际数据的访问次数,尤其当索引结构和数据存储分离时,效率更高。然而,创建和维护...

    二叉排序树和折半查找

    这种结构使得二叉排序树在插入、删除和查找操作上的性能表现优秀,尤其在树保持平衡的情况下。 1. **二叉排序树的插入操作**: 插入新节点时,首先与根节点比较。如果新节点的值小于根节点,则插入到左子树;反之...

    数据结构(查找)习题及答案

    数据结构中的查找技术是计算机科学中的重要概念,用于在数据集合中寻找特定元素。本题主要涉及了多种查找方法,包括顺序查找、折半查找、哈希查找以及B-树和二叉排序树的构建与操作。以下是这些知识点的详细说明: ...

    数据结构大实验动态查找表

    2-3树保持了二叉查找树的性质,即所有的左子节点的键都小于父节点,所有的右子节点的键都大于父节点。在2-3树中,插入操作可以通过分裂节点来保持树的平衡。 B+树是B树的一个变种,主要区别在于所有数据都存储在...

    二叉排序树的建立,删除,查找,动态

    这种结构使得二叉排序树在查找、插入和删除操作上有较高的效率。 1. **建立二叉排序树**: 建立二叉排序树的过程通常是从空树开始,通过不断地插入节点来构建。每次插入新节点时,都会将其与当前树中的节点进行...

    数据结构实验——二叉排序树查找

    实验内容:建立有n个元素的二叉排序树,并在其上进行查找。 实验说明:(1)建立n个元素的二叉树,以链式结构存储,数据元素为整型。(2)在该二叉树上查找某数据,若查找成功则输出成功信息,若查找失败,则插入该数据...

    数据结构树 图 查找 排序C语言实现

    在“数据结构树 图 查找 排序C语言实现”这个主题中,我们将深入探讨四种核心概念:树、图、查找算法以及排序算法,并通过C语言来实现这些概念。 1. **树数据结构**:树是一种非线性的数据结构,由节点(或称为顶点...

Global site tag (gtag.js) - Google Analytics