红黑树

作者: Drew_MyINTYRE | 来源:发表于2021-06-17 08:53 被阅读0次

    红黑树是一种平衡二叉查找树。发明平衡二叉查找树这类数据结构的初衷是,解决普通二叉查找树在频繁的插入、删除等动态更新的情况下,出现时间复杂度退化的问题。红黑树的高度近似 log2n,所以它是近似平衡,插入、删除、查找操作的时间复杂度都是 O(logn)。

    平衡二叉查找树中“平衡”的意思,其实就是让整棵树左右看起来比较“对称”、比较“平衡”,不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些,相应的插入、删除、查找等操作的效率高一些。

    因为红黑树是一种性能非常稳定的二叉查找树,所以,在工程中,但凡是用到动态插入、删除、查找数据的场景,都可以用到它。不过,它实现起来比较复杂,如果自己写代码实现,难度会有些高,这个时候,我们其实更倾向用跳表来替代它。

    动态数据结构是支持动态的更新操作,里面存储的数据是时刻在变化的,通俗一点讲,它不仅仅支持查询,还支持删除、插入数据。而且,这些操作都非常高效。如果不高效,也就算不上是有效的动态数据结构了。所以,这里的红黑树算一个,支持动态的插入、删除、查找,而且效率都很高。链表、队列、栈实际上算不上,因为操作非常有限,查询效率不高。那现在你再想一下还有哪些支持动态插入、删除、查找数据并且效率都很高的的数据结构呢??

    • 散列表:插入删除查找都是O(1), 是最常用的,但其缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于那些不需要顺序遍历,数据更新不那么频繁的。

    • 跳表:插入删除查找都是O(logn), 并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的,其顺序遍历和区间查找非常方便。

    • 红黑树:插入删除查找都是O(logn), 中序遍历即是顺序遍历,稳定。缺点是难以实现,去查找不方便。其实跳表更佳,但红黑树已经用于很多地方了。

    相关文章

      网友评论

          本文标题:红黑树

          本文链接:https://www.haomeiwen.com/subject/ylbqyltx.html