• Dec 26, 2017 News![CFP] The annual meeting of IJFCC Editorial Board, ICCTD 2018, will be held in Istanbul, Turkey during March 24-26, 2018.   [Click]
  • Dec 26, 2017 News!IJFCC Vol. 5, No. 1-No. 4 has been indexed by EI (Inspec).   [Click]
  • Dec 26, 2017 News!IJFCC Vol. 4, No. 6 has been indexed by EI (Inspec).   [Click]
General Information
    • ISSN: 2010-3751
    • Frequency: Bimonthly (2012-2016); Quarterly (Since 2017)
    • DOI: 10.18178/IJFCC
    • Editor-in-Chief: Prof. Mohamed Othman
    • Executive Editor: Ms. Cherry L. Chan
    • Abstracting/ Indexing: Google Scholar,  Crossref, Electronic Journals LibraryEI (INSPEC, IET), etc.
    • E-mail:  ijfcc@ejournal.net 
Editor-in-chief
Prof. Mohamed Othman
Department of Communication Technology and Network Universiti Putra Malaysia, Malaysia
It is my honor to be the editor-in-chief of IJFCC. The journal publishes good papers in the field of future computer and communication. Hopefully, IJFCC will become a recognized journal among the readers in the filed of future computer and communication.
IJFCC 2015 Vol.4(1): 63-66 ISSN: 2010-3751
DOI: 10.7763/IJFCC.2015.V4.357

A Simple Dynamic Programming Algorithm for Counting Red Nodes in Red-Black Trees

Daxin Zhu, Xiaodong Wang, and Jun Tian
Abstract—In this paper, we are interested in the number of red nodes in red-black trees. We first present an O(n2log n) time dynamic programming solution for computing r(n), the largest number of red internal nodes in a red-black tree on n keys. 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.

Index Terms—Red-black trees, red internal nodes, dynamic programming, linear time solution.

Daxin Zhu is with Quanzhou Normal University, Quanzhou, China (e-mail: dex@qztc.edu.cn).
Xiaodong Wang and Jun Tian are with Fujian University of Technology, Fuzhou, China (e-mail:wangxd135@139.com, tianjunfjmu@126.com).

[PDF]

Cite: Daxin Zhu, Xiaodong Wang, and Jun Tian, "A Simple Dynamic Programming Algorithm for Counting Red Nodes in Red-Black Trees," International Journal of Future Computer and Communication vol. 4, no. 1, pp. 63-66, 2015.

Copyright © 2008-2018. International Journal of Future Computer and Communication. All rights reserved.
E-mail: ijfcc@ejournal.net