Contains

if (root == null) {
    return false;
}
int comparison = item.compareTo(root.data);
if (comparison == 0) {
    return true;
} else if (comparison < 0) {
    return contains(root.left, item);
} else {
    return contains(root.right, item);
}

Remove

• if the node is a leaf, return null
• if the node has one child, replace its data with its child, delete its child.
• if the node has two children, replace its data with its successor, delete the successor

Successor

private T findMin(TreeNode<T> subtree) {
    if (subtree == null) {
        return null;
    }

    while (subtree.left != null) {
        subtree = subtree.left;
    }
    return subtree.data;
}

Remove

• CodingRooms
• Run Unit Tests in IntelliJ

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?

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

Self-balancing pseudocode

// psuedocode
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?
   } else if (balance < -1) {
     // right-right or 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”?