[C++로 배우는 알고리즘과 자료구조 심화] Day 6: 스플레이 트리 (Splay Tree)

스플레이 트리 (Splay Tree)

스플레이 트리는 자가 조정 이진 탐색 트리입니다. 각 연산 후, 스플레이 연산을 통해 접근한 노드를 트리의 루트로 이동시킵니다. 이는 자주 접근하는 노드를 트리의 상위로 올려, 평균적으로 빠른 접근을 가능하게 합니다.

스플레이 트리의 주요 특징

1. 자가 조정: 각 연산 후 접근한 노드를 루트로 이동시키는 스플레이 연산을 수행합니다.
2. 평균 시간 복잡도: (O(\log n)) (최악의 경우 시간 복잡도: (O(n)))
3. 회전 연산: 좌회전, 우회전, 좌-좌 회전, 우-우 회전, 좌-우 회전, 우-좌 회전을 포함한 회전 연산을 사용합니다.

스플레이 트리의 기본 연산

1. 삽입 (Insert): 새로운 노드를 삽입하고 스플레이 연산을 수행합니다.
2. 삭제 (Delete): 특정 키를 가진 노드를 삭제하고 스플레이 연산을 수행합니다.
3. 검색 (Search): 특정 키를 가진 노드를 검색하고 스플레이 연산을 수행합니다.

스플레이 트리의 구현

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

 

스플레이 트리 노드 정의

#include <iostream>

// 스플레이 트리 노드 구조체 정의
struct SplayNode {
    int key;
    SplayNode* left;
    SplayNode* right;

    SplayNode(int key) : key(key), left(nullptr), right(nullptr) {}
};

 

스플레이 트리 클래스 정의

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

private:
    SplayNode* rightRotate(SplayNode* x);
    SplayNode* leftRotate(SplayNode* x);
    SplayNode* splay(SplayNode* root, int key);
};

SplayTree::SplayTree() {}

 

회전 연산 정의

// 오른쪽 회전 함수 정의
SplayNode* SplayTree::rightRotate(SplayNode* x) {
    SplayNode* y = x->left;
    x->left = y->right;
    y->right = x;
    return y;
}

// 왼쪽 회전 함수 정의
SplayNode* SplayTree::leftRotate(SplayNode* x) {
    SplayNode* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}

 

스플레이 연산 정의

// 스플레이 연산 함수 정의
SplayNode* SplayTree::splay(SplayNode* root, int key) {
    if (root == nullptr || root->key == key) {
        return root;
    }

    // 키가 루트의 키보다 작은 경우
    if (key < root->key) {
        if (root->left == nullptr) {
            return root;
        }

        // 좌-좌 회전 (Zig-Zig)
        if (key < root->left->key) {
            root->left->left = splay(root->left->left, key);
            root = rightRotate(root);
        }
        // 좌-우 회전 (Zig-Zag)
        else if (key > root->left->key) {
            root->left->right = splay(root->left->right, key);
            if (root->left->right != nullptr) {
                root->left = leftRotate(root->left);
            }
        }

        return (root->left == nullptr) ? root : rightRotate(root);
    } else {
        if (root->right == nullptr) {
            return root;
        }

        // 우-우 회전 (Zag-Zag)
        if (key > root->right->key) {
            root->right->right = splay(root->right->right, key);
            root = leftRotate(root);
        }
        // 우-좌 회전 (Zag-Zig)
        else if (key < root->right->key) {
            root->right->left = splay(root->right->left, key);
            if (root->right->left != nullptr) {
                root->right = rightRotate(root->right);
            }
        }

        return (root->right == nullptr) ? root : leftRotate(root);
    }
}

 

삽입 연산 정의

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

    root = splay(root, key);

    if (root->key == key) {
        return root;
    }

    SplayNode* newNode = new SplayNode(key);

    if (key < root->key) {
        newNode->right = root;
        newNode->left = root->left;
        root->left = nullptr;
    } else {
        newNode->left = root;
        newNode->right = root->right;
        root->right = nullptr;
    }

    return newNode;
}

 

삭제 연산 정의

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

    root = splay(root, key);

    if (key != root->key) {
        return root;
    }

    SplayNode* temp;
    if (root->left == nullptr) {
        temp = root;
        root = root->right;
    } else {
        temp = root;
        root = splay(root->left, key);
        root->right = temp->right;
    }

    delete temp;
    return root;
}

 

검색 연산 정의

// 검색 함수 정의
SplayNode* SplayTree::search(SplayNode* root, int key) {
    return splay(root, key);
}

 

중위 순회 정의

// 중위 순회 함수 정의
void SplayTree::inorder(SplayNode* root) {
    if (root != nullptr) {
        inorder(root->left);
        std::cout << root->key << " ";
        inorder(root->right);
    }
}

 

사용 예제

int main() {
    SplayTree splayTree;
    SplayNode* root = nullptr;

    // 노드 삽입
    root = splayTree.insert(root, 100);
    root = splayTree.insert(root, 50);
    root = splayTree.insert(root, 200);
    root = splayTree.insert(root, 40);
    root = splayTree.insert(root, 30);
    root = splayTree.insert(root, 20);

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

    std::cout << "키 30 검색 후 루트:" << std::endl;
    root = splayTree.search(root, 30);
    splayTree.inorder(root);
    std::cout << std::endl;

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

    return 0;
}

 

설명

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

스플레이 트리의 기본 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 7: 스킵 리스트(Skip List)"에 대해 학습하겠습니다.