company x has created a new variant on red black trees which also uses blue as a col 5187659
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. (a) In class we found that the height, h, of a red-black tree is lessthanorequalto 2 log_2 (n + 1) (where n is the number of keys). Find and prove that a similar bound on height of the red-black-blue trees.