On Determination of Balance Ratio for Some Tree Structures - Archive ouverte HAL Access content directly
Conference Papers Year : 2016

On Determination of Balance Ratio for Some Tree Structures

(1) , (2) , (3)
1
2
3
Xiaodong Wang
  • Function : Author
  • PersonId : 1023690

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)$$.
Fichier principal
Vignette du fichier
432484_1_En_17_Chapter.pdf (134.13 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01647999 , version 1 (24-11-2017)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

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⟩
40 View
86 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More