On Determination of Balance Ratio for Some Tree Structures
Abstract
In this paper, we studies the problem to find the maximal number of red nodes of a kind of balanced binary search tree. We have presented a dynamic programming formula for computing r(n), the maximal number of red nodes of a red-black tree with n keys. The first dynamic programming algorithm uses O(n2logn)
time and uses O(nlogn)
space. The basic algorithm is then improved to a more efficient O(n) time algorithm. The time complexity of the new algorithm is finally reduced to O(n) and the space is reduced to only O(logn)
.
Domains
| Origin | Files produced by the author(s) |
|---|
Loading...
