This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Self Balancing Binary Search Tree”.
1. Which of the following is a self – balancing binary search tree?
A) 2-3 tree
B) Threaded binary tree
C) AA tree
Explanation: A self-balancing binary search tree is an AA tree, which is a variant of the red-black tree. Treat is a randomised binary search tree, and 2-3 is a B-tree of order 3. A balanced binary tree is not a threaded binary tree.
2. A self – balancing binary search tree can be used to implement ________
A) Priority queue
B) Hash table
C) Heap sort
D) Priority queue and Heap sort
Explanation: To achieve the best worst-case efficiency, self-balancing binary search trees can be used to build and maintain ordered lists. As a result, a self-balancing binary search tree may be used to enforce an ordered priority queue.
3. In which of the following self – balancing binary search tree the recently accessed element can be accessed quickly?
A) AVL tree
B) AA tree
C) Splay tree
D) Red – Black tree
Explanation: The recently accessed element in a Splay tree can be easily accessed. The frequently accessed nodes in the Splay tree are relocated to the root to make them easier to reach again.
4. The minimum height of self balancing binary search tree with n nodes is _____
C) 2n + 1
D) 2n – 1
Explanation: In order to keep the height proportional to log2, self-balancing binary trees change the height by performing transformations on the tree at key insertion times (n).
5. Binary tree sort implemented using a self balancing binary search tree takes O(n log n) time in the worst case but still it is slower than merge sort.
Explanation: When using a self-balancing binary search tree, the worst case output of binary tree sort is O(n log n). To balance the tree, self-balancing binary search trees perform transformations, which results in balancing overhead. Binary tree sort is slower than merger sort because of this overhead.
6. Which of the following is not the self balancing binary search tree?
A) AVL Tree
B) 2-3-4 Tree
C) Red – Black Tree
D) Splay Tree
Explanation: 2-4-3 The tree is made up of balanced search trees. It is not, however, a binary tree. It is not, therefore, a self-balancing binary tree. Self-balancing binary search trees include the AVL tree, Red-Black Tree, and Splay tree.
7. The binary tree sort implemented using a self – balancing binary search tree takes ______ time is worst case.
A) O(n log n)
D) O(log n)
Explanation: The binary tree sort’s worst-case running time is O. (n2). However, using a self-balancing binary search tree, the worst-case running time can be reduced to O(n log n).
8. An AVL tree is a self – balancing binary search tree, in which the heights of the two child sub trees of any node differ by _________
A) At least one
B) At most one
D) At most two
Explanation: The height difference between the two child sub trees of any node in an AVL tree is at most one. If the height difference is greater than one, the AVL tree rotates to bring the tree back into equilibrium.
9. Associative arrays can be implemented using __________
B) A doubly linked list
C) A single linked list
D) A self balancing binary search tree
Explanation: Associative arrays can be implemented using a self-balancing binary search tree, which has a worst-case time performance of O. (log n).
10. Self – balancing binary search trees have a much better average-case time complexity than hash tables.
Explanation: In the average case, lookup, insertion, and deletion hash tables take O(1) time, while self-balancing binary search trees take O(2) time (log n). As a result, hash tables perform better in the average-case scenario.
Any node-based binary search tree that automatically keeps its height (maximum number of levels below the root) small in the face of arbitrary item insertions and deletions is called a self-balancing (or height-balanced) binary search tree. These structures may be used to implement other abstract data structures such as associative arrays, priority queues, and sets, as well as mutable ordered lists. The symmetric binary B-tree was renamed to red–black tree, which is a kind of self-balancing binary search tree, but the initials can still be confused with the generic definition of self-balancing binary search tree.