[C++로 배우는 알고리즘과 자료구조 심화] Day 7: 스킵 리스트 (Skip List)

스킵 리스트 (Skip List)

스킵 리스트는 연결 리스트에 인덱스를 추가하여 검색, 삽입, 삭제 연산의 시간 복잡도를 (O(\log n))으로 개선한 자료구조입니다. 여러 레벨로 구성된 연결 리스트로, 각 레벨마다 원소를 건너뛰어가며 검색할 수 있습니다. 이는 균형 이진 탐색 트리와 유사한 시간 복잡도를 가지면서도 구현이 간단합니다.

스킵 리스트의 주요 특징

1. 시간 복잡도:
   • 평균: (O(\log n))
   • 최악의 경우: (O(n))
2. 레벨 구조: 여러 레벨의 리스트로 구성되며, 각 레벨은 원소를 건너뛰어가며 검색할 수 있도록 합니다.
3. 확률적 균형 유지: 랜덤하게 레벨을 선택하여 원소를 삽입함으로써 확률적으로 균형을 유지합니다.

스킵 리스트의 기본 연산

1. 삽입 (Insert): 새로운 원소를 삽입하고 레벨을 랜덤하게 결정합니다.
2. 삭제 (Delete): 특정 키를 가진 원소를 삭제합니다.
3. 검색 (Search): 특정 키를 가진 원소를 검색합니다.

스킵 리스트의 구현

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

 

스킵 리스트 노드 정의

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

// 스킵 리스트 노드 구조체 정의
struct SkipListNode {
    int key;
    std::vector<SkipListNode*> forward;

    SkipListNode(int key, int level) : key(key), forward(level, nullptr) {}
};

스킵 리스트 클래스 정의

class SkipList {
public:
    SkipList(int maxLevel, float probability);
    void insert(int key); // 원소 삽입 함수
    void deleteNode(int key); // 원소 삭제 함수
    bool search(int key); // 원소 검색 함수
    void display(); // 스킵 리스트 출력 함수

private:
    int randomLevel(); // 랜덤 레벨 생성 함수
    SkipListNode* createNode(int key, int level); // 노드 생성 함수

    int maxLevel;
    float probability;
    int level;
    SkipListNode* header;
};

// 스킵 리스트 생성자 정의
SkipList::SkipList(int maxLevel, float probability) {
    this->maxLevel = maxLevel;
    this->probability = probability;
    this->level = 0;
    this->header = new SkipListNode(-1, maxLevel);
    std::srand(std::time(0));
}

 

랜덤 레벨 생성 및 노드 생성 함수 정의

// 랜덤 레벨 생성 함수 정의
int SkipList::randomLevel() {
    int lvl = 1;
    while (((double)std::rand() / RAND_MAX) < probability && lvl < maxLevel) {
        lvl++;
    }
    return lvl;
}

// 노드 생성 함수 정의
SkipListNode* SkipList::createNode(int key, int level) {
    return new SkipListNode(key, level);
}

 

삽입 연산 정의

// 원소 삽입 함수 정의
void SkipList::insert(int key) {
    std::vector<SkipListNode*> update(maxLevel, nullptr);
    SkipListNode* current = header;

    for (int i = level; i >= 0; i--) {
        while (current->forward[i] != nullptr && current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    current = current->forward[0];

    if (current == nullptr || current->key != key) {
        int rlevel = randomLevel();

        if (rlevel > level) {
            for (int i = level + 1; i < rlevel; i++) {
                update[i] = header;
            }
            level = rlevel;
        }

        SkipListNode* newNode = createNode(key, rlevel);

        for (int i = 0; i < rlevel; i++) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
    }
}

 

삭제 연산 정의

// 원소 삭제 함수 정의
void SkipList::deleteNode(int key) {
    std::vector<SkipListNode*> update(maxLevel, nullptr);
    SkipListNode* current = header;

    for (int i = level; i >= 0; i--) {
        while (current->forward[i] != nullptr && current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    current = current->forward[0];

    if (current != nullptr && current->key == key) {
        for (int i = 0; i <= level; i++) {
            if (update[i]->forward[i] != current) {
                break;
            }
            update[i]->forward[i] = current->forward[i];
        }

        while (level > 0 && header->forward[level] == nullptr) {
            level--;
        }

        delete current;
    }
}

 

검색 연산 정의

// 원소 검색 함수 정의
bool SkipList::search(int key) {
    SkipListNode* current = header;

    for (int i = level; i >= 0; i--) {
        while (current->forward[i] != nullptr && current->forward[i]->key < key) {
            current = current->forward[i];
        }
    }

    current = current->forward[0];

    return current != nullptr && current->key == key;
}

 

스킵 리스트 출력 함수 정의

// 스킵 리스트 출력 함수 정의
void SkipList::display() {
    for (int i = 0; i <= level; i++) {
        SkipListNode* node = header->forward[i];
        std::cout << "레벨 " << i << ": ";
        while (node != nullptr) {
            std::cout << node->key << " ";
            node = node->forward[i];
        }
        std::cout << std::endl;
    }
}

 

사용 예제

int main() {
    SkipList list(4, 0.5);

    list.insert(3);
    list.insert(6);
    list.insert(7);
    list.insert(9);
    list.insert(12);
    list.insert(19);
    list.insert(17);
    list.insert(26);
    list.insert(21);
    list.insert(25);

    std::cout << "스킵 리스트 내용:" << std::endl;
    list.display();

    std::cout << "\n원소 19 검색: " << (list.search(19) ? "존재" : "존재하지 않음") << std::endl;

    std::cout << "\n원소 19 삭제 후 스킵 리스트 내용:" << std::endl;
    list.deleteNode(19);
    list.display();

    return 0;
}

 

설명

1. 스킵 리스트 노드 구조체:
   • key: 노드의 키 값입니다.
   • forward: 각 레벨에서 다음 노드를 가리키는 포인터 배열입니다.
2. 스킵 리스트 클래스:
   • insert: 새로운 원소를 삽입하고 랜덤 레벨을 결정합니다.
   • deleteNode: 특정 키를 가진 원소를 삭제합니다.
   • search: 특정 키를 가진 원소를 검색합니다.
   • randomLevel: 랜덤 레벨을 생성합니다.
   • createNode: 노드를 생성합니다.
   • display: 스킵 리스트의 내용을 출력합니다.
3. 사용 예제:
   • 노드를 삽입하고 스킵 리스트의 내용을 출력합니다.
   • 노드를 검색하여 존재 여부를 확인합니다.
   • 노드를 삭제한 후 스킵 리스트의 내용을 다시 출력합니다.

스킵 리스트의 기본 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 8: 최소 커버링 트리 (Minimum Spanning Tree) 심화"에 대해 학습하겠습니다.