Physics Forums (http://www.physicsforums.com/index.php)
-   Engineering, Comp Sci, & Technology Homework (http://www.physicsforums.com/forumdisplay.php?f=158)
-   -   Step-by-step insertion of elements into a 2-3 tree? (http://www.physicsforums.com/showthread.php?t=584741)

 pythonscript Mar7-12 01:21 PM

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

1. The problem statement, all variables and given/known data

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...eexercise.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...solutions.png/

Thank you!

 All times are GMT -5. The time now is 11:05 PM.