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

Content
 

Volumes > Vol. 3 > No. 3

 
   

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

PP: 103-108
Author(s)
Daxin Zhu, Xiaodong Wang, Jun Tian,
Abstract
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