c++) AVL 트리 ( 삽입, 삭제, 트리 출력 )

알고리즘 카테고리의 AVL 트리 게시글의 내용으로 코드 작성하였습니다.

최대한 트리 모양으로 출력하려고 했는데, UI 프로그램을 쓰지않고 콘솔로 하려니 어렵군요.

좀 비슷하게 흉내내 봤는데, 조금만 트리가 커지면 깨집니다.

그러니까 크게 믿지말고 참고만 하고 쓰세요. ( 트리 모양 출력 부분 )

출력을 제외한 AVL 트리 로직은 맞을 거에요 (아마 ㅎㅎ)

코드

- AVL.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;

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

public:
	AVL();
	AVL(int element);

	// 핵심 매서드
	void insertItem(int element);
	void removeElement(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);

	// avl 트리 매서드
	void repair(Node *now);
	int needRepair(Node *position);

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

	// rotate
	Node *LL(Node *rot);
	Node *RR(Node *rot);
	Node *LR(Node *rot);
	Node *RL(Node *rot);

	// get
	Node *getRoot();

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

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

// 루트 초기화 생성자
AVL::AVL(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 AVL::insertItem(int element) {
	Node *tmp = treeSearch(root, element);

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

// 노드 삭제
void AVL::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);
	}

	// last step
	// 수리
	repair(zs);
}

// 트리 검색
// 원소의 위치를 반환
Node *AVL::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 AVL::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 *AVL::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 *AVL::inOrderSuc(Node *now) {
	Node *tmp = now->rightc;

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

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

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

	return ret;
}

// 노드의 높이를 반환
int AVL::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;
}


/*
** AVL 트리  매서드
*/
// 균형을 맞춤
void AVL::repair(Node *now) {
	Node *tmp = now;

	while (tmp != nullptr) {
		// balance check
		int factor = needRepair(tmp);

		if (factor > 1) {
			if (needRepair(tmp->leftc) > 0) {
				LL(tmp);
			}
			else {
				LR(tmp);
			}
		}
		else if (factor < -1) {
			if (needRepair(tmp->rightc) > 0) {
				RL(tmp);
			}
			else {
				RR(tmp);
			}
		}
		tmp = tmp->parent;
	}
}

// 균형 맞출 필요가 있는지 확인
int AVL::needRepair(Node *position) {
	int left, right;
	Node *leftc = position->leftc;
	Node *rightc = position->rightc;

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

	int dif = left - right;

	return dif;
}


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

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


// rotate
// from left -> a , b , c  nodes 
Node *AVL::LL(Node *rot) {
	Node *tmp = rot->leftc;

	// b -> top
	tmp->parent = rot->parent;
	if (isRoot(tmp)) root = tmp;
	else {
		if (rot == rot->parent->leftc) rot->parent->leftc = tmp;
		else rot->parent->rightc = tmp;
	}

	// T_2 to c
	rot->leftc = tmp->rightc;
	tmp->rightc->parent = rot;

	// b and c link
	tmp->rightc = rot;
	rot->parent = tmp;

	return tmp;
}

Node *AVL::RR(Node *rot) {
	Node *tmp = rot->rightc;

	// b -> top
	tmp->parent = rot->parent;
	if (isRoot(tmp)) root = tmp;
	else {
		if (rot == rot->parent->leftc) rot->parent->leftc = tmp;
		else rot->parent->rightc = tmp;
	}

	// T_1 to a
	rot->rightc = tmp->leftc;
	tmp->leftc->parent = rot;

	// a and b link
	tmp->leftc = rot;
	rot->parent = tmp;

	return tmp;
}

Node *AVL::RL(Node *rot) {
	// first step
	Node *tmp = rot->rightc;
	Node *tmp2 = LL(tmp);
	rot->rightc = tmp2;
	tmp2->parent = rot;

	// last step
	return RR(rot);
}

Node *AVL::LR(Node *rot) {
	// first step
	Node *tmp = rot->leftc;
	Node *tmp2 = RR(tmp);
	rot->leftc = tmp2;
	tmp2->parent = rot;

	// last step
	return LL(rot);
}


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


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

// 트리 모양 출력
void AVL::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;
}

- main.cpp

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

using namespace std;

#define NUM 10

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

	cout << "AVL Tree Test Start !!! " << endl;
	AVL avlTree((int)(rand()%20+1));
	avlTree.display();
	cout << endl << endl;
	cout << "***********************************************************************" << endl << endl << endl;

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

	cout << endl << endl << "AVL Tree Result !!! " << endl;
	avlTree.display();

	cout << "***********************************************************************" << endl << endl << endl;

	// remove
	cout << endl << endl << endl << "AVL Tree Remove Test !!!" << endl;
	while (1) {
		int n;
		cout << "this turn remove value(0 : end the program) : ";
		cin >> n;
		if (n == 0) break;
		avlTree.removeElement(n);
		avlTree.display();
	}
	return 0;
}

실행 화면

보시면 원소 1이 삽입되는 순간, LL 회전을 하게 됩니다.

균형을 유지했죠?

원소 입력을 계속 받으면서..

(중복 데이터는 받지 않았습니다.)

이렇게!!

찌부러진 트리가 완성됬습니다.

( 누가 트리 작성 코드 고쳐서 저에게 제공좀.. )

이제 삭제 작업입니다.

위 트리에서 ( 8 데이터 ) 를 삭제했는데요.

하나가지고는 티도 안나군요.

이번에는 ( 1과 4 데이터) 두개를 삭제해보겠습니다. 균형을 맞추나 볼게요.

다행히 아직은 잘 유지되네요.

그럼 마지막으로 루트 데이터를 제거해보고 마무리 짓겠습니다.

이상 무!

마무리

트리 모양 출력하는 코드 작성하는게 복잡하군요.

지쳐서 안떠오르는건지

하드 코딩으로 하다보니 트리의 노드 개수가 증가하면 할수록 박살납니다.

ㅎㅎ!

코드의 문제점 발견되면 말씀해주세요!

저도 피드백 하게 ㅜㅜ

혼자만 알고 넘어가시지 말구요!

스플레이 트리랑 RB 트리만 하고 탐색 트리는 마무리 해야겠어요.

시간 나는대로 해서 11월 안에 탐색 트리 마무리 하는것이 목표입니다.

올해 안에 그래프까지 할 수 있을지 모르겠군요.. 노력하겠습니다.