wiki上的定义似乎不准确:
http://en.wikipedia.org/wiki/Red-black_tree#Properties
所有黑色节点的树是红黑树吗?
更新
由于 rbtree 的定义不那么严格,我们如何决定将黑色节点的子节点打印为红色还是黑色?
wiki上的定义似乎不准确:
http://en.wikipedia.org/wiki/Red-black_tree#Properties
所有黑色节点的树是红黑树吗?
更新
由于 rbtree 的定义不那么严格,我们如何决定将黑色节点的子节点打印为红色还是黑色?
红黑树只是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 个节点。请注意,这基本上只是一个普通的二叉搜索树。
是的,所有节点都是黑色的树可以是红黑树。这棵树必须是一棵完美的二叉树(所有叶子都在同一深度或同一级别,并且每个父节点都有两个子节点),因此它是唯一一棵黑色高度 等于其树高的树。
有可能拥有一个包含所有黑色节点的适当的红黑树。简单地说,只有一个节点或只有叶节点是根的直接子节点的 RBTree 将是所有后节点。
为了回答问题的第二部分,关于决定将节点打印为红色还是黑色,该信息存储在每个节点中。
在典型的二叉搜索树中,每个节点都包含一个值、一个左指针和一个右指针(可能还有父指针)。在红黑树中,每个节点都包含所有这些内容以及一个额外的字段,该字段指示该节点是红色还是黑色。然后,树上的各种操作(例如插入或删除)负责以一致的方式维护此颜色信息。
您永远不会得到一棵未着色的树并被告知为节点选择颜色(可能作为家庭作业或考试问题除外)。
下面是一个例子来说明红黑树的所有节点都是黑色的:
首先,将{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}按升序插入红黑树。然后,从红黑树中按降序删除{10, 9, 8}。
最后这棵红黑树的所有节点都是黑色的。
一棵节点全为黑色的红黑树与节点都只有一个键的B-树(m=4)相同。
是的,具有所有黑色节点的树可以是红黑树。可以证明,这样的树必须是完全填充的树才能保持等黑深度特性。
你可以自己证明一棵全黑节点的树可以是一棵红黑树,方法是构建一个这样的小树。例如:
2,black
1,black 3,black
这棵树具有所有黑色节点,并且满足所有条件。假设根节点的父节点为 nil,并且两个叶节点的子节点都为 nil。希望这会有所帮助。
是的,但对于具有所有红色节点的红黑树来说,情况并非如此。这样的树是无效的。哪些节点必须为黑色是有限制的。例如,叶节点必须是黑色的,而红色节点的子节点都必须是黑色的。