CODEWITHSUNDEEP
algorithmred-black-tree
dublintech
dublintech

Reputation: 17785

Children in a red / black tree?

According to this explanation of red black tree, the tree must have the following properties:

  1. A node is either red or black.
  2. The root is black. (This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice-versa, this rule has little effect on analysis.)
  3. All leaves (NIL) are black. (All leaves are same color as the root.)
  4. Both children of every red node are black.
  5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

What is stopping someone making every single node black?

Upvotes: 2

Views: 776

Answers (2)

vishnu viswanath
vishnu viswanath

Reputation: 3854

It is possible. But to maintain condition 5, sometimes you might want to color a node RED.

e.g., Consider the following example.

  a
 / \
b   c

Here all nodes can be BLACK

Now if you want to insert a new node, which color will you choose? RED. since if you choose black, the condition 5 will not be satisfied. So basically you can keep inserting RED nodes unless any of the conditions (1-4) is not broken

Upvotes: 2

interjay
interjay

Reputation: 110108

The last rule you quoted is "Every simple path from a given node to any of its descendant leaves contains the same number of black nodes."

If all nodes are black, then the path from the root to any leaf must contain the same number of nodes. In other words, all leaves are at the same depth - so this is only possible for a perfect binary tree.

Upvotes: 1

Related Questions