Splay Tree
Section
Splaying이라는 기법이 사용되며, 이는 특정 노드에 대해 접근을 하면, 이를 루트로 위치하도록 재배치 하는 기법의 트리
1. 특징
-
구현이 단순
-
많이 접근한 노드에 대해서 빠른 접근이 가능하다
-
접근 빈도가 불균등하거나 비 랜덤 패턴의 경우 O(lgn)보다 더 유리하다.
-
AVL-Tree와 RB-Tree와 달리 추가 데이터 저장 필요 없다.
-
최악의 경우 높이가 선형, 즉 O(n)이 나올 수 있다.
-
세그먼트 트리로 이용이 가능하다.
- k번째 원소 찾기, 구간 합, lazy Propagation, 구간 뒤집기 모두 쉽게 할 수 있다.
- x노드를 접근한다면, splay를 통해 root로 올라오면서 x보다 작은 노드들은 Left에, 큰 노드들은 Right에 모이는 특성을 이용
2. 사용 예
캐시, 가비지 컬렉터 알고리즘
3. 사용 기법
◾ Rotate
다른 balance binary search tree들과 같은 rotate 개념이다.
◾ Splay
rotate를 기본으로, 탐색/삽입/삭제한 노드를 root에 위치할 때 까지 rotate시켜가는 기법
-
Zig : 기준 노드 x, z의 부모 노드 y가 root일 때
y를 기준으로 rotate 해주는것을 Zig라고 한다.
-
Zig-Zig : x의 할아버지 노드(z)에 대해 자식 y의 방향과 y에 대한 x의 방향이 같을 때
한마디로
z->y 방향 == y->x 방향
rotate(y)후, rotate(x) 해주는 것을 Zig-Zig라고 한다.
-
Zig-Zag: x의 할아버지 노드(z)에 대해 자식 y의 방향과 y에 대한 자식 x의 방향이 다를 때
한마디로
z->y 방향 != y->x 방향
rotate(x)후,rotate(x) 해주는 것을 Zig-Zig라고 한다.
4. 구현
📌 삽입
일반 BST와 동일하게 삽입한 후, 삽입한 노드 x를 기준으로 splay를 수행해 주면 된다.
📌 삭제
삭제도 삽입과 마찬가지로 일반 BST 삭제 연산과 방법은 동일하고 splay를 해주면되는데 삭제에는 추가로 여러 방법이 존재하는데, 삭제할 노드를 기준으로 splay를 수행 후, successor를 찾아 successor를 root로 만드는 방법과 삭제를 먼저 수행 후에 그 노드를 대신해서 오는 노드를 기준으로 splay를 수행하면 된다.
📌 순회 과정
순회는 일반 BST와 동일하게 전위 / 중위 / 후위 순회로 순회가 가능하다.
📌 탐색 과정
탐색 또한 일반 BST와 동일하게 찾으려는 key가 현재 노드보다 작다면 왼쪽으로, 크다면 오른쪽으로 탐색이 가능하지만, 많이 탐색한 key일수록 상단 부근에 위치하기 때문에 O(lgn)보다 유리하다.
5. 시간 복잡도
삽입/탐색 시 가장 작은 숫자나 가장 큰 숫자를 접근한다면, 트리는 O(n)으로 선형적인 트리가 생성이 되지만, 무작위 splay를 통해 구조를 바꿔 줄 수도 있고, 자주 접근 하는 노드는 O(lgn)보다 빠르게 접근이 가능하기 때문에 상각 O(lgn)으로 볼 수 있다.
구현 코드
📃 구현 코드 (c++) ( 접기 / 펼치기 )
/*
* 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;
}