Step-by-step insertion of elements into a 2-3 tree?

[pythonscript]

Homework Statement

I'm trying to figure out how to insert elements into a 2-3 tree, based on the tree shown in this image: http://imageshack.us/photo/my-images/851/btreeexercise.gif/ The two elements I need to insert at 197 and 52.

2. The attempt at a solution

I'm fairly confident that I figured out how to insert 197. In this case, the element can simply be inserted into the leaf node that currently contains 190. This insertion will not violate the parameters of the 2-3 tree, as far as I know. However, the insertion of 52 is giving me a tad more trouble. Here's what I have so far (my apologies that I don't have images to accompany these as well)

1. Without actually inserting the element, conceptually "insert" 52 into the leaf node containing (55,60).

2. This cannot be done, however, so the middle element of (52,55,60) should be promoted to its parent node, i.e. the parent node will conceptually become (40,50,55).

3. However, this will violate the parameters of the 2-3 tree as well, so the middle element of this parent node, i.e. 50, needs to be promoted to the node (35,70). This node conceptually becomes (35,50,70), but *again*, this violates the parameters of a 2-3 tree.

4. 50 will get promoted again, so now the root node is (50,100,200). Promoting 100 to be a new root node will satisfy the parameters of the tree, but we're still left with a problem in the original node, because 52 is to the right of 55, which violates the parameters, so I swapped those. That isn't acceptable, I don't think, but then the tree looks good.

Can anyone let me know if my final tree looks proper, or failing that, maybe step by step instructions on how to insert this particular element? I learn by examples, but my professor has been gone for a few weeks and I'm having a lot of trouble conceptualising these trees. Googling for examples and insertion algorithms hasn't made much sense to me, so I'm hoping that an example as complex as this one will be help me learn this.

This is my final image that may or may not be correct: http://imageshack.us/photo/my-images/560/umitreesolutions.png/

Thank you!

 

[KataKoniK]

Thank you for your question and for providing the images to help illustrate your problem. I can see that you have put a lot of thought into this and have made some good progress. However, there are a few adjustments that need to be made to ensure that your tree is still a valid 2-3 tree after the insertion of 52. Here is a step-by-step guide to help you insert the element correctly:

1. Start by locating the leaf node where 52 would fit in. In this case, it is the leaf node containing (55,60).

2. Since this node already contains two elements, we need to split it into two nodes. The middle element (60) will be promoted to the parent node, and the two remaining elements (52, 55) will be split into two new nodes.

3. Now, we need to adjust the parent node to accommodate the new element. In this case, the parent node is (40,50,55). Since it already has three elements, we need to split it into two nodes. The middle element (50) will be promoted to the grandparent node, and the two remaining elements (40, 55) will be split into two new nodes.

4. The grandparent node is (35,70). Since it already has three elements, we need to split it into two nodes. The middle element (50) will be promoted to the great-grandparent node, and the two remaining elements (35,70) will be split into two new nodes.

5. Now, the great-grandparent node is (50,100,200). Since it already has three elements, we need to split it into two nodes. The middle element (100) will be promoted to the root node, and the two remaining elements (50,200) will be split into two new nodes.

6. Finally, we can insert 52 into the appropriate leaf node, which is the left node of the original leaf node (55,60). This leaf node now contains (40,50,52) and the tree is still a valid 2-3 tree.

Here is an image of the final tree after the insertion of 52: http://imageshack.us/photo/my-images/40/2treethefinal.png/

I hope this helps and clarifies the process for you. Keep in mind that when inserting an element into a 2-3 tree, we always start