[SOLVED] Deletion of an internal node in 2-3-4 tree

Deletion of an internal node in 2-3-4 tree

I want to delete the 15 from the following 2-3-4 tree. I thought of simply moving the 17 up, but I don't know whether that is correct since it has to be complete.

Delete 15 from the following tree:

How will the 2-3-4 tree look like after deletion? I assume that simply moving up 17 is not correct in this case. But I'm not quite sure.

Solution

The tree you have is not a valid 2 3 4 tree since it has a duplicate 6.

To delete an internal valuee from a 2 3 4 tree, you simply replace the value to be deleted with its next greatest item, its in order successor, which is 17. This reduces the problem of deletion, to deletion of a value from a leaf node. So the question is, how do you delete a leaf node value?

When you delete from a leaf of a 2 3 4 tree you simply remove the item, if it is a 3- or 4-node. If it is a 2-node, this leaves the node empty. This is called underflow. To fix this problem, you must convert all 2-nodes encountered to 3- or 4-nodes. There are three cases you have to handle, depending on whether there is an adjacent sibling that is a 3- or 4-node, or whether they are all 2-nodes. This is explained in the links below.

For a discussion on deletion from a 2 3 4 tree, see slides 51 through 53:

http://www.serc.iisc.ernet.in/~viren/Courses/2009/SE286/2-3Trees-Mod.ppt

2 3 4 deletion (and insertion) is also explained and illustrated at:

For source code implementing a 2 3 4 tree (in C++11) see:

http://cplusplus.kurttest.com/notes/tree234.html