splay tree

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);
	}
}