# Deleting Element from 2-3 Tree Example

• MHB
• evinda
In summary, when deleting an element in a 2-3 tree, the key is first checked to see if it is contained in a leaf node. If so, it is simply deleted. Otherwise, the next key in the in-order traversal is used to replace the key and then deleted. If the node from which the key is deleted still has a key, the algorithm terminates. If it is the root, it is deleted and the child becomes the new root. If it has at least one sibling node, the key is moved to the node and replaced with the rightmost or leftmost key of the sibling node, depending on the case. If the sibling node is a 2-node, it is merged with the key of the
evinda
Gold Member
MHB
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)

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.

## 1. What is a 2-3 tree?

A 2-3 tree is a type of data structure in computer science that is used to store and organize data in a balanced and efficient way. It is a type of binary search tree where each internal node has either two or three child nodes.

## 2. How do you delete an element from a 2-3 tree?

To delete an element from a 2-3 tree, you must first find the node containing the element. If the node has two elements, simply delete the element from the node. If the node has three elements, replace the element to be deleted with the smallest element in the right subtree. If the right subtree is empty, replace the element to be deleted with the largest element in the left subtree. If both subtrees are empty, simply delete the element from the node. Then, rebalance the tree to maintain its 2-3 properties.

## 3. What is the time complexity of deleting an element from a 2-3 tree?

The time complexity of deleting an element from a 2-3 tree is O(log n), where n is the number of elements in the tree. This is because the algorithm for deletion involves finding the node containing the element, which takes O(log n) time in a balanced tree. The rebalancing process also takes O(log n) time.

## 4. What happens to the other elements in the tree when an element is deleted from a 2-3 tree?

When an element is deleted from a 2-3 tree, the other elements in the tree remain unchanged in terms of their position and relationship with other elements. However, the tree may need to be rebalanced in order to maintain its 2-3 properties.

## 5. Can you delete elements from a 2-3 tree in any order?

Yes, you can delete elements from a 2-3 tree in any order. The structure of the tree will remain the same, but the elements may be rearranged as the tree is rebalanced after each deletion.

• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
9
Views
2K
• Programming and Computer Science
Replies
5
Views
2K
• Programming and Computer Science
Replies
2
Views
1K
• Programming and Computer Science
Replies
1
Views
2K
• Programming and Computer Science
Replies
14
Views
3K
• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
15
Views
3K
• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
4
Views
1K