Login New user?  
Applied Mathematics & Information Sciences Letters
An International Journal


Volumes > Vol. 3 > No. 3


On the Maximal Number of Monochrome Nodes in the Dichromatic Balanced Trees

PP: 103-108
Daxin Zhu, Xiaodong Wang, Jun Tian,
In this paper, we investigate the number of nodes of same color in dichromatic balanced trees. We first present a dynamic programming algorithm for computing the maximum number of red internal nodes in a dichromatic balanced trees on n keys in O(n2 logn) time. Then the time complexity is improved to O(n). Finally, we can present an O(n) time algorithm using only O(logn) space based on the special structure of the solution.

  Home   About us   News   Journals   Conferences Contact us Copyright naturalspublishing.com. All Rights Reserved