비선형 자료 구조 심화 (AVL 트리, Red-Black 트리)

자료 구조에서 트리는 매우 중요한 비선형 구조입니다. 특히, 균형을 유지하는 이진 탐색 트리의 두 가지 형태인 AVL 트리와 Red-Black 트리는 효율적인 검색, 삽입, 삭제 연산을 가능하게 해줍니다. 이번 포스팅에서는 이 두 가지 트리에 대해 깊이 있는 설명을 제공하고, Java와 C로 구현하는 방법을 살펴보겠습니다.

AVL 트리

AVL 트리는 1962년에 Adelson-Velsky와 Landis에 의해 소개된 균형 이진 탐색 트리입니다. 모든 노드의 왼쪽과 오른쪽 서브트리 높이 차이가 최대 1을 유지하도록 설계되어, 항상 균형을 유지하는 것이 특징입니다. 이를 통해 삽입, 삭제, 검색 연산이 평균적으로 O(log N)의 시간 복잡도를 가집니다.

AVL 트리 특징

• 높이 균형: 각 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하입니다.
• 회전 연산: 불균형 상태가 되면, 단순 또는 이중 회전을 통해 트리의 균형을 맞춥니다.
• 높이 제한: 균형을 유지하기 때문에 트리의 높이는 O(log N)으로 유지됩니다.

AVL 트리의 연산

• 삽입 연산: 노드를 삽입한 후, 불균형 상태가 발생하면 이를 회전 연산으로 해결합니다.
• 삭제 연산: 노드를 삭제한 후에도 마찬가지로 균형을 유지하기 위해 회전 연산을 사용합니다.

Java로 AVL 트리 구현하기

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

    AVLNode(int key) {
        this.key = key;
        this.height = 1;
    }
}

class AVLTree {
    private AVLNode root;

    int height(AVLNode N) {
        return (N == null) ? 0 : N.height;
    }

    int getBalance(AVLNode N) {
        return (N == null) ? 0 : height(N.left) - height(N.right);
    }

    AVLNode rightRotate(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        return x;
    }

    AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y;
    }

    AVLNode insert(AVLNode node, int key) {
        if (node == null) return new AVLNode(key);

        if (key < node.key) node.left = insert(node.left, key);
        else if (key > node.key) node.right = insert(node.right, key);
        else return node;

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

        int balance = getBalance(node);

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

        return node;
    }

    void insert(int key) {
        root = insert(root, key);
    }
}

C로 AVL 트리 구현하기

#include <stdio.h>
#include <stdlib.h>

typedef struct AVLNode {
    int key;
    int height;
    struct AVLNode *left;
    struct AVLNode *right;
} AVLNode;

int height(AVLNode *N) {
    return (N == NULL) ? 0 : N->height;
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

AVLNode* newNode(int key) {
    AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
    node->key = key;
    node->height = 1;
    node->left = node->right = NULL;
    return node;
}

AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

AVLNode* leftRotate(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

int getBalance(AVLNode* N) {
    return (N == NULL) ? 0 : height(N->left) - height(N->right);
}

AVLNode* insert(AVLNode* node, int key) {
    if (node == NULL) return newNode(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;

    node->height = 1 + max(height(node->left), height(node->right));

    int balance = getBalance(node);

    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

Red-Black 트리

Red-Black 트리는 균형 잡힌 이진 탐색 트리의 또 다른 형태로, 삽입과 삭제 연산이 더 간단한 것이 특징입니다. 각 노드는 빨간색 또는 검은색을 가지며, 이러한 색 규칙을 통해 트리의 균형을 유지합니다.

Red-Black 트리의 특징

1. 각 노드는 빨간색 또는 검은색이다.
2. 루트 노드는 항상 검은색이다.
3. 모든 리프(NIL) 노드는 검은색이다.
4. 빨간색 노드의 자식은 항상 검은색이다 (즉, 빨간색 노드는 연속될 수 없다).
5. 임의의 노드에서 모든 리프에 이르는 경로에는 동일한 수의 검은색 노드가 존재한다.

이 규칙을 통해 트리는 항상 균형을 유지하며, 삽입 및 삭제의 시간 복잡도는 O(log N)으로 유지됩니다.

Red-Black 트리의 연산

• 삽입 연산: 새 노드를 빨간색으로 삽입하고, 위반된 규칙을 회전을 통해 수정합니다.
• 삭제 연산: 노드를 삭제한 후, 규칙 위반을 해결하기 위해 추가적인 회전을 수행합니다.

Java로 Red-Black 트리 구현하기

// Red-Black 트리의 Java 구현은 일반적으로 복잡합니다.
class RedBlackTree {

    private final int RED = 0;
    private final int BLACK = 1;

    class Node {
        int data, color;
        Node left, right, parent;

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

    private Node root = null;

    // Rotate left
    private void rotateLeft(Node node) {
        Node rightChild = node.right;
        node.right = rightChild.left;

        if (rightChild.left != null) {
            rightChild.left.parent = node;
        }
        rightChild.parent = node.parent;

        if (node.parent == null) {
            root = rightChild;
        } else if (node == node.parent.left) {
            node.parent.left = rightChild;
        } else {
            node.parent.right = rightChild;
        }
        rightChild.left = node;
        node.parent = rightChild;
    }

    // Rotate right
    private void rotateRight(Node node) {
        Node leftChild = node.left;
        node.left = leftChild.right;

        if (leftChild.right != null) {
            leftChild.right.parent = node;
        }
        leftChild.parent = node.parent;

        if (node.parent == null) {
            root = leftChild;
        } else if (node == node.parent.left) {
            node.parent.left = leftChild;
        } else {
            node.parent.right = leftChild;
        }
        leftChild.right = node;
        node.parent = leftChild;
    }

    // Fix violation after insertion
    private void fixInsert(Node node) {
        while (node.parent != null && node.parent.color == RED) {
            Node grandparent = node.parent.parent;
            if (node.parent == grandparent.left) {
                Node uncle = grandparent.right;
                if (uncle != null && uncle.color == RED) {
                    // Case 1: Uncle is red
                    grandparent.color = RED;
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node = grandparent;
                } else {
                    if (node == node.parent.right) {
                        // Case 2: Node is right child
                        node = node.parent;
                        rotateLeft(node);
                    }
                    // Case 3: Node is left child
                    node.parent.color = BLACK;
                    grandparent.color = RED;
                    rotateRight(grandparent);
                }
            } else {
                Node uncle = grandparent.left;
                if (uncle != null && uncle.color == RED) {
                    // Case 1: Uncle is red
                    grandparent.color = RED;
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node = grandparent;
                } else {
                    if (node == node.parent.left) {
                        // Case 2: Node is left child
                        node = node.parent;
                        rotateRight(node);
                    }
                    // Case 3: Node is right child
                    node.parent.color = BLACK;
                    grandparent.color = RED;
                    rotateLeft(grandparent);
                }
            }
        }
        root.color = BLACK;
    }

    // Insert a node
    public void insert(int data) {
        Node newNode = new Node(data);
        if (root == null) {
            root = newNode;
            root.color = BLACK;
            return;
        }

        Node current = root, parent = null;
        while (current != null) {
            parent = current;
            if (data < current.data) {
                current = current.left;
            } else if (data > current.data) {
                current = current.right;
            } else {
                return; // Duplicate keys not allowed
            }
        }

        newNode.parent = parent;
        if (data < parent.data) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }

        fixInsert(newNode);
    }

    // In-order traversal
    public void inOrderTraversal(Node node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.data + " ");
            inOrderTraversal(node.right);
        }
    }

    public void printTree() {
        inOrderTraversal(root);
        System.out.println();
    }

    public static void main(String[] args) {
        RedBlackTree rbt = new RedBlackTree();
        rbt.insert(10);
        rbt.insert(20);
        rbt.insert(30);
        rbt.insert(15);
        rbt.insert(25);
        rbt.insert(5);

        System.out.println("In-order traversal of the Red-Black Tree:");
        rbt.printTree();
    }
}

C로 Red-Black 트리 구현하기

// Red-Black 트리의 C 구현 또한 매우 복잡하며, 삽입 및 삭제 연산 시 다양한 색상 규칙과 회전을 고려해야 합니다.
#include <stdio.h>
#include <stdlib.h>

#define RED 0
#define BLACK 1

typedef struct Node {
    int data;
    int color;
    struct Node *left, *right, *parent;
} Node;

Node *root = NULL;

Node *createNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->color = RED;
    newNode->left = newNode->right = newNode->parent = NULL;
    return newNode;
}

void leftRotate(Node *x) {
    Node *y = x->right;
    x->right = y->left;
    if (y->left != NULL)
        y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == NULL)
        root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;
    x->parent = y;
}

void rightRotate(Node *x) {
    Node *y = x->left;
    x->left = y->right;
    if (y->right != NULL)
        y->right->parent = x;
    y->parent = x->parent;
    if (x->parent == NULL)
        root = y;
    else if (x == x->parent->right)
        x->parent->right = y;
    else
        x->parent->left = y;
    y->right = x;
    x->parent = y;
}

void fixInsert(Node *z) {
    while (z->parent != NULL && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            Node *y = z->parent->parent->right;
            if (y != NULL && y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(z->parent->parent);
            }
        } else {
            Node *y = z->parent->parent->left;
            if (y != NULL && y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rightRotate(z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(z->parent->parent);
            }
        }
    }
    root->color = BLACK;
}

void insert(int data) {
    Node *z = createNode(data);
    Node *y = NULL;
    Node *x = root;

    while (x != NULL) {
        y = x;
        if (z->data < x->data)
            x = x->left;
        else
            x = x->right;
    }

    z->parent = y;
    if (y == NULL)
        root = z;
    else if (z->data < y->data)
        y->left = z;
    else
        y->right = z;

    fixInsert(z);
}

void inorderTraversal(Node *node) {
    if (node == NULL)
        return;
    inorderTraversal(node->left);
    printf("%d ", node->data);
    inorderTraversal(node->right);
}

int main() {
    insert(10);
    insert(20);
    insert(30);
    insert(15);
    insert(25);
    insert(5);

    printf("Inorder Traversal of Created Tree:\n");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

결론

AVL 트리와 Red-Black 트리는 모두 균형 잡힌 이진 탐색 트리로, 효율적인 데이터 검색과 수정이 가능하도록 도와줍니다. AVL 트리는 더 엄격한 균형을 유지하여 검색 연산에 유리하지만, 삽입과 삭제 연산이 빈번한 경우 Red-Black 트리가 더 효율적일 수 있습니다. 상황에 맞는 트리 구조를 선택하여 프로그램의 성능을 최적화하는 것이 중요합니다.

이 글을 통해 AVL 트리와 Red-Black 트리에 대한 기본 개념과 Java, C로의 간단한 구현을 배울 수 있었기를 바랍니다. 각 트리의 특성을 이해하고, 언제 사용해야 할지를 명확히 하는 것이 중요합니다.