[자료구조] AVL 트리 이론, 구현

AVL 트리

AVL 트리는 이진 탐색 트리의 속성을 갖는다.

왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 최대 1이다.

높이 차이가 1보다 커지는 경우가 생기면 회전을 통해서 균형을 잡는다.

 

회전(Rotation)

LL(Left - Left) case

삽입 또는 삭제로 인해 Left - Left로 서브 트리가 불균형을 이루는 것을 LL 문제라 한다.

LL Case

4번 노드의 오른쪽 자식 노드를 6번 노드로 변경한다.

4번 노드의 우측 자식인 것을 6번 노드의 왼쪽 자식노드로 변경한다. (4보다는 크고 6보다는 작기 때문)

4번 노드를 부모 노드로 승격 시킨다.

= 우회전 (Right Rotation)

 

RR(Right - Right) case

삽입 또는 삭제로 인해 Right- Right로 서브 트리가 불균형을 이루는 것을 RR 문제라 한다.

RR Case

8번 노드의 왼쪽 자식을 6번으로 변경한다.

8번 노드의 왼쪽 자식 인것을 6번 노드의 오른쪽 자식노드로 변경한다. (6보단 크고 8보단 작기 때문)

8번 노드를 부모 노드로 승격한다.

= 좌회전 (Left Rotation)

 

LR(Left - Right) case

삽입 또는 삭제로 인해 Left - Right로 서브 트리가 불균형을 이루는 것을 LR 문제라 한다.

LR Case

우선 RR 문제부터 해결해야한다.

6번 노드를 축으로 Left Rotation(좌회전)을 하고 나면 LL 문제가 생긴다.

이때는 Right Rotation(우회전)을 해서 균형을 맞춰준다.

= 좌회전 후 우회전

 

RL(Right - Left) case

삽입 또는 삭제로 인해 Right - Left로 서브 트리가 불균형을 이루는 것을 RL 문제라 한다.

RL Case

우선 LL 문제부터 해결해야한다.

8번 노드를 축으로 Right Rotation(우회전)을 하고 나면 LL 문제가 생긴다.

이때는 Left Rotation(좌회전)을 해서 균형을 맞춰준다.

= 우회전 후 좌회전

 

AVLTree 메소드

public class AVLTree {
    AVLNode root;

    // 노드의 높이를 반환하는 메소드(null인 경우는 -1)
    int height(AVLNode node) {
        if (node == null)
            return -1;
        return node.height;
    }

    // 노드의 균형인수를 구하는 메소드 : 서브트리 높이 - 오른쪽 서브트리 높이
    private int getBalance(AVLNode node) {
        if (node == null) {
            return 0;
        }
        return height(node.left) - height(node.right);
    }
}

AVL 트리는 균형 인수를 구해가며 균형이 깨졌을 때 균형 조정을 계속 해줘야하므로 높이를 반환하는 height() 메소드와 균형 인수를 구하는 getBalance() 메소드를 생성해주었다,

 

    // 노드의 왼쪽 회전
    private AVLNode leftRotate(AVLNode parent) {
        AVLNode newParent = parent.right;
        AVLNode T2 = newParent.left;

        newParent.left = parent;
        parent.right = T2;

        parent.height = Math.max(height(parent.left), height(parent.right)) + 1;
        newParent.height = Math.max(height(newParent.left), height(newParent.right)) + 1;

        return newParent;
    }

    // 노드의 오른쪽 회전
    private AVLNode rightRotate(AVLNode parent) {
        AVLNode newParent = parent.left;
        AVLNode T2 = newParent.right;

        newParent.right = parent;
        parent.left = T2;

        parent.height = Math.max(height(parent.left), height(parent.right)) + 1;
        newParent.height = Math.max(height(newParent.left), height(newParent.right)) + 1;

        return newParent;
    }

위에서 LL, RR, LR, RL상황에서 설명한 좌회전과 우회전을 하는 메소드이다.

 

// AVL 트리에 데이터 삽입
    public void insert(Integer data) {
        this.root = insert(this.root, data);
    }

    // 재귀적으로 적절한 위치에 데이터 삽입 / 균형 조정
    private AVLNode insert(AVLNode node, Integer data) {
        if (node == null) {
            return new AVLNode(data);
        }

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

        node.height = 1 + Math.max(height(node.left), height(node.right));
        int balance = getBalance(node);

		// LL상황 - 우회전
        if (balance > 1 && data < node.left.data)
            return rightRotate(node);
        // RR상황 - 좌회전
        if (balance < -1 && data > node.right.data) 
            return leftRotate(node);
        
        // LR상황 - 좌회전 -> 우회전
        if (balance > 1 && node.left.data < data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        
        // RL상황 - 우회전 -> 좌회전
        if (balance < -1 && data < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

 데이터를 삽입 시 LL, RR, LR, RL상황에 맞게 회전을 통해서 균형을 맞추는 AVL 트리 삽입 메소드이다