2-3 Tree Problems Solutions                            Carol Zander (CSS 343)
---------------------------

1. Consider the 2-3 tree. Show the new tree after the insertion of 20.  
             40,55             
         /     |     \
    30,35      45        70,90
   /  |  \    /  \     /   |  \
10,15 33 36  42  47  60,62 80  99

The 20 "joins" the 10,15 node and the node is split with 15 moving up.
In an interim view, imagine 15,30,35 having 4 children:

             40,55             
         /      \     \
  15,30,35       45        70,90
 /  |  |  \     /  \     /   |  \
 10 20 33 36   42  47  60,62 80  99

The 15,30,35 is split with the 30 moving up.  In an interim view,
imagine 30,40,55 having 4 children:

          30, 40, 55             
      /     /    \     \
    15     35     45        70,90
   /  \   /  \   /  \     /   |  \
  10  20 33  36 42  47  60,62 80  99

The 30,40,55 node is split with 40 moving up.  The final tree is:
                    40
               /          \
           30                55             
      /      \            /      \
    15        35        45        70,90
   /  \      /  \      /  \     /   |  \
  10  20    33  36    42  47  60,62 80  99

2. Build a 2-3 tree by inserting 30, 50:       30,50

Now insert 60:         30,50,60   // interim imaginery step, split, 50 moves up

                          50
                         /  \
                       30    60      

Now insert 40, 70:        50
                         /  \
                     30,40   60,70      

Insert 20:           50      
                    /  \
             20,30,40   60,70     // interim imaginery step, split, 30 moves up

                   30,50      
                  /  |  \
                20  40   60,70     

Insert 25:         30,50      
                  /  |  \
             20,25  40   60,70    

Insert 65:         30,50      
                  /  |  \
             20,25  40   60,65,70  // interim imaginery step, split, 65 moves up

                 30,50,65      
                /  |  \  \
           20,25  40   60 70      // interim imaginery step, split, 50 moves up

                   50
                 /    \
               30      65      
              /  \    /  \
          20,25  40  60   70

Insert 63, 75:        50
                   /      \
                 30        65      
                /  \      /  \
            20,25  40  60,63  70,75

Insert 80:     50
            /      \
          30        65      
         /  \      /  \
     20,25  40  60,63  70,75,80  // interim imaginery step, split, 75 moves up

               50
            /      \
          30        65,75      
         /  \      /  |   \
     20,25  40  60,63 70   80  

Insert 85:    50
           /      \
         30        65,75      
        /  \      /  |   \
    20,25  40  60,63 70   80,85 

Insert 90:
            50
         /      \
       30        65,75      
      /  \      /  |   \
  20,25  40  60,63 70   80,85,90  // interim imaginery step, split, 85 moves up

            50
         /      \
       30        65,75,85     // interim imaginery step, split, 75 moves up
      /  \      /  |   \  \
  20,25  40  60,63 70  80  90

             50  ,  75
         /       |      \
       30        65       85     
      /  \      /  \     /  \
  20,25  40  60,63  70  80   90

Insert 92:
             50  ,  75
         /       |      \
       30        65       85     
      /  \      /  \     /  \
  20,25  40  60,63  70  80   90,92

Insert 95:
             50  ,  75
         /       |      \
       30        65       85     
      /  \      /  \     /  \
  20,25  40  60,63  70  80   90,92,95   // imaginery step, split, 92 moves up

             50  ,  75
         /       |      \
       30        65       85,92
      /  \      /  \     /  |   \
  20,25  40  60,63  70  80  90   95   

Insert 97:
             50  ,  75
         /       |      \
       30        65       85,92
      /  \      /  \     /  |   \
  20,25  40  60,63  70  80  90   95,97

Insert 99:
             50  ,  75
         /       |      \
       30        65       85,92
      /  \      /  \     /  |   \
  20,25  40  60,63  70  80  90   95,97,99  // imaginery step, split, 97 moves up

             50  ,  75
         /       |      \
       30        65       85,92,97         // imaginery step, split, 92 moves up
      /  \      /  \     /  |   \  \
  20,25  40  60,63  70  80  90   95 99

             50  ,  75   ,   92            // imaginery step, split, 75 moves up
         /       |       |       \
       30        65      85       97    
      /  \      /  \    /  \     /  \
  20,25  40  60,63  70 80  90  95    99

                    75
                 /       \        
             50              92            
         /       \        /      \
       30        65      85       97    
      /  \      /  \    /  \     /  \
  20,25  40  60,63  70 80  90  95    99