|
|
 |
| |
|
|
|
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. |
|
|
|
|
|
|
|
