Volume 13 Number 4 (Apr. 2018)
Home > Archive > 2018 > Volume 13 Number 4 (Apr. 2018) >
JCP 2018 Vol.13(4): 461-470 ISSN: 1796-203X
doi: 10.17706/jcp.13.4.461-470

Red Green Black Trees: Extension to Red Black Trees

Seyfeddine Zouana, Djamel Eddine Zegour
Laboratoire de la Communication dans les Systèmes Informatiques, Ecole nationale Supérieure d'Informatique, ESI (ex:INI), Oued-Smar, Algiers, Algeria. 
Abstract—This paper propose an extended form of Red Black trees. It presents a new explicit balancing algorithm called Red Green Black trees. This structure tolerates some degree of imbalance that allows a decrease of the number of rebalancing relaxing the update operations. Through the use of three color nodes, the structure tolerates series of two nodes between Black nodes and defines a less balanced tree. It is interesting because the imbalance doesn't affect the update time and save the same level of performances of Red Black trees of O(log(n)). In fact, Red Green Black trees can provide better performances in environment where the restructuring is most frequent with Red Black trees.

Index Terms—Red black trees, balanced trees, rebalancing, restructuring.

[PDF]

Cite: Seyfeddine Zouana, Djamel Eddine Zegour, "Red Green Black Trees: Extension to Red Black Trees," Journal of Computers vol. 13, no. 4, pp. 461-470, 2018.

General Information

ISSN: 1796-203X
Frequency: Monthly (2006-2014); Bimonthly (Since 2015)
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO, DOAJ, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Sep 26, 2017 News!

    Papers published in JCP Volume 12 have all been indexed by DBLP   [Click]

  • Sep 02, 2016 News!

    Vol 11, No 3 has been indexed by EI (Inspec)   [Click]

  • Sep 22, 2017 News!

    Vol 13, No 6 has been published with online version 11 papers are published in this issue after peer review   [Click]

  • Aug 14, 2017 News!

    Vol 13, No 5 has been published with online version   [Click]

  • Jun 21, 2017 News!

    Vol 13, No 4 has been published with online version   [Click]

  • Read more>>