Project 2 Notes

🔙HOME

First Things First

Quiz 2. 15 minutes, closed-book

On Canvas: link
Multiple choices: select ALL answers that apply!
Access code: binary

Segment Intersection (AVL Trees)

Project Overview and General Remarks

The line sweep algorithm is provided to you
- No need to worry about the segment intersection algorithm per se, just the data structures used
Implement BinarySearchTree and AVLTree
- BinarySearchTree implements the OrderedSet interface:
  - height(): need to maintain the height during operations
  - search(), contains(), insert(), remove(): lecture notes
  - keys(): in-order traversal of the BST
    - returns a sorted list
- AVLTree extends BinarySearchTree by overriding:
  - insert(): balance the tree by (single, double) rotations
  - remove(): balance the tree by (single, double) rotations
    - Where, when, how? (We'll find out later)

BST Implementation Details

One caveat of `insert()`…

We should note that the contracts of insert() are different between the student support code version and the textbook version, so a direct copy-and-paste apparently won't work!

public Node<K> insert(K key) {
    // ... YOUR CODE
}

Your code is expected to return (quote the support code): "the location where the insert occurred", that is, a reference to the newly-inserted node.
However, the code in the book returns the root of the tree.

You need to adapt the code…

Also, make sure to update:

height (updateHeight()) for all ancestors
size of the tree (numNodes)

Same for remove(). The height of an empty tree is \(-1\):

static protected <K> int get_height(Node<K> n) {
    if (n == null) return -1;
    else return n.height;
}

Possible helper functions

Optional. You may do it differently.

set_left() and set_right(): setting the children of a node
Question: how to set the left child of n to be l?
- Previously we used n.left = l in the lecture.
  - Does it still work?
    - No. It doesn't set the parent of l to be n.
    - We didn't have parent in the BST lecture.
  - But why do we need parent this time?
    - Hint: Lab 4
- Define two helper functions. Each does 3 things:
  1. n.left = l (or n.right = r)
  2. l.parent = n if l != null
  3. update the height of n - why?
replace(): replace a tree
Replace a tree with root n with another tree with root m, we case split on the parent of n, producing 3 cases:
1. no parent (n.parent == null)
2. has parent and n is left child (n == n.parent.left)
  - set the left child of parent to be m
3. has parent and n is right child (n == n.parent.right)
  - set the right child of parent to be m

AVL Specific Implementation Details

Do normal BST insert or remove. Fix the AVL property using balance().

Where to re-balance?

Quote textbook p. 125:

We will show how to re-balance the tree at the first (i.e., deepest) such node, and we will prove that this re-balancing guarantees that the entire tree satisfies the AVL property.

Slightly confusing. In fact, we need to re-balance the tree from the current node of the operation, insert() or remove(), all the way up to the root node!

If you define insert() and remove() recursively, you need to call balance() on the current root of the sub-tree before you return.

Update the height whenever we re-balance a node.

When to re-balance?

This is where height comes into play. isAVL() is defined as:

static class Node<K> implements Location<K> {
    public boolean isAVL() {
        int h1, h2;
        h1 = get_height(left);
        h2 = get_height(right);
        return Math.abs(h2 - h1) < 2;
    }
}

public class AVLTree<K> extends BinarySearchTree<K> {
    public boolean isAVL() {
        if (root == null)
            return true;
        else
            return root.isAVL();
    }
  }

A tree is an AVL tree (balanced) if:

it is empty, or
the height difference of its two sub-trees \(<2\)

We re-balance when the tree is not AVL.

How to re-balance? Rotations

Single rotations: right_rotate() and left_rotate()
Consider right rotate (book Figure 4.40), is the following code correct?
```
private Node right_rotate(Node y) {
    Node x = y.left;
    set_left(y, x.right);
    set_right(x, y);
    return x;
}
```
Left rotate is the mirror of right rotate.
Double rotations

Book Figure 4.43