侧边栏壁纸
博主头像
996worker

祇園精舎の鐘の聲, 諸行無常の響き有り。

  • 累计撰写 174 篇文章
  • 累计创建 45 个标签
  • 累计收到 8 条评论

目 录CONTENT

文章目录

红黑树, AVL树和B树的区别

996worker
2021-11-01 / 0 评论 / 0 点赞 / 211 阅读 / 772 字
温馨提示:
本文最后更新于 2021-11-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

红黑树与AVL树

  • 1、红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。
  • 2、平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知。

AVL树是最早出现的自平衡二叉(查找)树

红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。

红黑树和AVL树的区别在于它使用颜色来标识结点的高度,它所追求的是局部平衡而不是AVL树中的非常严格的平衡。

红黑树是牺牲了严格的高度平衡的优越条件为代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。

此外,由于它的设计,任何不平衡都会在三次旋转之内解决。

当然,还有一些更好的,但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。

红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高.

红黑树和B树

B树又叫平衡多路查找树。B树是为了磁盘或其它存储设备而设计的一种多叉, 相对于二叉,B树每个内结点有多个分支,即多叉.

平衡多路查找树与红黑树很相似,但在降低磁盘I/0操作方面要更好一些。 许多数据库系统都一般使用B树或者B树的各种变形结构,如下文即将要介绍的B+树,B+树更加矮胖.

红黑树与B树的区别在于,B树的结点可以有许多子女,从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样,一棵含n个结点的 B树的高度也为O(lgn) ,但可能比一棵红黑树的高度小许多,应为它的分支因子比较大。所以, B树可以在O(logn)时间内,实现各种如插入(insert),删除(delete)等动态集合操作.

Copyright

July、weedge、Frankie

0

评论区