Project 1

Project 1 is due Sunday. Questions?

Right Rotation

L = root.left
root.left = L.right
L.right = root
return L

Makes L the new root of this subtree.

Left Rotation

Similar idea:

R = root.right
root.right = R.left
R.left = root
return R

• Makes R the new root of this subtree
• Inverse operations:
  • Right rotation followed by left rotation?

Exercise

Draw the trees we obtain after the following sequence of operations:

• (Create a new tree)
• Insert 0, 4, 2
• Rotate right around 4
• Insert -1, 1
• Rotate left around 0

Unbalanced Trees

Unbalanced Trees

• Can also define left-right and left-left unbalanced trees
• In general:
  • if heights of left and right subtrees differ by more than 1
• Keep track of the height of each node
• If one subtree has a larger height than the other, rebalance
• How do we rebalance? Tree rotations!

Algorithms for balancing

Some unbalanced trees can be rebalanced easily:

• right-right: rotate left
• left-left: rotate right

Right-left

Exercise

Forget about the code for a bit. What should a self-balancing tree do when we insert in the following order: 1, 2, 3, 4, 5, 6, 7?

Draw the pictures of the BSTs that result. When do we trigger a “rebalancing”?

Visualization

• Self-balancing visualization
• When are rebalancings triggered?

Self-balancing pseudocode

// pseudocode
private TreeNode<T> insert(T item, TreeNode<T> subtree) {
   // code to insert
   int balance = height(subtree.left) - height(subtree.right);
   if (balance > 1) {
     // left-left or left-right?
     // check height()
   } else if (balance < -1) {
     // right-right or right-left?
   }
}

RR

RL

Difference?

Code Snippet

private TreeNode<T> balance(TreeNode<T> subtree) {
   int balance = height(subtree.left) - height(subtree.right);
   if (balance > 1) {
     // left-left
     if (height(subtree.left.left) >= height(subtree.left.right)) {
       subtree = rotateRight(subtree);
     } else {
       // left-right
       // left rotation turns this into left-left
       subtree.left = rotateLeft(subtree.left);
       // right rotation rebalances
       subtree = rotateRight(subtree);
     }

   } else if (balance < -1) {
     // right-right or right-left?
     // do the opposite as above
   }

   // update height
   subtree.height = 1 + Math.max(height(subtree.left), height(subtree.right));
   return subtree;
}

Video

Video

In the above video, I go through the proof that all the operations are \(O(\log(n))\).

Level-order

Given a tree T, output its nodes in level-order. That is, output the root first, then output the root’s children, then the grandchildren, etc.

Hint:

• Nothing to do with BST
• We’ve seen this before (kind of)…?

AVL Sort

Implement a method in the AVL Tree class which returns a List of items in sorted order:

public List<T> sort() {
  // your code here
  
}

Asymptotic running time (if the tree has \(N\) elements)?

AVL Sort (continued)

Asymptotic running time of the following:

public static <T> List<T> sort(List<T> list) {
  AVLTree<T> tree = new AVLTree<>();
  for (T item : list) {
    tree.insert(item);
  }
  return tree.sort();
}