问题标签 [red-black-tree]

我有一个项目，我必须在从兆字节到兆字节的数据上实现快速搜索、插入和删除操作。我最近一直在研究数据结构并分析它们。具体来说，我想介绍3个案例并提出问题：

1. 数据远远超过内存一次可以处理的数据（样本范围为 10-15 TB）。在这种情况下，我会将数据结构存储在磁盘上。

2. 与系统的内存相比，数据相对较少，因此可以在内存中存储和操作以提高速度。

3. 数据超过可用内存，并假设它小于页面文件中可能的连续数据块的大小。因此，我将数据结构存储在磁盘上的文件中，并对文件进行内存映射。

我得出的结论是：

对于案例 1，我应该使用 B-Tree 来加快访问速度，因为它可以节省磁盘旋转产生的延迟

对于案例 2，我应该使用红黑树来更快地访问，因为数据在内存中，而不是。如果我使用 B 树，在更糟糕的情况下需要扫描的元素会少于我必须做的一个

对于案例3，我对此表示怀疑，磁盘上的页面文件使用本机OS I/O对文件进行操作，那么B树应该是更好的选择还是红黑树？

我想知道以上三个结论哪里对，哪里不对，以及如何在三个不同的情况下提高性能。

我正在使用 C++ 语言，带有一棵红黑树和一棵 B 树，它们都是我从头开始设计的。我正在使用 Boost 库进行文件映射。

更新 1::在 stackoverflow 中阅读这篇文章。得到了一些真正好的见解，这让我觉得我在案例中所做的比较类型可能是错误的。在投票最多的答案http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html中发布了一个链接

wiki上的定义似乎不准确：

http://en.wikipedia.org/wiki/Red-black_tree#Properties

所有黑色节点的树是红黑树吗？

更新

由于 rbtree 的定义不那么严格，我们如何决定将黑色节点的子节点打印为红色还是黑色？

我正在开发一个涉及维护两个本地目录之间一致性的应用程序。具体来说，目录应该是相同的，除了其中一个目录中的所有文件都以某种特定方式修改（这部分对我的问题不重要）。

在运行时，我的应用程序运行两个进程，它们侦听每个路径下发生的变化，并在必要时执行相关操作以使它们恢复同步。

就我的具体问题而言：我正在寻找有关何时启动应用程序的诡计情况的建议。此时，每个进程都需要检查它所关注的两个路径下的所有文件/文件夹，以查看在应用程序未运行时是否有任何变化。（让我们假设应用程序在关闭时无法被操作系统通知任何发生的事情，因此需要直接检查每个文件/文件夹。）

每个进程都可以访问（并维护）其指定路径下所有文件/文件夹的持久数据结构。我在想每个文件和文件夹的数据结构中应该包含以下内容：

• 文件/文件夹名称；
• 文件哈希（CRC32）；
• 文件/文件夹最后一个 mod 数据；和
• 文件/文件夹大小。

这些信息显然有助于检查文件/文件夹的任何更改，但是存储它们的最佳方式是什么？

在我看来，处理应用程序启动情况的一种明智方法是让每个进程递归扫描其指定路径下的所有文件/文件夹，并将扫描到的每个文件的元数据与其数据结构中存储的元数据进行比较. 然后流程还应该遍历数据结构以查找已从路径中删除的内容。在此过程中可能会遇到的一些情况是：

• 文件已修改（在数据结构中找到文件名，但哈希值不同）；
• 添加的文件（在数据结构中找不到相同的文件名或哈希）；
• 文件重命名（具有相同哈希的文件存在于数据结构中，但文件名不同）；
• 添加的文件夹（数据结构中没有文件夹名称）；
• 删除文件夹（数据结构中的文件夹名称，但不在路径下）；
• 文件夹重命名（棘手的一个）。

那么，用于此任务的最佳数据结构是什么？在我的脑海中，我正在考虑某种形式的排序关联数组，例如，一棵红黑树，它存储file和folder对象。每个file对象都包含和属性name，而每个对象都包含和属性，其中存储了另一个关联数组，其中包含下面的所有内容。给定任意文件的路径，例如 ，您从根 ( ) 开始，检查等等，直到您到达的父对象。hashmod-datefoldernamechildrenchildren/foo/bar/file.txtfoobarfile.txt

我能想到的另一种选择是仅将所有内容平坦地存储，这样就有一个红黑树，其中每个键是每个文件/文件夹的完整路径，值是file/folder对象。这可能会更快地进行检索，但是如果不遍历所有值就不可能检测到重命名的文件/文件夹，这听起来很昂贵。在第一种方法中，识别重命名可能只涉及检查数据结构的一部分而不是全部。

抱歉，上述想法并没有经过深思熟虑。该领域的最新技术是什么，对于这些类型的问题是否有任何成熟的方法？

我知道 STL 中的 Map 容器内部是一棵红黑树，它是一棵自平衡树。

在 Map 中，最低的元素位于树的顶部。因此，对于整数到“任何东西”的映射，最小的整数将位于顶部，依此类推。它总是平衡自己。这就是为什么我们在搜索整数及其相关值时会得到 log n 复杂度。

但是在将字符串映射到“任何东西”的情况下，如果可以，它如何平衡和排序自己？哪个字符串会在树的顶部？它是否与 ASCII 值匹配？

这可能很蹩脚，但我需要知道这一点，因为我必须确保我在代码中遵守 log n 的复杂性。

从“Introduction to Algorithms 2nd edition”我得到了这个删除算法：

现在这个算法的问题很少，一个主要问题是，如果你尝试用节点 1、2、3、4、5、6（按此顺序放置）构建树（你可以在这里做），然后删除节点 2 ，该算法的第 4,5 和 6 行返回 nullptr (x == nullptr)。谁能帮我这个？

以下是辅助算法（来自同一本书）：

执行

假设我有一棵二叉搜索树，它最初满足所有红黑条件，并且对于某个集合S中的每个整数s都包含一个节点。接下来，我要新建一个节点；说a（不在S中）。

这种添加的结果在重新平衡后是否独一无二？

换句话说：插入节点后是否只有一种方法可以重新平衡红黑树？

我相信它们并不是独一无二的，尽管我没有提供任何证据（也没有多少信心）。我只是想知道是否有比我更博学的人会如此好心地启迪我？

摘自“算法简介，第 2 版”：C++ 中删除算法的实现如下所示：

问题是，当我按 1、2、3、4、5、6、7、8 顺序创建树时，树看起来像这样：

如果我要从这棵树中删除根，我会得到：

这段代码显然不起作用，请记住它是从本问题开头提到的书中逐行实现的。

谁能帮助我并向我解释我该如何解决它？

我已经阅读了一些关于自平衡二叉树的问答，但我对所有这些都不太熟悉。

我认识的第一个是 AVL，第二个是红黑树。

有一点我不太明白：根据一些书籍和文章，AVL 执行搜索的速度比红黑树快一点，嗯，这是可以理解的。

1. 那么红黑树相对于 AVL 的优势是什么？

2. 在 AVL 中，可能在每次插入之后，我们都必须检查平衡，但在红黑树中，我们不必经常做类似的事情，对吧？

PS：我搜索了类似的东西，但我没有得到令人满意的答案。希望有朋友可以给我详细的自平衡树对比。

我在课堂上得到了一棵红黑树的代码。用于创建节点的结构没有父指针。我的大部分项目都在工作，但我无法弄清楚如何在 O(lg n) 时间内计算排名。通过排名，我的意思是如果您要进行中序遍历并将键保存到从索引 1 开始的数组中，那么给定键将存储的索引。这样做将在 O(n) 时间内完成，但这是不允许的。

通读 CLRS，扩充数据结构一章有代码返回给定键的排名。这正是我所需要的，但问题是代码使用了父指针。由于我们从未在任何红黑树示例中使用父指针，并且此代码不包含父指针，我不认为我们要更改整个给定代码只是为了使排名起作用，这导致我相信有一种方法可以在不使用父指针的情况下做到这一点。

节点结构中存在的（字段？）是：键（int）、指向左孩子的指针、指向右孩子的指针、子树大小（int）和颜色（int）。

所有代码都是用 C 语言完成的。我正在寻找的是这是否可能，以及我如何在有或没有源代码的情况下完成此任务（一个好的解释将是完美的）。

我已经了解以下数据结构，并且正在寻找它们在实际应用程序中的示例用法；

• 二叉搜索树
• 红黑树
• 区间树（增强 RBT）
• 哈希表