On the performance of balance factors of the dichromatic balanced trees for massive data

DOI

10.2991/icence-16.2016.58How to use a DOI?

Keywords

Balanced Trees; Recursive Algorithms; Closed-Form Solutions

Abstract

In this paper, we are interested in minimal number of red-nodes in a red-black tree. An time dynamic programming algorithm is presented first for computing , the smallest number of red internal nodes in a red-black tree on keys. We then improve the algorithm to a new time algorithm. Then the algorithm is improved further to some time recursive and nonrecursive algorithms. These improved algorithms finally led to a closed-form solution of .

Copyright

© 2016, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Xiaodong Wang
AU  - Daxin Zhu
PY  - 2016/09
DA  - 2016/09
TI  - On the performance of balance factors of the dichromatic balanced trees for massive data
BT  - Proceedings of the 2nd International Conference on Electronics, Network and Computer Engineering (ICENCE 2016)
PB  - Atlantis Press
SP  - 275
EP  - 279
SN  - 2352-538X
UR  - https://doi.org/10.2991/icence-16.2016.58
DO  - 10.2991/icence-16.2016.58
ID  - Wang2016/09
ER  -