5강. 고급 데이터 구조

5. 고급 데이터 구조

---

5.1 AVL 트리와 레드-블랙 트리

AVL 트리(AVL Tree)
AVL 트리는 1962년 Georgy Adelson-Velsky와 Evgenii Landis에 의해 소개된 이진 탐색 트리로, 모든 노드의 균형을 유지하기 위해 각 노드의 왼쪽 서브트리와 오른쪽 서브트리 높이 차이가 최대 1이 되도록 유지합니다. 삽입 또는 삭제 후에 균형을 맞추기 위해 회전 연산을 수행합니다.

AVL 트리의 시간 복잡도:
- 삽입, 삭제, 검색: \(O(\log n)\)
트리의 높이가 \(O(\log n)\)이므로, 삽입, 삭제, 검색 모두 \(O(\log n)\) 시간이 소요됩니다.

// AVL 트리 예시 (간단한 노드 회전 예제 포함)
class AVLNode {
    int key, height;
    AVLNode left, right;

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

class AVLTree {
    AVLNode root;

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

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

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

    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 preOrder(AVLNode 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();

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

        System.out.println("Preorder traversal of constructed tree is : ");
        tree.preOrder(tree.root);
    }
}

 

레드-블랙 트리(Red-Black Tree)
레드-블랙 트리는 1972년 Rudolf Bayer에 의해 소개된 이진 탐색 트리로, 균형을 유지하기 위해 각 노드를 빨간색 또는 검은색으로 칠합니다. 레드-블랙 트리는 삽입, 삭제 후에도 트리의 균형을 유지하기 위한 규칙을 따릅니다.

레드-블랙 트리의 시간 복잡도:
- 삽입, 삭제, 검색: \(O(\log n)\)
트리의 높이가 \(O(\log n)\)이므로, 삽입, 삭제, 검색 모두 \(O(\log n)\) 시간이 소요됩니다.

// 레드-블랙 트리 예시 (간단한 삽입 예제 포함)
class RedBlackNode {
    int data;
    RedBlackNode left, right, parent;
    boolean color; // true for red, false for black

    RedBlackNode(int data) {
        this.data = data;
        this.color = true; // New nodes are initially red
    }
}

class RedBlackTree {
    private RedBlackNode root;
    private RedBlackNode TNULL;

    public RedBlackTree() {
        TNULL = new RedBlackNode(0);
        TNULL.color = false;
        TNULL.left = null;
        TNULL.right = null;
        root = TNULL;
    }

    private void preOrderHelper(RedBlackNode node) {
        if (node != TNULL) {
            System.out.print(node.data + " ");
            preOrderHelper(node.left);
            preOrderHelper(node.right);
        }
    }

    private void fixInsert(RedBlackNode k) {
        RedBlackNode u;
        while (k.parent.color == true) {
            if (k.parent == k.parent.parent.right) {
                u = k.parent.parent.left; 
                if (u.color == true) {
                    u.color = false;
                    k.parent.color = false;
                    k.parent.parent.color = true;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.left) {
                        k = k.parent;
                        rightRotate(k);
                    }
                    k.parent.color = false;
                    k.parent.parent.color = true;
                    leftRotate(k.parent.parent);
                }
            } else {
                u = k.parent.parent.right; 

                if (u.color == true) {
                    u.color = false;
                    k.parent.color = false;
                    k.parent.parent.color = true;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.right) {
                        k = k.parent;
                        leftRotate(k);
                    }
                    k.parent.color = false;
                    k.parent.parent.color = true;
                    rightRotate(k.parent.parent);
                }
            }
            if (k == root) {
                break;
            }
        }
        root.color = false;
    }

    private void leftRotate(RedBlackNode x) {
        RedBlackNode y = x.right;
        x.right = y.left;
        if (y.left != TNULL) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    private void rightRotate(RedBlackNode x) {
        RedBlackNode y = x.left;
        x.left = y.right;
        if (y.right != TNULL) {
            y.right.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.right) {
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }
        y.right = x;
        x.parent = y;
    }

    public void insert(int key) {
        RedBlackNode node = new RedBlackNode(key);
        node.parent = null;
        node.data = key;
        node.left = TNULL;
        node.right = TNULL;
        node.color = true; 

        RedBlackNode y = null;
        RedBlackNode x = this.root;

        while (x != TNULL) {
            y = x;
            if (node.data < x.data) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        node.parent = y;
        if (y == null) {
            root = node;
        } else if (node.data < y.data) {
            y.left = node;
        } else {
            y.right = node;
        }

        if (node.parent == null) {
            node.color = false;
            return;
        }

        if (node.parent.parent == null) {
            return;
        }

        fixInsert(node);
    }

    public void preorder() {
        preOrderHelper(this.root);
    }

    public static void main(String[] args) {
        RedBlackTree tree = new RedBlackTree();
        tree.insert(8);
        tree.insert(18);
        tree.insert(5);
        tree.insert(15);
        tree.insert(17);
        tree.insert(25);
        tree.insert(40);
        tree.insert(80);
        System.out.println("Preorder traversal of constructed tree is : ");
        tree.preorder();
    }
}

5.2 B-트리와 B+트리

B-트리(B-Tree)
B-트리는 1972년에 Rudolph Bayer와 Edward McCreight에 의해 소개된 트리 데이터 구조로, 자식 노드의 개수가 많고 노드의 분할과 병합이 자주 발생하는 트리입니다. B-트리는 데이터베이스와 파일 시스템에서 널리 사용됩니다.

B-트리의 시간 복잡도:
- 삽입, 삭제, 검색: \(O(\log n)\)
트리의 높이가 \(O(\log n)\)이므로, 삽입, 삭제, 검색 모두 \(O(\log n)\) 시간이 소요됩니다.

// B-트리 예시 (간단한 삽입 예제 포함)
class BTreeNode {
    int[] keys;
    int t;
    BTreeNode[] C;
    int n;
    boolean leaf;

    public BTreeNode(int t, boolean leaf) {
        this.t = t;
        this.leaf = leaf;
        this.keys = new int[2 * t - 1];
        this.C = new BTreeNode[2 * t];
        this.n = 0;
    }

    public void traverse() {
        int i;
        for (i = 0; i < this.n; i++) {
            if (!this.leaf) {
                C[i].traverse();
            }
            System.out.print(" " + this.keys[i]);
        }
        if (!this.leaf) {
            C[i].traverse();
        }
    }

    public BTreeNode search(int k) {
        int i = 0;
        while (i < n && k > keys[i]) {
            i++;
        }
        if (keys[i] == k) {
            return this;
        }
        if (leaf) {
            return null;
        }
        return C[i].search(k);
    }

    private void insertNonFull(int k) {
        int i = n - 1;
        if (leaf) {
            while (i >= 0 && keys[i] > k) {
                keys[i + 1] = keys[i];
                i--;
            }
            keys[i + 1] = k;
            n++;
        } else {
            while (i >= 0 && keys[i] > k) {
                i--;
            }
            if (C[i + 1].n == 2 * t - 1) {
                splitChild(i + 1, C[i + 1]);
                if (keys[i + 1] < k) {
                    i++;
                }
            }
            C[i + 1].insertNonFull(k);
        }
    }

    private void splitChild(int i, BTreeNode y) {
        BTreeNode z = new BTreeNode(y.t, y.leaf);
        z.n = t - 1;
        for (int j = 0; j < t - 1; j++) {
            z.keys[j] = y.keys[j + t];
        }
        if (!y.leaf) {
            for (int j = 0; j < t; j++) {
                z.C[j] = y.C[j + t];
            }
        }
        y.n = t - 1;
        for (int j = n; j >= i + 1; j--) {
            C[j + 1] = C[j];
        }
        C[i + 1] = z;
        for (int j = n - 1; j >= i; j--) {
            keys[j + 1] = keys[j];
        }
        keys[i] = y.keys[t - 1];
        n++;
    }
}

class BTree {
    BTreeNode root;
    int t;

    public BTree(int t) {
        this.root = null;
        this.t = t;
    }

    public void traverse() {
        if (root != null) {
            root.traverse();
        }
    }

    public BTreeNode search(int k) {
        if (root == null) {
            return null;
        } else {
            return root.search(k);
        }
    }

    public void insert(int k) {
        if (root == null) {
            root = new BTreeNode(t, true);
            root.keys[0] = k;
            root.n = 1;
        } else {
            if (root.n == 2 * t - 1) {
                BTreeNode s = new BTreeNode(t, false);
                s.C[0] = root;
                s.splitChild(0, root);
                int i = 0;
                if (s.keys[0] < k) {
                    i++;
                }
                s.C[i].insertNonFull(k);
                root = s;
            } else {
                root.insertNonFull(k);
            }
        }
    }

    public static void main(String[] args) {
        BTree t = new BTree(3);
        t.insert(10);
        t.insert(20);
        t.insert(5);
        t.insert(6);
        t.insert(12);
        t.insert(30);
        t.insert(7);
        t.insert(17);

        System.out.println("Traversal of the constructed tree is ");
        t.traverse();
    }
}

 

B+트리(B+Tree)
B+트리는 B-트리의 확장 버전으로, 데이터베이스와 파일 시스템에서 더 효율적으로 사용됩니다. B+트리는 모든 값이 리프 노드에 저장되며, 리프 노드가 양방향으로 연결된 구조입니다.

B+트리의 시간 복잡도:
- 삽입, 삭제, 검색: \(O(\log n)\)
트리의 높이가 \(O(\log n)\)이므로, 삽입, 삭제, 검색 모두 \(O(\log n)\) 시간이 소요됩니다.

5.3 우선순위 큐와 힙

우선순위 큐(Priority Queue)
우선순위 큐는 각 요소가 우선순위를 가지며, 높은 우선순위를 가진 요소가 먼저 처리되는 큐입니다. 힙은 우선순위 큐를 구현하는데 가장 많이 사용되는 자료구조입니다.

우선순위 큐의 시간 복잡도:
- 삽입: \(O(\log n)\)
- 삭제: \(O(\log n)\)
힙을 사용하여 구현하면 삽입과 삭제 모두 \(O(\log n)\)의 시간이 소요됩니다.

// 우선순위 큐와 힙 예시
import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue<>();
        pq.add(10);
        pq.add(20);
        pq.add(15);

        System.out.println("Priority Queue elements:");
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 우선순위가 높은 요소부터 출력
        }
    }
}

5.4 유니온-파인드 구조

유니온-파인드 구조(Union-Find Structure)
유니온-파인드 구조는 상호 배타적 집합을 관리하는 자료구조로, 서로 다른 집합을 합치고(Union), 특정 요소가 속한 집합을 찾는(Find) 연산을 효율적으로 수행합니다. 유니온-파인드 구조는 그래프에서 사이클을 감지하거나, 서로 연결된 구성 요소를 찾는 데 유용하게 사용됩니다.

유니온-파인드 구조의 시간 복잡도:
- 유니온 연산: \(O(\log n)\)
- 파인드 연산: \(O(\log n)\)
경로 압축(Path Compression)과 유니온 바이 랭크(Union by Rank)를 사용하면 거의 상수 시간에 가까운 성능을 얻을 수 있습니다.

// 유니온-파인드 구조 예시
class UnionFind {
    private int[] parent, rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 경로 압축
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    public static void main(String[] args) {
        UnionFind uf = new UnionFind(10);
        uf.union(1, 2);
        uf.union(2, 3);
        uf.union(4, 5);
        uf.union(6, 7);
        uf.union(5, 6);
        uf.union(3, 7);

        System.out.println("Find(1): " + uf.find(1)); // 출력: 1
        System.out.println("Find(5): " + uf.find(5)); // 출력: 4
        System.out.println("Find(7): " + uf.find(7)); // 출력: 4
    }
}

---

해시태그: #알고리즘 #Algorithm #프로그래밍 #Programming #컴퓨터과학 #ComputerScience #코딩 #Coding #고급데이터구조 #AdvancedDataStructures #AVL트리 #AVLTree #레드블랙트리 #RedBlackTree #B트리 #BTree #B플러스트리 #BPlusTree #우선순위큐 #PriorityQueue #힙 #Heap #유니온파인드 #UnionFind #Java #자바 #코딩공부 #개발자 #Developer