탐색(Search) - AVL트리

정의

Adelson-Velskii와 Landis에 의해 1962년에 제안된 트리로서 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1이하인 이진 탐색 트리. AVL트리는 트리가 비균형 상태가 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. 따라서 항상 균형트리로 보장되기 때문에 O(logn)시간 안에 끝나게 된다. 또한 삽입과 삭제 연산도 O(logn)시간 안에 할 수 있다. 균형 상태를 알 수 있게 하는 용어로 균형 인수라는 단어를 사용한다. 균형 인수란 (왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이)로 정의된다. 모든 노드의 균형 인수가 ±1이하이면 AVL트리이다. 아래 그림을 보면 이해가 쉽게 된다.

---

---

탐색 연산

일반적인 이진 탐색 트리와 동일, O(logn)

삽입 연산

삽입 연산 시에 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있으므로 새로운 노드 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드, 즉 균형 인수가 ±2가 된 가장 가까운 조상 노의 서브 트리들에 대하여 다시 균형을 잡아야한다. 균형을 다시 잡는 경우에는 총 4가지의 경우가 있다.

---

---

오른쪽으로 shift하고 오른쪽 서브트리를 오른쪽 형제노드에게 붙여준다.

---

---

왼쪽으로 shift하고 왼쪽 서브트리를 왼쪽에 형제노드에게 붙여준다.

---

---

LR노드를 RR회전(반시계 방향) 후 LR을 LL회전(시계 방향)을 시켜준다.

---

---

RL노드를 LL회전(시계 방향) 후 RL을 RR회전(반시계 방향)을 시켜준다.

---

---

코드

#include<stdio.h> 
#include<stdlib.h> 

// AVL 트리 노드 정의
typedef struct AVLNode
{
	int key;
	struct AVLNode* left;
	struct AVLNode* right;
} AVLNode;

int Max(int x, int y)
{
	if (x >= y)
		return x;
	else return y;
}
// 트리의 높이를 반환
int getHeight(AVLNode* node)
{
	int height = 0;

	if (node != NULL)
		height = 1 + Max(getHeight(node->left),
			getHeight(node->right));

	return height;
}
// 노드의 균형인수를 반환
int getBalance(AVLNode* node)
{
	if (node == NULL) return 0;

	return getHeight(node->left)
		- getHeight(node->right);
}

// 노드를 동적으로 생성하는 함수
AVLNode* createNode(int key)
{
	AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
	node->key = key;
	node->left = NULL;
	node->right = NULL;
	return(node);
}

// 오른쪽으로 회전시키는 함수
AVLNode* rotateRight(AVLNode* parent)
{
	AVLNode* child = parent->left;
	parent->left = child->right;
	child->right = parent;

	// 새로운 루트를 반환
	return child;
}

// 왼쪽으로 회전시키는 함수
AVLNode* rotateLeft(AVLNode* parent)
{
	AVLNode* child = parent->right;
	parent->right = child->left;
	child->left = parent;

	// 새로운 루트 반환
	return child;
}

// AVL 트리에 새로운 노드 추가 함수
// 새로운 루트를 반환한다. 
AVLNode* insert(AVLNode* node, int key)
{
	// 이진 탐색 트리의 노드 추가 수행
	if (node == NULL) // node가 비어있을 때
		return(createNode(key));

	if (key < node->key) // insert할 key값이 현재 노드보다 작을 때
		node->left = insert(node->left, key);
	else if (key > node->key)// insert할 key값이 현재 노드보다 클 때
		node->right = insert(node->right, key);
	else	// 동일한 키는 허용되지 않음
		return node;

	// 노드들의 균형인수 재계산
	int balance = getBalance(node);

	// LL 타입 처리
	if (balance > 1 && key < node->left->key)
		return rotateRight(node);

	// RR 타입 처리
	if (balance < -1 && key > node->right->key)
		return rotateLeft(node);

	// LR 타입 처리
	if (balance > 1 && key > node->left->key)
	{
		node->left = rotateLeft(node->left);
		return rotateRight(node);
	}

	// RL 타입 처리
	if (balance < -1 && key < node->right->key)
	{
		node->right = rotateRight(node->right);
		return rotateLeft(node);
	}
	return node;
}

// 중위 순회 함수
void inorder(AVLNode* root)
{
	if (root != NULL)
	{
		inorder(root->left);
		printf("[%d] ,%d ", root->key, getBalance(root));

		inorder(root->right);
	}
}

//전위순회함수
void preorder(AVLNode* root)
{
	if (root != NULL)
	{

		printf("[%d] ,%d ", root->key, getBalance(root));
		preorder(root->left);
		preorder(root->right);
	}

}
int main(void)
{
	AVLNode* root = NULL;

	// 예제 트리 구축
	root = insert(root, 10);
	root = insert(root, 20);
	root = insert(root, 30);
	root = insert(root, 40);
	root = insert(root, 50);
	root = insert(root, 25);
	root = insert(root, 27);
	root = insert(root, 29);

	printf("중위 순회 결과 \n");
	inorder(root);
	printf("\n\n");
	printf("전위 순회 결과 \n");
	preorder(root);



	return 0;
}