问题标签 [red-black-tree]

我正在寻找一个带有红黑树和链接列表实现的库，它提供了不能快速失败的迭代器。我希望拥有与使用 STL 在 C++ 中相同的功能，即：

• 在树/列表中的插入不会使任何迭代器无效
• 删除仅使指向被删除元素的迭代器无效
• 可以以某种方式存储迭代器的“位置”并引用它指向的值

这个实现会很好，因为它可以在使用列表/树的一部分时提供修改列表/树的能力。这里有些例子：

• 将链表/红黑树中的相邻元素获取到 O(1) 中的某个存储值
• 批量插入/删除（没有限制，例如每个位置增量一个删除）
• 通过迭代器的位置在 O(1) 中拆分链表
• 存储迭代器位置时更有效的删除（例如，通过将迭代器保持在链表中的某个位置，删除是 O(1)，而不是 O(N)）

我还希望该库/源代码/实现具有一些 Apache/GPL 友好的许可证并且具有相当的可扩展性（因此我可以进行自己的修改以实现一些操作，例如上面示例中的操作）。

如果不存在这样的库，是否有其他库可以帮助我自己实现这两个数据结构？

我开始研究一个新的家庭项目，我需要用那里的路径索引特定的文件名。该程序将索引我本地硬盘上的文件，而无需处理文件的内容（所以我假设/希望它会是简单的实现）。首先，用户将插入一个文件扩展名列表以获取索引（在设置期间）。然后程序将运行并创建保存用户输入的特定文件路径的数据结构。

按数据结构检索数据如下所示：

我的硬盘上文件的路径=函数（用户输入的文件名）

我想了很久，写了一个数据结构的设计，这是我的建议（设计插图）：

1. 我将使用带有散列函数的数组将扩展名映射到单元格（每个单元格表示
   扩展文件的第一个字母）。

2. 在每个单元格内都会有一个以相同字母开头的扩展名列表。

3. 对于列表中的每个节点，都会有一个用于搜索文件名的红黑树，然后在我们找到文件名后，程序将检索存储在树
   节点中的文件的路径。

哦，顺便说一句，我通常用 c（低级）或 c++ 编程。

我这里需要一些一般的背景知识，我在网上找不到..

我的主要疑问是，如果我想用红黑树实现 Multiset 结构，我是否必须将 Multiset 的每个元素（每个重复元素也......）放入 RB 树中，还是有办法保存唯一元素以及它们的多样性？

所有这一切都应该只用一棵红黑树完成，没有其他结构。（你可能已经猜到了，这是一个家庭作业。）

我正在寻找如何在不使用虚拟节点（即叶节点实际上是空指针）的情况下实现删除红黑树中的元素的指南。我在 google/wikipedia 和标准文献（sedgewick 和 cormen 等）上找到的所有实现都使用虚拟 NIL 节点，我想避免这种情况。

如何在使用自平衡树实现的关联数组中处理冲突？如果两个对象具有相同的哈希值，它们是存储在连接到树节点的链表中还是创建了两个节点？如果是前者，那么它是怎样的O(log n)，如果是后者，二叉搜索树如何处理相同的键（哈希）？

我一直在尝试创建一个仅实现插入、搜索和中序遍历方法的红黑树，以便我可以将它与我之前制作的类似 AVL 树进行比较。我已经使用了 Cormen 文本中的所有算法：算法简介，但由于某种原因，我似乎无法让它正常工作。

例如，当我插入 a、b、c 并尝试进行中序遍历时，我会丢失 c。我已经检查了文本中的算法大约 10 次，以确保我做的一切都是正确的，而且我似乎找不到任何错误。

谁能告诉我我是否insertFix()正确地执行了该方法以及旋转。

下面是我的头文件，让您了解我如何设置节点：

这是我的insertFix()方法，它在正常插入之后运行，您可以在任何普通的二叉搜索树中找到：

下面是我的两种旋转方法，一种是右旋转（RR），另一种是左旋转（LR）：

我知道这是要查看的大量代码，但我正在竭尽全力试图找出我做错了什么。我有一种感觉，我在其中一个旋转的某个地方弄乱了指针，但我不知道在哪里。任何帮助将非常感激！

红黑树中的一个节点可以有一个红色和一个黑色的孩子吗？

我有以下树，我在这里只指定了颜色。叶节点被忽略。

我的作业中的一个问题是找到确切的下限

在 rb 树中。界限一定不是渐近的。有什么建议么？

您的帮助将不胜感激。

I'm currently implementing a red-black tree data structure to perform some optimizations for an application.

In my application, at a given point I need to remove all elements less than or equal to a given value (you can assume that the elements are integers) from the tree.

I could delete the elements one by one, but I would like to have something faster. Therefore, my question is: if I delete a whole subtree of a red-black tree, how could I fix the tree to recover the height and color invariants?