精华内容
下载资源
问答
  • RB-Tree和AVL树作为BBST,其实现的算法时间复杂度相同,AVL作为最先提出的BBST,貌似RB-tree实现的功能都可以用AVL树是代替,那么为什么还需要引入RB-Tree呢? 红黑树不追求"完全平衡",即不像AVL那样要求节点的 |...

    RB-Tree和AVL树作为BBST,其实现的算法时间复杂度相同,AVL作为最先提出的BBST,貌似RB-tree实现的功能都可以用AVL树是代替,那么为什么还需要引入RB-Tree呢?

    红黑树不追求"完全平衡",即不像AVL那样要求节点的 |balFact| <= 1,它只要求部分达到平衡,但是提出了为节点增加颜色,红黑是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多。
    就插入节点导致树失衡的情况,AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance,旋转的量级是O(1)
    删除节点导致失衡,AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡,旋转的量级为O(logN),而RB-Tree最多只需要旋转3次实现复衡,只需O(1),所以说RB-Tree删除节点的rebalance的效率更高,开销更小!
    AVL的结构相较于RB-Tree更为平衡,插入和删除引起失衡,如2所述,RB-Tree复衡效率更高;当然,由于AVL高度平衡,因此AVL的Search效率更高啦。
    针对插入和删除节点导致失衡后的rebalance操作,红黑树能够提供一个比较"便宜"的解决方案,降低开销,是对search,insert ,以及delete效率的折衷,总体来说,RB-Tree的统计性能高于AVL.
    故引入RB-Tree是功能、性能、空间开销的折中结果。
    5.1 AVL更平衡,结构上更加直观,时间效能针对读取而言更高;维护稍慢,空间开销较大。
    5.2 红黑树,读取略逊于AVL,维护强于AVL,空间开销与AVL类似,内容极多时略优于AVL,维护优于AVL。
    基本上主要的几种平衡树看来,红黑树有着良好的稳定性和完整的功能,性能表现也很不错,综合实力强,在诸如STL的场景中需要稳定表现。
    红黑树的查询性能略微逊色于AVL树,因为其比AVL树会稍微不平衡最多一层,也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较,但是,红黑树在插入和删除上优于AVL树,AVL树每次插入删除会进行大量的平衡度计算,而红黑树为了维持红黑性质所做的红黑变换和旋转的开销,相较于AVL树为了维持平衡的开销要小得多

    总结:实际应用中,若搜索的次数远远大于插入和删除,那么选择AVL,如果搜索,插入删除次数几乎差不多,应该选择RB。

    展开全文
  • RB-Tree和AVL树作为BBST,其实现的算法时间复杂度相同,AVL作为最先提出的BBST,貌似RB-tree实现的功能都可以用AVL树是代替,那么为什么还需要引入RB-Tree呢? 红黑树不追求"完全平衡",即不像AVL那样要求节点的|...

    RB-Tree和AVL树作为BBST,其实现的算法时间复杂度相同,AVL作为最先提出的BBST,貌似RB-tree实现的功能都可以用AVL树是代替,那么为什么还需要引入RB-Tree呢?

    1. 红黑树不追求"完全平衡",即不像AVL那样要求节点的 |balFact| <= 1,它只要求部分达到平衡,但是提出了为节点增加颜色,红黑是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多。
    2. 就插入节点导致树失衡的情况,AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance,旋转的量级是O(1)
      删除节点导致失衡,AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡,旋转的量级为O(logN),而RB-Tree最多只需要旋转3次实现复衡,只需O(1),所以说RB-Tree删除节点的rebalance的效率更高,开销更小!
    3. AVL的结构相较于RB-Tree更为平衡,插入和删除引起失衡,如2所述,RB-Tree复衡效率更高;当然,由于AVL高度平衡,因此AVL的Search效率更高啦。
    4. 针对插入和删除节点导致失衡后的rebalance操作,红黑树能够提供一个比较"便宜"的解决方案,降低开销,是对search,insert ,以及delete效率的折衷,总体来说,RB-Tree的统计性能高于AVL.
    5. 故引入RB-Tree是功能、性能、空间开销的折中结果
      5.1 AVL更平衡,结构上更加直观,时间效能针对读取而言更高;维护稍慢,空间开销较大。
      5.2 红黑树,读取略逊于AVL,维护强于AVL,空间开销与AVL类似,内容极多时略优于AVL,维护优于AVL。
      基本上主要的几种平衡树看来,红黑树有着良好的稳定性和完整的功能,性能表现也很不错,综合实力强,在诸如STL的场景中需要稳定表现。

    红黑树的查询性能略微逊色于AVL树,因为其比AVL树会稍微不平衡最多一层,也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较,但是,红黑树在插入和删除上优于AVL树,AVL树每次插入删除会进行大量的平衡度计算,而红黑树为了维持红黑性质所做的红黑变换和旋转的开销,相较于AVL树为了维持平衡的开销要小得多

    1. 总结:实际应用中,若搜索的次数远远大于插入和删除,那么选择AVL,如果搜索,插入删除次数几乎差不多,应该选择RB。
    展开全文
  • 为什么map,set 不用AVL树作为底层实现? 用过 STL map 么, 你用...至于, 为什么不用 AVL 树作为底层实现, 那是因为 AVL 树是高度平衡的树, 而每一次对树的修改, 都要 rebalance, 这里的开销会比红黑树大. 红黑树插...

    为什么map,set 不用AVL树作为底层实现?

    用过 STL map 么, 你用过 linux 么(这个说大了), 他们都有红黑树的应用. 当你对搜索的效率要求较高,并且数据经常改动的情景,你可以用红黑树, 也就是 map。

    至于, 为什么不用 AVL 树作为底层实现, 那是因为 AVL 树是高度平衡的树, 而每一次对树的修改, 都要 rebalance, 这里的开销会比红黑树大. 红黑树插入只要两次旋转, 删除至多三次旋转. 但不可否认的是, AVL 树搜索的效率是非常稳定的. 选取红黑树, 我认为是一种折中的方案。

     

    红黑树和AVL树的效率对比:

    1. 如果插入一个node引起了树的不平衡,AVL和RB-Tree都是最多只需要2次旋转操作,即两者都是O(1);但是在删除node引起树的不平衡时,最坏情况下,AVL需要维护从被删node到root这条路径上所有node的平衡性,因此需要旋转的量级O(logN),而RB-Tree最多只需3次旋转,只需要O(1)的复杂度。

    2. 其次,AVL的结构相较RB-Tree来说更为平衡,在插入和删除node更容易引起Tree的unbalance,因此在大量数据需要插入或者删除时,AVL需要rebalance的频率会更高。因此,RB-Tree在需要大量插入和删除node的场景下,效率更高。自然,由于AVL高度平衡,因此AVL的search效率更高。

    3. map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说,RB-tree的统计性能是高于AVL的。

    最坏情况下,AVL树有最多O(logN)次旋转,而红黑树最多三次。

    展开全文
  • 数据库索引为什么要用 B+ 树而不用红黑树呢?

    万次阅读 多人点赞 2017-09-15 22:06:09
    既然如此,那么数据库索引为什么不用 AVL 树或者红黑树呢? 这就牵扯到一个问题了,不考虑每种数据结构的前提条件而选择数据结构都是在耍流氓。 AVL和红黑树基本都是存储在内存中才会使用的数据结构,那磁盘中会...

     

    AVL 树和红黑树这些二叉树结构的数据结构可以达到最高的查询效率这是毋庸置疑的。

    既然如此,那么数据库索引为什么不用 AVL 树或者红黑树呢?

    这就牵扯到一个问题了,不考虑每种数据结构的前提条件而选择数据结构都是在耍流氓。

    AVL 数和红黑树基本都是存储在内存中才会使用的数据结构,那磁盘中会有什么不同呢?

    这就要牵扯到索引的存储原理了

    页是 InnoDB存储引擎管理数据库的最小磁盘单位。

    一个页中包括很多数据行。

    那么,现在问题就来了

    一个父节点只有 2 个子节点,并不能填满一个页上的所有内容啊?那多余的内容岂不是要浪费了?我们怎么才能把浪费的这部分内容利用起来呢?哈哈,答案就是 B+ 树,让一个父节点有多个子节点就可以了。

    由于 B+ 树分支比二叉树更多,所以相同数量的内容,B+ 树的深度更浅,深度代表什么?代表磁盘 io 次数啊!

    所以,涉及到磁盘上查询的数据结构,一般都用 B+ 树啦。

     

     

     

     

     

    展开全文
  • 为什么都用红黑树不用AVL树? 1. 如果插入一个node引起了树的不平衡, AVL和RB-Tree都是最多只需要2次旋转操作,即两者都是O(1); 但是在删除node引起树的不平衡时,最坏情况下, AVL需要维护从被删node到root这条...
  • 一轮面试: 小数是怎么存的 算法题:N二进制有多少个1 Linux命令(不熟悉 ...为什么不用AVL和红黑树存? 说实习项目 redis用了哪些 持久化和复制 git 聊一聊实验室项目 有哪些offer 二轮面试 ...
  • 第一次面试 1.小数是怎么存的 2.算法题:N二进制有多少个1 3.Linux命令(不熟悉 4.JVM垃圾回收算法 ...10.为什么不用AVL和红黑树存? 11.说实习项目 12.redis用了哪些 12.持久化和复制 13.g...
  • 第一次面试 1.小数是怎么存的 2.算法题:N二进制有多少个1 3.Linux命令(不熟悉 4.JVM垃圾回收算法 ...10.为什么不用AVL和红黑树存? 11.说实习项目 12.redis用了哪些 12.持久化和复制 13.git ...
  • 一 B树的由来 B树指的是一类树,包括B-树,B+树,B*树等,是一种自平衡的搜索树,它...1. 为什么不用二叉平衡树 传统用来搜索的平衡二叉树有很多,AVL树,红黑树等。这些树在一般情况下的查询性能非常好,但当数...
  • 2、为什么红黑树不用其他平衡树等? 红黑树复杂度是logn,链表是n。还有1.8链表用了尾插法每次插入都要循环整个链表,所以当链表太长时插入效率也会变低,所以用红黑树替换链表。而用红黑树不用其他例avl是在...
  • 分类 学校相关 问了本科硕士学校,为什么选择考研去兰州大学? 专业排名、项目、研究方向、成果 专业知识 Q:哈希表的实现方式?冲突的解决? A:一段连续的存储空间,...为什么不用AVL树而选择红黑树红黑树...
  • 引申问题:为什么不用BTree?问题3:Mysql索引中存储什么样的数据?问题4:为什么要使用长度尽量短的字段建立索引?为什么尽量使用定长数据类型建立索引问题5:聚簇索引非聚簇索引区别问题6:一个表中,最多有多少...
  • MySql

    2020-10-08 23:11:18
    MySql用的是B+树,为什么不用普通二叉树、红黑树、B树? 二叉树在数据量很大的情况下树的高度会变的很高,查询效率就低,红黑树和AVL树虽然有自平衡的优点,但是它们每个节点只能存一个索引,但是一次磁盘IO是可以读...
  • MySQL的索引深入剖析

    2020-05-08 22:57:51
    文章目录一. 索引是什么???1.官方解释2.... 为什么不用红黑树?7. B+Hash索引三、B+树的落地实现1. MyISAM2. InnoDB3. 什么叫做聚集索引(聚簇索引)?4. 为什么在辅助索引里面存储的是主键值而
  • 7.10.1 为什么需要一些新的算法 7.10.2 外部排序模型 7.10.3 简单算法 7.10.4 多路合并 7.10.5 多相合并 7.10.6 替换选择 小结 练习题 参考文献 第8章 不相交集类 8.1 等价关系 8.2 动态等价性问题 8.3 ...
  • 7.12.1为什么需要一些新的算法217 7.12.2外部排序模型217 7.12.3简单算法217 7.12.4多路合并218 7.12.5多相合并219 7.12.6替换选择219 小结220 练习221 参考文献225 第8章不相交集类227 8.1等价关系227 ...

空空如也

空空如也

1
收藏数 20
精华内容 8
关键字:

为什么不用avl和红黑树