A Survey on Balanced Binary Search Trees methods

Binary Search Trees (BSTs) are fundamental data structures in computer science; because of their implicit key sorting and linked node structure, they provide effective sorting and simple update operations. They achieve their highest performance when they are balanced. A non-balanced Binary Search Tree is no more efficient than a regular linked list. In the present literature, multiple methods to balance Binary Search Tree were proposed. Previous researches have focused on solving the question “What is the best Balanced Binary Search Tree method adapted for data management scenario?”, but recently proposed methods have not been studied yet. In this paper, we have conducted a comparison of classical and most recently balanced Binary Search Trees methods, to allow software developers to choose the most efficient Binary Search Tree method based on the data management problem they face.