Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Exam 1 #12 (RBT properties)
Exam question (abbreviated):

Suppose you allowed, at most, two red nodes in a row on any path from an interior node to a leaf in a RBT. Suppose further, a path from the root to a leaf has 11 black nodes. What is the most number of red leaves that can appear on that path?

Can anyone explain the idea we are trying to understand here? Also how would one set this up when solving the problem?
You're just trying to see how the tree grows when you increase the number of consecutive red nodes allowed with no effect on runtime complexity.

So to maximize the number of red l̶e̶a̶v̶e̶s̶ nodes in the path, you start with a black root, add two reds in the path, one black, two reds, and so on, until you reach 11 black nodes. So the answer would be 22.
So does it not matter that these are internal nodes or leaf nodes?

Forum Jump:

Users browsing this thread: 1 Guest(s)