问题标签 [red-black-tree-insertion]

我正在尝试在 Rust 中实现红黑树。在与编译器斗争了 2 天后，我准备放弃并在这里寻求帮助。

这个问题对我有很大帮助：如何在 Rust 中处理/规避“无法分配给...在 & 引用后面”？

我查看了 Rust 中 RB-Trees 的现有示例代码，但我看到的所有示例代码都使用了某种形式的不安全操作或null，我们不应该在这里使用。

我有以下代码：

该行new_node.parent = Some(Box::new(self));给了我错误。我理解为什么会发生错误（self被声明为可变引用）并且我不知道如何解决这个问题，但我需要self成为一个可变引用以便我可以修改我的树（除非你可以提出更好的建议）。

我试图将 声明T_Node为具有可变引用而不是 just Node，但这只会产生更多问题。

我也乐于接受有关更好地选择变量类型的建议以及其他建议。

任何帮助表示赞赏。

所以我在搞乱红/黑树可视化器（https://www.cs.usfca.edu/~galles/visualization/RedBlack.html），并遇到了以下树（按 10、40 的顺序插入, 25, 35, 30, 45)。我知道 AVL 树不能在两条最短路径和最长路径之间存在高度差，但如果这同样适用于红/黑树，我会感到困惑。有人能指出使这棵树有效的特定属性，以便我加深对这种数据结构的理解吗？

我在考试中被问到这个问题，但是我对老师的回答不太相信，请问您对此有何看法。

红黑树上的旋转...

1. 保留所有节点的黑色高度。
2. 保留按顺序排列。

以上说法正确的是：

    A. (1) 单独
    B. (2) 单独
    C. (1) 和 (2)两者
    D. (1) 和 (2)都不是。

老师声称旋转不会保留黑色高度，答案是B：它仅保留按顺序排列。但是，我坚信它保留了所有节点的黑色高度，答案是C，而不是B。

我是对的还是我的老师是对的？

我一直在玩 RBT 可视化工具，但不明白如何将以下内容视为高度平衡。维基百科文章声称，如果满足 RBT 属性，则最远叶子的高度不大于最近叶子高度的两倍。根据我的理解，即使满足 RBT 属性（深度 1 为 1，深度 6 为 3），以下内容也会违反此属性。我的逻辑在哪里有缺陷？

您好，我有一个任务是实现 RBT 树，然后作为应用程序在其中插入字典，以实现更有效的插入和搜索操作。当我插入字典文件时，它只读取第一个单词和第二个单词，但不修复第二个单词的插入，当我调试问题时，此错误显示在enter image description here中。问题出在 insertfixup 方法中。我认为这就是你所在的位置，但我不确定为什么即使我没有用任何东西初始化你，它也会给我同样的错误，所以我尝试用 TNULL 初始化它，它仍然是一样的，我希望我的问题很清楚

我正在构建一个红黑树作为一个学校项目，我已经完成了代码，但由于某种原因，当我运行程序测试用例时，我在 nilNode 为黑色时得到了错误，我无法弄清楚为什么会这样。

程序代码

我试图做什么 - 更改节点结构中的颜色 - 更改 nill 节点的颜色 - 更改根节点的颜色

我得到的错误

我正在学习如何在 Java 中实现红黑树，我查阅了 Sanfoundry 的源代码：https ://www.sanfoundry.com/java-program-implement-red-black-tree/ 但我不能了解插入节点的功能代码在这里：

谁能向我解释为什么当一个黑色节点同时有 2 个红色子节点和 handleReorient 函数的含义时我们需要修复颜色，tks all ！

在将节点插入红黑树之后，我正在尝试编写一个函数来平衡红黑树，但是我得到了一个空指针异常。在第 156 行，当我将 temp 分配给 node.parent.parent.right 时，temp 为 null，这意味着 node.parent.parent.right 为 null。我不确定为什么。任何人都可以查看我的代码并尝试帮助我弄清楚为什么会出现这个问题吗？

所以我从这里（GeeksForGeeks）获取了一个插入红黑树的代码并稍微修改了它。

特别是BSTInsert功能：

我认为root->left->parent = root;当我插入一个新节点时，上面的函数正在为每个节点执行。因此，我希望它只将新父节点分配给新节点，而不是执行前一个节点的行。因此我将代码修改为：

基本上，它将新指针 pt 的父级设置为空根的父级，如果空根没有父级（主树的根），那么它将 pt 设置为根。

这是我的全部修改代码，有更多（次要）更改：

现在我的问题是，为什么它会抛出错误？我想不出我做错了什么，我在这里错过了什么吗？如果是这样，那么正确的修改方法是什么BSTInsert ，它不会引发错误，也不会一遍又一遍地重新分配父母。

当我尝试使用1）红黑插入算法和
2）首次转换为 2-4 棵树时创建/插入红黑树时，
两个答案都会产生不同的结果。可能吗？还是我没有正确实施？