Data Structures

Professor Abdul-Quader

Lesson 8 (AVL Trees / Hashtable Intro)

Presentations

Finishing presentations today.

Self-balancing algorithm

  • Keep track of the heights of each node.
  • Make sure to update the height during rotations.
  • At the end of insert or remove, rebalance.

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;
}

Test it out

  • Let’s implement the above
  • Starter code
  • Test it out on random insertions and in-order insertions
  • What are the heights if we insert 100 elements? 1000?

Video

Analysis

  • Adelson-Velsky, Landis (1962): AVL Trees
  • Height is \(O(\log(n))\)
  • So contains is \(O(\log(n))\).
  • Insert/remove may trigger rebalancings. How many?
    • Only up one branch of the tree! So still \(O(\log(n))\).
  • Adelson-Velsky/Landis proved: worst case height is about \(1.44 \log(n)\).

Running times

  • BST: average case \(O(\log(N))\) (not proven)
    • Worst case \(O(N)\)
  • AVL Tree: best case = average case = worst case = \(O(\log(N))\)

Proof Idea

  • How do we prove that the worst case height is \(O(\log(N))\)?
  • What is the “worst case” for an AVL tree?
  • Maybe each node is unbalanced, slightly?
  • Let \(N(h)\) be the number of nodes in the worst possible AVL tree of height \(h\).
  • Come up with a recurrence.

Video

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

Challenge questions

  • Tree (not necessarily BST / AVL): Level-order traversal
  • AVL Tree Sort / running times
  • Tree (not necessarily BST / AVL): Path from root to a node N
  • Tree (not necessarily BST / AVL): Node N, height \(h\), find ancestor of \(N\) that is \(h\) levels above.
  • Tree (not necessarily BST / AVL): two nodes, find lowest common ancestor

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();
}

Homework 2

Due Thursday, March 6 on BrightSpace. Submit a single PDF file.

  1. Prove (by induction) that there are \(2^{h+1} - 1\) nodes in a complete binary tree of height \(h\), assuming the last level is completely filled.
  2. Write a method which outputs the nodes of a binary tree in level-order. Do this in linear time (\(O(n)\)), and explain why your method runs in that time.

Homework 2

  1. Describe how you would modify the binary search tree (and its TreeNode class) to support a findKth(int k) method. This method should return the \(k\)-th smallest element of the tree in \(O(\log(N))\) time (on average if it’s a BST, or always if it’s an AVL tree). You do not need to write actual code here, but you do need to explain the algorithm, and what changes need to be made to the tree / node classes to support this.
// reveal.js plugins