This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “2-3 Tree”.
1. Which of the following is not true about the 2-3 tree?
A) all leaves are at the same level
B) it is perfectly balanced
C) postorder traversal yields elements in sorted order
D) it is B-tree of order 3
Explanation: The leaves of a 2-3 tree are all at the same stage. In addition, 2-3 trees are perfectly balanced since every path from the root node to the null connection is the same length. In-order traversal of a 2-3 tree yields elements in sorted order.
2. AVL trees provide better insertion the 2-3 trees.
Explanation: Insertion in the AVL and 2-3 trees necessitates looking for the correct insertion position as well as transformations to balance the node. Both trees take O(log n) time to search, but the AVL tree takes O(log n), while the 2-3 tree takes O(log n) (1). As a result, a 2-3 tree yields stronger extractions.
3. Which of the following is false?
A) 2-3 tree requires less storage than the BST
B) lookup in 2-3 tree is more efficient than in BST
C) 2-3 tree is shallower than BST
D) 2-3 tree is a balanced tree
Explanation: In the 2-3 tree, search is more effective than in the BST. 2-3 tree is a balanced tree that is shallower than BST and performs effective insertion and deletion. However, the BST needs more storage than the 2-3 tree.
4. Which of the following data structure can provide efficient searching of the elements?
A) unordered lists
B) binary search tree
D) 2-3 tree
Explanation: In a binary search tree, treap, and 2-3 tree, the average case time for lookup is O(log n), and in unordered lists, it is O(log n) (n). However, only 2-3 trees perform lookup efficiently in the worst case, as it takes O(log n), while others take O. (n).
5.The height of 2-3 tree with n elements is __
A) between (n/2) and (n/3)
C) between (n) and log2(n + 1)
D) between log3(n + 1) and log2(n + 1)
Explanation: The number of elements in a 2-3 tree with height h is between 2h – 1 and 3h – 1. Therefore, the 2-3 tree with n elements will have the height between log3(n + 1) and log2(n + 1).
6.Which of the following the BST is isometric with the 2-3 tree?
A) Splay tree
B) AA tree
D) Red – Black tree
Explanation: The AA tree is the most isometric of the three trees. Each node in an AA tree is assigned a level, which corresponds to the height of the corresponding 2-3 tree node. As a result, we can transform a 2-3 tree into an AA tree.
7. 2-3 tree is a specific form of _________
A) B – tree
B) B+ – tree
C) AVL tree
Explanation: The 2-3 trees is a balanced tree. It is a specific form the B – tree. It is B – tree of order 3, where every node can have two child subtrees and one key or 3 child subtrees and two keys.
8. Which of the following is the 2-3 tree?
Explanation: At node2, the tree should have two subtrees but no more than three elements. Three child subtrees should exist for the node with elements 11 and 15.
9. The figure shown below is a 2-3 tree. What is the result of deleting 110 from the tree?
Explanation: As node 110 is removed, the corresponding node becomes null, causing the 2-3 tree properties to be broken. As a result, element 93 from its sibling node is transferred to the root, and element 100 from the root node is fed to the empty node.
10. LLRB maintains 1-1 correspondence with 2–3 trees.
Explanation: LLRB (Left Leaning Red Black tree)is the data structure which is used to implement the 2-3 tree with very basic code. The LLRB is like the 2-3 tree where each node has one key and two links. In LLRB the 3-node is implemented as two 2-nodes connected by the red link that leans left. Thus, LLRB maintains 1-1 correspondence
Every node with children (internal node) has either two children (2-node) and one data element or three children (3-nodes) and two data elements in a 2–3 tree data structure. A B-tree of order 3 is a 2–3 tree. The leaf nodes (nodes on the outside of the tree) have no children and just one or two data elements. In 1970, John Hopcroft invented 2–3 trees.
2–3 trees must be balanced, which means that each leaf must be at the same level. As a result, each node’s right, middle, and left subtrees contain the same or nearly the same amount of data.