Consider a 2,3,4 tree like so,
53 / \ / \ / \ 46 60 | 70 / \ / \ \ / \ / \ \ / \ / \ \ 41 48 55|59 65|68 73|75|79
How to delete 41 from the tree from here ? I would like to know the intermediate steps involved.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
The problem you're encountering is that a deletion is cascading and triggering another deletion. In particular, you're deleting from a node with only one key. Rather than working from the bottom up, it may be easier to work from the top downwards to preserve all of the properties of the 2-3-4 tree while giving an extra key to the node you're deleting from. Here are the rules for deletion:
So starting from the tree below, we see that 41 is the only key in its node so let's start from the root and perform operations as necessary on the way to 41. We start at the root 53 and do nothing:
--> 53 / \ / \ / \ 46 60 | 70 / \ / \ \ / \ / \ \ / \ / \ \ 41 48 55|59 65|68 73|75|79
Then we get to 46 which is a 2-node. One of its siblings has more than 1 key so we perform operation 1. In particular, have the parent steal a sibling key 60 and have the node containing 46 steal 53 from the parent. The original left child of 60 becomes the right child of 53.
60 / \ / \ / \ --> 46 | 53 70 / | \ \ \ / | \ \ \ / | \ \ \ 41 48 55|59 65|68 73|75|79
Finally we're at 41 which is also a 2-node and all of its siblings are 2-nodes so we perform operation 3. In particular, we steal 46 from the parent and fuse 41, 46, and 48 into a new node.
60 / \ / \ / \ 53 70 / \ / \ / \ / \ / \ / \ --> 41|46|48 55|59 65|68 73|75|79
Now the node containing 41 has more than one key so we can go ahead and delete 41.