4.2. AVL Trees

This section discusses a type of balanced binary search trees called AVL Trees.

AVL (Adelson-Velsky and Landis) trees preserve the balance at all time by keeping track of the height of every node through a balance factor.

AVL Node

Let us create the AVLNode class inheriting AbstractBinaryNode:

public class AVLNode<T extends Comparable<T>> extends AbstractBinaryNode<T, AVLNode<T>> {
    private int height;

    public AVLNode(T key) {
        super(key);
        height = 1;
    }

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }
}

• L2: keeps track of the height of this node.

• L6: a node with no children has the height of 1.

We then override the setLeftChild() and setRigthChild() methods such that the height of this node gets adjusted accordingly with the new child by calling the resetHeights() method:

@Override
public void setLeftChild(AVLNode<T> node) {
    super.setLeftChild(node);
    resetHeights();
}

@Override
public void setRightChild(AVLNode<T> node) {
    super.setRightChild(node);
    resetHeights();
}

/** Resets the heights of this node and its ancestor, recursively. */
public void resetHeights() {
    resetHeightsAux(this);
}

private void resetHeightsAux(AVLNode<T> node) {
    if (node != null) {
        int lh = node.hasLeftChild() ? node.getLeftChild().getHeight() : 0;
        int rh = node.hasRightChild() ? node.getRightChild().getHeight() : 0;
        int height = Math.max(lh, rh) + 1;

        if (height != node.getHeight()) {
            node.setHeight(height);
            resetHeightsAux(node.getParent());  // recursively update parent height
        }
    }
}

• L15: adjusts the height of this node and its ancestors, recursively.

• L20-22: retrieve the height of this node.

• L24-27: resets the height of this node if different and makes the recursive call to its parent.

What are the heights of 3, 5, and 7 in the figure below when the height of 4 changes from 3 to 4?

Finally, we define the getBalanceFactor() method that returns the height difference between the left-subtree and the right-subtree of this node:

/** @return height(left-subtree) - height(right-subtree). */
public int getBalanceFactor() {
    if (hasBothChildren())
        return left_child.getHeight() - right_child.getHeight();
    else if (hasLeftChild())
        return left_child.getHeight();
    else if (hasRightChild())
        return -right_child.getHeight();
    else
        return 0;
}

How can we tell if the node is unbalanced by using the balance factor?

AVL Tree

Let us create the AVLTree class that inherits AbstractBalancedBinarySearchTree and override the createNote(), rotateLeft(), and rotateRight() methods:

public class AVLTree<T extends Comparable<T>> extends AbstractBalancedBinarySearchTree<T, AVLNode<T>> {
    @Override
    public AVLNode<T> createNode(T key) {
        return new AVLNode<>(key);
    }

    @Override
    protected void rotateLeft(AVLNode<T> node) {
        super.rotateLeft(node);
        node.resetHeights();
    }

    @Override
    protected void rotateRight(AVLNode<T> node) {
        super.rotateRight(node);
        node.resetHeights();
    }
}

• L10,16: resets the height of node after rotation.

node.resetHeights() does not reset heights of nodes in its subtree. Would this cause an issue?

We then override the balance() method:

@Override
protected void balance(AVLNode<T> node) {
    if (node == null) return;
    int bf = node.getBalanceFactor();

    if (bf == 2) {
        AVLNode<T> child = node.getLeftChild();

        if (child.getBalanceFactor() == -1)
            rotateLeft(child);

        rotateRight(node);
    }
    else if (bf == -2) {
        AVLNode<T> child = node.getRightChild();

        if (child.getBalanceFactor() == 1)
            rotateRight(child);

        rotateLeft(node);
    }
    else
        balance(node.getParent());
}

• L6: the left-subtree is longer.

  • L9-10: the case of left zig-zag.

  • L12: the case of left linear.

• L14: the right-subtree is longer.

  • L17: the case of right zig-zag.

  • L20: the case of right linear.

The followings demonstrate how the balance() method works in AVL Trees:

What is the worst-case complexity of the balance() method in AVLTree?