我在 Coursera 算法课程之一中遇到了这个问题，并意识到我不知道该怎么做。但是，我仍然对此有一些想法。我首先想到的是使用优化的位集（如 Java 的BitSet）来获取映射节点的key -> color. 因此，我们只需要为整棵树分配一个比特集并将其用作颜色信息源。如果树中没有重复的元素 - 它应该可以工作。
很高兴看到其他人对此任务的想法。
问问题
3787 次
5 回答
22
只需修改 BST。对于黑色节点，什么都不做。而对于红色节点，交换它的左孩子和右孩子。在这种情况下，一个节点可以根据其右孩子是否大于其左孩子来调整为红色或黑色。
于 2015-07-26T02:49:54.540 回答
11
使用节点中一个指针的最低有效位来存储颜色信息。在大多数平台上，节点指针应该包含偶数地址。在此处查看详细信息。
于 2013-04-18T16:36:26.823 回答
1
一种选择是使用需要较少记账的树，例如展开树。但是，展开树尤其不适合迭代（它们在随机查找方面要好得多），因此它们可能不适合您正在工作的领域。
您也可以根据节点位置为整个红黑树使用一个 BitSet，例如根是第 0 位，根的左分支是第 1 位，右分支是第 2 位，左分支的左分支是第三位等；这样，是否存在重复元素无关紧要。在遍历树时，记下您所在的位。
就空间而言，为树使用一个位集而不是为每个节点分配一个布尔值会更有效；每个布尔值将占用至少一个字节，并且可能会占用一个字，具体取决于对齐方式，而位集将仅占用每个节点的一位（加上 2x 位以考虑最短分支长度的一半的最大不平衡树）最长的分支）。
于 2013-04-18T16:53:07.380 回答
1
我们可以将红色节点定义为将孩子放在错误位置的节点，而不是在孩子上使用布尔属性。
如果我们这样做，所有叶子节点都保证是黑色的，我们应该在插入新节点时将父节点与他的兄弟节点交换（使他成为红色）。
于 2017-07-27T10:58:18.577 回答
1
我们可以使用 2 条规则：
因为根节点总是黑色的，所以红色节点总是有一个父节点。
RB BST 的顺序总是 left_child < parent < right_child
然后我们将这样做：
保持黑色节点不变。
对于红色节点，我们称其为 R，我们假设它为其父节点 P 的左子节点。
将红色节点值从 更改R 为R'，而R' = P + P - R
现在R' > P，但是因为它是左子树，我们会发现顺序不匹配。
如果我们发现订单不匹配，那么我们就会知道它是一个红色节点。而且很容易回到原来的样子R = P + P - R'
于 2018-03-26T13:49:12.037 回答