[자료구조] AVL 트리

AVL 트리란?

균형 이진 탐색 트리 (BST)의 한 종류로, 각 노드의 균형을 유지하여 탐색, 삽입, 삭제 연산을 O(log N) 시간에 수행할 수 있는 자료구조

 

균형 이진 탐색 트리이기 때문에 각 노드의 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 -1, 0, 1 사이로 유지된다.

트리가 한쪽으로 치우치는 것을 방지하여 탐색, 삽입, 삭제 연산의 성능을 보장한다.

 

• BF = (왼쪽 서브트리의 높이 - 오른쪽 서브 트리의 높이)의 절댓값
• 모든 노드의 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
• BF가 2 이상이 되면 회전을 통해 균형을 잡는다.

AVL 트리

---

AVL 트리 연산, 시간 복잡도

삽입, 삭제 모두 일반적인 BST 삽입, 삭제를 수행한다.

삽입, 삭제 후 BF를 계산하고, BF가 -1, 0, 1 범위를 벗어나면 회전을 수행한다.

 

삽입 : O(log N)

삭제 : O(log N)

탐색 : O(log N)

 

=> AVL 트리는 항상 균형을 유지하므로, 최악의 경우에도 O(log N)을 보장

 

---

AVL 트리 회전

1. LL 회전

• 삽입 노드가 왼쪽-왼쪽(LL) 구조를 만들 때 발생
• 오른쪽으로 회전 수행

    30
   /
  20
 /
10

 

회전 후

   20
  /  \
 10   30

 

2. RR 회전

• 삽입 노드가 오른쪽-오른쪽(RR) 구조를 만들 때 발생
• 왼쪽으로 회전 수행

 10
   \
    20
      \
       30

 

회전 후

   20
  /  \
 10   30

 

3. LR 회전

• 삽입 노드가 왼쪽-오른쪽(LR) 구조를 만들 때 발생
• 왼쪽으로 회전 후 오른쪽으로 회전 수행

    30
   /
  10
    \
     20

 

왼쪽으로 회전 후

    30
   /
  20
 /
10

 

오른쪽으로 회전 후 

   20
  /  \
 10   30

 

4. RL 회전

• 삽입 노드가 오른쪽-왼쪽(RL) 구조를 만들 때 발생
• 오른쪽으로 회전 후 왼쪽으로 회전 수행

 10
   \
    30
   /
  20

 

오른쪽으로 회전 후

 10
   \
    20
      \
       30

 

왼쪽으로 회전 

   20
  /  \
 10   30

 

 

 

---

AVL 트리 구현

 

AVL Node

package avl;

import bst.TreePrinter;

public class AVLNode implements TreePrinter.PrintableNode {
    Integer data;
    AVLNode left;
    AVLNode right;
    int height;

    public AVLNode(Integer data) {
        this.data = data;
        height = 0;
    }

    // 트리 출력
    @Override
    public TreePrinter.PrintableNode getLeft() {
        return left;
    }

    @Override
    public TreePrinter.PrintableNode getRight() {
        return right;
    }

    @Override
    public String getText() {
        return "["+data+"]";
    }
}

 

 

AVL Tree

package avl;

public class AVLTree {
    AVLNode root;

    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);
    }

    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;
    }

    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);

        if (balance > 1 && data < node.left.data)
            return rightRotate(node);

        if (balance < -1 && data > node.right.data) {
            return leftRotate(node);
        }

        if (balance > 1 && node.left.data < data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        if (balance < -1 && data < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }
}

 

 

AVL Main

package avl;

import bst.TreePrinter;

public class AVLMain {
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        // 87 26 34 78 90
        tree.insert(87);
        tree.insert(26);
        tree.insert(34);
        tree.insert(78);
        tree.insert(90);
        TreePrinter.print(tree.root);
        System.out.println();
        System.out.println();
        System.out.println();
        System.out.println();

        tree.insert(42);
        TreePrinter.print(tree.root);

    }
}

 

 

82, 26, 34, 78, 90 삽입

 87 26 34 78 90

 

 

42 삽입