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
Daxin Zhu
• Function : Author
Tinran Wang
• Function : Author
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)$.

#### Domains

Computer Science [cs]

### Dates and versions

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

### Identifiers

• HAL Id : hal-01647999 , version 1
• DOI :

### 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⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

40 View