问题标签 [red-black-tree]

boost::multi_index::multi_index_container对于硬盘存储，我需要一个基于红黑树（类似于 ）的多索引容器。所有数据必须存储在硬盘上而不是内存中。

是否存在符合所述条件的开源​​容器？

笔记。我用C++.

我只是在对 RedBlack Tree 进行一些研究。我知道 .Net 4.0 中的 SortedSet 类使用 RedBlack 树。所以我像使用 Reflector 一样把这部分拿出来，并创建了一个 RedBlackTree 类。现在我在这个 RedBlackTree 和 SortedSet 上运行一些性能测试，插入 40000 个连续的整数值（从 0 到 39999），我很惊讶地发现性能差异很大，如下所示：

背后的原因是什么？顺便说一句，我只在发布配置中运行了测试，这里是小测试代码

编辑

我还想分享我提取的 RBTree 代码，以便您也可以运行诊断程序

编辑

我对其他一些数据结构（一些由我创建*，一些来自 .net 框架**）进行了相同的诊断，这是有趣的结果

RBTree 与上面相同（从 SortedSet 类中剥离出来）。我也尝试了 400000 个值，但 RBTree 似乎在使用 FOREVER，我真的不知道为什么。

任何人都可以向我建议任何指向用于插入和删除红黑树的迭代算法的指针吗？.Net/C# 中可用的所有算法都基于递归，我不能相信它可以处理大量数据（因此插入/删除的递归深度很大）。有人有基于迭代的吗？

注意：Goletas.Collection 对 AVL 树使用迭代算法，该算法对大量数据非常有效，我也希望红黑树也有类似的东西。

下周我有一个算法考试，并被要求准备考试。其中一个问题让我很难过。

“我们可以画一棵有7个黑色节点和10个红色节点的红黑树吗？为什么？”

听起来可以很快回答，但我无法解决这个问题。

CRLS 为我们提供了具有 n 个内部节点的 RB 树的最大高度：2*lg(n+1)。

我认为这个问题可以单独使用这个引理来解决，但我不确定。

有小费吗？

红黑（RB）树有哪些应用？是否有任何应用程序只能使用 RB 树而不能使用其他数据结构？

我正在考虑尝试使用树结构进行索引，因为我想测试它是否比我当前的索引实现更快，这本质上是基于哈希的查找。

我已经阅读了有关 B-Trees、AVL-Trees 和 Red-Black Trees 性能的各种问题和文章，并且在性能方面看不出它们之间有多大区别。

人们会推荐什么树结构，为什么？理想情况下，它应该有一个现有的 .Net 实现可用，但我不反对在必要时实现我自己的

是否有一种算法允许删除 RB 中的多个节点，或者从 RB 中删除节点的唯一算法是以某种方式执行此操作：
1. 删除一个和
2. 如有必要，修复树

我一直试图了解两者之间的区别，因为它们适用于用于选择要在某些 CPU 调度程序中运行的任务的不同算法。

将所需时间最短的进程放在左侧并从左侧选择节点运行的 RB 树与将它们放在最短作业第一顺序的队列之间有什么区别？

我在哪里可以找到一个可以使用的？或者就此而言，如果你知道的话，一个很好的“标准”数据结构集合？

除了红黑更容易实现。

在两棵树中，所有操作（插入、删除、查找）似乎都具有 O(log n) 的时间复杂度。我缺少的这些操作之间是否有一定的区别？

如果你用谷歌搜索“red-black”“2-3 tree”，你找不到两者之间的任何比较..

我开始明白红黑通常被认为是最好的。（我听说 [EDIT] 为什么红黑树比 AVL 树（同一类别）[/EDIT] 更快的原因之一是“应用到持久数据结构”的效率，因为重新平衡效率；但这并没有不回答我的问题..)