Deleting Element from 2-3 Tree Example

[evinda]

Hello! (Wave)

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

1. 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'$.
2. Let $N$ the node from which the key is deleted. If $N$ continues to have a key, the algorithm terminates.
3. 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.
4. 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'$).
   1. $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.
   2. $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.

Could you give me an example for each case? (Thinking)

 

[Future Bruno]

Sure! Case 1: Let's say we have a 2-3 tree with the following elements: A, B, C, D, E. We want to delete the element B. In this case, B is in a leaf node so we can simply delete it. Case 2: Let's say we have a 2-3 tree with the following elements: A, B, C, D, E. We want to delete the element A. In this case, A is not in a leaf node, so we replace it with B (the next key in the in-order traversal) and delete B instead. Case 3: Let's say we have a 2-3 tree with the following elements: A, B, C, D, E, F. Node A has two children, nodes B and C. We want to delete the element A. In this case, the child of A (node B) becomes the new root of the tree. Case 4: Let's say we have a 2-3 tree with the following elements: A, B, C, D, E, F. Node A has two children, nodes B and C. Node B has two children, nodes D and E. We want to delete the element A. In this case, we move the separating key (B) from Node A to Node B and replace B at its father with the rightmost key of Node C (F). Both Node A and Node C now have one key and the algorithm terminates. Case 5: Let's say we have a 2-3 tree with the following elements: A, B, C, D, E, F. Node A has two children, nodes B and C. Node B is a 2-node. We want to delete the element A. In this case, we merge the separating key (B) with the key of Node B (C) to a new 3-node that replaces Nodes A and B and is the unique child of Node A (which doesn't have a key anymore). We set N=A and continue with step 3.