在红黑树中存储颜色信息时如何节省内存？

Question

我在Coursera算法课程中遇到了这个问题，意识到我不知道如何解决。但是，我对此有一些想法。脑海中浮现出的第一件事是使用优化的位集（如Java的BitSet）来获取映射节点的key -> color。所以，我们只需要为整个树分配一个位集，并将其用作颜色信息源。如果树中没有重复元素，那么它应该可以工作。

很高兴看到其他人对这个任务的想法。

- Vladimir Kostyukov

Answer 1

只需修改二叉搜索树(BST)。对于黑节点，不做任何操作。对于红节点，交换其左子节点和右子节点。在这种情况下，一个节点可以根据其右子节点是否大于其左子节点来确定为红色或黑色。

- icystar

---

这不能用于没有两个子节点的节点。 - Jingguo Yao

当然可以：只需检查一个节点是否在错误的位置。如果没有节点，则无需检查，因为我们从不给空节点设置红色链接。 - lwassink

如果“空节点”表示没有任何子节点的节点，则可能存在红色的“空节点”。只需检查红黑树维基百科条目upload.wikimedia.org/wikipedia/commons/thumb/6/66/…中的示例即可。鉴于此，我认为所提出的方案将无法区分红色的“空节点”和黑色的“空节点”。 - victorx

这听起来比被接受的答案要糟糕得多 - 你需要检查两倍数量的链接！ - nspo

Answer 2

使用节点中的其中一个指针的最低有效位来存储颜色信息。对于大多数平台，节点指针应该包含偶地址。详见此处。

- Alexey Frunze

---

你说得完全正确，这是最常见的方法。然而，在Java中，这是不可能的，因为Java不会暴露其指针的位。虽然我不确定情况是否如此，但OP可能正在使用Java。 - templatetypedef

@templatetypedef 这个问题并没有明确针对Java，它只是提到了一个类似于Java的数据结构，所以可能是也可能不是。 - Alexey Frunze

没错，我并不是指Java作为目标语言，而是期望一种可移植的解决方案（不需要这些底层细节）。无论如何，我甚至无法理解这个答案。@AlexeyFrunze，你能否详细解释一下这个想法（例如在C语言和4字节指针中）？ - Vladimir Kostyukov

优化红黑树颜色位。 - Alexey Frunze

Answer 3

我们可以使用两个规则：

1. 由于根节点始终是黑色的，所以红色节点将始终有一个父节点。

2. RB BST总是按照左子节点 < 父节点 < 右子节点的顺序排列

然后我们会这样做：

1. 保持黑色节点不变。

2. 对于红色节点，我们称其为R，我们假设它是其父节点P的左子节点。

将红色节点的值从R更改为R'，其中R' = P + P - R

现在R' > P，但作为左子树，我们将发现顺序不匹配。

如果我们发现顺序不匹配，则知道它是红色节点。并且很容易回到原始状态R = P + P - R'

- Yifei Huang

Answer 4

与其在子节点上使用布尔属性，我们可以将“红节点”定义为具有错误位置的子节点。

如果我们采用这种方式，所有叶节点都保证是黑色的，插入新节点时应该将其父节点与兄弟节点交换（使其变为红色）。

- Denis Larionov

Answer 5

一种选择是使用需要较少簿记的树，例如splay tree。然而，特别是伸展树在迭代方面并不是很好（它们更擅长随机查找），因此它们可能不适合您所在的领域。

您还可以基于节点位置使用一个BitSet来表示整个红黑树，例如，根是第0位，根的左支是第1位，右支是第2位，左支的左支是第3位，等等；这样，是否存在重复元素就不重要了。在遍历树时，请注意您所处的位位置。

从空间效率上讲，使用一个位集合来表示树要比为每个节点分配一个布尔值更加高效；每个布尔值将占用至少一个字节，并且可能会占用一个字，具体取决于对齐方式，而位集合仅占用每个节点的一位（加上2倍的位，以便考虑到最大程度不平衡的树，其中最短的支路长度是最长支路长度的一半）。

- Zim-Zam O'Pootertoot