---
description: This section discusses abstraction of binary search trees.
---

# 4.2. Balanced BST

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:

{% embed url="https://www.slideshare.net/jchoi7s/balanced-bst-rotation" %}

> 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`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/tree/AbstractBinarySearchTree.java) that inherits the abstract class `AbstractBinarySearchTree`:

{% code lineNumbers="true" %}
```java
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);
    }
}
```
{% endcode %}

> Where does `node` end up being after the rotations?

The followings demonstrate how the `rotateLeft()` method works:

{% embed url="https://www.slideshare.net/jchoi7s/balanced-bst-rotate-left/jchoi7s/balanced-bst-rotate-left" %}

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

{% code lineNumbers="true" %}
```java
@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);
```
{% endcode %}

* `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?
