通过与 Jira 对比,让您更全面了解 PingCode

  • 首页
  • 需求与产品管理
  • 项目管理
  • 测试与缺陷管理
  • 知识管理
  • 效能度量
        • 更多产品

          客户为中心的产品管理工具

          专业的软件研发项目管理工具

          简单易用的团队知识库管理

          可量化的研发效能度量工具

          测试用例维护与计划执行

          以团队为中心的协作沟通

          研发工作流自动化工具

          账号认证与安全管理工具

          Why PingCode
          为什么选择 PingCode ?

          6000+企业信赖之选,为研发团队降本增效

        • 行业解决方案
          先进制造(即将上线)
        • 解决方案1
        • 解决方案2
  • Jira替代方案

25人以下免费

目录

为什么STL和linux都使用红黑树作为平衡树的实

选择红黑树作为底层实现红黑树是一种类平衡树, 但它不是高度的平衡树, 但平衡的效果已经很好了。STL map , nginx,linux 虚拟内存管理,他们都有红黑树的应用。

一、为什么STL和linux都使用红黑树作为平衡树的实现

选择红黑树作为底层实现红黑树是一种类平衡树, 但它不是高度的平衡树, 但平衡的效果已经很好了。STL map , nginx,linux 虚拟内存管理,他们都有红黑树的应用。

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树(平衡二叉树)

AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树的高度差不超过1,和红黑树相比,AVL树是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差的绝对值不超过1。不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入与删除次数比较少,但查找多的情况。:

相关文章