c++) 스플레이 트리 (Splay Tree)

Splay Tree 코드 게시글입니다.

지난번에 포스팅했던, AVL 트리 코드를 거의 그대로 가져다 썼습니다. ㅎㅎ

그래서 쓰지 않는 메서드들도 꽤 있네요 ㅎㅎ ㅜㅜ

정리가 좀 안된 감이 있지만, 코드 자체가 쉬우니 금방 이해하실 수 있을겁니다.

코드

- main.cpp

#include "Splay.h"
#include <ctime>
#include <cstdlib>

#define NUM 6

int main() {
	srand((unsigned int)time(nullptr));

	cout << "Splay Tree Test Start !!! " << endl;
	Splay splayT((int)(rand() % 20 + 1));

	cout << "root : " << splayT.getRoot()->data << endl;
	splayT.print(splayT.getRoot());

	for (int i = 0; i < NUM; ++i) {
		int t = (int)(rand() % 20 + 1);
		cout << endl << endl << "this turn's value : " << t << endl;
		splayT.insertItem(t);

		cout << "root : " << splayT.getRoot()->data << endl;
		splayT.print(splayT.getRoot());
	}

	cout << endl << endl << "Splay Tree Result !!! " << endl;
	cout << "root : " << splayT.getRoot()->data << endl;
	splayT.print(splayT.getRoot());



	// find
	cout << endl << endl << endl << "Splay Tree Find Test !!!" << endl;
	while (1) {
		int n;
		cout << "this turn find value(0 : end the program) : ";
		cin >> n;
		if (n == 0) break;

		splayT.findElement(n);
		cout << "root : " << splayT.getRoot()->data << endl;
	}


	// remove
	cout << endl << endl << endl << "Splay Tree Remove Test !!!" << endl;
	while (1) {
		int n;
		cout << "this turn remove value(0 : end the program) : ";
		cin >> n;
		if (n == 0) break;

		splayT.removeElement(n);
		cout << "root : " << splayT.getRoot()->data << endl;
		splayT.print(splayT.getRoot());
		cout << endl;
	}

	return 0;
}

- Splay.h

#pragma once
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <queue>

using namespace std;

// 노드 정보
typedef struct Node {
	Node *parent = nullptr;
	Node *leftc = nullptr;
	Node *rightc = nullptr;
	int data = NULL;
} Node;

// Splay Tree Class
class Splay {
	Node *root;

public:
	Splay();
	Splay(int element);

	// 핵심 매서드
	void insertItem(int element);
	void removeElement(int element);
	void findElement(int element);
	Node *treeSearch(Node *now, int element);

	// 트리 기본 매서드
	void expand(Node *external, int element);
	Node *reduce(Node *external);
	Node *inOrderSuc(Node *now);
	int depth(Node *now);
	int height(Node *now);

	// Splay 트리 매서드
	void doSplay(Node *now);
	
	// rotate
	void rightRotate(Node *x, Node *y);
	void leftRotate(Node *x, Node *y);

	// 트리 boolean 매서드
	bool isRoot(Node *tmp);
	bool isExternal(Node *tmp);

	// get
	Node *getRoot();

	// print
	void display();
	void print(Node *p);
};

// 생성자
Splay::Splay() {}

// 루트 초기화 생성자
Splay::Splay(int element) {
	root = new Node;
	root->data = element;
	root->parent = nullptr;
	root->leftc = new Node;
	root->rightc = new Node;

	root->leftc->parent = root;
	root->rightc->parent = root;
}

/*
** 핵심 메서드
*/
// 노드 삽입
void Splay::insertItem(int element) {
	Node *tmp = treeSearch(root, element);

	if (isExternal(tmp)) {
		expand(tmp, element);
		doSplay(tmp);
	}
}

// 노드 삭제
void Splay::removeElement(int element) {
	Node *tmp = treeSearch(root, element);

	if (isExternal(tmp)) {
		cout << " No Such Key" << endl;
		return;
	}

	// first step
	// 삭제
	Node *child = tmp->leftc;
	if (!isExternal(child)) {
		child = tmp->rightc;
	}

	Node *zs;

	// 둘 중 하나라도 외부노드라면
	if (isExternal(child)) {
		zs = reduce(child);
	}
	// 둘 다 내부노드라면
	else {
		// 중위 순회 계승자
		// inOrder Successor
		child = inOrderSuc(tmp);
		Node *y = child->parent;

		// y 값 tmp 위치에 복사 (제거하려는 노드 위치에)
		tmp->data = y->data;

		// child, y 제거
		zs = reduce(child);
	}

	// 부모 splay
	doSplay(zs->parent);
}

// 사전 검색
void Splay::findElement(int element) {
	Node *tmp = treeSearch(root, element);

	// 값이 없다면
	if (isExternal(tmp)) {
		cout << "No Such Key" << endl;
		
		// 부모를 Splay
		doSplay(tmp->parent);
	}
	// 값이 있다면
	else {
		cout << "fond element " << tmp->data << endl;
		
		// 자신을 스플레이
		doSplay(tmp);
	}
}

// 트리 검색
// 원소의 위치를 반환
Node *Splay::treeSearch(Node *now, int element) {
	if (element == now->data) return now;

	Node *tmp = nullptr;
	if (element < now->data) {
		tmp = now->leftc;
	}
	else {
		tmp = now->rightc;
	}

	if (isExternal(tmp)) return tmp;
	treeSearch(tmp, element);
}


/*
** 트리 기본 매서드
*/
// 내부 노드로 확장
void Splay::expand(Node *external, int element) {
	external->data = element;
	external->leftc = new Node;
	external->rightc = new Node;

	external->leftc->parent = external;
	external->rightc->parent = external;
}

// 노드 제거
Node *Splay::reduce(Node *external) {
	Node *w = external->parent;
	Node *g = w->parent;

	// sibling
	Node *zs;
	if (external == w->leftc) {
		zs = w->rightc;
	}
	else {
		zs = w->leftc;
	}

	// connect with grandparent;
	zs->parent = g;

	if (w == g->leftc) {
		g->leftc = zs;
	}
	else {
		g->rightc = zs;
	}

	// deallocate
	delete external;
	delete w;

	return zs;
}

// 중위 순휘 계승자
Node *Splay::inOrderSuc(Node *now) {
	Node *tmp = now->rightc;

	while (!isExternal(tmp)) {
		tmp = tmp->leftc;
	}
	return tmp;
}

// 깊이를 반환
int Splay::depth(Node *now) {
	int ret = 0;

	while (!isRoot(now)) {
		now = now->parent;
		++ret;
	}

	return ret;
}

// 노드의 높이를 반환
int Splay::height(Node *now) {
	int h = 0;
	int left = 0, right = 0;

	if (now->leftc->data != NULL) {
		left = height(now->leftc);
	}
	if (now->rightc->data != NULL) {
		right = height(now->rightc);
	}

	int maxHeight = max(left, right);
	h = 1 + maxHeight;

	return h;
}


/*
** Splay 트리  매서드
*/
void Splay::doSplay(Node *now) {
	// 예외처리
	if (now == nullptr) return;

	// 루트에 도착하면 종료
	if (isRoot(now)) {
		root = now;
		return;
	}

	// 부모가 루트인가?
	if (isRoot(now->parent)) {
		if (now == now->parent->leftc) {
			rightRotate(now, root);
		}
		else {
			leftRotate(now, root);
		}
		root = now;
		return;
	}

	// 나머지 경우
	Node *p = now->parent;
	Node *gp = p->parent;

	if (now == gp->leftc->leftc) {
		rightRotate(p, gp);
		rightRotate(now, p);
	}
	else if (now == gp->rightc->rightc) {
		leftRotate(p, gp);
		leftRotate(now, p);
	}
	else if (now == gp->rightc->leftc) {
		rightRotate(now, p);
		leftRotate(now, gp);
	}
	else {
		leftRotate(now, p);
		rightRotate(now, gp);
	}

	// recur
	doSplay(now);
}

/*
** Rotate
*/
// Right
void Splay::rightRotate(Node *x, Node *y) {
	y->leftc = x->rightc;
	x->rightc->parent = y;

	x->parent = y->parent;
	if (y->parent != nullptr) {
		if (y == y->parent->leftc) y->parent->leftc = x;
		else y->parent->rightc = x;
	}

	x->rightc = y;
	y->parent = x;
}

// Left
void Splay::leftRotate(Node *x, Node *y) {
	y->rightc = x->leftc;
	x->leftc->parent = y;

	x->parent = y->parent;
	if (y->parent != nullptr) {
		if (y == y->parent->leftc) y->parent->leftc = x;
		else y->parent->rightc = x;
	}

	x->leftc = y;
	y->parent = x;
}


/*
** 트리 boolean 매서드
*/
// 루트인가?
bool Splay::isRoot(Node *tmp) {
	return tmp->parent == nullptr;
}

// 외부 노드인가?
bool Splay::isExternal(Node *tmp) {
	return tmp->data == NULL;
}


// get
Node *Splay::getRoot() {
	return root;
}

// 출력
// inorder
void Splay::print(Node *p) {
	if (!isExternal(p->leftc)) print(p->leftc);
	cout << p->data << " ";
	if (!isExternal(p->rightc)) print(p->rightc);
}

// 트리 모양 출력
void Splay::display() {
	int n = depth(root);
	int width = 40;

	queue<Node*> level;

	level.push(root);

	cout << "***********************************************************************" << endl;
	while (!level.empty()) {
		if (n != depth(level.front())) {
			n = depth(level.front());
			width /= 2;
			cout << endl;
		}

		Node *now = level.front();

		if (now->leftc != nullptr)	level.push(now->leftc);
		if (now->rightc != nullptr)	level.push(now->rightc);

		cout << setw(width);

		if (now->data != NULL) cout << now->data;
		else cout << " ";

		cout << setw(width) << "";
		level.pop();
	}
	cout << endl;
}

실행 화면

- 노드 삽입

- 노드 탐색

- 노드 삭제

이제,RB 트리만 하면 다음 챕터로 넘어 가겠군요.

빨강~까망트리 빨리 하고 탐색트리 마무리 하고싶네요.