3) (Research question) What are AVL Trees? What are the differences between BST\

Question

3) (Research question) What are AVL Trees? What are the differences between BST's and AVL Trees? What are the differences between Red-Black Trees and AVL Trees? When would you choose BST's, AVL Trees or Red-Black Trees to solve a problem (give examples)?
Tips: Be very detailed. A mature analysis of their differences is expected. The examples don't need to be numerical but a clear explanation of the scenarios is expected.

Subject : Computer Algorithms

Book: Introduction to Algorithms 3rd edition

Ebook URL: http://ce.bonabu.ac.ir/uploads/30/CMS/user/file/115/EBook/Introduction.to.Algorithms.3rd.Edition.Sep.2010.pdf

Explanation / Answer

AVL tree is a balanced tree, where the tree can not be skewed in one particular subtree. It balances itself so that the difference between the height of the subtrees for any node is not more than a constant value.

Binary search trees do guarantee a quick search of the elements (Ologn). While AVL tree is a special version of (balanced) BST, it also maintains the BST properties and for AVL tree also, search time complexity is O(logn). For BST, worst search time complexity is O(n), when the tree is completely skewed, and the element being searched for , is at the leaf. But AVL tree reduces the worst case search time complexity to O(logn).

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.