热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

说一下B+tree和二叉搜索树的区别?说一下二叉搜索树和AVL树、红黑树之间的差别...

https:blog.csdn.netkingcat666articledetails45248487http:www.cnblogs.comFMOONp9487472.html二

https://blog.csdn.net/kingcat666/article/details/45248487

http://www.cnblogs.com/FMOON/p/9487472.html

二叉查找树(BST),平衡二叉查找树(AVL),红黑树(RBT),B~/B+树(B-tree)优势:

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

(2) 查找的时间复杂度大体维持在O(log(N))数量级上。可能有些结构在最差的情况下效率将会下降很快,比如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)。

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

 

AVL树(平衡二叉查找树),解决单支的情况。平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。

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

 

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

 

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

 

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

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

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

 红黑树 (Red-Black Tree )

  二叉平衡树的严格平衡策略以牺牲建立查找结构(插入&#xff0c;删除操作为代价&#xff0c;换来了稳定的O(logN) 的查找时间复杂度

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

红黑树的特性:
&#xff08;1&#xff09;每个节点或者是黑色&#xff0c;或者是红色。
&#xff08;2&#xff09;根节点是黑色。
&#xff08;3&#xff09;每个叶子节点&#xff08;NIL&#xff09;是黑色。 [注意&#xff1a;这里叶子节点&#xff0c;是指为空(NIL或NULL)的叶子节点&#xff01;]
&#xff08;4&#xff09;如果一个节点是红色的&#xff0c;则它的子节点必须是黑色的。
&#xff08;5&#xff09;从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。&#xff08;接近平衡二叉树&#xff09;

最长路径长度不超过最短路径长度的2倍

主要是用它来存储有序的数据。C&#43;&#43; STL中的set、map&#xff0c;以及Linux虚拟内存的管理&#xff0c;都是通过红黑树去实现的。

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

 

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

 

    (3) 删除代价&#xff1a;RBT的删除操作代价要比AVL要好的多&#xff0c;删除一个结点最多只需要3次旋转操作。

 

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

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

 

b&#43;树&#xff1a;多路的平衡二叉树

在B&#43;树中&#xff0c;所有记录节点都是按键值的大小顺序存放在同一层的叶节点中&#xff0c;各叶节点指针进行连接

小结

       B树&#xff1a;二叉树&#xff0c;每个结点只存储一个关键字&#xff0c;等于则命中&#xff0c;小于走左结点&#xff0c;大于

走右结点&#xff1b;

       B-树&#xff1a;多路搜索树&#xff0c;每个结点存储M/2到M个关键字&#xff0c;非叶子结点存储指向关键

字范围的子结点&#xff1b;

       所有关键字在整颗树中出现&#xff0c;且只出现一次&#xff0c;非叶子结点可以命中&#xff1b;

       B&#43;树&#xff1a;在B-树基础上&#xff0c;为叶子结点增加链表指针&#xff0c;所有关键字都在叶子结点

中出现&#xff0c;非叶子结点作为叶子结点的索引&#xff1b;B&#43;树总是到叶子结点才命中&#xff1b;

       B*树&#xff1a;在B&#43;树基础上&#xff0c;为非叶子结点也增加链表指针&#xff0c;将结点的最低利用率

从1/2提高到2/3&#xff1b;

转:https://www.cnblogs.com/FMOON/p/9487472.html



推荐阅读
  • 提升学习效率不仅需要正确的方法,还需要一些实用的小技巧。本文总结了多条有助于提高学习效果的建议,包括合理安排时间、选择合适的学习环境、运用记忆技巧等。通过这些方法,可以帮助学生更好地集中注意力,提高学习效率,达到事半功倍的效果。 ... [详细]
  • `chkconfig` 命令主要用于管理和查询系统服务在不同运行级别中的启动状态。该命令不仅能够更新服务的启动配置,还能检查特定服务的当前状态。通过 `chkconfig`,管理员可以轻松地控制服务在系统启动时的行为,确保关键服务正常运行,同时禁用不必要的服务以提高系统性能和安全性。本文将详细介绍 `chkconfig` 的各项参数及其使用方法,帮助读者更好地理解和应用这一强大的系统管理工具。 ... [详细]
  • Windows环境下RabbitMQ安装详尽指南
    Windows环境下RabbitMQ安装详尽指南 ... [详细]
  • 作为软件工程专业的学生,我深知课堂上教师讲解速度之快,很多时候需要课后自行消化和巩固。因此,撰写这篇Java Web开发入门教程,旨在帮助初学者更好地理解和掌握基础知识。通过详细记录学习过程,希望能为更多像我一样在基础方面还有待提升的学员提供有益的参考。 ... [详细]
  • MySQL 8.0 MGR 自动化部署与配置:DBA 和开源工具的高效解决方案
    MySQL 8.0 MGR 自动化部署与配置:DBA 和开源工具的高效解决方案 ... [详细]
  • C++ 开发实战:实用技巧与经验分享
    C++ 开发实战:实用技巧与经验分享 ... [详细]
  • 本文全面解析了JavaScript中的DOM操作,并提供了详细的实践指南。DOM节点(Node)通常代表一个标签、文本或HTML属性,每个节点都具有一个nodeType属性,用于标识其类型。文章深入探讨了DOM节点的创建、查询、修改和删除等操作,结合实际案例,帮助读者更好地理解和掌握DOM编程技术。 ... [详细]
  • 在VS2013中编译FFMPEG时遇到的问题及解决方案
    在使用VS2013编译旧版本FFMPEG库时遇到了一些问题,因为官方并未提供预编译的LIB和DLL文件。由于对Linux环境不熟悉,只能在Windows环境下进行配置和编译。具体步骤如下:首先,下载FFMPEG的源代码;然后,安装必要的编译工具和依赖项;接着,配置Visual Studio 2013的项目设置;最后,解决编译过程中出现的各种错误和警告。通过这些步骤,最终成功编译出所需的FFMPEG库文件。 ... [详细]
  • 图论入门基础教程
    图论是计算机科学和数学中的重要分支,本教程旨在为初学者提供全面的基础知识。通过实例解析,如“昂贵的聘礼”问题,讲述了一个年轻探险家在印第安部落与酋长女儿的爱情故事,展示了图论在解决实际问题中的应用。教程内容涵盖了图的基本概念、表示方法以及常见算法,适合各类读者学习。 ... [详细]
  • 技术日志:使用 Ruby 爬虫抓取拉勾网职位数据并生成词云分析报告
    技术日志:使用 Ruby 爬虫抓取拉勾网职位数据并生成词云分析报告 ... [详细]
  • 计算机视觉领域介绍 | 自然语言驱动的跨模态行人重识别前沿技术综述(上篇)
    本文介绍了计算机视觉领域的最新进展,特别是自然语言驱动的跨模态行人重识别技术。上篇内容详细探讨了该领域的基础理论、关键技术及当前的研究热点,为读者提供了全面的概述。 ... [详细]
  • 本文深入解析了HTML框架集(FRAMESET)的使用方法及其应用场景。首先介绍了几个关键概念,如如何通过FRAMESET标签将主视图划分为多个独立的区域,每个区域可以加载不同的HTML文件。此外,还详细探讨了FRAMESET在实际开发中的优缺点,并提供了具体的实例代码,帮助开发者更好地理解和应用这一技术。 ... [详细]
  • 深入解析HTTPS:保障Web安全的加密协议
    本文详细探讨了HTTPS协议在保障Web安全中的重要作用。首先分析了HTTP协议的不足之处,包括数据传输过程中的安全性问题和内容加密的缺失。接着介绍了HTTPS如何通过使用公钥和私钥的非对称加密技术以及混合加密机制,确保数据的完整性和机密性。最后强调了HTTPS的安全性和可靠性,为现代网络通信提供了坚实的基础。 ... [详细]
  • 在 CentOS 6.5 系统上部署 VNC 服务器的详细步骤与配置指南
    在 CentOS 6.5 系统上部署 VNC 服务器时,首先需要确认 VNC 服务是否已安装。通常情况下,VNC 服务默认未安装。可以通过运行特定的查询命令来检查其安装状态。如果查询结果为空,则表明 VNC 服务尚未安装,需进行手动安装。此外,建议在安装前确保系统的软件包管理器已更新至最新版本,以避免兼容性问题。 ... [详细]
  • POJ3669题目解析:基于广度优先搜索的详细解答
    POJ3669(http://poj.org/problem?id=3669)是一道典型的广度优先搜索(BFS)问题。由于陨石的降落具有时间属性,导致地图状态会随时间动态变化。因此,可以利用结构体来记录每个陨石的降落时间和位置,从而有效地进行状态更新和路径搜索。 ... [详细]
author-avatar
killphp
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有