Journals Proceedings

Abstract

Since the invention of AVL trees in 1962 and Red-black trees in 1978, researchers were divided in two separated communities, AVL supporters and Red-Black ones. Indeed, AVL trees are commonly used for retrieval applications whereas Red Black trees are used in updates operations, so, the choice of a structure must be done firstly even if the operations are not known to be searches or updates. That is the main reason why we propose a common tree with the same complexity and memory space, representing both an AVL and a Red-Black tree, this new tree allows to gather together the two communities on one hand, and to expand the scope of AVL and Red-Black tree applications on the other hand.