问题标签 [red-black-tree]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - 红黑树插入问题
我是红黑树的新手，我遇到了这个问题的根源。旋转和插入方法看起来是正确的。但是，当我输入数字时
100
45
34
55
74
50
130
120
125
160
165
150
我从程序中得到以下输出。最右边的数字是节点中的数字，然后是颜色，然后是节点的父节点。根节点没有列出父节点。节点 45 和 74 都是 RED 并且这两个节点不能都是红色的，因为这违反了 RED Black Tree 属性：红色的父母总是有两个黑色的孩子。在这个问题上的任何帮助都会很棒。
34 [BLACK] (45)
45 [RED] (74)
50 [RED] (55)
55 [BLACK] (45)
74 [RED] (120)
100 [BLACK] (74)
120 [BLACK]
125 [BLACK] (130)
130 [RED] (120)
150 [RED] (160)
160 [BLACK] (130)
165 [RED] (160)
红黑树.h /*
RedBlackTree.cpp BST::insert(rbnode) 函数适用于此类，因为函数中的差异是在使用其他函数之前完成的。
algorithm - 红黑树伪代码冗余
在介绍算法第三版时，他们有一个红黑树删除的伪代码实现。这里是...
TREE-MINIMUM 只是找到树中的最小值，RB-TRANSPLANT 获取第二个参数的父节点并让它指向第三个参数，并让第三个参数的父节点成为第二个参数的父节点。
根据我的评论，他们测试 yp 是否为 z，如果是，则将 xp 设置为 y。但是 x 已经是 y.right，所以这就像说 y.right.p = y，但是 y.right.p 已经是 y！他们为什么这样做？
这是他们的解释...
“但是，当 y 的原始父节点是 z 时，我们不希望 xp 指向 y 的原始父节点，因为我们正在从树中删除该节点。因为节点 y 将向上移动以占据 z 在树中的位置，所以在第 13 行将 xp 设置为 y 会导致 xp 指向 y 的父节点的原始位置，即使 x == T.nil。”</p>
所以他们想让 x 的父母成为 y……它已经是 y……
algorithm - 红黑树是如何工作的？
关于红黑树有很多问题，但没有一个回答它们是如何工作的。为什么叫红黑？这如何使树保持平衡（从而提高不平衡的正常二叉搜索树的性能）？我只是在寻找它如何工作以及为什么工作的概述。
c# - 红黑树插入修复错误
我有一个关于在 c# 中插入红黑树的作业问题。我编写了下面的代码，该程序在添加前 3 个数字时没有任何问题。当我尝试添加第 4 个数字时，我得到一个 NullReferenceException。我试图解决这个错误 2 天，但我无法弄清楚。
}
c++ - 红黑树 - 预购印刷树
我已经基于 Cormen 实现了红黑树，但我一定破坏了一些东西，因为它不能正常工作。我相信我正确地重写了 Cormen，但我不知道出了什么问题……我怎么知道……我取了 10 个值并检查了树的外观（http://secs.ceas.uc.edu/~franco /C321/html/RedBlack/redblack.html）和我的看起来确实不同。因此，我恳请任何可以帮助我找出问题所在的提示，整个代码很长，但是没有它我无法重现错误，对此感到抱歉。我认为有罪的是插入后旋转和/或修复......
编辑：新代码，但它仍然会导致红色甚至黑色违规，尽管我可以发誓我只是将伪代码重写为 C++ ......
database - 红黑树有什么缺点？
从我读到的关于红黑树的所有内容来看，它们似乎是存储数据的最佳数据结构。
我正在尝试建立一个数据库，我想知道，就红黑树的实现而言，我应该在哪里更加小心，不应该做什么。
红黑真的那么完美吗？
c++ - 红黑树-删除
我已经为 RBT 实现了删除功能（基于 Cormen），它看起来很有效，但是预先测试删除 + 打印树给了我错误的答案。我花了几个小时寻找可能出了什么问题，但找不到任何东西......
这是按顺序打印树的功能：
以下是要删除的其他重要内容：
data-structures - 为什么 avl 树的搜索速度比红黑树快？
我在avl树搜索速度更快但无法理解的几个地方阅读过它。据我了解：红黑树的最大高度 = 2*log(N+1) AVL 树的高度 = 1.44*logo(N+1)
是因为AVL更短吗？
algorithm - 我可以将红黑树表示为二叉叶树吗？
我一直在玩 Haskell 中的 RB 树实现，但很难稍微改变它，所以数据只放在叶子中，就像在二叉叶树中一样：
除了节点的颜色之外，内部节点还将保存其他信息，例如树的大小（就像在正常的 RB 树中一样，但数据仅保存在叶子中）。我也不需要对插入的数据进行排序。我在插入数据时仅使用 RB 来获得平衡树，但我想保持插入数据的顺序。
原始代码是（来自冈崎书）：
我将其更改为：（导致异常：函数 ins 中的非详尽模式）
原来的平衡函数是：
从我上面的代码中可以明显看出，我做了一些改变。
提前感谢您的帮助:)
编辑：对于我正在寻找的那种表示，Chris Okasaki 建议我使用二进制随机访问列表，如他的书中所述。另一种方法是简单地调整 Data.Set 中的代码，它被实现为权重平衡树。
algorithm - 我可以在红黑树中插入未排序的数据吗？
虽然我仍在努力寻找解决方案问题，我有另一个可能更容易。下面是冈崎红黑树实现的插入函数。我想要做的是在我插入树时保持数据未排序。因此，每次插入时，数据总是会转到最左边/最底部的叶子。无需比较 x < y、x > y 或 x == y。一开始似乎很简单，只需移除这些防护，然后只做：ins s@(T color ayb) = balance color (ins a) y b。行为似乎是树保持平衡，但颜色变得有点混乱。最终这会影响未来的插入。知道如何实现这一点吗？我认为这可能是我对上一个问题的第一步。我刚开始玩 Haskell，所以我没有把它简单化。非常感谢。