트리 | 균형 이진 탐색 트리

균형 이진 탐색 트리

균형 이진 탐색 트리(Balanced Binary Search Tree)는 이진 탐색 트리(Binary Search Tree, BST)의 일종으로, 각 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 특정 기준 이하로 유지되도록 하여 트리의 균형을 맞추는 데이터 구조입니다. 이 균형을 통해 트리의 깊이를 최소화하여 탐색, 삽입, 삭제 연산에서 최악의 경우 시간 복잡도를 O(log n)으로 보장합니다.

일반적인 이진 탐색 트리에서 노드가 한쪽으로 치우친 경우, 탐색 시간이 최악의 경우 O(n)이 될 수 있습니다. 이를 방지하기 위해 균형을 맞추는 기법이 필요한데, 균형 이진 탐색 트리에서는 트리의 높이가 가능한 한 작고 균형 있게 유지되도록 노드들의 삽입과 삭제를 수행합니다.

 

대표적인 균형 이진 탐색 트리의 종류는 다음과 같습니다:

1. AVL 트리

• AVL(Adelson-Velsky and Landis) 트리는 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1을 유지하도록 하는 이진 탐색 트리입니다.
• 삽입 및 삭제 연산 후 트리의 균형을 유지하기 위해 필요한 경우 트리의 회전 연산(단일 회전 또는 이중 회전)을 수행합니다.
• 시간 복잡도:
  • 탐색, 삽입, 삭제: O(log n)

2. 레드-블랙 트리

• 레드-블랙 트리는 모든 노드가 '빨강' 또는 '검정' 색을 가지며, 특정 규칙을 따라 트리의 균형을 유지하는 이진 탐색 트리입니다.
• 레드-블랙 트리는 AVL 트리보다 조금 더 유연하게 균형을 유지하여 삽입과 삭제의 성능이 더 나은 경우가 많습니다.
• 트리의 높이가 항상 2 * log(n) 이내로 유지되므로 균형 상태를 어느 정도 보장하면서도 삽입, 삭제 연산의 부담이 적습니다.
• 시간 복잡도:
  • 탐색, 삽입, 삭제: O(log n)

3. 2-3 트리

• 2-3 트리는 각 노드가 2개 또는 3개의 자식 노드를 가질 수 있는 트리입니다.
• 모든 리프 노드의 깊이가 동일하게 유지되어 트리가 항상 균형을 이루게 됩니다.
• 레드-블랙 트리는 2-3 트리의 변형 형태라고 볼 수 있습니다.

균형 이진 탐색 트리의 장점

• 빠른 검색: 트리의 높이가 O(log n)으로 제한되기 때문에, 탐색, 삽입, 삭제 연산을 평균적으로 효율적으로 수행할 수 있습니다.
• 자동 균형 유지: 삽입 및 삭제 연산 이후에도 트리가 자동으로 균형을 유지하여 최악의 경우에도 일정한 성능을 보장합니다.

균형 이진 탐색 트리의 단점

• 구현 복잡도: 균형을 유지하기 위해 삽입과 삭제 연산 시 회전이나 색 변경 등 추가 작업이 필요하므로 일반적인 이진 탐색 트리에 비해 구현이 복잡합니다.
• 삽입/삭제 비용: 균형을 유지하기 위한 추가 작업으로 인해 삽입과 삭제 연산의 비용이 증가할 수 있습니다. 하지만 평균적인 탐색 시간은 보장됩니다.

회전 연산

균형을 맞추기 위해 사용되는 회전 연산(Rotation) 은 트리의 형태를 바꾸지 않고도 트리의 균형을 맞출 수 있는 중요한 연산입니다. 회전 연산에는 크게 단일 회전(Single Rotation) 과 이중 회전(Double Rotation) 이 있습니다. 이 연산들은 AVL 트리나 레드-블랙 트리와 같은 구조에서 삽입 또는 삭제 후 균형을 맞출 때 자주 사용됩니다.

균형 이진 탐색 트리는 데이터가 자주 삽입되고 삭제되면서 검색 속도가 중요한 경우에 유용합니다. 예를 들어, 데이터베이스 인덱스나 파일 시스템의 디렉터리 구조와 같은 곳에서 널리 사용됩니다.

 

자바 구현 코드

class Node {
    int key;
    int height;
    Node left, right;

    Node(int d) {
        key = d;
        height = 1;
    }
}

public class AVLTree {
    Node root;

    // A utility function to get the height of the tree
    int height(Node N) {
        if (N == null)
            return 0;
        return N.height;
    }

    // A utility function to get maximum of two integers
    int max(int a, int b) {
        return (a > b) ? a : b;
    }

    // A utility function to right rotate subtree rooted with y
    Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        // Perform rotation
        x.right = y;
        y.left = T2;

        // Update heights
        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        // Return new root
        return x;
    }

    // A utility function to left rotate subtree rooted with x
    Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        // Perform rotation
        y.left = x;
        x.right = T2;

        // Update heights
        x.height = max(height(x.left), height(x.right)) + 1;
        y.height = max(height(y.left), height(y.right)) + 1;

        // Return new root
        return y;
    }

    // Get Balance factor of node N
    int getBalance(Node N) {
        if (N == null)
            return 0;
        return height(N.left) - height(N.right);
    }

    Node insert(Node node, int key) {
        // 1. Perform the normal BST insertion
        if (node == null)
            return (new Node(key));

        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else // Duplicate keys not allowed
            return node;

        // 2. Update height of this ancestor node
        node.height = 1 + max(height(node.left), height(node.right));

        // 3. Get the balance factor of this ancestor node to check whether
        //    this node became unbalanced
        int balance = getBalance(node);

        // If this node becomes unbalanced, then there are 4 cases

        // Left Left Case
        if (balance > 1 && key < node.left.key)
            return rightRotate(node);

        // Right Right Case
        if (balance < -1 && key > node.right.key)
            return leftRotate(node);

        // Left Right Case
        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Left Case
        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        // return the (unchanged) node pointer
        return node;
    }

    // A utility function to print preorder traversal of the tree.
    // The function also prints height of every node
    void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.key + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        /* Constructing tree given in the above figure */
        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 20);
        tree.root = tree.insert(tree.root, 30);
        tree.root = tree.insert(tree.root, 40);
        tree.root = tree.insert(tree.root, 50);
        tree.root = tree.insert(tree.root, 25);

        /* The constructed AVL Tree would be
             30
            /  \
           20   40
          /  \     \
         10  25    50
        */
        System.out.println("Preorder traversal of constructed tree is : ");
        tree.preOrder(tree.root);
    }
}