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〉
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

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

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

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〉

Partager

Métriques

Consultations de la notice

27