CODEWITHSUNDEEP
data-structuresred-black-tree
Tomer
Tomer

Reputation: 1704

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

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!

Upvotes: 1

Views: 1091

Answers (2)

Pubudu Mahesh Meththananda
Pubudu Mahesh Meththananda

Reputation: 387

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

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

Upvotes: 1

special
special

Reputation: 641

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

Upvotes: 0

Related Questions