Properties of Red-Black Tree: Every node is either red or black. The root is black. Every leaf (NIL) is black. If a node is red, then both its children are black. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes. According to the properties, are these valid or invalid red black trees? A. I think this is valid B. I think this is valid, but I am not sure since there two adjacent red nodes? C. I think this is valid, but I am not sure since there two adjacent red nodes? D. I think this is not valid since it violate Property 4? Did I understand these properties of a RBtree right? If not, where am I wrong?

algorithmred-black-tree

The Coder

Reputation: 93

Which of these are valid Red-Black Trees?

Properties of Red-Black Tree:

Every node is either red or black.
The root is black.
Every leaf (NIL) is black.
If a node is red, then both its children are black.
For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

According to the properties, are these valid or invalid red black trees?

I think this is valid

I think this is valid, but I am not sure since there two adjacent red nodes?

I think this is not valid since it violate Property 4?

Did I understand these properties of a RBtree right? If not, where am I wrong?

Upvotes: 2

Answers (3)

cheeseandtomato

Reputation: 25

A red-black tree is basically identical to a 2-3-4 tree(4-Btree), even though the splitting/swapping method is upside down. 2-3-4 trees have fixed-size 3-node buckets. The color black means that it's the central node of the 3-bucket. Any red-black tree is considered as a perfect quadtree/binary tree (of 3-node-buckets) with empty nodes(black holes and red holes).

In other words, every black node (every 3-bucket) has its absolute position in the perfect tree(2 dimensional unique Cartesian or 4-adic/2-adic unique fraction number).

NIL nodes are just extra flags to save space; you don't have enough memory to store a perfect quadtree/binary tree.

The easiest way to check a red-black tree is to check that each black node is a new bucket(going down) and each red node is grouped with the above black node(same bucket). If the central black node has less than 2 red nodes, you can just add empty red holes next to the central black node(left and right).

A new black node is always the grandson of the last black node, and each black node can have only two red daughter-nodes and no black son-nodes. If the red daughter(mother) is empty(dead/unborn), the motherless grandson-node is directly linked to its grandfather-node.

A motherless black grandson-node has no brother, but he can have a black cousin-node next to him; the 2 cousins are linked to the same grandfather.

A quadtree is a subset of a binary tree.

All black nodes have even heights(2,4,6...), and all red nodes have odd heights(1,3,5...). Optionally, you can use the half unit 0.5.

The 3-bucket has a fixed size 3; just add extra red holes(unborn unlinked red daughters) to make the size 3.

Upvotes: 0

trincot

Reputation: 350147

You have listed the properties of Red-Black trees correctly. Of the four trees only C is not a valid red-black tree:

A.

This is a valid tree. Wikipedia confirms:

every perfect binary tree that consists only of black nodes is a red–black tree.

B.

I think this is valid, but I am not sure since there two adjacent red nodes?

It is valid. There is no problem with red nodes being siblings. They just should not be in a parent-child relationship.

C.

I think this is valid, but I am not sure since there two adjacent red nodes?

It is not valid. Not because of the adjacent red nodes, but because of property 5. The node with label 12 has paths to its leaves with varying number of black nodes. Same for the node 25.

As a general rule, a red node can never have exactly one NIL-leaf as child. Its children should either both be NIL-leaves, or both be (black) internal nodes. This follows from the properties.

D.

I think this is not valid since it violate Property 4?

Property 4 is not violated: the children of the red nodes are NIL leaves (not visualised here), which are black. The fact that these red nodes have black NIL leaves as siblings is irrelevant: there are no rules that concern siblings. So this is valid.

For an example that combines characteristics of tree C and D, see this valid tree depicted in the Wikipedia article, which also depicts the NIL leaves:

Upvotes: 4

SJHowe

Reputation: 776

A, B & D are valid red-black trees

C is not valid red-black tree as the black height from root to leaf is not the same. It is 2 in some paths and 1 in other paths. It violates what you stated as rule 5.

If 12 had a right child that was black and 25 a left child that was black, then it would be a red-black tree.

Upvotes: 2

Which of these are valid Red-Black Trees?

Answers (3)

Related Questions