%0 Conference Proceedings
%T On Determination of Balance Ratio for Some Tree Structures
%+ Hangzhou Normal University
%+ Peking University [Beijing]
%+ Fujian University of Technology
%A Zhu, Daxin
%A Wang, Tinran
%A Wang, Xiaodong
%Z Part 6: Algorithms and Computational Models
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 13th IFIP International Conference on Network and Parallel Computing (NPC)
%C Xi'an, China
%Y Guang R. Gao
%Y Depei Qian
%Y Xinbo Gao
%Y Barbara Chapman
%Y Wenguang Chen
%I Springer International Publishing
%3 Network and Parallel Computing
%V LNCS-9966
%P 205-212
%8 2016-10-28
%D 2016
%R 10.1007/978-3-319-47099-3_17
%Z Computer Science [cs]Conference papers
%X 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)$$.
%G English
%Z TC 10
%Z WG 10.3
%2 https://inria.hal.science/hal-01647999/document
%2 https://inria.hal.science/hal-01647999/file/432484_1_En_17_Chapter.pdf
%L hal-01647999
%U https://inria.hal.science/hal-01647999
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC10
%~ IFIP-NPC
%~ IFIP-WG10-3
%~ IFIP-LNCS-9966