Week 05 Tutorial Notes

Group Question

1. Do rotations to bring the node with value 7 to the root of the tree. Draw the tree after each rotation.




2. \(|L - R|\) is the difference in height between the left and right substrees. A tree is considered height balanced if \(|L - R| \leq 1 \) holds for every node. Which of the following trees are unbalanced?
   


3. Investigate the following trees (A) and (B):
1. Is the straight-line case height balanced? What rotation/s will fix it?
2. Is the zig-zag case height balanced? What rotation/s will fix it? Draw the steps showing how to do this.



4. Your task is to draw out the solution for this problem:
   
   1. Is the AVL tree height balanced?
   2. Draw the AVL tree and Insert 5.
   3. Unwinding the recursion from inserting node 5, what is the first node that makes the AVL tree height unbalanced?
   4. From the unbalanced node in (c) is it a Straight-line case or Zigzag case?
   5. Draw the AVL tree that will fix the height resulting from the rotations done in (d).
   6. Is the final AVL tree height balanced?
   
   
5. Your task is to draw the solution for this problem:

   struct node *rotateLeft(struct node *parent);
   

   Redraw the diagram to answer the following questions:

   

   
   

   1. Label the "child" pointer for a left rotation on your diagram.
   2. Draw a second diagram that shows the resulting tree after the left rotation.
   3. Write the pseudocode implementation for rotateLeft(parent). Such that diagram 1 is your input and diagram 2 is the output.

      Restriction: Do not create additional pointers. Only use the parent and child pointers.





Group Work Answers:

Click each section to reveal.

Part 1:



Part 2:

The unbalanced trees are [B, D, F]

Part 3:

1. Unbalanced. A right rotation at the root will fix the height.
2. Unbalanced. A left rotation at the left child first and then right rotation will fix the height.

Part 4:

1. The AVL is height balanced. AVL trees are always height balanced by construction.
2. 
3. The first unbalanced node is 3.
4. This is a zig-zag case. See the red arrows in the above picture.
5. See above picture.
6. The AVL is still height balanced after we do the rotations.

Part 5:



struct node *rotateLeft(struct node *parent) {
    struct node *child = parent->right;
    parent->right = child->left;
    child->left = parent;
    return child;
}