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.