- #1

evinda

Gold Member

MHB

- 3,836

- 0

I am looking at the deletion of an element of a 2-3 tree.

- If the key that we want to delete (let $K$ ) is contained in a leaf, we delete it.

Otherwise, the key (let $K'$) that is the next of $K$ in the in-order traversal is contained in a leaf, so we replace $K$ with $K'$ and delete $K'$. - Let $N$ the node from which the key is deleted. If $N$ continues to have a key, the algorithm terminates.
- If $N$ is the root, we delete it. In this case, $N$ can have one or no child. If it has no child, the tree after the deletion is empty.

Otherwise the child of $N$ is the new root of the tree. - Otherwise, $N$ has at least one sibling node. Let $N'$ be any sibling node of $N$. Let $P$ be the father of $N,N'$ and let $S$ be the key of $P$ that separates the two subtrees(that leads from $P$ to $N$ and $N'$).
- $N'$ is a 3-node exactly at the left (exactly at the right ) of $N$. We move $S$ to $N$ and we replace $S$ at its father with the rightmost (leftmost) key of $N'$. If $N$ and $N'$ are internal nodes, we convert the rightmost (leftmost) subtree of $N'$ to a leftmost (rightmost) subtree of $N$. Both $N,N'$ have now one key and the algorithm terminates.
- $N'$ is a 2-node. We merge $S$ with the key of $N'$ to a new 3-node, that replaces $N, N'$ and is the unique child of $P$ (that doesn't have a key anymore). We set $N=P$ and continue with step 3.