2-3 Deletion (Case #1)

Deletion algorithm

Deletion in 2-3 trees is implemented based on the same scenarios discussed in the last lesson but in the reverse order. The deletion algorithm also takes $O(Logn)$ time. Just like insertion, deletion also begins from the leaf node. The deletion in 2-3 trees is performed based on these scenarios.

$$$$

Case 1: Element at leaf

When the element that needs to be removed is present at the leaf node, check how many keys are present in that node. This further divides the algorithm into two scenarios:

1.1 Leaf node has more than one key

If the leaf at which the element is to be deleted has more than one key, then simply delete the element.

Example: See the following example where the node has more than one key.