Week 12

1. * Given the above 2-3 tree insert the keys 44, 45, 46, 47. Show tree at each step.

   
                      50
                     /   \
                 30         70,90
                / \        /  |  \
            10,20 40      60 80  99   
   
   insert 44
   
                      50
                     /   \
                 30         70,90
                / \        /  |  \
            10,20 40,44   60 80  99   
   
   insert 45
   
                      50
                     /   \
                 30         70,90
                / \        /  |  \
            10,20 40,44,45 60 80  99   
   
   (promote middle one - split the kids)
   
                      50
                     /   \
                 30,44      70,90
                / |  \     /  |  \
            10,20 40 45   60 80  99   
   
   insert 46
                      50
                     /   \
                 30,44       70,90
                / |  \      /  |  \
            10,20 40 45,46 60 80  99   
   
   insert 47
                      50
                     /   \
                 30,44           70,90
                / |  \          /  |  \
            10,20 40 45,46,47  60 80  99   
   
   (promote middle one - split the kids)
   
                      50
                     /   \
                 30,44,46      70,90
                / |  \  \     /  |  \
            10,20 40 45 47  60 80  99   
   
   (promote middle one - split the kids)
   
                     44, 50
                   /  |   \
                 30  46      70,90
                / |  /  \    /  |  \
            10,20 40 45 47  60 80  99   
   
   do sanity check - did I get it right? (I find these torturous).  Actually same example as in lecture notes where the diagrams are better!
     Given the above 2-3 tree delete the keys 60,70,80.  Show tree at each step. (Just ensure given key is deleted and that you have a valid 2-3 tree afterwards by merging. Can use Carrano's algorithm if you wish but not necessary).
   
   
                      50
                     /   \
                 30        70,90
                / \       /  |  \
            10,20 40     60 80  99   
   
   just do it by eye - never have to do it again in your life - no point in learning an abstruse algorithm.  Just gaining understanding about their structure
   
   delete 60
                      50
                     /   \
                 30        70,90
                / \         |  \
            10,20 40        80  99   
   
       not valid so merge 70 and 80
   
                      50
                     /   \
                 30         90
                / \         /    \
            10,20 40      70,80  99   
   
   delete 70
   
                      50
                     /   \
                 30          90
                / \          /  \
            10,20 40       80  99   
   
   delete 80
   
                      50
                     /   \
                 30         90
                / \           \
            10,20 40           99   
   
   not valid - must have 2 or 3 children (or none - not allowed 1 kid ) 
   
                      50
                     /   \
                 30        90,99
                / \           
            10,20 40              
   
   not valid - leaves must be at same level 
   
                     30,50
                   /   |   \
               10,20  40    90,99
                            
    
    
   
     Write the pseudocode for an postorder traversal of a 2-3 tree.  
   (inorder given in lectures so just need to know that post means after)
   
   
      void postorder(twoThreeTree tt)
      {
         if (tit is not empty)
         {
             if ( node pointed to by tt is a 2-node)
             {
                  postorder(tt->left);
                  postorder(tt->right);
                  visit tt->data;
             }
            else // 3-node  
             {
                  postorder(tt->left);
                  postorder(tt->mid);
                  visit (tt->SmallData);
                  postorder(tt->right);
                  visit (tt->LargeData);
             }
         }
      }
   
   
   
   
   An AVL tree is a self-balancing binary search tree (does rotations after insertions to retain balance)
   Use the same binary search tree algorithms we already know and love.
   
    Write a c++ function for determining the height of an AVL tree.  Assume the following definition of a node :
   struct node
   {
       int data;
       node *left;
       node *right;
   };
   int height (node * t)
   // pre : none
   // post : returns the height of the tree
   
   {
      if (t == NULL)
         return 0;
      else return 1 + max(height(t->left), height(t->right));
   }
   
   
    Write a c++ function for determining the largest value in an AVL tree.
   int findMax( node * t)
   // pre : none
   // post : returns the maximum value in an AVL tree or INT_MIN if none exists
   {
      if (t== NULL)
        return INT_MIN;
      else
      {
         while (t->right != NULL)
           t = t->right;
         return t->data;
      }
   }
   
      
   
   Red-black trees are binary search trees.
   Use the same binary search tree algorithms we already know and love.
   
    Write a c++ function for determining if two red-black trees are equal.
   Two red-black trees are equal if they are the same shape and contain the same data in the corresponding nodes.
   struct node
   {
      int data;
      bool isRed;
      node *left;
      node *right;
   };
   bool areEqual (node *t1, node *t2)
   // pre : none
   // post : returns true if both trees are equal and otherwise false
   {
       if (t1 == NULL && t2 == NULL)
           return true;
       else if (t1 == NULL || t2 == NULL)
           return false;
       return t1->data == t2->data && areEqual(t1->left, t2->left) &&
        areEqual(t1->right, t2->right);
   }
   
     When are B-trees of higher order (degree) an advantage?
   
   When used as indexes for secondary storage - short fat trees reduce disk accesses.   DBMS use B-trees of very high order (>500)