红黑树有用的地方
可能的重复：
红黑树
我开始观看讲座在麻省理工学院关于红黑树及其之后15分钟就放弃了。
当然，我没有看过前面的 10 个讲座，但为什么在进入理论之前没有现实世界的例子呢？
有人可以举个例子并解释为什么红黑树是一种重要的数据结构吗？
Possible Duplicate:
Red-Black Trees
I started watching a lecture at mit on red-black trees and after 15 minutes gave up.
Sure, I have not watched the previous 10 lectures but why no real world example before going into the theory?
Can someone give an example and explain why red-black trees are an essential data structure?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
红黑树是自平衡的，因此可以在 O(log n) 时间内插入、删除和搜索。其他类型的平衡树（例如 AVL 树）对于插入和删除操作通常较慢。
另外，红黑树的代码往往更简单。
它们非常适合创建映射或关联数组以及专用数据存储。我在高速电信应用中使用了一个来实现成本最低的路由系统。
Red-black trees are self-balancing, and so can insert, delete, and search in O(log n) time. Other types of balanced trees (e.g. AVL trees) are often slower for insert and delete operations.
In addition, the code for red-black trees tends to be simpler.
They are good for creating Maps or associative arrays, and special-purpose data stores. I used one in a high speed telecom application to implement a least-cost routing system.
注：我没看过讲座。
红黑树是二叉搜索树，在添加或删除项目时自平衡。此功能保证此树中的每个搜索都具有
O(logn)复杂度。如果您构造一棵树而不平衡它，则可能会创建一棵退化树，它实际上是一个具有
O(n)复杂度的链表。Note: I haven't seen the lecture.
Red-black trees are binary search trees that are self-balancing when an item is added or removed. This feature guarantees that every search within this tree has
O(logn)complexity.If you construct a tree without balancing it, it is possible to create a degenrated tree that is effectively a linked list with
O(n)complexity.维基百科说“自平衡二叉搜索树”。
“简单地说，红黑树是一种二叉搜索树，它的插入和删除方式使得该树始终保持合理平衡。”
当数据恰好被排序时这会有所帮助。如果没有平衡，树就会变成链表。
Wikipedia says "self-balancing binary search tree".
"Put very simply, a red–black tree is a binary search tree that inserts and deletes in such a way that the tree is always reasonably balanced."
Which helps when data happens to be sorted. Without the balancing the tree devolves to a linked list.
维基百科提供了解释和重要示例。
红黑树为插入时间、删除时间和搜索时间提供最坏情况的保证。这对于实时应用程序非常有用。
一个真实的例子是 Linux 内核中的完全公平调度程序。
Wikipedia provides an explanation and an important example.
Red-black trees provide worst-case guarantees for insertion time, deletion time and search time. This can be very useful for real time applications.
A real world example is the Completely Fair Scheduler in the Linux kernel.