Java Implementation of AVL Tree Data Structure

AVL Tree Class Implementation in Java

The following source code implements a generic self-balancing AVL Tree (AVLTree<T extends Comparable<T>>) in Java, supporting insertion, deletion, rotation balancing, search, and edge counting.

Class Definition and Constructors

public class AVLTree<T extends Comparable<T>> {
    private AVLNode<T> raiz;
    String cadena = "";

    public AVLTree() {
        raiz = null;
    }

    public AVLNode<T> getRaiz() {
        return raiz;
    }

    public T getInfoRaiz() {
        return raiz.getInfo();
    }

Search Operations

    public AVLNode<T> find(T info) {
        if (raiz == null) {
            return null;
        }
        return findR(raiz, info);
    }

    private AVLNode<T> findR(AVLNode<T> node, T info) {
        if (node == null)
            return null;
        if (node.getInfo().compareTo(info) == 0)
            return node;
        if (node.getInfo().compareTo(info) < 0)
            return findR(node.getRight(), info);
        if (node.getInfo().compareTo(info) > 0)
            return findR(node.getLeft(), info);
        return null;
    }

Insertion Operations

    public AVLNode<T> add(T info) {
        if (find(info) != null) {
            return null;
        }
        return raiz = addR(raiz, info);
    }

    private AVLNode<T> addR(AVLNode<T> node, T info) {
        if (node == null) {
            return new AVLNode<T>(info);
        }
        if (info.compareTo(node.getInfo()) == 0) { // Ya hay un nodo igual
            return null;
        }
        if (info.compareTo(node.getInfo()) > 0) {
            if (node.getRight() != null) {
                node.setRight(addR(node.getRight(), info));
            } else {
                node.setRight(new AVLNode<T>(info));
            }
        }
        if (info.compareTo(node.getInfo()) < 0) {
            if (node.getLeft() != null) {
                node.setLeft(addR(node.getLeft(), info));
            } else {
                node.setLeft(new AVLNode<T>(info));
            }
        }
        return updateTree(node);
    }

Deletion Operations

    public AVLNode<T> remove(T node) {
        if (node == null || find(node) == null)
            return null;
        return raiz = removeR(raiz, node);
    }

    private AVLNode<T> removeR(AVLNode<T> node, T info) {
        if (info.compareTo(node.getInfo()) < 0)
            node.setLeft(removeR(node.getLeft(), info));
        else {
            if (info.compareTo(node.getInfo()) > 0)
                node.setRight(removeR(node.getRight(), info));
            else {
                if (node.getLeft() == null)
                    return node.getRight();
                if (node.getRight() == null)
                    return node.getLeft();
                else {
                    node.setInfo(getMax(node.getLeft()));
                    node.setLeft(removeR(node.getLeft(), node.getInfo()));
                }
            }
        }
        return updateTree(node);
    }

Balancing and Rotations

    private AVLNode<T> updateTree(AVLNode<T> node) {
        node.setFactorBalanceAltura();
        if (node.getBalanceFactor() == -2) {
            if (node.getLeft().getBalanceFactor() == 1) {
                node = doubleLeftRotation(node);
            } else {
                node = singleLeftRotation(node);
            }
        } else if (node.getBalanceFactor() == 2) {
            if (node.getRight().getBalanceFactor() == -1) {
                node = doubleRightRotation(node);
            } else {
                node = singleRightRotation(node);
            }
        }
        return node;
    }

    private AVLNode<T> singleLeftRotation(AVLNode<T> node) {
        AVLNode<T> aux = node.getLeft();
        node.setLeft(aux.getRight());
        aux.setRight(node);
        updateTree(node);
        return updateTree(aux);
    }

    private AVLNode<T> singleRightRotation(AVLNode<T> node) {
        AVLNode<T> aux = node.getRight();
        node.setRight(aux.getLeft());
        aux.setLeft(node);
        updateTree(node);
        return updateTree(aux);
    }

    private AVLNode<T> doubleLeftRotation(AVLNode<T> node) {
        node.setLeft(singleRightRotation(node.getLeft()));
        return singleLeftRotation(node);
    }

    private AVLNode<T> doubleRightRotation(AVLNode<T> node) {
        node.setRight(singleLeftRotation(node.getRight()));
        return singleRightRotation(node);
    }

Utility and Traversal Methods

    private T getMax(AVLNode<T> node) {
        while (node.getRight() != null) {
            node = node.getRight();
        }
        return node.getInfo();
    }

    public int numAristas(T a, T b) {
        AVLNode<T> nodoA = find(a);
        AVLNode<T> nodoB = find(b);
        if (a.compareTo(b) < 0)
            return numAristasR(nodoA.getRight().getInfo(), b);
        if (a.compareTo(b) > 0)
            return numAristasR(nodoB.getLeft().getInfo(), b);
        return 0;
    }

    public int numAristasR(T a, T b) {
        AVLNode<T> nodoA = find(a);
        AVLNode<T> nodoB = find(b);
        if (a.compareTo(b) == 0)
            return 0;
        if (a.compareTo(b) < 0)
            return numAristasR(nodoA.getRight().getInfo(), b) + 1;
        if (a.compareTo(b) > 0)
            return numAristasR(nodoB.getLeft().getInfo(), b) + 1;
        return 0;
    }
}