트리(Tree) 자료구조의 확장인 AVL 트리와 레드-블랙 트리

728x90

AVL 트리(AVL Tree)와 레드-블랙 트리(Red-Black Tree)는 이진 탐색 트리(Binary Search Tree, BST)의 균형을 유지하여 검색, 삽입, 삭제 연산의 성능을 보장하는 균형 이진 탐색 트리(Balanced Binary Search Tree)의 대표적인 예입니다. AVL 트리는 모든 노드의 서브트리 높이 차이가 1 이하로 유지되도록 설계되었으며, 레드-블랙 트리는 색상을 이용하여 균형을 유지합니다. 이러한 균형 트리는 최악의 경우에도 O(log n)의 시간 복잡도로 연산을 수행할 수 있게 합니다.

AVL 트리와 레드-블랙 트리의 등장 배경

기본 이진 탐색 트리는 특정 입력 순서에 따라 편향될 수 있어, 최악의 경우 O(n) 시간 복잡도를 가질 수 있습니다. 이를 해결하기 위해 트리의 균형을 유지하는 방법들이 개발되었으며, 그 중 AVL 트리와 레드-블랙 트리가 널리 사용됩니다. AVL 트리는 보다 엄격한 균형을 유지하여 검색이 매우 빠르지만, 삽입과 삭제 시 회전 연산이 자주 필요합니다. 반면, 레드-블랙 트리는 균형을 약간 느슨하게 유지하면서도 삽입과 삭제 시 회전 연산의 빈도를 줄여 전체적인 성능을 향상시킵니다.

AVL 트리와 레드-블랙 트리는 데이터베이스 인덱스, 파일 시스템, 메모리 관리, 네트워크 라우팅 등 다양한 실무 분야에서 핵심적인 역할을 합니다. 이 자료구조들은 대규모 데이터 처리와 빠른 검색이 요구되는 시스템에서 높은 효율성을 제공합니다.

균형 이진 탐색 트리(Balanced Binary Search Tree)의 개념

균형 이진 탐색 트리는 이진 탐색 트리의 한 종류로, 트리의 높이를 최소화하여 모든 연산의 시간 복잡도를 O(log n)으로 유지하는 자료구조입니다. AVL 트리와 레드-블랙 트리는 이러한 균형을 유지하는 두 가지 주요 방법을 제공합니다.

균형 이진 탐색 트리의 특징

높이 균형: 트리의 높이를 최소화하여 연산의 효율성을 보장합니다.
회전 연산: 삽입과 삭제 시 트리의 균형을 유지하기 위해 회전 연산을 수행합니다.
색상 속성 (레드-블랙 트리의 경우): 노드에 색상을 부여하여 트리의 균형을 유지합니다.

AVL 트리와 레드-블랙 트리의 차이점

균형의 엄격성: AVL 트리는 서브트리 높이 차이가 1 이하로 매우 엄격하게 균형을 유지하는 반면, 레드-블랙 트리는 색상 규칙을 통해 서브트리 높이 차이를 완화시켜 균형을 유지합니다.
회전 연산의 빈도: AVL 트리는 회전 연산이 자주 발생할 수 있지만, 레드-블랙 트리는 회전 연산의 빈도가 상대적으로 낮습니다.
검색 성능: AVL 트리는 보다 엄격한 균형을 유지하여 검색 성능이 약간 더 우수할 수 있습니다.

AVL 트리(AVL Tree)의 개념

AVL 트리는 Adelson-Velsky and Landis에 의해 고안된 균형 이진 탐색 트리로, 모든 노드의 서브트리 높이 차이가 1 이하로 유지되도록 설계되었습니다. 이는 트리의 균형을 유지함으로써 최악의 경우에도 O(log n)의 시간 복잡도를 보장합니다.

AVL 트리의 특징

높이 균형: 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1입니다.
회전 연산: 삽입과 삭제 후 균형을 맞추기 위해 단일 회전(Single Rotation)이나 이중 회전(Double Rotation)을 수행합니다.
빠른 검색: 엄격한 균형 유지로 인해 검색 연산이 매우 빠릅니다.

AVL 트리의 회전 유형

LL 회전: 왼쪽 자식의 왼쪽 서브트리에 삽입된 경우 단일 오른쪽 회전.
RR 회전: 오른쪽 자식의 오른쪽 서브트리에 삽입된 경우 단일 왼쪽 회전.
LR 회전: 왼쪽 자식의 오른쪽 서브트리에 삽입된 경우 왼쪽 자식에 대해 왼쪽 회전 후, 루트에 대해 오른쪽 회전.
RL 회전: 오른쪽 자식의 왼쪽 서브트리에 삽입된 경우 오른쪽 자식에 대해 오른쪽 회전 후, 루트에 대해 왼쪽 회전.

레드-블랙 트리(Red-Black Tree)의 개념

레드-블랙 트리는 색상을 사용하여 트리의 균형을 유지하는 자료구조입니다. 각 노드는 레드(Red) 또는 블랙(Black)으로 색칠되어 있으며, 특정 규칙을 통해 트리의 균형을 유지합니다. 이는 삽입과 삭제 시 색상 변경과 회전 연산을 통해 트리의 균형을 유지합니다.

레드-블랙 트리의 특징

색상 속성: 각 노드는 레드 또는 블랙으로 색칠됩니다.
루트 노드는 항상 블랙입니다.
레드 노드의 자식은 항상 블랙입니다. (레드 노드 연속 금지)
모든 경로에서 블랙 노드의 수는 동일합니다.
새로 삽입된 노드는 레드입니다.

레드-블랙 트리의 균형 유지

삽입: 새로운 노드를 삽입한 후, 색상 규칙을 위반할 경우 색상 변경과 회전 연산을 통해 균형을 회복합니다.
삭제: 노드를 삭제한 후, 색상 규칙을 위반할 경우 색상 변경과 회전 연산을 통해 균형을 회복합니다.

AVL 트리와 레드-블랙 트리 구현하기

Python으로 AVL 트리 구현하기

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1  # 노드의 높이

class AVLTree:
    def __init__(self):
        self.root = None

    # 노드의 높이를 반환
    def get_height(self, node):
        if not node:
            return 0
        return node.height

    # 노드의 균형 인수를 반환
    def get_balance(self, node):
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    # 오른쪽 회전
    def right_rotate(self, y):
        x = y.left
        T2 = x.right

        # 회전 수행
        x.right = y
        y.left = T2

        # 높이 업데이트
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))

        # 새로운 루트 반환
        return x

    # 왼쪽 회전
    def left_rotate(self, x):
        y = x.right
        T2 = y.left

        # 회전 수행
        y.left = x
        x.right = T2

        # 높이 업데이트
        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        # 새로운 루트 반환
        return y

    # 노드를 삽입
    def insert(self, key):
        self.root = self._insert_rec(self.root, key)

    def _insert_rec(self, node, key):
        # 일반적인 BST 삽입
        if not node:
            return AVLNode(key)
        elif key < node.key:
            node.left = self._insert_rec(node.left, key)
        elif key > node.key:
            node.right = self._insert_rec(node.right, key)
        else:
            return node  # 중복 키는 무시

        # 노드의 높이 업데이트
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

        # 균형 인수 계산
        balance = self.get_balance(node)

        # 불균형 경우 회전 수행

        # LL 케이스
        if balance > 1 and key < node.left.key:
            return self.right_rotate(node)

        # RR 케이스
        if balance < -1 and key > node.right.key:
            return self.left_rotate(node)

        # LR 케이스
        if balance > 1 and key > node.left.key:
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)

        # RL 케이스
        if balance < -1 and key < node.right.key:
            node.right = self.right_rotate(node.right)
            return self.left_rotate(node)

        return node

    # 노드를 삭제
    def delete(self, key):
        self.root = self._delete_rec(self.root, key)

    def _delete_rec(self, node, key):
        # 일반적인 BST 삭제
        if not node:
            return node
        elif key < node.key:
            node.left = self._delete_rec(node.left, key)
        elif key > node.key:
            node.right = self._delete_rec(node.right, key)
        else:
            # 노드가 하나 또는 자식이 없는 경우
            if not node.left:
                temp = node.right
                node = None
                return temp
            elif not node.right:
                temp = node.left
                node = None
                return temp
            # 노드가 두 개의 자식을 가진 경우
            temp = self.get_min_value_node(node.right)
            node.key = temp.key
            node.right = self._delete_rec(node.right, temp.key)

        if not node:
            return node

        # 노드의 높이 업데이트
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

        # 균형 인수 계산
        balance = self.get_balance(node)

        # 불균형 경우 회전 수행

        # LL 케이스
        if balance > 1 and self.get_balance(node.left) >= 0:
            return self.right_rotate(node)

        # LR 케이스
        if balance > 1 and self.get_balance(node.left) < 0:
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)

        # RR 케이스
        if balance < -1 and self.get_balance(node.right) <= 0:
            return self.left_rotate(node)

        # RL 케이스
        if balance < -1 and self.get_balance(node.right) > 0:
            node.right = self.right_rotate(node.right)
            return self.left_rotate(node)

        return node

    # 최소값 노드 찾기
    def get_min_value_node(self, node):
        current = node
        while current.left:
            current = current.left
        return current

    # 중위 순회
    def inorder_traversal(self):
        res = []
        self._inorder_rec(self.root, res)
        return res

    def _inorder_rec(self, node, res):
        if node:
            self._inorder_rec(node.left, res)
            res.append(node.key)
            self._inorder_rec(node.right, res)

    # 트리 출력
    def display(self):
        levels = []
        self._display_rec(self.root, 0, levels)
        for i, level in enumerate(levels):
            print(f"Level {i}: {level}")

    def _display_rec(self, node, depth, levels):
        if node:
            if len(levels) <= depth:
                levels.append([])
            levels[depth].append(node.key)
            self._display_rec(node.left, depth + 1, levels)
            self._display_rec(node.right, depth + 1, levels)

# AVL 트리 사용 예시
if __name__ == "__main__":
    avl = AVLTree()
    elements = [10, 20, 30, 40, 50, 25]
    for el in elements:
        avl.insert(el)
    print("Inorder Traversal:", avl.inorder_traversal())  # 출력: [10, 20, 25, 30, 40, 50]
    avl.display()
    # 출력:
    # Level 0: [30]
    # Level 1: [20, 40]
    # Level 2: [10, 25, 50]

    avl.delete(30)
    print("Inorder Traversal after deleting 30:", avl.inorder_traversal())  # 출력: [10, 20, 25, 40, 50]
    avl.display()
    # 출력:
    # Level 0: [25]
    # Level 1: [20, 40]
    # Level 2: [10, 50]

코드 설명

AVLNode 클래스:
- init 메서드:
  - 각 노드가 가지는 속성을 초기화합니다.
  - key: 노드의 값.
  - left, right: 왼쪽 자식 노드와 오른쪽 자식 노드.
  - height: 노드의 높이 (초기값은 1).
AVLTree 클래스:
- init 메서드:
  - 트리의 루트 노드를 초기화합니다 (None).
- get_height 메서드:
  - 주어진 노드의 높이를 반환합니다. 노드가 None이면 0을 반환합니다.
- get_balance 메서드:
  - 주어진 노드의 균형 인수를 계산합니다. 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값.
- right_rotate 메서드:
  - 오른쪽 회전을 수행하여 트리의 균형을 맞춥니다.
  - 회전 후 노드들의 높이를 업데이트하고, 새로운 루트 노드를 반환합니다.
- left_rotate 메서드:
  - 왼쪽 회전을 수행하여 트리의 균형을 맞춥니다.
  - 회전 후 노드들의 높이를 업데이트하고, 새로운 루트 노드를 반환합니다.
- insert 메서드:
  - 새로운 키를 트리에 삽입합니다.
  - _insert_rec 메서드를 호출하여 재귀적으로 노드를 삽입하고, 필요한 경우 회전 연산을 수행합니다.
- _insert_rec 메서드:
  - 재귀적으로 트리를 탐색하여 새로운 키를 삽입할 위치를 찾습니다.
  - 삽입 후 노드의 높이를 업데이트하고, 균형 인수를 계산하여 불균형 시 회전 연산을 수행합니다.
- delete 메서드:
  - 특정 키를 가진 노드를 트리에서 삭제합니다.
  - _delete_rec 메서드를 호출하여 재귀적으로 노드를 삭제하고, 필요한 경우 회전 연산을 수행합니다.
- _delete_rec 메서드:
  - 재귀적으로 트리를 탐색하여 특정 키를 가진 노드를 삭제합니다.
  - 삭제 후 노드의 높이를 업데이트하고, 균형 인수를 계산하여 불균형 시 회전 연산을 수행합니다.
- get_min_value_node 메서드:
  - 주어진 노드의 서브트리에서 가장 작은 값을 가진 노드를 찾습니다.
- inorder_traversal 메서드:
  - 트리를 중위 순회하여 정렬된 키들의 리스트를 반환합니다.
- display 메서드:
  - 트리의 구조를 레벨별로 출력합니다.
사용 예시:
- AVL 트리에 여러 요소를 삽입하고, 중위 순회를 통해 정렬된 순서대로 요소를 확인합니다.
- 트리의 구조를 레벨별로 출력하여 균형이 유지되고 있는지 확인합니다.
- 특정 키를 삭제한 후, 트리의 구조와 중위 순회 결과를 다시 확인합니다.

AVL 트리와 레드-블랙 트리의 응용 예제

데이터베이스 인덱스 관리

데이터베이스는 대량의 데이터를 효율적으로 검색하기 위해 인덱스를 사용합니다. 인덱스는 이진 탐색 트리나 레드-블랙 트리를 기반으로 하여 특정 열의 값을 키로 사용하고, 해당 키에 대한 데이터의 위치를 값으로 저장합니다.

class Database:
    def __init__(self):
        self.records = []
        self.index = AVLTree()

    def add_record(self, record):
        self.records.append(record)
        record_id = len(self.records) - 1
        self.index.insert(record['id'])

    def get_record_by_id(self, id):
        # AVL 트리에서 id를 검색하여 해당 레코드의 인덱스를 찾음
        inorder = self.index.inorder_traversal()
        if id in inorder:
            return self.records[id]
        return None

# 사용 예시
if __name__ == "__main__":
    db = Database()
    db.add_record({'id': 1, 'name': 'Alice'})
    db.add_record({'id': 2, 'name': 'Bob'})
    db.add_record({'id': 3, 'name': 'Charlie'})

    print(db.get_record_by_id(2))  # 출력: {'id': 2, 'name': 'Bob'}

코드 설명

Database 클래스:
- init 메서드:
  - records: 데이터베이스 레코드를 저장하는 리스트.
  - index: AVL 트리를 사용하여 레코드의 'id'를 인덱싱.
- add_record 메서드:
  - 새로운 레코드를 records 리스트에 추가.
  - 레코드의 'id'를 AVL 트리에 삽입하여 인덱스를 구축.
- get_record_by_id 메서드:
  - AVL 트리를 중위 순회하여 'id'가 존재하는지 확인.
  - 'id'가 존재하면 해당 레코드를 반환, 그렇지 않으면 None 반환.
사용 예시:
- 데이터베이스에 세 개의 레코드를 추가하고, 'id'가 2인 레코드를 검색하여 출력.

레드-블랙 트리 응용 예제

우선순위 큐(Priority Queue) 구현

레드-블랙 트리는 우선순위 큐의 구현에 이상적인 자료구조로, 힙과 유사하게 우선순위에 따라 데이터를 관리할 수 있습니다. 레드-블랙 트리를 사용하면 동적 삽입과 삭제가 용이하며, 균형을 유지하여 검색 성능을 보장합니다.

class PriorityQueue {
    constructor() {
        this.rbTree = new RedBlackTree();
    }

    enqueue(key) {
        this.rbTree.insert(key);
    }

    dequeue() {
        // 레드-블랙 트리에서 가장 큰 키(우선순위가 높은)를 찾아 삭제
        let current = this.rbTree.root;
        if (current === this.rbTree.NIL) {
            throw new Error("PriorityQueue is empty");
        }
        while (current.right !== this.rbTree.NIL) {
            current = current.right;
        }
        let maxKey = current.key;
        this.rbTree.delete(maxKey);
        return maxKey;
    }

    peek() {
        let current = this.rbTree.root;
        if (current === this.rbTree.NIL) {
            throw new Error("PriorityQueue is empty");
        }
        while (current.right !== this.rbTree.NIL) {
            current = current.right;
        }
        return current.key;
    }

    isEmpty() {
        return this.rbTree.root === this.rbTree.NIL;
    }

    size() {
        // 중위 순회를 통해 크기를 계산
        return this.rbTree.inorderTraversal().length;
    }

    display() {
        this.rbTree.display();
    }
}

// 우선순위 큐 사용 예시
const pq = new PriorityQueue();
pq.enqueue(10);
pq.enqueue(5);
pq.enqueue(15);
pq.enqueue(20);
pq.enqueue(0);

console.log("Priority Queue:", pq.rbTree.inorderTraversal()); // 출력: [0, 5, 10, 15, 20]

console.log("Peek:", pq.peek()); // 출력: 20
console.log("Dequeue:", pq.dequeue()); // 출력: 20
console.log("Priority Queue after dequeue:", pq.rbTree.inorderTraversal()); // 출력: [0, 5, 10, 15]

console.log("Size:", pq.size()); // 출력: 4
console.log("Is Empty:", pq.isEmpty()); // 출력: false

코드 설명

PriorityQueue 클래스:
- constructor 메서드:
  - rbTree: 레드-블랙 트리를 사용하여 우선순위 큐를 구현.
- enqueue 메서드:
  - 새로운 키를 우선순위 큐에 삽입하기 위해 레드-블랙 트리에 추가.
- dequeue 메서드:
  - 레드-블랙 트리에서 가장 큰 키(우선순위가 높은)를 찾아 삭제하고 반환.
- peek 메서드:
  - 우선순위가 가장 높은 키를 찾아 반환.
- isEmpty, size, display 메서드:
  - 큐의 상태를 확인하고, 현재 트리의 상태를 출력.
사용 예시:
- 우선순위 큐에 여러 키를 삽입하고, 가장 높은 우선순위를 가진 키를 추출한 후 큐의 상태를 출력.
- 큐의 크기와 비어있는지 여부를 확인.

AVL 트리와 레드-블랙 트리의 장단점

AVL 트리의 장점

높은 검색 성능: 엄격한 균형 유지로 인해 검색 연산이 매우 빠릅니다.
높은 데이터 접근성: 트리의 높이가 낮아 데이터 접근이 용이합니다.
단일 회전으로 균형 유지: 일부 케이스에서는 단일 회전으로 균형을 유지할 수 있어 효율적입니다.

AVL 트리의 단점

삽입 및 삭제의 복잡성: 균형을 유지하기 위해 삽입과 삭제 시 회전 연산이 자주 필요할 수 있습니다.
구현의 복잡성: 레드-블랙 트리에 비해 구현이 다소 복잡합니다.
높은 회전 빈도: 특히 데이터가 정렬된 형태로 삽입될 경우 회전 연산이 빈번하게 발생할 수 있습니다.

레드-블랙 트리의 장점

균형 유지의 효율성: AVL 트리에 비해 균형을 유지하기 위한 회전 연산의 빈도가 낮아 삽입과 삭제가 더 효율적입니다.
유연한 균형 유지: 약간 느슨한 균형 유지로 인해 다양한 패턴의 데이터에 대해 안정적인 성능을 제공합니다.
상용 라이브러리의 활용: 많은 프로그래밍 언어에서 레드-블랙 트리를 기반으로 한 자료구조(예: Java의 TreeMap, C++의 std::map)를 제공하여 손쉽게 활용할 수 있습니다.

레드-블랙 트리의 단점

검색 성능의 제한: AVL 트리에 비해 검색 성능이 약간 낮을 수 있습니다.
복잡한 색상 규칙: 색상 속성으로 인해 구현이 다소 복잡할 수 있습니다.
트리 구조의 이해 필요: 색상 규칙과 회전 연산을 이해해야 하므로 학습 곡선이 존재합니다.

AVL 트리와 레드-블랙 트리는 균형 이진 탐색 트리의 대표적인 예로, 데이터의 효율적인 저장과 검색을 가능하게 하는 강력한 자료구조입니다. 이들은 데이터베이스 인덱스, 파일 시스템, 메모리 관리 등 핵심적으로 사용되며, 각자의 장단점을 바탕으로 특정 상황에 맞게 선택하여 활용할 수 있습니다.

참고 자료

https://ko.wikipedia.org/wiki/AVL_%ED%8A%B8%EB%A6%AC

AVL 트리 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 자가 균형 이진 탐색 트리이다. 스스로 균형을 잡는 데이터 구조 중 처음으로

ko.wikipedia.org

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년

ko.wikipedia.org

https://www.geeksforgeeks.org/introduction-to-avl-tree/

AVL Tree Data Structure - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

https://www.geeksforgeeks.org/introduction-to-red-black-tree/

Introduction to Red-Black Tree - GeeksforGeeks

www.geeksforgeeks.org

728x90

저작자표시

'개발일지 > 자료구조' 카테고리의 다른 글

트라이(Trie): 효율적인 문자열 검색과 자동 완성을 위한 자료구조 (3)	2024.11.20
힙(Heap): 효율적인 우선순위 관리와 정렬을 위한 자료구조 (2)	2024.11.18
그래프(Graph): 복잡한 관계를 표현하고 처리하는 자료구조 (0)	2024.11.17
이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree): 효율적인 데이터 구조와 검색 (1)	2024.11.16
해시 테이블(Hash Table)과 딕셔너리(Dictionary): 빠른 데이터 검색과 저장 (1)	2024.11.15

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

JinHwan.J

트리(Tree) 자료구조의 확장인 AVL 트리와 레드-블랙 트리

AVL 트리와 레드-블랙 트리의 등장 배경

균형 이진 탐색 트리(Balanced Binary Search Tree)의 개념

균형 이진 탐색 트리의 특징

AVL 트리와 레드-블랙 트리의 차이점

AVL 트리(AVL Tree)의 개념

AVL 트리의 특징

AVL 트리의 회전 유형

레드-블랙 트리(Red-Black Tree)의 개념

레드-블랙 트리의 특징

레드-블랙 트리의 균형 유지

AVL 트리와 레드-블랙 트리 구현하기

Python으로 AVL 트리 구현하기

코드 설명

AVL 트리와 레드-블랙 트리의 응용 예제

데이터베이스 인덱스 관리

코드 설명

레드-블랙 트리 응용 예제

우선순위 큐(Priority Queue) 구현

코드 설명

AVL 트리와 레드-블랙 트리의 장단점

AVL 트리의 장점

AVL 트리의 단점

레드-블랙 트리의 장점

레드-블랙 트리의 단점

참고 자료

'개발일지 > 자료구조' 카테고리의 다른 글

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역

트리(Tree) 자료구조의 확장인 AVL 트리와 레드-블랙 트리

AVL 트리와 레드-블랙 트리의 등장 배경

균형 이진 탐색 트리(Balanced Binary Search Tree)의 개념

균형 이진 탐색 트리의 특징

AVL 트리와 레드-블랙 트리의 차이점

AVL 트리(AVL Tree)의 개념

AVL 트리의 특징

AVL 트리의 회전 유형

레드-블랙 트리(Red-Black Tree)의 개념

레드-블랙 트리의 특징

레드-블랙 트리의 균형 유지

AVL 트리와 레드-블랙 트리 구현하기

Python으로 AVL 트리 구현하기

코드 설명

AVL 트리와 레드-블랙 트리의 응용 예제

데이터베이스 인덱스 관리

코드 설명

레드-블랙 트리 응용 예제

우선순위 큐(Priority Queue) 구현

코드 설명

AVL 트리와 레드-블랙 트리의 장단점

AVL 트리의 장점

AVL 트리의 단점

레드-블랙 트리의 장점

레드-블랙 트리의 단점

참고 자료

'개발일지 > 자료구조' 카테고리의 다른 글

관련글

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역