AVL 트리

AVL 트리

AVL트리는 좌우 서브 트리의 높이의 차이가 1 이하인 트리로, 자가 균형 이진 탐색 트리이다. AVL 트리는 왜 등장하게 됐을까?

트리의 좌우 균형이 잘 맞을수록 트리의 높이는 낮아진다. 이진 탐색 트리에서 트리의 높이가 최소일 때 탐색 연산의 시간 복잡도는 $O(logN)$이고, 최고일 때의 시간 복잡도는 $O(N)$이다. 완전 이진 트리와 편향 이진 트리를 생각하면 된다.

트리의 높이를 최소로 유지함으로써 연산의 시간복잡도를 $O(logN)$으로 만들기 위해 스스로 균형을 맞추는 AVL 트리가 등장하게 된 것이다.

[10, 20, 30, 40, 50]으로 트리를 만들었을 때, AVL 트리(왼쪽)과 이진 탐색 트리(오른쪽)이다.

---

균형 인수

각 노드의 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이를 균형 인수(BF: Balance Factor)이라고 한다. AVL 트리의 모든 노드의 균형 인수는 [-1, 0, 1]이다.

트리의 균형 인수를 표시한 것이다. 편의를 위해 서브 트리가 없을 경우의 높이는 0으로 설정했다.

---

AVL 트리 연산

AVL 트리도 이진 탐색 트리이므로 삽입과 삭제 연산은 일반적인 이진 탐색 트리와 같다. 하지만 AVL 트리는 삽입, 삭제 연산 후에 추가로 균형을 맞춰주는 rotate 연산이 필요하다. 연산은 4종류로 나뉜다.

LL 회전 연산

트리의 불균형이 처음으로 일어나는 노드를 X라고 했을 때, X의 왼쪽 서브 트리의 왼쪽 서브 트리에 노드가 추가되어 불균형이 발생하는 경우이다. 이 경우에 트리를 오른쪽으로 회전시켜주면 된다.

먼저 Y의 오른쪽 서브 트리를 X의 왼쪽 서브 트리로 만들고, X를 Y의 오른쪽 서브 트리로 만든다. LL 타입의 연산 결과는 다음과 같다.

---

RR 회전 연산

X의 오른쪽 서브 트리의 오른쪽 서브 트리에 노드가 추가되어 불균형이 발생하는 경우이다. 이 경우에 트리를 왼쪽으로 회전시켜주면 된다.

먼저 Y의 왼쪽 서브 트리를 X의 오른쪽 서브트리로 만들고, X를 Y의 왼쪽 서브 트리로 만든다. RR 타입의 연산 결과는 다음과 같다.

---

LR 회전 연산

X의 왼쪽 서브 트리의 오른쪽 서브 트리에 노드가 추가되어 불균형이 발생하는 경우이다. LR 타입과 RL 타입은 이전과 다르게 두 번의 연산을 해야 한다.

Y-Z 구간에 대하여 RR 연산을 한다.

그 후 LL 연산을 하면 된다.

---

RL 회전 연산

X의 오른쪽 서브 트리의 왼쪽 서브 트리에 노드가 추가되어 불균형이 발생하는 경우이다.

Y-Z 구간에 대하여 LL 연산을 한다.

그 후 RR 연산을 하면 된다.

---

AVL 트리 구현

class Tree {
    private Node root = null;

    public class Node {
        int data;
        Node left, right;

        Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    public Node getRoot() {
        return root;
    }

    public int getHeight(Node node) {
        if(node == null) {
            return 0;
        }

        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }

    public int getBf(Node node) {
        if(node == null) {
            return 0;
        }

        return Math.abs(getHeight(node.left) - getHeight(node.right));
    }

    public Node insert(Node node, int data) {
        if(node == null) {
            Node newNode = new Node(data);

            if(root == null) {
                root = newNode;
            }

            return newNode;
        }

        if(data < node.data) {
            node.left = insert(node.left, data);
        }
        else if(data > node.data) {
            node.right = insert(node.right, data);
        }
        else {
            return node;
        }

        int Bf = getBf(node);

        if(Bf > 1) {
            if(data < node.left.data) { // LL
                return rotateRight(node);
            }
            else { // LR
                node.left = rotateLeft(node.left);
                return rotateRight(node);
            }
        }

        if(Bf < -1) {
            if(data > node.right.data) { // RR
                return rotateLeft(node);
            }
            else { // RL
                node.right = rotateLeft(node.right);
                return rotateLeft(node);
            }
        }
        
        return node;
    }

    private Node rotateLeft(Node parent) {
        Node child = parent.right;
        parent.right = child.left;
        child.left = parent;
        return child;
    }

    private Node rotateRight(Node parent) {
        Node child = parent.left;
        parent.left = child.right;
        child.right = parent;
        return child;
    }
}