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

本文介绍了一棵全黑节点的树是一棵红黑树吗?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

似乎Wiki上的定义不准确:

It seems the definition on wiki is not precise:

en.wikipedia/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.