A note on the largest number of red nodes in red-black trees

Yingjie Wu, Daxin Zhu, Lei Wang +1

In this paper, we are interested in the number of red nodes in red-black trees. We first present an $O(n^2\log n)$ time dynamic programming solution for computing $r(n)$, the large…