[C++로 배우는 알고리즘과 자료구조 심화] Day 4: 이면 탐색 트리 (Treap)

이면 탐색 트리 (Treap)

이면 탐색 트리(Treap)는 이진 탐색 트리(BST)와 힙(Heap)의 특성을 동시에 가지는 자료구조입니다. 각 노드는 키(key)와 우선순위(priority)를 가지며, 다음 두 가지 성질을 만족합니다:

1. 이진 탐색 트리 성질: 키의 값에 대해 이진 탐색 트리 성질을 만족합니다.
2. 힙 성질: 우선순위에 대해 최대 힙 또는 최소 힙 성질을 만족합니다.

트라이의 주요 특징

1. 삽입, 삭제, 검색:
   • 평균 시간 복잡도: (O(\log n))
   • 최악의 경우 시간 복잡도: (O(n))
2. 회전 연산:
   • 이중회전을 통해 트리의 균형을 유지합니다.

트라이의 기본 연산

1. 삽입 (Insert): 새로운 노드를 삽입합니다.
2. 삭제 (Delete): 특정 키를 가진 노드를 삭제합니다.
3. 검색 (Search): 특정 키를 가진 노드를 검색합니다.

트라이의 구현

다음은 C++로 트라이를 구현한 예제입니다. 삽입, 삭제, 검색 연산을 포함합니다.

 

트라이 노드 정의

#include <iostream>
#include <cstdlib>

// 트라이 노드 구조체 정의
struct TreapNode {
    int key, priority;
    TreapNode* left;
    TreapNode* right;

    TreapNode(int key) : key(key), priority(std::rand()), left(nullptr), right(nullptr) {}
};

 

트라이 클래스 정의

class Treap {
public:
    Treap();
    TreapNode* search(TreapNode* root, int key);
    TreapNode* insert(TreapNode* root, int key);
    TreapNode* deleteNode(TreapNode* root, int key);
    void inorder(TreapNode* root);

private:
    TreapNode* rightRotate(TreapNode* y);
    TreapNode* leftRotate(TreapNode* x);
};

Treap::Treap() {}

 

회전 연산 정의

// 오른쪽 회전 함수 정의
TreapNode* Treap::rightRotate(TreapNode* y) {
    TreapNode* x = y->left;
    TreapNode* T2 = x->right;

    // 회전 수행
    x->right = y;
    y->left = T2;

    return x;
}

// 왼쪽 회전 함수 정의
TreapNode* Treap::leftRotate(TreapNode* x) {
    TreapNode* y = x->right;
    TreapNode* T2 = y->left;

    // 회전 수행
    y->left = x;
    x->right = T2;

    return y;
}

 

삽입 연산 정의

// 삽입 함수 정의
TreapNode* Treap::insert(TreapNode* root, int key) {
    if (root == nullptr) {
        return new TreapNode(key);
    }

    if (key <= root->key) {
        root->left = insert(root->left, key);

        // 힙 성질을 위반하는 경우 회전 수행
        if (root->left->priority > root->priority) {
            root = rightRotate(root);
        }
    } else {
        root->right = insert(root->right, key);

        // 힙 성질을 위반하는 경우 회전 수행
        if (root->right->priority > root->priority) {
            root = leftRotate(root);
        }
    }

    return root;
}

 

삭제 연산 정의

// 삭제 함수 정의
TreapNode* Treap::deleteNode(TreapNode* root, int key) {
    if (root == nullptr) {
        return root;
    }

    if (key < root->key) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->key) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == nullptr) {
            TreapNode* temp = root->right;
            delete root;
            root = temp;
        } else if (root->right == nullptr) {
            TreapNode* temp = root->left;
            delete root;
            root = temp;
        } else if (root->left->priority < root->right->priority) {
            root = leftRotate(root);
            root->left = deleteNode(root->left, key);
        } else {
            root = rightRotate(root);
            root->right = deleteNode(root->right, key);
        }
    }

    return root;
}

 

검색 연산 정의

// 검색 함수 정의
TreapNode* Treap::search(TreapNode* root, int key) {
    if (root == nullptr || root->key == key) {
        return root;
    }

    if (key < root->key) {
        return search(root->left, key);
    }

    return search(root->right, key);
}

 

중위 순회 정의

// 중위 순회 함수 정의
void Treap::inorder(TreapNode* root) {
    if (root != nullptr) {
        inorder(root->left);
        std::cout << "키: " << root->key << " | 우선순위: " << root->priority << std::endl;
        inorder(root->right);
    }
}

 

사용 예제

int main() {
    Treap treap;
    TreapNode* root = nullptr;

    // 노드 삽입
    root = treap.insert(root, 50);
    root = treap.insert(root, 30);
    root = treap.insert(root, 20);
    root = treap.insert(root, 40);
    root = treap.insert(root, 70);
    root = treap.insert(root, 60);
    root = treap.insert(root, 80);

    std::cout << "중위 순회 결과:" << std::endl;
    treap.inorder(root);

    std::cout << "\n키 20 삭제 후 중위 순회 결과:" << std::endl;
    root = treap.deleteNode(root, 20);
    treap.inorder(root);

    std::cout << "\n키 30 삭제 후 중위 순회 결과:" << std::endl;
    root = treap.deleteNode(root, 30);
    treap.inorder(root);

    std::cout << "\n키 50 삭제 후 중위 순회 결과:" << std::endl;
    root = treap.deleteNode(root, 50);
    treap.inorder(root);

    return 0;
}

 

설명

1. 트라이 노드 구조체:
   • key: 노드의 키 값입니다.
   • priority: 노드의 우선순위 값입니다.
   • left, right: 왼쪽 및 오른쪽 자식 노드를 가리킵니다.
2. 트라이 클래스:
   • insert: 새로운 노드를 삽입합니다. 삽입 후 힙 성질을 유지하기 위해 회전 연산을 수행합니다.
   • deleteNode: 특정 키를 가진 노드를 삭제합니다. 삭제 후 힙 성질을 유지하기 위해 회전 연산을 수행합니다.
   • search: 특정 키를 가진 노드를 검색합니다.
   • rightRotate, leftRotate: 힙 성질을 유지하기 위해 회전 연산을 수행합니다.
   • inorder: 트리의 중위 순회를 수행하여 노드를 출력합니다.
3. 사용 예제:
   • 노드를 삽입하고 중위 순회를 통해 트리 구조를 출력합니다.
   • 노드를 삭제한 후, 중위 순회를 통해 트리 구조가 올바른지 확인합니다.

이면탐색트리(Treap)의 기본 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 5: 균형 이진 탐색 트리 (AVL 트리, Red-Black 트리)"에 대해 학습하겠습니다.