Question

what is the largest possible number of internal nodes in a redblack tree with black height k? what is the smallest possiblenumber?

Answer 1

A Red Black Tree is a type of self-balancing(BST) in this tree ,each node is red or black colored. The red black tree meets all the properties of the binary search tree, but some additional properties have been added to a Red Black Tree.

A Red-Black tree's height is O(Logn) where (n is the tree's amount of nodes).

In a red-black tree with black height k

The maximum number of internal nodes is
`2^(2k)`
`-1`.

The smallest possible number is
`2^(k)`
`-1`.