问题标签 [red-black-tree]

I have a red-black tree (binary tree, all the leaves are within 2 levels). I can navigate through nodes: to left, right or parent. I know the entire count of nodes.

I have to find the N-th smallest element in a tree. Is there any way to do this faster than in O(n)? Any ideas of optimizing access by index?

这是一棵红黑树。

对于伪代码“p[z] <-- y”，java 中的解释是：

或者

谢谢 ：）

我们被要求在 Java 中实现一棵红黑树，但我不确定这是如何完成的。如果有人能评论我的节点类以实现 r/b 树，那就太好了。开始了：

}

对于我的数据结构类，我们被要求采用先前实现的平衡树（来自先前的项目）并使用它来实现 C++ 标准映射类的部分内容。

http://cplusplus.com/reference/stl/map/

我认为最明显的第一步是模板化整个类，允许单独的键和存储类型。当然，我遇到了模板问题。通常，我的模板一直有效，直到我尝试对使用本地嵌套数据类型“rbNode”的函数进行模板化。如果我在函数定义中包含模板参数，则会出现语法错误。如果我将它们排除在外，我会收到“不包括模板参数”错误。

这是在 Visual Studio 2010 中给我错误的类实现（下面列出的错误）：

然而，这个函数编译得很好，上面的函数被注释掉了：

特别是，我得到

missing ';' before '*' 并且 missing type specifier - int assumed. Note: C++ does not support default-int 在线上实现了“LLRotation”的名称（在评​​论中指出）。我对模板不是很有经验，所以我觉得我犯了一个非常愚蠢的错误。无论如何，如果您需要更多我的代码或更多信息，请告诉我。任何帮助是极大的赞赏。

注意：我确信我的代码中有很多不好的做法，等等。我还在学习。随意指出它们，但我最关心的是模板问题。

好的，我正在阅读一些关于 RedBlackTrees 的代码。我注意到这一行“v1 = v2 = v3 = v4;” 我理解类似“v1 += v2”（将 v2 添加到 v1 的当前值）和“v1 = v2”（创建从 v2 到 v1 的引用）等内容。

但我很好奇内存/引用中发生了什么 current = parent = grand = header;

http://faculty.washington.edu/moishe/javademos/REDBlack/RedBTree.java

编辑：晚上 10:46

我仍然需要等待 10 分钟才能批准问题，对不起等待的女士们和先生们。

I cannot manage to get my head around redbacktrees, based on this implementation http://pastebin.com/Gg3YbPUg.

I've just made a simple tree using the numbers 1,14,15,2,11,7,5,8

And based off the example from http://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html, My Tree should look something like...

And my console output from the printTree function

Is...

(for reading purposes I have renamed 0 and 1 as COLOR RED AND BLACK) From what I understand the "header" variable is the root of the tree.

If I was to do something like

From the above pastebin implementation of RedBlackTree how do I know what my current parent element is for n?

来自Data Structures and Problem Solving Using Java的原始 Mark Allen Weis RedBlackTree 实现在这里找到。

我似乎无法理解从树中删除节点的问题。在阅读了维基百科资源后，我注意到“is_leaf()”函数。这个和 Mark Weis 实现的问题是没有办法分辨哪个节点是叶子，哪个不是叶子

Is_Leaf java实现

控制台输出

树格式（来自控制台）

规则：

1. 根是黑色的
2. 每个红色节点都有一个黑色父节点
3. 红色节点的任何子节点都是黑色的 - 红色节点不能有红色子节点
4. 从根到叶的每条路径都包含相同数量的黑色节点

所以我的问题是如何实现从这个红树和背树的实现中删除？

我有一个订单统计增强红黑树。

它在大多数情况下都有效。但我需要实现一个快速函数（O（lg n）），它主要按排序顺序返回节点的位置。就像我教科书中的 OS-rank 函数一样。但有一个转折：如果两个节点具有相同的分数，则返回值应该相同。这是 os-rank 函数（在伪代码中，对于给定的节点 x，其中 root 是树的根）。

但是：我需要的是，如果 A 有键 1 而节点 B 有键 1，则函数对两者都返回 1。等等。我尝试过这样的事情。

你猜怎么着：一个测试用例失败了。我想知道这是否是一种正确的做事方式，或者我是否犯了一些我没有看到的错误（否则错误出现在 Node.#nodeswithkeyhigher(key) 函数中）。

我已经实现了一棵红黑树，但效果不佳。它以不正确的方式插入节点。我认为这是因为 FixUp。有谁知道我错在哪里？当我插入（1、4、9、16）时。在节点 16，它将根颜色设置为红色。然后它停止。

我已经调试了它，但我自己无法找到错误。我是 c# 的新手，而且我现在已经工作了大约 3 个小时。没有成功。

这是我的代码：

我一直在实现一个 LLRB 包，它应该能够在Sedgewick 描述的自下而上 2-3 或自上而下 2-3-4 两种模式中的任何一种模式下运行（代码- 改进的代码，虽然只处理 2-这里有3 棵树，感谢 RS 的指针）。

Sedgewick 对 2-3 模式的树操作提供了非常清晰的描述，尽管他花了很多时间谈论 2-3-4 模式。他还展示了在插入过程中对颜色翻转顺序的简单更改如何改变树的行为（在 2-3-4 中向下拆分或在 2-3 向上拆分）：

然而，他用以下内容掩盖了 2-3-4 LLRB 中的删除：

下一页的代码是 LLRB 2-3 树的 delete() 的完整实现。它基于在自顶向下的 2-3-4 树中插入方法的逆向：我们在沿着搜索路径向下的途中执行旋转和颜色翻转，以确保搜索不会在 2 节点上结束，这样我们就可以删除底部的节点。我们使用方法 fixUp() 在 insert() 代码中的递归调用之后共享颜色翻转和旋转的代码。使用 fixUp()，我们可以在搜索路径上留下右倾的红色链接和不平衡的 4 节点，确保这些条件在向上树的过程中得到修复。（该方法对 2-3-4 树也是有效的，但是当搜索路径之外的右节点是 4 节点时需要额外的旋转。）

他的 delete() 函数：

我的实现为 2-3 树上的所有树操作正确维护 LLRB 2-3 不变量，但对于 2-3-4 树上的右侧删除子类失败（这些失败的删除导致右倾斜的红色节点，但滚雪球到树不平衡，最后是空指针取消引用）。从对讨论 LLRB 树并包括在任一模式下构建树的选项的示例代码的调查来看，似乎没有一个正确实现从 2-3-4 LLRB 中删除（即没有一个提到额外的旋转，例如 Sedgewick 的 java上面和这里）。

我很难弄清楚他所说的“当搜索路径之外的正确节点是 4 节点时额外旋转”是什么意思；大概这是向左旋转，但是在何时何地？

如果我在调用 fixUp() 之前或在 fixUp 函数结束时向左旋转通过 4 节点等效项（即 RR 节点）或右倾斜 3 节点等效项（BR 节点），我仍然会得到相同的不变矛盾.

这是我发现的最小失败示例的树状态（通过从 0 到相应最大值的顺序插入元素生成）。

第一对树显示了从删除元素 15 之前的不变一致性状态到之后的明显破坏状态的转换。

第二个与上面基本相同，但删除了 0..16 的 16 个（删除 15 个导致相同的拓扑）。请注意，不变矛盾设法跨越根节点。

关键是要了解如何将在树向下遍历到目标节点期间产生的违规恢复。以下两棵树分别显示了上面的第一棵树在分别向左和向右走之后的样子（没有删除，在使用 fixUp() 向上走之前）。

尝试在不使用 fixUp 的情况下删除“-1”后：

尝试在不使用 fixUp 的情况下删除“16”后：

当节点只有一个红色的右孩子时，尝试向左旋转似乎是解决方案的一部分，但它不能正确处理连续的两个红色右孩子，当两个孩子都是红色时，在此之前使用 FlipColor似乎进一步改善了这种情况，但仍然违反了一些不变量。

如果我进一步检查右孩子的右孩子在其兄弟姐妹为黑色时是否为红色，如果这是真的，我只失败一次，但此时我觉得我需要一个新的理论而不是一个新的本轮.

有任何想法吗？

作为参考，我的实现在这里可用（不，它不是 Java）。

跟进：

我对此感兴趣的部分原因是为了证实许多人声称 2-3 LLRB 树比 2-3-4 LLRB 树更有效。我的基准测试已经证实了插入和删除的这一点（2-3 大约快 9%），但我发现 2-3-4 树的检索速度要快得多。

以下时间在运行中具有代表性且一致：

第一列是工作台名称，第二列是操作数，第三列是结果。i5M 2.27 上的基准测试。

我已经查看了 2-3 树和 2-3-4 树的分支长度，其中几乎没有解释检索差异（从根到节点的平均距离和 1000 棵树的 SD，每棵树都有 10000 个随机插入）：