3 Apr 1996

Outline

• Insertion to 2-3 trees
• Tree rotations

2-3 Trees

Two-three trees have the following two invariants:

• Every non-leaf node has either 2 or 3 children. (But not just 1.)
• All leaves are at the same level of the tree.

The method for inserting is as follows:

1. Add the new item to the leaf you would reach if you were searching for the item.
2. If the leaf now has three items, push the middle one up to the parent.
3. If the parent now has three items, push its middle item up to its parent, and so on. Notice that a new level is added to the tree only at the root. (That's why all of the leaves are always at the same level.)

   Here's an example consisting of instructors of introductory courses, cs advisors, and staff:

                      carl    ;   doug
                   /          |         \
              avrim         danny          mark;presley
              /   \         /   \         /    |    \
          allan   bruce  cathy  dave  maria   phil  terri
   

   Now let's insert a few items.

   katheryn

   Goes into node with maria

   emilio

   There's no more room! Push katheryn up a level. Again, not enough room; Push mark up a level. Again, not enough room; Push doug up a level.

   Now the tree looks like:

                                   doug
                             /             \
                      carl                       mark
                  /        \                 /          \
               avrim        danny       katheryn        presley
              /   \         /   \         /   \        /       \
          allan   bruce  cathy  dave  emelio maria    phil   terri
   

   Insert a few more:

   mo

   Goes into node with phil

   mary

   Not enough room; push mo up to node with presley

                          
                                   doug
                             /              \
                      carl                       mark
                    /      \                   /      \
               avrim        danny       katheryn       mo;presley
              /   \         /   \         /   \        /   |    \
          allan   bruce   cathy dave  emelio maria  mary  phil   terri
   

   Tree Rotations

   Idea is that in a binary search tree, can go back and forth between these two:

                 x                           y
                / \                         / \
              T1   y     <------>          x   T3
                  / \                     / \
                 T2  T3                 T1  T2
   

   Draw a binary search tree, and see what would happen if you did a rotation in some places. For example:

          1                                             3
         / \                                           / \
        0   3     left rotation at node 1            1     5
           / \      ------------------>             / \   / \
          2   5                                    0   2 4   6
             / \
            4   6
   

   Notice that this rotation transformed a tree with depth 3 into a tree with depth 2, thus improving its balance.

   Let's write the code to perform a left rotation:

       struct tree_node {
           int             value;
           tree_node       *left;
           tree_node       *right;
       };
   
       tree_node*
       rotate_left(tree_node *y) {
           tree_node       *x = y->right;
           y->right = x->left;
           x->left = y;
           return x;
       }
   

   Here's the general picture. We start with:

                 o y
               /   \
              o     o x
             /_\   / \
              A  o     o
                /_\   /_\
                 B     C
   

   After x = y->right and y->right = x->left, we have:

            o y              o x
          /   \               \
         o     o               o 
        /_\   /_\             /_\
         A     B               C
   

   After x->left = y we have:

                 o x
                / \
              o y   o
            /  \   /_\
           o    o   C
          /_\  /_\
           A    B