Question

Let TB and T2-3 be, respectively, a classical binary search tree and a 2-3 tree constructed for the same list of keys inserted in the corresponding trees in the same order. True or false: Searching for the same key in T2-3 always takes fewer or the same number of key comparisons as searching in Tg?

Answer 1

The statement is true.

This is because T 2-3 is a 2-3 tree which is a kind of balanced binary search tree. In a 2-3 tree, all the leaf nodes are in the same level and the number of children is either 2 or 3 in every node.

TB is a classical binary search tree and so there is a chance that the tree might be skewed.

This can be illustrated by the following sequence of insertion :

1, 2, 3, 4, 5

The corresponding 2-3 tree will be :

3 4 F 5 N

The corresponding classical binary search tree will be :

2 3 5 5

So, in order to search the key 5 in 2-3 tree, the time taken is O(log n) where n is the total number of nodes whereas in the classical binary search tree, it would take O(n) time.

There are same number of comparisons for searching a key in both the trees when the classical binary tree has a height of O(log n).

Hence, it is proved that T 2-3 always takes fewer or the same number of key comparisons as searching in TB tree.