자료구조 - AVL 트리

AVL 트리

---

AVL 트리는 모든 노드의 왼쪽 및 오른쪽 하위 트리 높이 차이가 1보다 클 수 없는 이진 탐색트리로 자체 균형 이진 탐색 트리라고도 한다.

모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이를 노드의 균형 요소(BF, Balance Factor)라고 하는데 이러한 균형 요소를 가지고 트리의 균형을 확인하여 노드를 적절한 곳으로 재배치해준다.

그렇다면 그냥 이진 탐색 트리를 사용하면 되지 굳이 AVL 트리를 사용하는 이유가 뭘까?

일단 이진 탐색 트리는 루트 노드를 중심으로 들어오는 데이터가 큰지, 작은 지를 판별해 데이터를 삽입하게 된다.

이진 탐색 트리의 특징은 효율적으로 탐색, 삽입, 삭제를 할 수 있는데 데이터를 삽입하고 삭제하는 것은 결국 탐색이 먼저 이루어져야 하므로 이진 탐색 트리에서 중요한 것은 탐색이라고 생각할 수 있다.

그렇다면 데이터가 루트 노드에 비해서 계속 큰 값만 들어온다면 어떻게 될까?

10부터 50까지 데이터가 들어온다고 가정하면 아래 그림과 같이 트리가 만들어진다.

편향 이진 트리

이렇게 한쪽으로만 치우쳐진 이진트리를 편향 이진트리라고 하는데 이러면 앞서 설명했던 탐색의 효율이 굉장히 안 좋아지게 된다.

 

위와 같은 그림이 있을 때 왼쪽의 이진트리에서는 어떤 데이터든지 2번의 탐색만으로 원하는 데이터를 찾을 수 있는 반면, 편향 이진트리는 최악의 경우에 50까지 탐색을 해야 되는 문제가 발생한다.

시간 복잡도는 보면 편향 이진 트리에서는 최악의 경우 O(N) 시간 복잡도를 가지지만 AVL 트리로 재구성하면 O(logN)으로 탐색의 성능이 향상된다.

이러한 편향 이진트리의 문제를 해결하기 위해 만들어진 것이 AVL 트리이다.

AVL 트리에서는 균형을 잡는 방법이 총 4가지가 있다. 하나씩 살펴보자.

 

LL(Left-Left)

---

먼저 왼쪽 하위 트리가 계속 생기는 케이스를 보면 마지막으로 C라는 노드가 들어왔을 때 A의 BF가 2로 되기 때문에 트리의 균형이 깨지게 된다. 이때 우회전을 통해서 트리의 균형을 다시 잡게 된다.

우회전을 하는 방법은 B 노드가 부모 노드가 되고 기존의 부모 노드였던 A 노드가 B의 오른쪽 자식 노드가 되도록 회전한다.

그림에는 없지만 만약 B 노드 오른쪽 자식 노드로 D라는 노드가 있다고 가정해 보면 우회전할 시 해당 D 노드는 A의 왼쪽 자식 노드가 된다.

 

 

RR(Right-Right)

---

다음으로 알아볼 케이스는 오른쪽 하위 트리가 계속 생기는 케이스이다.

이럴 경우에는 LL 케이스와는 반대로 좌회전을 하게 되는데 B 노드가 부모 노드가 되고 A 노드가 왼쪽 자식 노드가 된다. 우회전과 마찬가지로 만약 B노드에 왼쪽 자식 노드가 있다면 해당 노드를 B 노드가 좌회전하고 나서 A 노드의 오른쪽 자식 노드로 이동시킨다.

 

LR(Left-Right)

---

LR 케이스는 왼쪽 자식 노드가 오른쪽 자식 노드를 가지고 있을 때 균형이 깨지는 케이스이다.

해당 케이스는 먼저 A 노드와 B 노드를 좌회전을 통해서 LL 케이스를 만들고 그다음 우회전을 통해서 트리의 균형을 맞추게 된다.

 

RL(Right-Left)

---

RL 케이스는 앞서 살펴본 LR 케이스와 반대로 생각하면 된다.

B와 C 노드를 우회전하여 RR 케이스로 만들고 좌회전을 하여 트리의 균형을 맞춘다.

 

코드로 보는 AVL 트리

---

AVL 트리를 구현하면서 총 3개의 클래스 파일을 만들었다. AVL 트리 객체를 생성하여 메서드를 호출하는 AVLMain 클래스를 제외하고 가장 핵심인 Node와 AVLTree 클래스를 알아보자.

 

Node 클래스

public class Node {

    Node left;          // 현재 노드에서 왼쪽 자식 노드
    Node right;         // 현재 노드에서 오른쪽 자식 노드

    Integer height;     // 높이를 저장할 변수
    Integer value;      // 각 노드의 값을 저장할 변수
    Integer bf;

    // TODO: 생성자
    public Node(Integer data) {
        this.height = 1;
        this.left = null;
        this.right = null;
        this.value = data;
        this.bf = 0;
    }

    // TODO: BF 저장하기
    public void setBf(Integer bf) {
        this.bf = bf;
    }
}

코드를 살펴보면 노드가 가지는 정보를 설정하였는데 노드가 가질 수 있는 왼쪽, 오른쪽 자식 트리와 현재 노드의 높이, 값, BF를 저장할 수 있는 변수를 선언했다.

생성자를 통해서 노드가 만들어지면 루트 노드가 만들어지게 되는데 최초에는 높이를 1로 설정하였고 자식 노드가 만들어지기 전이여서 왼쪽, 오른쪽 자식 노드는 null로 설정했다. 그리고 루트 노드를 생성하면서 받는 데이터를 value에 저장해 주고, 현재 자식 노드가 없기 때문에 bf는 0으로 설정하였다.

 

AVL 클래스

AVL 클래스는 총 7개의 메서드로 구현해 봤다.

public AVLTree() {
    this.root = null;
}

public void add(int value) {
    if (root == null) {         // 처음 삽입되는 노드를 루트 노드로
        root = new Node(value);
    } else {                    // 다음으로 들어오는 노드는 루트 노드를 기준으로 삽입
        insert(root, value);
    }
}

먼저 AVL 트리가 만들어지면 root 노드를 null로 초기화를 해준다.

그다음에 노드가 들어오면 root 노드를 먼저 생성해 주고 만약 root 노드가 있다면 해당 노드를 기준으로 자식 노드를 생성하게 된다.

 

// TODO: 데이터 삽입 기능
    private Node insert(Node node, int value) {
        if (node == null) return new Node(value);   // 노드가 없을 때 노드를 추가해준다.

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

        // 현재 노드의 높이를 구한다.
        maxHeight(node);

        Integer bf = getBf(node);
        node.setBf(bf);

        if (bf > 1 && value < node.left.value) {        // LL Case
//            root = rightRotate(node);
//            return root;
            return rightRotate(node);
        }
        if (bf < -1 && value > node.right.value) {      // RR Case
//            root = rightRotate(node);
//            return root;
            return leftRotate(node);
        }
        if (bf > 1 && value > node.left.value) {        // LR Case
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        if (bf < -1 && value < node.right.value) {      // RL Case
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

데이터 삽입 기능에서 첫 번째로 살펴볼 부분은 root 노드의 value와 매개변수로 받은 value를 비교하여 왼쪽 혹은 오른쪽 자식 노드를 생성해 주는데 재귀를 통해서 노드의 자식 노드가 없을 경우 생성할 수 있게 구현하였다.

그다음 노드의 높이를 구하고 해당 높이를 가지고 BF 값을 구하여 저장해 준다.

앞에서 설명했던 AVL이 균형을 잡는 4가지 방법을 BF를 통해서 어떤 케이스인지 판별하고 우회전, 좌회전을 수행하게 된다.

 

// TODO: 우회전 기능
private Node rightRotate(Node parent) {
    // 노드 회전하기
    Node newParent = parent.left;
    Node rightSubTree = newParent.right;

    newParent.right = parent;
    parent.left = rightSubTree;

    // 새로운 높이 구하기
    maxHeight(parent);
    maxHeight(newParent);

    // 위치가 변경된 노드들의 BF값 새로 구하기
    Integer parentBf = getBf(parent);
    Integer newParentBf = getBf(newParent);
    parent.setBf(parentBf);
    newParent.setBf(newParentBf);

    return newParent;
}

// TODO: 좌회전 기능
private Node leftRotate(Node parent) {
    // 노드 회전하기
    Node newParent = parent.right;
    Node leftSubTree = newParent.left;

    newParent.left = parent;
    parent.right = leftSubTree;

    // 새로운 높이 구하기
    maxHeight(parent);
    maxHeight(newParent);
    
    // 위치가 변경된 노드들의 BF값 새로 구하기
    Integer parentBf = getBf(parent);
    Integer newParentBf = getBf(newParent);
    parent.setBf(parentBf);
    newParent.setBf(newParentBf);

    return newParent;
}

삽입 기능 다음으로 AVL 트리의 균형을 잡기 위한 좌회전, 우회전 기능을 구현하였는데 가장 중요한 기능이라고 생각한다.

우회전 기능을 설명해 보면 매개변수로 받은 노드의 왼쪽 자식 노드를 새로운 부모를 뜻하는 newParent 변수에 저장하고 새로운 부모가 기존에 가지고 있던 오른쪽 자식 노드를 rightSubTree 변수에 저장한다.

그 후 새로운 부모 노드의 오른쪽 자식 노드로 기존의 부모 노드를 저장하고 해당 부모 노드의 왼쪽 자식 노드로 rightSubTree를 저장한다.

위의 설명까지 코드가 진행되면 회전이 끝나게 되고 위치가 바뀐 노드들의 높이와 BF를 새롭게 구해준다.

좌회전 기능은 우회전 기능과 같아서 새로운 부모와 서브 트리를 저장하는 위치만 바뀌면 된다.

 

// TODO: 높이를 구하는 기능
private Integer getHeight(Node node) {
    if (node == null) return 0;
    return node.height;
}

// TODO: BF를 구하는 기능
private Integer getBf(Node node) {
    if (node == null) return 0;
    return getHeight(node.left) - getHeight(node.right);
}

// TODO: 높이를 구하는 기능
private void maxHeight(Node node) {
    if (getHeight(node.left) >= getHeight(node.right)) {
        node.height = getHeight(node.left) + 1;
    } else if (getHeight(node.right) >= getHeight(node.left)) {
        node.height = getHeight(node.right) + 1;
    }
}

 

 

마지막으로 살펴볼 메서드는 높이와 BF를 구하는 메서드이다.

먼저 getHeight 메서드는 매개변수로 받아온 노드에 대한 높이를 구해주는 메서드로 노드가 null이라면 아직 생성되지 않았기 때문에 높이로 0을 반환해 준다.

getBf 메서드는 매개변수로 받은 노드의 BF 값을 구해주는 기능으로 마찬가지로 노드가 null이라면 아직 생성되지 않았기 때문에 BF를 0으로 반환해 주고, 노드가 있다면 해당 노드의 왼쪽과 오른쪽 높이를 비교하여 그 차이를 반환해 준다.

마지막 maxHeight 메서드는 매개변수로 받은 노드의 왼쪽과 오른쪽 높이를 비교하여 해당 노드의 높이 값을 올려주는 기능이다.