Menu
The smallest number of internal nodes in a red-black tree with black height of k is 2k-1 which is one in the following image:
The largest number of internal nodes with black height of k is 22k-1 which, if the black height is 2, should be 24 - 1 = 15. However, consider this image:
The number of internal nodes is 7. What am I doing wrong?
855
The actual expression for maximum number of internal nodes for a tree with black-height k is 4^(k)-1. In this case, it turns out to be 15. Save this answer.
Since the leaf must be black, there are at most the same number of red nodes as black nodes on the path. 2k − 1. The smallest possible number is 2 k − 1.
2) The Maximum number of nodes in a binary tree of height 'h' is 2h – 1. Here the height of a tree is the maximum number of nodes on the root to leaf path.
A red-black tree is a binary search tree such that each node (internal and external) is assigned a color (either red or black). The coloring of the tree must satisfy the following red-black properties: Every external leaf (NULL node) is considered to be black. If a node is red, then both its children are black.
The problem is you misunderstood the black height. The black height of a node in a red-black tree is the the number of black nodes from the current node to a leaf not counting the current node. (This will be the same value in every route). So if you just add two black leafs to every red node you will get a red-black tree with a black height of 2 and 15 internal nodes.
(Also in a red-black tree every red node has two black children so red nodes can't be leafs.)
68
You need to count the black NIL leafs in the tree if not this formula won't work. The root must not be RED that is in violation of one of the properties of a Red-Black tree.
29
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
