An Optimal Algorithm for Computing the Largest Number of Red Nodes

DOI

10.2991/icimm-15.2015.205How to use a DOI?

Keywords

Red-black trees; dynamic programming; data structure; time complexity

Abstract

In this paper, we investigate the problem to compute the largest number of red nodes in red-black trees in red-black trees. We first present a dynamic programming solution for computing r(n) , the largest number of red internal nodes in a red-black tree on n keys in O(n2 log n) time. Then the algorithm is improved to a new O(n) time algorithm. Based on the structure of the solution we finally present a linear time recursive algorithm using only O(log n) space.

Copyright

© 2015, 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  - Daxin Zhu
AU  - Xiaodong Wang
PY  - 2015/07
DA  - 2015/07
TI  - An Optimal Algorithm for Computing the Largest Number of Red Nodes
BT  - Proceedings of the 5th International Conference on Information Engineering for Mechanics and Materials
PB  - Atlantis Press
SP  - 1134
EP  - 1139
SN  - 2352-5401
UR  - https://doi.org/10.2991/icimm-15.2015.205
DO  - 10.2991/icimm-15.2015.205
ID  - Zhu2015/07
ER  -