An Optimal Algorithm for Computing the Largest Number of Red Nodes
Authors
Daxin Zhu, Xiaodong Wang
Corresponding Author
Daxin Zhu
Available Online July 2015.
- 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/).
Cite this article
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 -