4.2. Balanced BST

This section discusses abstraction of binary search trees.

A binary search tree gives the worst-case complexity of $O(n)$for searching a key when it is not balanced, where $n$ is the number of nodes in the tree:

Search	Insert	Delete
Unbalanced	$O(n)$	$O(n)$	$O(n) + \beta$
Balanced	$O(\log n)$	$O(\log n) + \alpha$	$O(\log n) + \beta$

To ensure the $O(\log n)$ complexity, it needs to be balanced at all time (or at most time).

Rotation

There are 4 cases of unbalanced trees to be considered:

• Left linear $\Rightarrow$ [3, 2, 1]

• Right linear $\Rightarrow$ [1, 2, 3]

• Left zig-zag $\Rightarrow$ [3, 1, 2]

• Right zig-zag $\Rightarrow$ [1, 3, 2]

These cases can be balanced by performing rotations as follows:

What should happen to the subtrees (red/orange/green/blue triangles) after the rotations?

Abstract Balanced Binary Search Tree

Let us create an abstract class AbstractBalancedBinarySearchTree that inherits the abstract class AbstractBinarySearchTree:

public abstract class AbstractBalancedBinarySearchTree<T extends Comparable<T>, N extends AbstractBinaryNode<T, N>> extends AbstractBinarySearchTree<T, N> {
    /**
     * Rotates the specific node to the left.
     * @param node the node to be rotated.
     */
    protected void rotateLeft(N node) {
        N child = node.getRightChild();
        node.setRightChild(child.getLeftChild());

        if (node.hasParent())
            node.getParent().replaceChild(node, child);
        else
            setRoot(child);

        child.setLeftChild(node);
    }

    /**
     * Rotates the specific node to the right.
     * @param node the node to be rotated.
     */
    protected void rotateRight(N node) {
        N child = node.getLeftChild();
        node.setLeftChild(child.getRightChild());

        if (node.hasParent())
            node.getParent().replaceChild(node, child);
        else
            setRoot(child);

        child.setRightChild(node);
    }
}

Where does node end up being after the rotations?

The followings demonstrate how the rotateLeft() method works:

https://www.slideshare.net/jchoi7s/balanced-bst-rotate-left/jchoi7s/balanced-bst-rotate-leftwww.slideshare.net

Let us override the add() and remove() methods that call the abstract method balance():

@Override
public N add(T key) {
    N node = super.add(key);
    balance(node);
    return node;
}

@Override
public N remove(T key) {
    N node = findNode(root, key);

    if (node != null) {
        N lowest = node.hasBothChildren() ? removeHibbard(node) : removeSelf(node);
        if (lowest != null && lowest != node) balance(lowest);
    }

    return node;
}

/**
 * Preserves the balance of the specific node and its ancestors.
 * @param node the node to be balanced.
 */
protected abstract void balance(N node);

• L3: calls the add() method in the super class, AbstractBinarySearchTree.

• L4: performs balancing on node that is just added.

• L14: performs balancing on node that is the lowest node in the tree affected by this removal.

• L24: defines a balancing algorithm for a specific type of balanced binary search trees.

What are the worst-case complexities of the add() and remove() methods above?