# Self Balancing Binary Search Tree Multiple Choice Questions and Answers (MCQs)

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
C) AA tree
D) Treap

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 _____
A) log2(n)
B) n
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.
A) True
B) False

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)
B) O(n)
C) O(n2)
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
C) Two
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 __________
A) B-tree