MySQL数据库设计总结

二叉查找树、平衡二叉树、红黑树、B-/B+树性能对比

PHPer 2018-09-16 142次浏览 0条评论 0 0 0
1. 二叉查找树 (Binary Search Tree)概念二叉查找树又称二叉搜索树,二叉排序树,特点如下:1. 左子树上所有结点值均小于根结点2. 右子树上所有结点值均大于根结点3. 结点...

1. 二叉查找树 (Binary Search Tree)

概念

二叉查找树又称二叉搜索树,二叉排序树,特点如下:1. 左子树上所有结点值均小于根结点2. 右子树上所有结点值均大于根结点3. 结点的左右子树本身又是一颗二叉查找树4. 二叉查找树中序遍历得到结果是递增排序的结点序列。

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 )

二叉查找树在最差情况下竟然和顺序查找效率相当,这是无法仍受的。事实也证明,当存储数据足够大的时候,树的结构对某些关键字的查找效率影响很大。当然,造成这种情况的主要原因就是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 )

二叉平衡树的严格平衡策略以牺牲建立查找结构(插入,删除操作)的代价,换来了稳定的O(logN) 的查找时间复杂度。但是这样做是否值得呢?能不能找一种折中策略,即不牺牲太大的建立查找结构的代价,也能保证稳定高效的查找效率呢? 答案就是:红黑树。

RBT 的操作代价分析:

(1)查找代价

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

(2)插入代价

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

登录 | 立即注册

更新于:2018-09-16 11:19:46
    您需要登录后才可以评论。 登录 | 立即注册
    相关内容

    Mysql问题整理

    这里整理下Mysql使用中遇到的各种问题

    Yii2数据库报错-SQLSTATE[HY093]: Invalid parameter number: no parameters were bound

    Mysql server has gone away 报错原因分析及解决办法

    mysql 警告 could not be resolved: Name or service not known

    Mysql用特殊字符设置密码遇到的问题

    Mysql的函数substring使用注意事项

    MySQL 5.7内存使用分析

    mysql 命令整理

    【mysql】主键、普通索引、唯一索引和全文索引的比较

    没有接收到要导入的数据。可能是文件名没有提交,也可能是文件大小超出 PHP 限制。

    推荐内容

    MySQL数据库设计总结

    规则1:一般情况可以选择MyISAM存储引擎,如果需要事务支持必须使用InnoDB存储引擎。注意:MyISAM存储引擎 B-tree索引有一个很大的限制:参与一个索引的所有字...

    什么是B-Tree

    二叉查找树、平衡二叉树、红黑树、B-/B+树性能对比

    使用Yii2遇到的问题整理

    Yii的东西很多,学习和使用的时候遇到了各种各样的问题,这里记录整理下,方便大家分享。composer安装kartik-v/yii2-mpdf时报错,这里记录下 Yii2用compos...

    Yii2用composer更新时遇到的错误

    Yii2 用composer update 时提示'git' 不是内部或外部命令,也不是可运行的程序或批处理文件

    Yii2​用composer安装kartik-v/yii2-mpdf时报错,成功解决后,再让其支持中文。

    使用Yii2的setFlash和bootstrap.min.js遇到的问题,bootstrap.min.js的bug?

    Yii2的action不支持大小写吗?其实是支持的

    composer install 使用tips-网上找的composer install的使用技巧方法

    关于编程时遇到意想不到的错误如何解决

    比如当你写的一个php脚本执行出现问题,如果你的脚本里自己带了对错误的处理,可能会显示那里出错了。或者你用的框架,框架里有debug模式,会报错。

    使用Laravel 5.4问题总结

    这里写下laravel5.4的总结,用laravel也有段时间了,优点就不用多说了,好上手,较易学较易用,blade模板是非常的好用,等等。laravel的缺点有几个,灵活性一般,框架稍...

    使用Laravel 5.4问题总结 Lost connection to MySQL server at 'reading initial communication ...

    Laravel 5.4各种错误提示总结

    localStorage介绍和使用

    一、什么是localStorage、sessionStorage在HTML5中,新加入了一个localStorage特性,这个特性主要是用来作为本地存储来使用的,解决了cookie存储空间不足的问题(co...

    localStorage的使用

    localStorage其他注意事项