Maximizing the Internal Path Length in Red‐Black Trees

A red‐black tree is a binary search tree with an extra color bit at each node. In a red‐black tree every node is colored either red or black and must satisfy the following properties:

1. Every node is either red or black.
2. All external (NIL) nodes are black.
3. Every red node has two black children.
4. For each internal node, all paths from that node to its descendant external nodes contain the same number of black nodes (i.e. the same black–height).

For any red–black tree T the internal path length (IPL) is defined as

[ IPL(T) = \sum_{v\in T} \text{length}(path(v)) ]

where for each internal node (v), (length(path(v))) is the number of edges from the root to (v). (Note that the root has depth 0.)

Given a positive odd integer (n) (the number of internal nodes), design an algorithm to compute the maximum value of (IPL(T)) over all red–black trees with (n) internal nodes. It can be shown that the maximum is attained by one of the most "unbalanced" red–black trees (i.e. a tree with the maximum possible height subject to the red–black constraints).

Input Constraints:

• The input consists of a single odd positive integer \(n\). (Note: In any red–black tree every internal node has two children (with external NIL nodes being black), so \(n\) is necessarily odd.)

Task: Output the maximum possible internal path length among all red–black trees with (n) internal nodes.

Note on red–black tree validity: A valid red–black tree must obey the following additional coloring rules:

• If a node is black, its children can be red or black.
• If a node is red then both its children must be black.
• If an internal node is a leaf (i.e. it has no children in the tree of internal nodes) then the paths to the NIL nodes (external nodes with defined depth \(-1\)) all contribute consistently to the black–height.

The algorithm below uses a dynamic programming recursion that tries to build a full (every internal node has exactly two children pointers) red–black tree (where extra NIL leaves are not counted) for a given number of nodes \(n\) while keeping track of the required black–height.

Mathematical Formulation: We define a function

[ f(n, b, c) = \text{maximum IPL obtainable from a red–black tree with}\ n \text{ internal nodes, with the root colored } c \text{ and with a prescribed black–height } b. ]

• Base case: A leaf tree (\(n=1\)) is valid only if \(b=1\); in that case \(f(1,1,\cdot)=0\) (the depth of the only node is 0).
• For an internal node (\(n \ge 3\)):
  • If the node is black (\(c=B\)), then each child must have a prescribed black–height \(b-1\).
  • If the node is red (\(c=R\)), then each child (which must be black by rule 3) must have black–height \(b\).
• When combining two subtrees (with, say, \(i\) and \(j\) nodes, \(i+j=n-1\)), every node in the subtree gets its depth increased by 1 so that the contribution increases by \(i+j\); hence a candidate answer is \[ f(i, \cdot, \cdot) + f(j, \cdot, \cdot) + (i+j). \]

Your task is to output the maximum IPL among all valid red–black trees with (n) nodes, that is,

[ answer = \max_{b} f(n, b, B) \quad (\text{the root is assumed to be black}) ]

Implement an algorithm based on the above idea. The following five solutions (in Python3, C++, Java, C, and JavaScript) all use a recursive dynamic programming approach with memoization. (The intended (n) is small so that this exponential algorithm suffices.)

inputFormat

A single line containing an odd positive integer (n), the number of internal nodes in the red–black tree.

outputFormat

A single integer representing the maximum possible internal path length among all valid red–black trees with (n) internal nodes.

sample

1

0