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,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Sep 13, 2018 News!

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

  • Aug 06, 2018 News!

    Vol 13, No 1-No 8 has been indexed by EI (Inspec)   [Click]

  • Aug 06, 2018 News!

    Vol 12, No 6 has been indexed by EI (Inspec)   [Click]

  • Apr 24, 2018 News!

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

  • Dec 26, 2017 News!

    Vol 12, No 1-No 5 has been indexed by EI (Inspec)     [Click]

  • Read more>>