# 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)$.
Type de document :
Communication dans un congrès
Guang R. Gao; Depei Qian; Xinbo Gao; Barbara Chapman; Wenguang Chen. 13th IFIP International Conference on Network and Parallel Computing (NPC), Oct 2016, Xi'an, China. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9966, pp.205-212, 2016, Network and Parallel Computing. 〈10.1007/978-3-319-47099-3_17〉
Domaine :
Liste complète des métadonnées

Littérature citée [7 références]

https://hal.inria.fr/hal-01647999
Contributeur : Hal Ifip <>
Soumis le : vendredi 24 novembre 2017 - 16:49:00
Dernière modification le : vendredi 24 novembre 2017 - 16:51:00

### Fichier

432484_1_En_17_Chapter.pdf
Fichiers produits par l'(les) auteur(s)

### Licence

Distributed under a Creative Commons Paternité 4.0 International License

### Citation

Daxin Zhu, Tinran Wang, Xiaodong Wang. On Determination of Balance Ratio for Some Tree Structures. Guang R. Gao; Depei Qian; Xinbo Gao; Barbara Chapman; Wenguang Chen. 13th IFIP International Conference on Network and Parallel Computing (NPC), Oct 2016, Xi'an, China. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9966, pp.205-212, 2016, Network and Parallel Computing. 〈10.1007/978-3-319-47099-3_17〉. 〈hal-01647999〉

### Métriques

Consultations de la notice

## 34

Téléchargements de fichiers