一个所有节点都是黑色的树是红黑树吗？

Question

一个所有节点都是黑色的树是红黑树吗？

data-structuresred-black-tree

16

看起来维基百科上的定义不是很精确：

http://en.wikipedia.org/wiki/Red-black_tree#Properties

一个所有节点都为黑色的树是否是红黑树？

更新

由于rbtree的定义不太严格，我们如何决定将黑色节点的子节点打印为红色还是黑色？

- cpuer

7个回答

10

是的，一个全部节点都是黑色的树可以是红黑树。这棵树必须是完美的二叉树（所有叶子在同一深度或层级，且每个父节点都有两个子节点），因此它是唯一一个其 黑高度 等于其 树高度 的树。

- Suriya Singh

3

有可能实现一个所有节点都为黑色的正确红黑树。很显然，只有一个节点或只有叶子节点是根节点的直接子节点的RBTree将会全部为黑节点。

- jwismar

红黑树的定义并不严格，你是如何定义你的确切红黑树的？ - cpuer

@cpuer - 我不明白你的问题。单节点树（只有一个根）必须是黑色的。如果根节点有叶子节点，那些叶子节点必须是黑色的。只有内部节点最终可能会变成红色 - 具体来说，每个添加的节点都被着为红色，直到确定是否需要重新着色。 - jwismar

每个添加的节点都会被涂成红色，直到你确定它是否需要重新着色。为什么维基页面上没有提到这一点呢？ - cpuer

@cpuer：它在“操作：插入”下面。 - jwismar

3

下面是一个示例，展示红黑树的所有节点都是黑色的情况：

首先，按升序将 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 插入到红黑树中。然后，按降序从红黑树中删除 {10, 9, 8}。

最终，这个红黑树的所有节点都是黑色的。

一个所有节点都是黑色的红黑树与所有节点仅有一个关键字的 B- 树（m=4）相同。

- shudeng wu

这提供了一个具体的过程来构建所有黑节点的红黑树。+1 - Yuki Inoue

2

回答问题的第二部分，即关于决定是否将节点打印为红色或黑色的问题，这些信息存储在每个节点中。

在典型的二叉搜索树中，每个节点都包含一个值、一个左指针和一个右指针（可能还有一个父指针）。在红黑树中，每个节点都包含所有这些东西，并且额外添加了一个字段，指示此节点是红色还是黑色。然后对树进行的各种操作，如插入或删除，负责以一致的方式维护该颜色信息。

你永远不会得到一个未着色的树，并被告知为节点选择颜色（除非可能是作业或考试题）。

- Chris Okasaki

2

为了澄清，因为我认为原贴作者的误解在这里，节点总是有颜色，而不仅仅是在打印时才有。这些颜色可以随插入/删除操作而改变，但节点的颜色始终为红色或黑色。红色和黑色不仅仅是装饰作用，它们是数据结构维护平衡属性的固有部分。 - Novak

1

是的，所有节点都为黑色的树可以是红黑树。可以证明这样的树必须是完全填充的树，以保持相等的黑深度属性。

您可以通过构建一个这种类型的小树来自行证明所有黑色节点的树可以是红黑树。例如：

                            2,black
                      1,black      3,black

这棵树有所有黑色节点并满足所有条件。假设根节点的父节点为 nil，叶子节点的两个子节点都是 nil。希望这可以帮到你。

- Rampal Chaudhary

0

是的，但对于所有节点都为红色的红黑树来说并非如此。这样的树是无效的。有关节点必须为黑色的限制。例如，叶节点必须为黑色，红色节点的子节点都必须为黑色。

- Alan Turing

我们如何决定是否将黑色节点的子节点打印为红色或黑色？ - cpuer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jtbandes · Accepted Answer

红黑树就是一个二叉树表示的2-3-4树。红黑树中的任何红色节点都对应于2-3-4树中其父节点的一部分。例如：

2-3-4 tree

           [black 5]
          /         \
      [red 3]     [black 6]
     /       \
[black 2] [black 4]

是2-3-4树的表示

    [3 | 5]
   /   |   \
 [2]  [4]  [6]

如果红黑树只有黑色节点，那么它表示一个只有2节点（单个条目）而不是3节点（例如示例中的[3 | 5]）或4节点的2-3-4树。请注意，这基本上只是一个普通的二叉搜索树。