Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

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)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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⟩

Share

Metrics

Record views

94

Files downloads

179