13

wiki上的定义似乎不准确：

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

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

更新

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

4

7 回答 7

8

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

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

是 2-3-4 树的表示

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

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

于 2011-06-20T03:58:09.303 回答
8

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

于 2013-04-04T01:08:37.330 回答
3

有可能拥有一个包含所有黑色节点的适当的红黑树。简单地说，只有一个节点或只有叶节点是根的直接子节点的 RBTree 将是所有后节点。

于 2011-06-20T03:53:48.227 回答
2

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

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

您永远不会得到一棵未着色的树并被告知为节点选择颜色（可能作为家庭作业或考试问题除外）。

于 2011-06-20T18:56:34.730 回答
2

下面是一个例子来说明红黑树的所有节点都是黑色的：

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

最后这棵红黑树的所有节点都是黑色的。

一棵节点全为黑色的红黑树与节点都只有一个键的B-树（m=4）相同。

于 2018-10-15T09:53:46.113 回答
1

是的，具有所有黑色节点的树可以是红黑树。可以证明，这样的树必须是完全填充的树才能保持等黑深度特性。

你可以自己证明一棵全黑节点的树可以是一棵红黑树，方法是构建一个这样的小树。例如：

                            2,black
                      1,black      3,black

这棵树具有所有黑色节点，并且满足所有条件。假设根节点的父节点为 nil，并且两个叶节点的子节点都为 nil。希望这会有所帮助。

于 2012-03-27T12:40:58.470 回答
0

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

于 2011-06-20T03:55:09.723 回答