CODEWITHSUNDEEP
algorithmbinary-treered-black-tree
Bob Smith
Bob Smith

Reputation: 55

How to create red black tree with max height?

A red black tree has a max height of 2 * log(n+1) so if the number of nodes is 15, then the max height should be 2 * log(16) or 8. I've been trying to draw a red black tree with height 8 while using only 15 nodes but I am unable to do so without breaking the rules of a red black tree. How would I create a red black tree of height 8 using 15 nodes?

Upvotes: 3

Views: 8239

Answers (2)

trincot
trincot

Reputation: 350147

There are at least two reasons why the proof that h(root) ≤ 2·log2(n+1) does not yield a tight upper bound:

  1. It assumes that the "black-height" of the children of a node is one less than that of the node itself. This is a simplification, because it could well be the same (when the node is black and has red children).

    As a consequence the number of internal nodes is getting a lower bound that is not as high as it in reality is, and thus the maximum height (derived from that) is not as low as in reality it is.

  2. It does not use all constraints that black-red trees must adhere to.

    It does use the properties that the root is black, and that a red node cannot have red children, and therefore "at least half of the nodes on any path from the root to a leaf are black".

    But... it does not take into account the restriction that the paths from the root to any of the leaves must all have the same number of black nodes.

    This constraint puts an additional limitation on the possible height of the tree, which this proof ignores.

However, the goal of the proof was not to have an upper limit that was as tight as possible, but to have one that is good enough to conclude that h(root) = O(log(n))

Upvotes: 1

夢のの夢
夢のの夢

Reputation: 5826

From the pseudocode I read from CLRS. the max height seems to be achieved when you newly insert a red node into the tree, before any rotation is applied to changing the color or balancing the tree. Following tree demos this with external node = 3, and max height = 4:

       black(h=4)
     /       \
   nul      red(h=3)
            /    \
          nul   red (h=2)
               /    \
             nul     nul (h=1)

The tree would then rotate and fix the newly inserted red node by rotating left

       black(h=3)
     /       \
   red      red(h=2)
  /   \    /    \
 nul  nul nul   nul(h=1)

resulting height is reduced and satisfies all the requirements.

Upvotes: 3

Related Questions