1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you know the different rules/cases for deleting from a 2-3-4 tree? Is there a particular step that you're stuck on? $\endgroup$ – roctothorpe Aug 5 '18 at 4:57
  • $\begingroup$ I have learned the rules. However, I don't know how to apply them. I know that, when 41 is removed it tries to borrow from the sibling 48, which does not have anything to lend. So, we are supposed to merge 46 and 48, creating an empty node in place of 46. If I borrow 60 now, I'm not able to preserve the search property. What to do after this ? Sorry for my bad tree picture. $\endgroup$ – rranjik Aug 5 '18 at 5:03
2
$\begingroup$

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:

  • If node containing key has more than one key, just remove the key.
  • Otherwise, we're trying to remove a 2-node (node containing 1 key). Traverse the path from the root to this node and perform one of the following operations on every 2-node except the root node to transform it into a 3-node or 4-node (node containing 2 or 3 keys):
    1. If node has a sibling that's a 3-node or a 4-node, have the parent steal a key from one such sibling and have the 2-node in question steal from the parent. The child of the sibling key we stole becomes a child of the node we just expanded.
    2. If the node's parent is a 2-node and its sibling is also a 2-node, fuse all three together into a new 4-node. Note that this can only happen when the parent is the root since all other 2-nodes should've already been fixed.
    3. If all of the node's siblings are 2-nodes, steal a key from the parent (we know we can do this because we're converting every node we hit into a 3-node or a 4-node) and fuse together the node, the stolen key, and an adjacent sibling.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.