一棵全黑节点的树是一棵红黑树吗?

问题描述

似乎Wiki上的定义不准确:

It seems the definition on wiki is not precise:

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

一棵带有所有黑色节点的树是一棵红黑树吗?

Is a tree with all black nodes a red black tree?

更新

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

With the definition of rbtree not so strict,how do we decide whether to print the children of a black node as red or black?

推荐答案

红黑树只是 2-3-4树.红黑树中的任何红色节点对应于类似的2-3-4树中其父节点的一部分.例如:

A red-black tree is simply a binary-tree representation of a 2-3-4 tree. Any red node in a red-black tree corresponds to a piece of its parent node in the analagous 2-3-4 tree. For example:

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

是2-3-4树的表示形式

is a representation of the 2-3-4 tree

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

如果一棵红黑树只有个黑色​​节点，则表示它是一个2-3-4树，其中只有2个节点(单个条目)，而不是3个节点(例如 [3 | 5] )或4个节点.注意，这基本上只是一个普通的二进制搜索树.

If a red-black tree has only black nodes, that means it represents a 2-3-4 tree with only 2-nodes (single entries), not 3-nodes (such as [3 | 5] in the example) or 4-nodes. Notice this is basically just a plain binary search tree.

这篇关于一棵全黑节点的树是一棵红黑树吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！