Number of Nodes with Specific Black-Height in Red-Red-Black trees

1
votes

I was asked in a homework assignment to answer a question regarding "Red-Red-Black" trees. The description of a red-red-black tree (copied from somewhere in the internet) is:

"A red-red-black tree is a binary search tree that satisfies the following conditions:

  1. Every node is either red or black
  2. Every leaf (nil) is black
  3. If a node is red and it's parent is red, then both its children are black
  4. Every simple path from a node to a descendant leaf contains the same number of black nodes (the black-height of the tree)"

I was asked, given a red-red-black tree with n nodes, what is the largest number of internal nodes with black-height k? What's the smallest number?

I've been trying to think about it for more then two hours now, but apart from headache I couldn't get anywhere.

Thanks!

2
data-structuresred-black-tree
point 3 doesn't sound right at all... and there should be another point saying that the root is always black. "Somewhere in the internet" is not always a good reference point... – Marsellus Wallace

2 Answers

0
votes

Two Red Node can never appear continuously. Number of Black node should be equal in when you traverse through any path.

0
votes

maximum number of nodes : (2^2k)-1

minimum number of nodes : (2^k)-1