Toward a Unique Representation for AVL and Red-Black Trees

Lynda Bounif, Djamel Eddine Zegour


We propose a unique representation of both AVL and Red-Black trees with the same time and space complexity. We describe all the maintenance operation and the algorithms for the insertion and deletion. We give the implementation of the proposed tree and the results. We then give a comparison of the three structures. The simulation results confirm the performance of the new representation relatively to the AVL and Red-Black tree.


Balanced binary trees, red-black trees, AVL trees, binary search tree, partitioning, data structures

Full Text: PDF