MySQL数据库设计总结

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

PHPer 2018-09-16 432次浏览 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 限制。

    推荐内容

    超省心游戏加速:Wireguard+udp加速(CentOS版)--(实测:超不省心),以后搜帖...

    Wireguard+udpspeeder+udp2raw游戏加速方案 ---------------------------------------错误报告及解决-----------...

    wireguard+udpspeeder+udp2raw多用户配置

    Wireguard+udpspeeder+udp2raw游戏加速方案改进版-实测有效

    基于CentOS7 Centos8平台搭建邮件服务器

    EwoMail​在Centos8上安装了,各种坑,各种报错。这个集成包太臃肿了。 20200416 EwoMail 已经弃用,国内的一家公司搞的坑爹产品。 20200418

    如何在RHEL8 / CentOS8上安装Webmin

    设置postfix作为邮件发送服务器

    查问我看笔记功能的实现过程-全文搜索待开启,试试yiisoft/yii2-sphinx

    查问我看笔记功能的实现的重点就是全文搜索,如果不用Yii自带的ActiveRecord的话,就要找扩展,先找了个yii-xunsearch,不行太差了,又找了yiisoft/yii2-elasticsearch,...

    yii2框架中使用sphinx使用搜索引擎 多条件选择搜索

    运行php composer.phar require --prefer-dist yiisoft/yii2-sphinx

    U盘安装U盘启动-U盘启动盘一键U盘装系统

    https://www.upandashi.com/ 先要做U盘启动盘,然后下载Win7镜像或Win7的Ghost文件,放到U盘里,然后插在电脑上做系统,注意主板要改成U盘优先启动。 ...

    MySQL数据库设计总结

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

    什么是B-Tree

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