红黑树有用的地方

Question

可能的重复：
红黑树

我开始在麻省理工学院观看关于红黑树的讲座，15 分钟后放弃了。

当然，我没有看过前面的 10 个讲座，但为什么在进入理论之前没有真实世界的例子？

有人可以举个例子并解释为什么红黑树是必不可少的数据结构吗？

Answer 1

红黑树是自平衡的，因此可以在 O(log n) 时间内插入、删除和搜索。其他类型的平衡树（例如 AVL 树）对于插入和删除操作通常较慢。

另外，红黑树的代码往往更简单。

它们非常适合创建映射或关联数组以及专用数据存储。我在高速电信应用中使用了一个来实现成本最低的路由系统。