An Optimal Algorithm for Computing the Largest Number of Red Nodes
Daxin Zhu, Xiaodong Wang · Advances in engineering research/Advances in Engineering Research · 2015
In this paper, we investigate the problem to compute the largest number of red nodes in red-black trees in red-black trees.We first present a dynamic programming solution for computing ) (n r , the largest number of red internal nodes in a red-black tree on n keys in ) log ( 2 n n O time.Then the algorithm is improved to a new ) (n O time algorithm.Based on the structure of the solution we finally present a linear time recursive algorithm using only ) log ( n O space.