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.

  • $\begingroup$ Not downvoting this, but check this out: en.wikipedia.org/wiki/Self-balancing_binary_search_tree It will give you efficient retrievals (whereas just BST alone may be O(n) retrieval) $\endgroup$ – Matthew C Feb 3 at 17:26
  • 5
    $\begingroup$ Interestingly, at stackoverflow the same question is asked by another person: stackoverflow.com/q/60015192 What a coincidence. $\endgroup$ – Hendrik Jan Feb 3 at 20:41
  • $\begingroup$ What did you try and where did you get stuck? We are happy to help you with your homework too, but we expect you to show some effort. For the time being, I voted to close your question but I'm happy to retract my vote after an edit. $\endgroup$ – Juho Feb 4 at 19:24

• 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.