# 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(n^2\log n)$ time and uses $O(n\log n)$ 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(\log n)$.
Document type :
Conference papers
Domain :

Cited literature [7 references]

https://hal.inria.fr/hal-01647999
Contributor : Hal Ifip <>
Submitted on : Friday, November 24, 2017 - 4:49:00 PM
Last modification on : Friday, November 24, 2017 - 4:51:00 PM

### File

432484_1_En_17_Chapter.pdf
Files produced by the author(s)

### Citation

Daxin Zhu, Tinran Wang, Xiaodong Wang. On Determination of Balance Ratio for Some Tree Structures. 13th IFIP International Conference on Network and Parallel Computing (NPC), Oct 2016, Xi'an, China. pp.205-212, ⟨10.1007/978-3-319-47099-3_17⟩. ⟨hal-01647999⟩

Record views