Binary search trees (BSTs) and AVL trees are concepts from the advanced data str
ID: 3690104 • Letter: B
Question
Binary search trees (BSTs) and AVL trees are concepts from the advanced data structures course. What is true about these 2 data structures?
Every BST is also an AVL tree. AVL trees have a better worst case space complexity when compared with a BST representing the same data.
Every AVL tree is a BST. AVL trees have a better worst case time complexity for add and remove operations when compare with a BST representing the same data.
A BST is balanced AVL tree.
BSTs and AVL trees are both trees, but they have no other relation to each other and one is not an extension of the other.
Every BST is also an AVL tree. AVL trees have a better worst case space complexity when compared with a BST representing the same data.
Every AVL tree is a BST. AVL trees have a better worst case time complexity for add and remove operations when compare with a BST representing the same data.
A BST is balanced AVL tree.
BSTs and AVL trees are both trees, but they have no other relation to each other and one is not an extension of the other.
Explanation / Answer
1. Every BST is also an AVL tree. AVL trees have a better worst case space complexity when compared with a BST representing the same data.
Ans: This is false because an AVL tree is a self-balancing binary search tree. So we can say an AVL tree is always a balanced tree. But there exists binary tree which is unbalanced. Hence every BST is not a AVL tree.
2. Every AVL tree is a BST. AVL trees have a better worst case time complexity for add and remove operations when compare with a BST representing the same data.
Ans: True. Because every AVL tree is a balanced binary searched tree. As the tree is balanced the number of operation needed to find any element is likely to be less than BST. Hence AVL tree has better worst case complexity.
3. A BST is balanced AVL tree.
Ans: False. BST can be both balanced and unbalanced. When BST become balanced it called AVL tree.
4. BSTs and AVL trees are both trees, but they have no other relation to each other and one is not an extension of the other.
Ans: First sentence is true. Obviously BST and AVL both are tree. But second sentence is not true. BST and AVL do have a relation with each other. When a BST is balanced it becomes AVL tree.
2. Every AVL tree is a BST. AVL trees have a better worst case time complexity for add and remove operations when compare with a BST representing the same data.
Ans: True. Because every AVL tree is a balanced binary searched tree. As the tree is balanced the number of operation needed to find any element is likely to be less than BST. Hence AVL tree has better worst case complexity.
3. A BST is balanced AVL tree.
Ans: False. BST can be both balanced and unbalanced. When BST become balanced it called AVL tree.
4. BSTs and AVL trees are both trees, but they have no other relation to each other and one is not an extension of the other.
Ans: First sentence is true. Obviously BST and AVL both are tree. But second sentence is not true. BST and AVL do have a relation with each other. When a BST is balanced it becomes AVL tree.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.