Abstract—In this paper, we are interested in the number of red nodes in red-black trees. We first present an O(n2log n) time dynamic programming solution for computing r(n), the largest number of red internal nodes in a red-black tree on n keys. Then the algorithm is improved to a new O(n) time algorithm. Based on the structure of the solution we finally present a linear time recursive algorithm using only O(log n) space.
Index Terms—Red-black trees, red internal nodes, dynamic programming, linear time solution.
Daxin Zhu is with Quanzhou Normal University, Quanzhou, China (e-mail: dex@qztc.edu.cn).
Xiaodong Wang and Jun Tian are with Fujian University of Technology, Fuzhou, China (e-mail:wangxd135@139.com, tianjunfjmu@126.com).
[PDF]
Cite: Daxin Zhu, Xiaodong Wang, and Jun Tian, "A Simple Dynamic Programming Algorithm for Counting Red Nodes in Red-Black Trees," International Journal of Future Computer and Communication vol. 4, no. 1, pp. 63-66, 2015.
