Company X has created a new variant on red-black trees which also uses blue as a

Question

Company X has created a new variant on red-black trees which also uses blue as a color for the nodes. They call these "red-black-blue trees". Below are the new rules for these trees: Every node is red, blue, or black. The root is black. Every leaf (NIL) is black. If a node is red, then both its children are black. If a node is blue, then both its children are red or black. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes. In class we found that the height, h, of a red-black tree is lessthanorequalto 2 log_2 n. Find a similar bound on height of the red-black-blue trees.

Explanation / Answer

Answer:

The same comparison can be made with B-trees with more orders that can be equal to a colored binary tree we just need more colors.In our case we add blue color then the blue–red–black tree defined like red–black trees but with the additional restriction that no two successive nodes in the hierarchy will be blue and all blue nodes will be children of a red node and then it becomes almost equal to a B-tree whose clusters will have at most 7 values in the following colors as blue, red, blue, black, blue, red, blue. All optimizationsare allowed in B-trees to increase the factors of clusters are allowed in the equivalent multicolored binary tree. Identifically maximizing the average fill factor in a equivalent B-tree is the same as decreasing the total height of the multicolored tree, by increasing the number of non-black nodes.

Intially, notice that for a red-black-blue tree with height h, l is at least h/2 by property as each red node strictly requires black children and blue children
The next step is to use the following lemma below :
      A subtree rooted at node p has at least 2^l(p) – 1 internal nodes
    The basic step is when h(p) = 0, which means that p is a leaf node and therefore l(p) = 0 and the subtree rooted at node p has 2^l(p)-1 = 2^0-1 = 1-1 = 0 nodes.
   Hypothesis: if node p1 with height x has 2^l(p1)-1 internal nodes then node p2 with height x+1 has 2^l(p2)-1
Any non-leaf node p and height > 0 we can see that the black height of any of its two children is at least equal to l(p)-1 — if the child is black, that is, otherwise it is equal to l(p) . By applying the hypothesis above we conclude that each child has at least 2^[l(p)-1]-1 internal nodes, accordingly node p has at least
2^[l(p)-1]-1 + 2^[l(p)-1]-1 + 1 = 2^l(p)-1 internal nodes, which ends the proof.
On implementing lemma to the root node we get n >= 2^(h/2) – 1
where n is the number of internal nodes of a red-black-blue tree. In detail with the equation we get h <= 2 log (n+1), which guarantees the height logarithmic bound of red-black-blue trees.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.