Suppose as a computer programmer, you have been assigned a task to develop a program to store the sorted data in ascending order. Initially you have used linked list data structure to store the data but search operation was time consuming then you decided to use BST (Binary Search Tree) but retrieval efficiency is not improved. In such situation, how can you improve the efficiency of search operation for BST? Justify your answer with solid reason.
• As a computer programmer keeping in mind the whole situation where we are going to insert sorted data in ascending order, I think we should use a balanced binary tree such as an AVL (Adelson-Velskii and Landis) tree, because our main concern is to increase the retrieval efficiency for BST.
• AVL Trees are best choice in scenarios where there are frequent data searching queries rather than a situation requiring frequent insertions and deletions.
• In the worst case scenario we have to search 1.44 log2n levels while searching an AVL tree. For searches, binary and AVL trees are the most efficient trees, so its best choice.