splay tree simulation
https://www.cs.usfca.edu/~galles/visualization/SplayTree.html
-
Run in O(logn) time on average
시간 복잡도는 평균 log n
-
Any single operation can take theta(n)
time in the worst case
어떠한 연산도 theta(n)시간 안에 처리
-
Any sequence of k splay tree
operations, with the tree initially empty and never exceeding n items, takes
O(klogn) worst-case time
어떠한 연속된 k splay 트리 연산도 klogn안에 연산
-
Simpler, faster, easier to
program
간단하고 빠르고 쉽다 프로그램한테
-
Fast access to entries that
have been accessed recently
최근에 접근했던 entry들에 빠르게 접근
-
The most widely used basic data
structure invented in the last 30 years
가장 범융적으로 쓰이는 자료구조 30년전에 만든,
-
Used in windows NT(in the
virtual memory networking), the gcc compiler, GNU c++ library, unix malloc
windows NT, gcc컴파일러, GNU c++ 라이브러리 , unix malloc에 사용
Find(k)
1.
We walk down the tree until w
e find the entry with the key k, or
reach a dead end.
2.
Let x be the node where the
search ended, whether it contains the key k or not.
3.
We splay X up the tree through
a sequence of rotations, so that X becomes the root of the tree.
-recently accessed entries are near the root of the tree
-improve the balance along the branch of the tree
3 case for splaying
Insert(k)
1.
Insert k just like in an
ordinary binary search tree
2.
Splay the new node to the root
Remote(k)
1.
Remove k just like in an
ordinary binary search tree
2.
Let x be the node removed from
the tree
3.
Splay x’s parent to the root
trianing
Your program reads its inputs from the input file “splay.in”,
and outputs its output to the output file “splay.out”. In splay.in, there are
two operations; insert(I) and find(F). For instance, “I 0” means, you have to
insert “0”into the splay tree. Then, you have to print out the modified splay
tree using inorder(I) traversal and preorder(P) traversal. In the below example,
there are six insert operations and one find operation. You have to print out
the modified splay tree after each operation using two traversal algorithms.
===========================================================
splay.in.
I 0
I 1
I 2
I 3
I 4
I 5
F 1
=========================================================
splay.out
I 0
P 0
I 0 1
P 1 0
I 0 1 2
P 2 1 0
I 0 1 2 3
P 3 2 1 0
I 0 1 2 3 4
P 4 3 2 1 0
#include
typedef struct tree_node{
int data;
struct tree_node *left_child, *right_child,*parent;
}*tree_pointer; //트리 구조체 선언
tree_pointer tree;
tree_pointer x;
tree_pointer p, pp;
int arr[1000],cnt=0;
void inorder(tree_pointer ptr);
void preorder(tree_pointer ptr);
tree_pointer insert(tree_pointer tr, int n);
tree_pointer left_rotation(tree_pointer tr);
tree_pointer right_rotation(tree_pointer tr);
tree_pointer splay(tree_pointer object);
tree_pointer find(int n,tree_pointer tr);
int main(){
FILE *fin = fopen("splay.in", "rb");
FILE *fout = fopen("splay.out", "w");
char instruct;
int n,temp;
int i = 0;
tree_pointer k;
tree = (tree_pointer)malloc(sizeof(struct tree_node));
while (1){
temp = fscanf(fin, "%c %d\r", &instruct, &n);
if (temp == -1)
break;
if (instruct == 'I'){
i++;
if (i == 1){
tree->data = n;
tree->left_child = NULL; tree->right_child = NULL; tree->parent = NULL;
}
else{
k = insert(tree, n); //insert해준후
tree = splay(k); //splay를 해주는데 splay를 하면 루트노드가 바뀌기 떄문에 루트노드를 return값으로 주었다.
}
}
else if (instruct == 'F'){
k = find(n,tree); //마찬가지로 find하고
tree = splay(k); //splay해준다
}
else{
fprintf(fout,"WRONG INPUT");
break;
}
cnt = 0;
inorder(tree); //inorder preorder 으로 프린트하는 코드이다.
fprintf(fout,"I ");
for (int j = 0; j < i; j++)
fprintf(fout, "%d ", arr[j]);
fprintf(fout, "\n");
cnt = 0;
preorder(tree);
fprintf(fout,"P ");
for (int j = 0; j < i; j++)
fprintf(fout, "%d ", arr[j]);
fprintf(fout, "\n\n");
}
}
void inorder(tree_pointer ptr){ //그동안 많이 했던 inorder알고릐즘!
if (ptr){
inorder(ptr->left_child);
if (ptr->data != -1) arr[cnt++] = ptr->data;
inorder(ptr->right_child);
}
}
void preorder(tree_pointer ptr){ //preorder알고리즘!!
if (ptr){
if (ptr->data != -1) arr[cnt++] = ptr->data;
preorder(ptr->left_child);
preorder(ptr->right_child);
}
}
tree_pointer insert(tree_pointer tr, char n){ //insert해주는 코드 AVL트리짤때랑 똑같이 짰다
if (tr == NULL)
{
x->data = n;
x->left_child = NULL;
x->right_child = NULL;
tr = x;
return x;
}
else
{
if (n < tr->data)
{
if (tr->left_child == NULL){
x = (tree_pointer)malloc(sizeof(struct tree_node));
x->parent = tr;
}
tr->left_child = insert(tr->left_child, n);
}
else
{
if (tr->right_child == NULL){
x = (tree_pointer)malloc(sizeof(struct tree_node));
x->parent = tr; //parent를 넣어주기 위해 여기에 malloc 코드를 짰다.
}
tr->right_child = insert(tr->right_child, n);
}
}
}
tree_pointer splay(tree_pointer object){
if (object->parent == NULL){
return object;
}
else{
if (object->parent->parent == NULL){ //move to root rotation
if (object->parent->right_child == object){
object = right_rotation(object);
}
else
object = left_rotation(object);
}
else{
p = object->parent;
pp = p->parent;
if (pp->right_child == p&&p->right_child == object){ //zigzig object->parent부터 로테이션을 돌리고 object를 rotation 돌린다.
p = right_rotation(p);
object = right_rotation(object);
}
else if (pp->left_child == p &&p->left_child == object){ //zigzig
p = left_rotation(p);
object = left_rotation(object);
}
else{ //zigzag object로테이션을 두번해준다!
if (object->parent->right_child == object){
object = right_rotation(object);
object = left_rotation(object);
}
else{
object = left_rotation(object);
object = right_rotation(object);
}
}
}
object = splay(object);
}
return object;
}
tree_pointer left_rotation(tree_pointer tr){ //left rotation 코드이다 tr과 tr->parent의 성분을 적절하게 바꾸어 줬다.
x = tr->right_child;
tr->right_child = tr->parent;
tr->right_child->left_child = x;
tr->parent = tr->right_child->parent;
tr->right_child->parent = tr;
if (tr->parent == NULL)
return tr;
else if (tr->parent->right_child == tr->right_child)
tr->parent->right_child = tr;
else
tr->parent->left_child = tr;
return tr;
}
tree_pointer right_rotation(tree_pointer tr){ //마찬가지로 left rotation과 비슷한 right rotation 코드
x = tr->left_child;
tr->left_child = tr->parent;
tr->left_child->right_child = x;
tr->parent = tr->left_child->parent;
tr->left_child->parent = tr;
if (tr->parent == NULL)
return tr;
else if (tr->parent->right_child == tr->left_child)
tr->parent->right_child = tr;
else
tr->parent->left_child = tr;
return tr;
}
tree_pointer find(int n,tree_pointer tr){ //루트붜 내려가면서 data가 n 인 노드를 찾는다.
if (tr->data == n){
return tr;
}
else if (tr->data > n){
find(n, tr->left_child);
}
else if (tr->data < n){
find(n, tr->right_child);
}
}
