A Survey on Maintaining Binary Search Tree in Optimal Shape

Binary search tree (BST) is one of the most widely used techniques for searching in non-linear data structure. If the BST is not maintained in optimal shape then the searching and insertion may need extra number of comparisons. In present literature, several BST algorithms have been proposed to maintain the BST in optimal shape. Different researchers have focused mainly on finding the total running time of BST algorithms but no one has focused on solving the mystery of "using which BST algorithm under what scenario". In this paper, we present a thorough comparison of existing techniques that ultimately enables software developers to select a particular BST technique according to the faced data management scenario.