[자료구조 트리] AVL 트리

  AVL 트리란 트리가 한쪽으로 치우쳐 자라나는 현상을 방지하여 트리 높이의 균형을 유지하는 이진 탐색 트리를 의미합니다. 트리에 노의 삽입이나 삭제로 인해 균형이 깨졌을 때, 회전 연산을 통하여 트리의 균형을 유지합니다. 왼쪽과 오른쪽 서브트리의 높이 차이가 2 이상일 때 불균형이 발생했다고 합니다.

  AVL 트리에서 삽입 또는 삭제 연산을 수행할 때 트리의 균형을 유지하기 위해 LL, RR, LR, RL 회전 연산이 사용됩니다. 각 회전 연산은 두 종류의 기본적인 연산으로 구현되는데, 오른쪽으로 회전하는 rotateRight와 왼쪽으로 회전하는 rotateLeft입니다.

 

  AVL 트리에서의 삽입과 삭제 구현 코드

class Node {
    int key;
    int height;
    Node left;
    Node right;
    Node(int key, Node left, Node right) {
        this.key = key;
        this.height = 0;
        this.left = left;
        this.right = right;
    }
}

class AVLTree {
    Node head;

    public int height(Node node) {
        if (node == null) {
            return -1;
        }
        return node.height;
    }
    public Node rightRotate(Node node) {
        Node lNode = node.left;
        node.left = lNode.right;
        lNode.right = node;
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        lNode.height = Math.max(height(lNode.left), height(lNode.right)) + 1;
        return lNode;
    }
    public Node leftRotate(Node node) {
        Node rNode = node.right;
        node.right = node;
        rNode.left = node;
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        rNode.height = Math.max(height(rNode.left), height(rNode.right)) + 1;
        return rNode;
    }
    public Node lrRotate(Node node) {
        node.left = leftRotate(node.right);
        return rightRotate(node);
    }
    public Node rlRotate(Node node) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }
    public int getBalance(Node node) {
        if (node == null) {
            return 0;
        }
        return height(node.left) - height(node.right);
    }
    public void insert(int key) {
        this.head = insert(this.head, key);
    }
    public Node insert(Node node, int key) {
        if (node == null) {
            return new Node(key, null, null);
        }
        if (key < node.key) {
            node.left = insert(node.left, key);
        } else {
            node.right = insert(node.right, key);
        }
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        int balance = getBalance(node);

        //LL
        if (balance > 1 && key < node.left.key) {
            return rightRotate(node);
        }
        //RR
        if (balance < -1 && key > node.right.key) {
            return leftRotate(node);
        }
        //LR
        if (balance > 1 && key > node.left.key) {
            return lrRotate(node);
        }
        //RL
        if (balance < -1 && key < node.right.key) {
            return rlRotate(node);
        }
        return node;
    }
}

class AVLTree2 extends AVLTree {
    public void delete(int key) {
        this.head = delete(this.head, key);
    }
    public Node delete(Node node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            node.left = delete(node.left, key);
        } else if (key > node.key) {
            node.right = delete(node.right, key);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            } else {
                Node predecessor = node;
                Node successor = node.left;
                while (successor.right != null) {
                    predecessor = successor;
                    successor = successor.right;
                }
                predecessor.right = successor.left;
                node.key = successor.key;
            }
        }
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        int balance = getBalance(node);

        //LL
        if (balance > 1 && getBalance(node.left) > 0) {
            return rightRotate(node);
        }
        //RR
        if (balance < -1 && getBalance(node.right) < 0) {
            return leftRotate(node);
        }
        //LR
        if (balance > 1 && getBalance(node.left) < 0) {
            return lrRotate(node);
        }
        //RL
        if (balance < -1 && getBalance(node.right) > 0) {
            return rlRotate(node);
        }
        return node;
    }
}

  AVL 트리에서의 탐색, 삽입, 삭제 연산은 공통적으로 루트부터 탐색을 시작하여 최악의 경우에는 이파리까지 내려갑니다. 삽입이나 삭제 연산은 루트까지 거슬러 올라가야 합니다. 트리를 한 층 내려갈 때는 순환 호출이 발생하여, 한 층을 올라갈 때 불균형이 발생하면 적절한 회전 연산을 수행하는데 각각 O(1) 시간이 걸립니다. 따라서 탐색, 삽입, 삭제 연산의 수행 시간은 AVL 트리의 높이에 비례하므로 각 연산의 수행 시간은 O(logN)입니다. 거의 정렬된 데이터를 삽입한 후에 랜덤 순서로 데이터를 탐색하는 경우 가장 좋은 성능을 보입니다. 반면에 이진 탐색 트리는 랜덤 순서의 데이터를 삽입한 후에 랜덤 순서로 데이터를 탐색하는 경우 가장 좋은 성능을 보입니다.

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.