问题标签 [red-black-tree]

如果我有 10 个元素并从一棵空树开始，以大 O 表示法将 10 个元素插入 Red Black 的复杂性是什么？

是否会超过 O(log 10)，因为每次插入元素时，它都必须为元素搜索适当的位置，并在祖先节点和子节点之间执行一系列旋转。因此，如果我有 N 个元素并在 Red Black Tree 中插入 N 次，那不是 O(n log n) 吗？

谢谢你的帮助。

我试图了解红黑树是如何工作的，假设图片中从第一个到第二个的过渡，我没有任何问题地得到它，在这之后根据教学资源，我需要对红色 G 节点进行本地修复. 因此，作为第二步的修复，G 是否只是简单地着色为黑色以保持红黑属性？

替代文字 http://img683.imageshack.us/img683/4929/rb1.jpg

谢谢

我需要找到一个可以使用以下操作的数据结构：

• 构建(S,k) - O(nlogn)
• 搜索(S,k) - O(logn)
• 插入(S,k) - O(logn)
• 删除(S,k) - O(logn)
• Decrease-Upto(s,k,d) - O(logn) - 这个方法应该减去 d(d>0) 每个 <=k 的节点

显而易见的第一个选择是 RedBlackTree。

但是，我无法找到关于 O(Logn) 中的 Decrease-Upto 的解决方案。如果 k 大于树中的最大键会发生什么 - 这种情况下我必须更新整个树。

有人可以提出其他建议吗？也许一些提示？

我正在大学学习算法课程，对于我的一个项目，我想在 C# 中实现一棵红黑树（实现本身不是项目，但只是我决定选择帮助我的东西） .

我的红黑树应该包含字符串键，我为每个节点创建的对象如下所示：

我已经添加了一些用于打印树、查找根、最小/最大键（按字母表）等的基本方法......

我在插入节点时遇到问题（因此，构建树）。熟悉红黑树的人都知道，在一侧添加节点时，可能会改变树的平衡。要解决此问题，您需要围绕树上的节点“旋转”以平衡树。

我用伪代码写了一个 RightRotate 和 LeftRotate 方法，然后当我尝试在 C# 中实现它时，我遇到了一堆我创建的 sRbTreeNode 对象的引用问题。

这是我为 LeftRotate 方法编写的伪代码：

我收到了直接实施它的建议，但没有使用我最初尝试过的“ref”关键字。我就是这样做的：

现在，当我调试时，我看到它工作正常，但是我传递给这个方法的对象只在方法的范围内旋转。当它离开此方法时，实际节点似乎没有任何变化。这就是为什么我首先想到使用'ref'关键字。

我究竟做错了什么 ？

我正在尝试在 C# 中实现一棵红黑树。我已经创建了一个名为 sRbTreeNode 的对象，它具有字符串键、颜色、左、右和父属性。我成功地实现了方法 Insert、InsertFixUp、LeftRotate、RightRotate、Delete，现在我遇到了方法 DeleteFixUp 的问题。

DeleteFixUp 负责在删除后再次平衡树（使用旋转和更改节点颜色）。

我尝试从一本名为“算法简介”的书中找到的伪代码实现该方法。

这是我的代码：

我每次在不同的地方都会遇到错误“对象引用未设置为对象的实例”......

我在互联网上搜索了这个的实现，刚刚找到了一篇关于 CodeProject 的文章，它的实现和我完全一样。我尝试复制他们的代码，希望我的眼睛错过了一些东西，但它也没有工作......

有人可以帮我，在我开始扯头发之前！！... ?? :)

I've been implementing my own version of a red-black tree, mostly basing my algorithms from Wikipedia (http://en.wikipedia.org/wiki/Red-black_tree). Its fairly concise for the most part, but there's one part that I would like clarification on.

When erasing a node from the tree that has 2 non-leaf (non-NULL) children, it says to move either side's children into the deletable node, and remove that child.

I'm a little confused as to which side to remove from, based on that. Do I pick the side randomly, do I alternate between sides, or do I stick to the same side for every future deletion?

最近在搜索树，遇到了红黑树，困惑的一点是，在rb树中，根节点应该是黑色的就好，现在我将如何决定传入节点是红色还是黑色.

我已经浏览了 wiki 文章，但没有找到解决方案。我可能是错的，但如果有人能指导我了解确切的材料，我会很高兴。

[编辑] 例如，如果我的键是 {7, 2, 4, 1, 9, 10, 8}

这里 7 是根，它呈现黑色，但 2 呈现什么颜色？我们如何决定呢？我们如何决定其他节点采用什么颜色？

我们是否有随机折腾来决定节点的颜色是红色还是黑色。或者是其他一些过程。

谢谢你。

我正在寻找一种类似于 CLR 中的红黑区间树的区间树算法，但默认情况下它支持合并区间，因此不会有任何重叠区间。

换句话说，如果您有一棵包含两个区间 [2,3] 和 [5,6] 的树，并且您添加了区间 [4,4]，那么结果将是一棵仅包含一个区间 [2,6] 的树。

谢谢

更新：我正在考虑的用例是计算传递闭包。区间集用于存储后继集，因为已发现它们非常紧凑。但是，如果您将区间集表示为链表，我发现在某些情况下它们可能会变得非常大，因此找到插入点所需的时间也是如此。因此我对区间树感兴趣。此外，可能会有很多将一棵树与另一棵树合并（即一组 OR 操作） - 如果两棵树都很大，那么使用两棵树的中序游走而不是重复插入每个间隔来创建一棵新树可能会更好。

我正在尝试使用来自linux/rbtree.h. 我可以在内核中的独立空间（例如模块）中正确插入红/黑树，但是当我尝试让相同的代码与or中rb_root声明的函数一起运行时，每次尝试插入时都会得到一个。task_structtask_struct->files_structSEGFAULT

这是一些代码：

在 task_struct 中，我rb_root为我的树创建了一个结构（不是指针）。在init_task.h宏INIT_TASK(tsk)中，我将其设置为等于RB_ROOT。要进行插入，我使用以下代码：

这就是问题发生的地方。

我的插入命令是所有 RBTree 内核文档中记录的标准插入：

有什么我想念的吗？

如果我在task_struct? 如果我rb_root在模块内部制作这个插件可以正常工作。但是，一旦我将实际的树根放入task_struct或什至 中task_struct->files_struct，我就会得到一个SEGFAULT. 不能在这些结构中添加根节点吗？

非常感谢任何提示。我已经尝试了几乎所有我能想到的东西。

编辑：

SEGFAULT尝试打印和访问树的任何行时，我在下一行得到一个。通过这一行，您应该了解我如何处理指针。rb_entry并且rb_first是内核中已经可用的方法。current是指向任务结构（当前工作进程）的指针，树是我的根节点（不是指针），它是任务结构的成员（我添加了）。rb_first需要传递一个指针*rb_root。我做错了。

我对 rb-trees 有疑问。根据维基百科，rb-tree 需要遵循以下内容：

1. 一个节点要么是红色的，要么是黑色的。
2. 根是黑色的。（这条规则在某些定义中使用，在其他定义中不使用。因为根总是可以从红色变为黑色，但不一定反之亦然，这条规则对分析几乎没有影响。）
3. 所有的叶子都是黑色的。
4. 每个红色节点的两个孩子都是黑色的。
5. 从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。

众所周知，一个 rb-tree 需要平衡，并且高度为 O(log(n))。但是，如果我们插入一个不断增加的数字序列（1,2,3,4,5...），理论上我们会得到一棵看起来像列表的树，并且它的所有高度都为 O(n)节点黑色，这与上面提到的 rb-tree 属性并不矛盾。那么，我哪里错了？？

谢谢。