Sign in Subscribe
4 min read

[밸런싱 트리] AVL Tree

밸런싱 트리에서 가장 간단한 AVL트리이다.

이 트리는 밸런싱은 회전으로 구한다.

적당한 그림이 없어 위키피디아에서 가져왔다.

위의 그림에서 보듯이 오른쪽으로 편향되어있어서 RR트리라고 한다.

반대로 왼쪽이면 LL이라고 한다. 이런 경우 밸런싱하기 위해서는 RR트리인경우 오른쪽으로 편향되어있으니 왼쪽으로 회전시켜 밸런싱을 구한다.

LL경우인경우는 RR트리를 반대로 회전 하면된다.

위의 그림은 오른쪽하고 왼쪽으로 편향되어 있는걸 볼수 있다.

이를 RL트리라고 하며 반대는 LR 트리가 있다.

쉽게 밸런싱하는 방법은 어떻게 할까 다른방법이 있겠지만 가장 쉽게 접근하는 방법은 우리가 아는 LL,RR트리로 바꾸어주면 된다.

 위에 사진은 RL트리이여 RL트리로 설명을 하자면

RL트리를 LL,RR트리로 바꾸어주면 된다고 앞서 설명을 했다.

그치만 RR트리로 바꾸는게 편할까 LL트리로 바꾸는게 편할까를 한번 생각해보면

앞에 있는 R을 L로 바꾸면 LL로 바꾸버리겠지만 이는 다른 트리에 밸런싱이 쉽게 깨지고  또한 구현이 힘들다 그래서 RR트리로 바꾸어 준다.

바꾸어 주는 방법은 오른쪽으로 한번 회전 시켜주면 된다.

이제 RL트리가 RR트리로 바꾸어지게 되었다.

RR트리를 밸런싱하는법은 앞서 설명한 방법을 통해서 밸런싱을 하면된다.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
 
#include <algorithm>
#include <iostream>

struct Node {
	Node(int n) {
		val = n;
		left = right = nullptr;
	}
	int val;
	Node * left, *right;

};

class AVLTree {
public:
	AVLTree() {
		head = nullptr;
	}
	bool insert(int v) {
		head = insertImp(head, v);
		return true;
	}
	Node* insertImp(Node * pa, int v) {
		Node * ptr;
		if (pa == nullptr) {
			pa = new Node(v);
			return pa;
		}
		if (pa->val == v) return pa;

		if (pa->val > v) pa->left = insertImp(pa->left, v);
		else if (pa->val < v) pa->right = insertImp(pa->right, v);

		int diff = getHeightDiff(pa);
		if (diff > 1) {
			if (getHeight(pa->left->left) > getHeight(pa->left->right)) {
				pa = route_LL(pa);
			}
			else {
				pa = route_LR(pa);
			}
		}
		else if (diff < -1) {
			//RL
			if (getHeight(pa->right->right) > getHeight(pa->right->left)) {
				pa = route_RR(pa);
			}//RR
			else {
				pa = route_RL(pa);
			}

		}
		return pa;
	}
	Node * route_LL(Node * node) {

		Node * preRoot = node->left;
		node->left = preRoot->right;
		preRoot->right = node;

		return preRoot;
	}
	Node * route_LR(Node * node) {
		node->left = route_RR(node->left);
		return route_LL(node);
	}
	Node * route_RR(Node * node) {

		Node * preRoot = node->right;
		node->right = preRoot->left;
		preRoot->left = node;
		return preRoot;
	}
	Node * route_RL(Node * node) {
		node->right = route_LL(node->right);
		return route_RR(node);
	}


int getHeightDiff(Node * head) {
	return getHeight(head->left) - getHeight(head->right);
}
int getHeight(Node * h) {
	if (h == nullptr)
		return 0;
	return 1 + std::max(getHeight(h->left), getHeight(h->right));
}

Node * head;

};

int main()
{
	AVLTree avltree;
	avltree.insert(10);
	avltree.insert(20);
	avltree.insert(30);
	avltree.insert(40);
	avltree.insert(50);
	avltree.insert(25);
	avltree.insert(2);
	avltree.insert(100);


	return 0;
}

 

삭제같은경우는 꽤 간단하니 위키피디아에서 검색해서 구현해보는걸 추천한다.

Published by:

rinechran