Splay Tree

Splaying이라는 기법이 사용되며, 이는 특정 노드에 대해 접근을 하면, 이를 루트로 위치하도록 재배치 하는 기법의 트리



1. 특징

  • 구현이 단순
  • 많이 접근한 노드에 대해서 빠른 접근이 가능하다
  • 접근 빈도가 불균등하거나 비 랜덤 패턴의 경우 O(lgn)보다 더 유리하다.
  • AVL-Tree와 RB-Tree와 달리 추가 데이터 저장 필요 없다.
  • 최악의 경우 높이가 선형, 즉 O(n)이 나올 수 있다.
  • 세그먼트 트리로 이용이 가능하다.
    • k번째 원소 찾기, 구간 합, lazy Propagation, 구간 뒤집기 모두 쉽게 할 수 있다.
    • x노드를 접근한다면, splay를 통해 root로 올라오면서 x보다 작은 노드들은 Left에, 큰 노드들은 Right에 모이는 특성을 이용



2. 사용 예

캐시, 가비지 컬렉터 알고리즘



3. 사용 기법

1) Rotate

다른 balance binary search tree들과 같은 rotate 개념이다.

2) Splay

rotate를 기본으로, 탐색/삽입/삭제한 노드를 root에 위치할 때 까지 rotate시켜가는 기법

Zig : 기준 노드 x, z의 부모 노드 y가 root일 때

alter-text

y를 기준으로 rotate 해주는것을 Zig라고 한다.


Zig-Zig : x의 할아버지 노드(z)에 대해 자식 y의 방향과 y에 대한 x의 방향이 같을 때

한마디로 z->y 방향 == y->x 방향

alter-text

rotate(y)후, rotate(x) 해주는 것을 Zig-Zig라고 한다.


Zig-Zag: x의 할아버지 노드(z)에 대해 자식 y의 방향과 y에 대한 자식 x의 방향이 다를 때

한마디로 z->y 방향 != y->x 방향

alter-text

rotate(x)후,rotate(x) 해주는 것을 Zig-Zig라고 한다.



4. 구현

1) 삽입

일반 BST와 동일하게 삽입한 후, 삽입한 노드 x를 기준으로 splay를 수행해 주면 된다.

2) 삭제

삭제도 삽입과 마찬가지로 일반 BST 삭제 연산과 방법은 동일하고 splay를 해주면되는데 삭제에는 추가로 여러 방법이 존재하는데, 삭제할 노드를 기준으로 splay를 수행 후, successor를 찾아 successor를 root로 만드는 방법과 삭제를 먼저 수행 후에 그 노드를 대신해서 오는 노드를 기준으로 splay를 수행하면 된다.

3) 순회 과정

순회는 일반 BST와 동일하게 전위 / 중위 / 후위 순회로 순회가 가능하다.

4) 탐색 과정

탐색 또한 일반 BST와 동일하게 찾으려는 key가 현재 노드보다 작다면 왼쪽으로, 크다면 오른쪽으로 탐색이 가능하지만, 많이 탐색한 key일수록 상단 부근에 위치하기 때문에 O(lgn)보다 유리하다.



5. 시간 복잡도

삽입/탐색 시 가장 작은 숫자나 가장 큰 숫자를 접근한다면, 트리는 O(n)으로 선형적인 트리가 생성이 되지만, 무작위 splay를 통해 구조를 바꿔 줄 수도 있고, 자주 접근 하는 노드는 O(lgn)보다 빠르게 접근이 가능하기 때문에 상각 O(lgn)으로 볼 수 있다.



6. 구현 코드

github에서 보기

/*
 * C++ 이용하여 Splay Tree 구현하기
 *
 * 목적 : Splay Tree 공부 하기 위해 작성했으며,
 *       C++ 이용하여 작성하시는 분들에게 도움이 되고자 했다.
 *
 * 설명 : key 값은 int만 가능 하며 중복 key는 허용 x
 *       단순 연결 리스트로 구현
 *
 *       class SplayTree
 *
 *       변수 :   root => root node
 *
 *       생성자 : SplayTree =>  root 를 null로 초기화
 *
 *       함수 :   IsKey => key값이 있는지 검사하는 함수
 *
 *               Insert => 일반 BST의 삽입함수에 끝에 Splay 추가 (return void)
 *               Delete => Splay후 successor를 root로 만드는 함수 (return void)
 *               Splay(x) => x를 root로 재조정 함수 ( return void)
 *               replace(x,y) => 삭제할 x와 successor 위치를 바꿔주는 함수 (return void)
 *
 *               RotateRight(x) => x기준 오른쪽으로 회전
 *               RotateLeft(x) => x기준 왼쪽으로 회전
 *
 *               Inorder,Preorder,Postorder => 순회 함수
 *               tree_minimum(x), tree_maximum(x) => 노드 x 기준으로 가장 왼쪽, 오른쪽 return 함수
 *
 *               DisplayMenu, SelectMenu => 초기 Menu판 print 함수
 *               Insert_helper,Delete_helper,order_helper,print_helper => 각각 이벤트 수행시 입력받고 조건 에러 처리 위한 함수 와 tree print
 * 해주는 함수
 *
 *
 * 작성자 : gowoonsori
 * github : https://github.com/gowoonsori/my-tech/tree/master/dataStructure/Tree
 */

#include <algorithm>  // max() 함수 이용
#include <iostream>

struct node {
    int key;
    node *left = nullptr;
    node *right = nullptr;
    node *parent = nullptr;
};
typedef node *NodePtr;

class SplayTree {
   private:
    NodePtr root;  //루트 노드

    // key값이 있는지 없는지 검사 있으면 pointer 값, 없으면 nullptr
    NodePtr IsKey(int item) {
        NodePtr t = root;

        /*key값을 찾거나 없다면 break*/
        while (t != nullptr && t->key != item) {
            t = (item < t->key) ? t->left : t->right;
        }
        return t;
    }

    /*새로운 key 삽입함수로 root노드 반환*/
    void Insert(int item) {
        /*새로운 노드 삽입*/
        if (this->root == nullptr) {
            NodePtr x = new node;
            x->key = item;
            this->root = x;
            return;
        }
        NodePtr y;  //삽입할 x의 부모노드 y
        NodePtr y_next = this->root;

        /*부모노드 y찾기*/
        while (y_next) {
            y = y_next;
            y_next = (y->key > item) ? y->left : y->right;
        }

        /*y의 자식으로 x붙여주기*/
        NodePtr x = new node;
        x->key = item;
        x->parent = y;
        if (y->key > item)
            y->left = x;
        else
            y->right = x;

        Splay(x);
    }

    /*key 삭제 함수*/
    void Delete(int item) {
        node *z = IsKey(item);
        Splay(z);  //삭제할 노드를 root로 올린 후 resturcture

        if (!z->left)  // left child가 null
            replace(z, z->right);
        else if (!z->right)  // left child가 null이 아니고 right child가 null일때
            replace(z, z->left);
        else {                                 //자식이 둘다있을때
            node *y = tree_minimum(z->right);  // find successor

            /*succesoor가 z의 오른쪽 자식일때*/
            if (y->parent != z) {
                replace(y, y->right);
                y->right = z->right;
                y->right->parent = y;
            }
            replace(z, y);
            y->left = z->left;
            y->left->parent = y;
        }

        delete z;
    }

    /* x를 기준으로 splay*/
    void Splay(NodePtr x) {
        /*x가 root가 될때까지*/
        while (x->parent) {
            NodePtr p = x->parent;
            NodePtr g = p->parent;

            /*x의 부모 노드가 root라면*/
            if (!x->parent->parent) {
                if (x->parent->left == x)
                    RotateRight(x->parent);
                else
                    RotateLeft(x->parent);
            }
            /*zig zig*/
            else if (x->parent->left == x && x->parent->parent->left == x->parent) {
                RotateRight(x->parent->parent);
                RotateRight(x->parent);
            } else if (x->parent->right == x && x->parent->parent->right == x->parent) {
                RotateLeft(x->parent->parent);
                RotateLeft(x->parent);
            }
            /*zig zag*/
            else if (x->parent->left == x && x->parent->parent->right == x->parent) {
                RotateRight(x->parent);
                RotateLeft(x->parent);
            } else {
                RotateLeft(x->parent);
                RotateRight(x->parent);
            }
        }
    } /*x를 중심으로 왼쪽으로 회전*/
    void RotateLeft(NodePtr x) {
        NodePtr y = x->right;

        x->right = y->left;
        if (y->left) {
            y->left->parent = x;
        }
        y->parent = x->parent;

        if (!x->parent) {
            root = y;
        } else if (x == x->parent->left) {
            x->parent->left = y;
        } else {
            x->parent->right = y;
        }
        x->parent = y;
        y->left = x;
    }
    /*x를 중심으로 오른쪽으로 회전*/
    void RotateRight(NodePtr x) {
        NodePtr y = x->left;

        x->left = y->right;
        if (y->right) {
            y->right->parent = x;
        }
        y->parent = x->parent;

        if (!x->parent) {
            root = y;
        } else if (x == x->parent->left) {
            x->parent->left = y;
        } else {
            x->parent->right = y;
        }
        x->parent = y;
        y->right = x;
    }

    /* 삭제시 */
    void replace(NodePtr u, NodePtr v) {
        if (!u->parent)
            root = v;
        else if (u == u->parent->left)
            u->parent->left = v;
        else
            u->parent->right = v;
        if (v) v->parent = u->parent;
    }

    /*y를 중심으로 오른쪽으로 회전*/

    /*show tree*/
    void print_helper(NodePtr root, std::string indent, bool last) {
        // print the tree structure on the screen
        if (root != nullptr) {
            std::cout << indent;
            if (last) {
                std::cout << "R----";
                indent += "     ";
            } else {
                std::cout << "L----";
                indent += "|    ";
            }

            std::cout << root->key << std::endl;
            print_helper(root->left, indent, false);
            print_helper(root->right, indent, true);
        }
    }

    /*중위순회*/
    void Inorder(NodePtr target) {
        if (target == nullptr) return;
        Inorder(target->left);
        std::cout << target->key << " ";
        Inorder(target->right);
    }
    /*후위순회*/
    void Postorder(NodePtr target) {
        if (target == nullptr) return;
        Postorder(target->left);
        Postorder(target->right);
        std::cout << target->key << " ";
    }
    /*전위순회*/
    void Preorder(NodePtr target) {
        if (target == nullptr) return;
        std::cout << target->key << " ";
        Preorder(target->left);
        Preorder(target->right);
    }

   public:
    SplayTree() { this->root = nullptr; }
    //최솟값 찾기
    NodePtr tree_minimum(NodePtr x) {
        while (x->left != nullptr) {
            x = x->left;
        }
        return x;
    }
    //최댓값 찾기
    NodePtr tree_maximum(NodePtr x) {
        while (x->right != nullptr) {
            x = x->right;
        }
        return x;
    }

    void DisplayMenuBoard() {
        std::cout << "         ** Splay Tree **     " << std::endl;
        std::cout << "                            " << std::endl;
        std::cout << "              Menu          " << std::endl;
        std::cout << "          1. Insert Key     " << std::endl;
        std::cout << "          2. Delete Key     " << std::endl;
        std::cout << "          3. Show Tree      " << std::endl;
        std::cout << "          4. choose order   " << std::endl;
        std::cout << "          5. show Menu      " << std::endl;
        std::cout << "          6. clear Display  " << std::endl;
        std::cout << "          7. exit           " << std::endl;
        std::cout << std::endl;
    }
    void SelectMenu() {
        DisplayMenuBoard();
        int i = -1;

        while (i != 8) {
            std::cout << "(show Menu : 5) -->  select :   ";
            std::cin >> i;
            switch (i) {
                case 1:
                    Insert_helper();
                    break;
                case 2:
                    Delete_helper();
                    break;
                case 3:
                    print_helper(root, "", true);
                    break;
                case 4:
                    Order_helper();
                    break;
                case 5:
                    DisplayMenuBoard();
                    break;
                case 6:
                    system("cls");
                    DisplayMenuBoard();
                    break;
                case 7:
                    return;
                default:
                    std::cout << " !!! Wrong entered !!!\n" << std::endl;
            }
        }
    }

    void Insert_helper() {
        int item;
        std::cout << "Key to insert  :  ";
        std::cin >> item;
        if (IsKey(item)) {
            std::cout << "!!! " << item << " is already exists !!!\n";
            return;
        }
        Insert(item);
        return;
    }

    void Delete_helper() {
        int item;
        std::cout << "Key to delete  :  ";
        std::cin >> item;
        if (!IsKey(item)) {
            std::cout << "!!! " << item << " is not exists !!!\n";
            return;
        }
        Delete(item);
        return;
    }

    void Order_helper() {
        int i;
        std::cout << "         == Order Menu ==" << std::endl;
        std::cout << "          1. PreOrder" << std::endl;
        std::cout << "          2. InOrder" << std::endl;
        std::cout << "          3. PostOrder" << std::endl;
        std::cout << "          4. exit" << std::endl;
        std::cout << " --> select  :  ";

        std::cin >> i;
        switch (i) {
            case 1:
                Preorder(this->root);
                std::cout << std::endl;
                break;
            case 2:
                Inorder(this->root);
                std::cout << std::endl;
                break;
            case 3:
                Postorder(this->root);
                std::cout << std::endl;
                break;
            case 4:
                return;
            default:
                std::cout << " !!! Wrong enter !!!\n" << std::endl;
                break;
        }
        return;
    }
};

int main() {
    SplayTree tree;
    tree.SelectMenu();

    return 0;
}

Tags :

Related Posts

PointRee 프로젝트 1 - 설계와 환경 구성

PointRee 프로젝트 1 - 설계와 환경 구성

웹 전반적인 흐름도 익히고 프레임워크들도 공부하기 위해 토이 프로젝트로 간단한 고객 정보를 관리하고 포인트 적립을 하는 웹을 구현해보고자 한다. 사용할 스택으로는 크게 React와 Spring Boot를 사용해서 개발해보려고 한다. React는 사용을 해본적이 있고 JS에 관심이 많기 때문에 선택을 하였고, 백을 JS 프레임워크가 아닌 굳이 Spring Boot를 사용하는 이유는 현재 졸업작품에서도 사용을 하고 있고 현재 흥미가 많은 프레임워크이기 때문에 더많은 공부를 위해 사용하기로 했다....

Read More
Home Server 만들기

Home Server 만들기

집 서버를 만들게 된 배경 집 컴퓨터를 교체하고 지인의 컴퓨터를 교체해주면서 부품들이 여럿 남게 되는 상황이 생겼는데, 그냥 버리기 아까워 컴퓨터를 한대 더 조립을 하게 되었다. 사양은 Intel(R) Celeron(R) CPU G3930 에 4G, 250Gb 이다. 컴퓨터를 조립 후 막상 사용할 곳이 없어 고민하던 중에 aws 프리티어도 끝났겠다 싶어 개발이나 테스트용으로 서버를 사용하면 좋을 것 같아 서버로 만들어보기로 했다....

Read More
배열

배열

배열은 연속된 메모리에 저장된 자료구조로 다른 자료구조 중 Random Access가 가장빠르고 고정된 길이의 자료구조이다. 배열과 비슷한 자료구조로 go에는 slice가 존재하는데 slice는 동적인 길이의 배열과 같다. 1. 선언 방식 배열은 고정된 size의 자료구조이기 때문에 변수를 선언하는 방식에서 타입을 **[]**를 이용해서 size를 선언해주면 된다. 배열안의 값들의 기본값은 제로값(zero value)로 할당된다....

Read More