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 回答