2. Define 2-3 tree. Give the worst-case efficiency of operations on 2-3 tree, build 2-3 tree for the list of keys 9, 5, 8, 3, 2, 4, 7by indicating each step of key insertion and node fits.
Answer:
One way to keep a search tree balanced is to allow more than one key per node. The simplest form of this idea is the 2-3 tree, introduced by John Hopcroft in 1970.
A 2-3 tree contains two types of nodes:
- 2-node: Contains one key K and has two children:
- Left child: subtree with keys less than K
- Right child: subtree with keys greater than K
(This is the same as a normal binary search tree node.)
- 3-node: Contains two ordered keys K1 and K2 such that K1 < K2, and has three children:
- Left child: subtree with keys less than K1
- Middle child: subtree with keys between K1 and K2
- Right child: subtree with keys greater than K2
Properties
- All leaves are on the same level — i.e., the tree is perfectly height-balanced.
- This balance is achieved by allowing more than one key per node.
Construction of a 2-3 tree for the list 9, 5, 8, 3, 2, 4, 7.
Height and Efficiency
- Efficiency of operations depends on the height (h) of the tree.
- For a minimum number of keys, a 2-3 tree is full of 2-nodes.
Then:
n ≥ 1 + 2 + … + 2^h = 2^(h+1) − 1
⇒ h ≤ log₂(n + 1) − 1
- For a maximum number of keys, a 2-3 tree is full of 3-nodes.
Then:
n ≤ 2(1 + 3 + 3² + … + 3^h) = 2 * (3^(h+1) − 1)/2 = 3^(h+1) – 1
⇒ h ≥ log₃(n + 1) − 1
So, the height h of a 2-3 tree satisfies:
log₃(n + 1) − 1 ≤ h ≤ log₂(n + 1) − 1
This implies:
- Search, Insertion, and Deletion all take O(log n) time in worst and average cases.