AVL Tree

AVL Tree

- AVL Tree는 left subtree와 right subtree의 높이차가 1 이하인 BST이다.

- AVL Tree는 balance가 타이트하게 유지되기 때문에 Red-Black Tree보다 height가 더 낮다. 따라서 탐색이 더 빠르다.

- AVL Tree가 insert, delete 연산에 대해서는 성능이 밀린다는 통념이 있다.

- 하지만 잘만 구현한다면 AVL Tree가 수행 시간이 더 짧다는 실험 결과가 있다. 그러나 그 사실을 아는 사람이 많지 않고 CLRS에서 AVL Tree를 다루지 않기 때문에 RB Tree가 더 자주 사용된다. 많은 프로그래밍 언어의 라이브러리에서 RB Tree가 사용된다.

 

AVL Tree Class

public class AVLTree<E> {
    class Node<T>{
        T data;
        Node<T> left, right, parent;

        public Node(T obj) {
            data = obj;
            left = right = parent = null;
        }
    }

    public Node<E> root;
    int currentSize;

    public AVLTree() {
        root = null;
        currentSize = 0;
    }

    ...
}

 

BST 클래스와 다를 바 없다. 그런 점에서 AVL Tree 클래스가 BST 클래스를 상속하도록 구현하기도 한다.

 

원칙적으로는

 

Tree rotations

private void changePivot(Node<E> from, Node<E> to, Node<E> parent) {
    // Assumption : Links inside the subtree are properly connected except for from's parent.

    // from.parent = to
    from.parent = to;

    // to.parent = parent
    to.parent = parent;

    // parent.child = to
    if (parent == null) {
        root = to;
        return;
    }

    if (parent.left == from)
        parent.left = to;
    else
        parent.right = to;
}

private void rotateLeft(Node<E> node){
    Node<E> tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;

    changePivot(node, tmp, node.parent);
}

private void rotateRight(Node<E> node){
    Node<E> tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;

    changePivot(node, tmp, node.parent);
}

private void rotateRightLeft(Node<E> node){
    rotateRight(node.right);
    rotateLeft(node);
}

private void rotateLeftRight(Node<E> node){
    rotateLeft(node.left);
    rotateRight(node);
}

 

강의에서 제공하는 코드는 node's parent link, tmp's parent link, parent's child link의 변화를 반영하지 않는다.

 

1. node's parent = tmp

2. tmp's parent = parent

3. parent's child = tmp

 

위의 3가지 작업을 추가로 해줘야 rotation 코드가 정상적으로 동작한다.

 

물론, parent가 null일 경우 (= node가 root인 경우), 3번 대신 root = tmp 를 실행해야 한다.

 

 

Height

private int height(Node<E> node) {
    if (node == null)
        return -1;
    else {
        return Math.max(height(node.left), height(node.right)) + 1;
    }
}

 

편의상 height method를 recursive method로 구현하였다.

 

이 method의 시간 복잡도는 O(n)이므로 실제로는 height를 이렇게 계산하면 안된다.  

 

원칙적으로는 각 노드에 height를 저장하고 각 과정에서 height를 계속 update 해주는 방식으로 구현해야 한다.

 

 

Check balance

private void checkBalance(Node<E> node) {
    if ((height(node.left) - height(node.right) > 1) || 
            (height(node.left) - height(node.right) < -1)){
        // imbalance occurs at "node"
        rebalance(node);
        return;
    }

    if (node.parent == null)
        return;

    checkBalance(node.parent);
}

 

Rebalance

private void rebalance(Node<E> node) {
    if (height(node.left) - height(node.right) > 1) {
        // the cause(added node) is in the left subtree of the node
        if (height(node.left.left) > height(node.left.right)) {
            // the cause is in the left-left subtree of the node
            rotateRight(node);
        } else {
            // the cause is in the left-right subtree of the node
            rotateLeftRight(node);
        }
    } else {
        // the cause is in the right subtree of the node
        if (height(node.right.left) > height(node.right.right)) {
            // the cause is in the right-left subtree of the node
            rotateRightLeft(node);
        } else {
            // the cause is in the right-right subtree of the node
            rotateLeft(node);
        }
    }
}

 

Add method

public void add(E obj) {
    Node<E> node = new Node<E>(obj);
    if (root == null)
        root = node;
    else
        add(root, node);
    currentSize++;

    checkBalance(node);
}

private void add(Node<E> parent, Node<E> newNode) {
    if (((Comparable<E>)newNode.data).compareTo(parent.data) > 0) {
        // go to the right
        if (parent.right == null) {
            parent.right = newNode;
            newNode.parent = parent;
        }
        else
            add(parent.right, newNode);
    } else {
        // go to the left
        if (parent.left == null) {
            parent.left = newNode;
            newNode.parent = parent;
        }
        else
            add(parent.left, newNode);
    }
}