Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 스플레이 트리(Splay Tree) 구현하기: 삽입, 삭제, 검색까지 한 번에

이 글에서는 스플레이 트리(Splay Tree)를 C++로 구현하는 방법을 다룹니다. 스플레이 트리는 자가 조정(self-adjusting) 이진 탐색 트리의 일종으로, 특정 노드에 접근할 때마다 해당 노드를 루트 위치로 끌어올리는 splay 연산을 수행합니다. 덕분에 자주 사용되는 데이터일수록 트리 상단에 가까워져 접근 속도가 빨라지며, 별도의 균형 정보를 저장할 필요 없이 분할 상환(amortized) 시간 복잡도 O(log n)을 보장합니다.

클래스 설명

SplayTree 클래스는 아래와 같은 핵심 함수들로 구성됩니다.

  • Splay(): top-down 방식의 스플레이 연산을 수행합니다. 헤더 노드의 rch는 왼쪽 트리를, lch는 오른쪽 트리를 가리키며, 탐색 과정에서 왼쪽·중앙·오른쪽 세 부분으로 트리를 나눈 뒤 마지막에 다시 하나로 조립합니다.
  • RR_Rotate(): 노드를 오른쪽으로 회전합니다.
  • LL_Rotate(): 노드를 왼쪽으로 회전합니다.
  • New_Node(): 새로운 노드를 생성합니다.
  • Insert(): 트리에 노드를 삽입합니다.
  • Delete(): 트리에서 노드를 삭제합니다.
  • Search(): 트리에서 노드를 검색합니다.
  • InOrder(): 중위 순회(inorder traversal)로 트리 전체를 출력합니다.

삽입(Insert) 로직 요약

  • 새 키가 루트의 키보다 작으면, 기존 루트의 왼쪽 서브트리를 새 노드의 왼쪽 자식으로 연결하고 새 노드를 루트로 만듭니다.
  • 새 키가 루트의 키보다 크면, 기존 루트의 오른쪽 서브트리를 새 노드의 오른쪽 자식으로 연결하고 새 노드를 루트로 만듭니다.
  • 같은 키가 이미 존재하면 중복 삽입 없이 기존 루트를 그대로 반환합니다.

전체 의사코드(Pseudocode)

Begin
    구조체 s를 생성하여 키 변수 k, 왼쪽 자식 포인터 lch, 오른쪽 자식 포인터 rch를 선언한다.
    클래스 SplayTree를 생성한다:
        RR_Rotate 함수를 생성하여 오른쪽 회전을 수행한다.
        LL_Rotate 함수를 생성하여 왼쪽 회전을 수행한다.
        Splay 함수를 생성하여 top-down 방식의 스플레이 연산을 구현한다.
            head.rch는 왼쪽 트리를, head.lch는 오른쪽 트리를 가리킨다.
            오른쪽 트리에 대한 링크를 생성한다.
            왼쪽 트리에 대한 링크를 생성한다.
            왼쪽, 중앙, 오른쪽 트리를 하나로 조립한다.
    New_Node() 함수를 생성하여 트리의 노드를 만든다.
    Insert() 함수를 생성하여 트리에 노드를 삽입한다.
        새 키가 루트 키보다 작으면 새 노드를 루트로, 기존 루트를 오른쪽 자식으로 연결한다.
        새 키가 루트 키보다 크면 새 노드를 루트로, 기존 루트를 왼쪽 자식으로 연결한다.
        같은 키가 존재하면 루트를 그대로 반환한다.
    Delete() 함수를 생성하여 트리에서 노드를 삭제한다.
    Search() 함수를 생성하여 트리에서 노드를 검색한다.
    InOrder() 함수를 생성하여 트리를 중위 순회한다.
    main() 함수를 생성하고, 사용자 선택에 따라 해당 함수를 호출한다.
End

예제 코드

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct s//node declaration
{
    int k;
    s* lch;
    s* rch;
};
class SplayTree
{
    public:
    s* RR_Rotate(s* k2)
    {
        s* k1 = k2->lch;
        k2->lch = k1->rch;
        k1->rch = k2;
        return k1;
    }
    s* LL_Rotate(s* k2)
    {
        s* k1 = k2->rch;
        k2->rch = k1->lch;
        k1->lch = k2;
        return k1;
    }
    s* Splay(int key, s* root)
    {
        if (!root)
        return NULL;
        s header;
        header.lch= header.rch = NULL;
        s* LeftTreeMax = &header;
        s* RightTreeMin = &header;
        while (1)
        {
            if (key < root->k)
            {
                if (!root->lch)
                break;
                if (key< root->lch->k)
                {
                    root = RR_Rotate(root);
                    if (!root->lch)
                    break;
                }
                RightTreeMin->lch= root;
                RightTreeMin = RightTreeMin->lch;
                root = root->lch;
                RightTreeMin->lch = NULL;
            }
            else if (key> root->k)
            {
                if (!root->rch)
                break;
                if (key > root->rch->k)
                {
                    root = LL_Rotate(root);
                    if (!root->rch)
                    break;
                }
                LeftTreeMax->rch= root;
                LeftTreeMax = LeftTreeMax->rch;
                root = root->rch;
                LeftTreeMax->rch = NULL;
            }
            else
            break;
        }
        LeftTreeMax->rch = root->lch;
        RightTreeMin->lch = root->rch;
        root->lch = header.rch;
        root->rch = header.lch;
        return root;
    }
    s* New_Node(int key)
    {
        s* p_node = new s;
        if (!p_node)
        {
            fprintf(stderr, "Out of memory!\n");
            exit(1);
        }
        p_node->k = key;
        p_node->lch = p_node->rch = NULL;
        return p_node;
    }
    s* Insert(int key, s* root)
    {
        static s* p_node = NULL;
        if (!p_node)
        p_node = New_Node(key);
        else
        p_node->k = key;
        if (!root)
        {
            root = p_node;
            p_node = NULL;
            return root;
        }
        root = Splay(key, root);
        if (key < root->k)
        {
            p_node->lch= root->lch;
            p_node->rch = root;
            root->lch = NULL;
            root = p_node;
        }
        else if (key > root->k)
        {
            p_node->rch = root->rch;
            p_node->lch = root;
            root->rch = NULL;
            root = p_node;
        }
        else
        return root;
        p_node = NULL;
        return root;
    }
    s* Delete(int key, s* root)//delete node
    {
        s* temp;
        if (!root)//if tree is empty
        return NULL;
        root = Splay(key, root);
        if (key != root->k)//if tree has one item
        return root;
        else
        {
            if (!root->lch)
            {
                temp = root;
                root = root->rch;
            }
            else
            {
                temp = root;
                root = Splay(key, root->lch);
                root->rch = temp->rch;
            }
            free(temp);
            return root;
        }
    }
    s* Search(int key, s* root)//searching
    {
        return Splay(key, root);
    }
    void InOrder(s* root)//inorder traversal
    {
        if (root)
        {
            InOrder(root->lch);
            cout<< "key: " <<root->k;
            if(root->lch)
            cout<< " | left child: "<< root->lch->k;
            if(root->rch)
            cout << " | right child: " << root->rch->k;
            cout<< "\n";
            InOrder(root->rch);
        }
    }
};
int main()
{
    SplayTree st;
    s *root;
    root = NULL;
    st.InOrder(root);
    int i, c;
    while(1)
    {
        cout<<"1. Insert "<<endl;
        cout<<"2. Delete"<<endl;
        cout<<"3. Search"<<endl;
        cout<<"4. Exit"<<endl;
        cout<<"Enter your choice: ";
        cin>>c;
        switch(c)//perform switch operation
        {
            case 1:
                cout<<"Enter value to be inserted: ";
                cin>>i;
                root = st.Insert(i, root);
                cout<<"\nAfter Insert: "<<i<<endl;
                st.InOrder(root);
                break;
            case 2:
                cout<<"Enter value to be deleted: ";
                cin>>i;
                root = st.Delete(i, root);
                cout<<"\nAfter Delete: "<<i<<endl;
                st.InOrder(root);
                break;
            case 3:
                cout<<"Enter value to be searched: ";
                cin>>i;
                root = st.Search(i, root);
                cout<<"\nAfter Search "<<i<<endl;
                st.InOrder(root);
                break;
            case 4:
                exit(1);
            default:
                cout<<"\nInvalid type! \n";
        }
    }
    cout<<"\n";
    return 0;
}

실행 결과

1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 7
After Insert: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 6
After Insert: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 4
After Insert: 4
key: 4 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 5
After Insert: 5
key: 4
key: 5 | left child: 4 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 3
After Insert: 3
key: 3 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 2
After Insert: 2
key: 2 | right child: 3
key: 3 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 3
Enter value to be searched: 2
After Search 2
key: 2 | right child: 3
key: 3 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 2
Enter value to be deleted: 3
After Delete: 3
key: 2 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 4

마무리

위 코드는 메뉴 기반 인터페이스를 통해 노드의 삽입, 삭제, 검색을 직접 테스트할 수 있도록 구성되어 있습니다. 실행 결과를 보면 매 연산 후 해당 키가 항상 루트 위치로 이동하는 것을 확인할 수 있는데, 이것이 바로 스플레이 트리의 핵심 동작 방식입니다. AVL 트리나 레드-블랙 트리와 달리 각 노드에 균형 정보를 저장하지 않아 메모리 오버헤드가 적고, 캐시 지역성이 뛰어나 실제 응용에서 유용하게 활용됩니다.