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

문자열

문자열

  • Java
  • 2021년 3월 27일

String 타입을 선언하는 방법 ◾ 리터럴 방식 String str = "Hello"; String str2 = "Hello"; System.out.println(str == str2); //true 편하기 때문에 많이 사용하는 방법으로 큰따옴표(" ")로 바로 할당하는 방법이다. 이 방법은 내부적으로 JVM메모리에 있는 상수풀에 저장이 되는데 이때문에 같은 문자열을 다른 변수에 선언을 하고 ==연산을 수행하면 true가 나오는 이유가 된다. 내부적으로...

Read More
Enum

Enum

  • Java
  • 2021년 1월 24일

백기선님의 유튜브 로 진행하시는 스터디를 진행하며 올리는 정리 블로그입니다. Java의 Enum도 기본적으로 c나 c++의 enum과 같은 목적을 위한 클래스로 JDK 1.5이후에 생긴 클래스이다. 잠깐 C언어 얘기를 하자면 C언어의 C99 이전에는 boolean타입을 제공하지 않았기 때문에 다음과 같이 사용하고는 했었다. typedef enum _boolean { FALSE, TRUE } boolean; #define FALSE...

Read More
어노테이션

어노테이션

  • Java
  • 2021년 1월 31일

메서드를 오버라이딩 할때 사용했던 @Override와 같이 @ 기호를 사용하는 문법 요소로 Java5부터 등장했다. 단어의 의미인 주석과는 비슷하지만 다른 역할로써 사용되는데 메서드/클래스 등에 의미를 단순히 컴파일러에게 알려주기 위한 표식이 아닌 컴파일타임 이나 런타임에 해석될 수 있다. 1) 장점 기존의 자바는 선언적 프로그래밍방식으로 개...

Read More