#4. AVL 트리

1.AVL트리는 균형이 갖춰진 이진트리를 의미한다.

2.완전 이진트리는 검색에 있어서 O(logN)의 시간 복잡도를 유지할 수 있다.

3.AVL트리는 간단한 구현과정으로 특정 이진 트리가 완전 이진 트리에 가까운 형태를 유지하도록 해준다.

 

AVL트리를 통해 얻는 이점?

 

한쪽으로 편향되어있는 트리 같은경우 너비우선탐색을 좀 더 효율적으로 만들어 줄 수있다.

 

균형인수를 통해 알고리즘을 세운다.

균형인수란? = ㅣ왼쪽 자식 높이 - 오른쪽 자식 높이ㅣ

 

특징

 

1.AVL트리느 모든 노드에 대한 균형 인수가 +1, 0 , -1 인 트리를 의미한다.

2.균형 인수가 위 세 가지 경우에 해당하지 않는 경우 '회전'을 통해 트리를 재구성한다.

3.AVL트리의 각 노드는 '균형 인수'를 계산하기 위한 목적으로 자신의 '높이' 값을 가진다.

 

 

균형이 깨지는 경우

1.LL형식: X의 왼쪽 자식의 왼쪽에 삽입하는 경우

 

 

LL형식

2.LR형식: X의 왼쪽 자식의 오른쪽에 삽입하는 경우

 

LR형식

3.RR형식:X의 오른쪽 자식의 오른쪽에 삽입하는 경우

RL형식

4.RL형식:X의 오른쪽 자식의 왼쪽에 삽입하는 경우

 

RR형식

 

 

코드예시

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


int getMax(int a, int b) {
	if (a > b) return a;
	return b;
}

typedef struct {
	int data;
	int height; //높이를 저장해야 시간 복잡도 보장.
	struct Node* leftChild;
	struct Node* rightChild;
} Node;

int getHeight(Node* node) {
	if (node == NULL) return 0;
	return node->height;
}

//모든 노드는 회전을 수행한 이후에 높이를 다시 계산
void setHeight(Node* node) {
	node->height = getMax(getHeight(node->leftChild), getHeight(node->rightChild)) + 1;
}//왼쪽자식의 높이,오른쪽자식의 높이 중 더 큰놈에다가 +1 한것이 본인 높이



//균형인수 구하는 함수
int getDifference(Node* node) {
	if (node == NULL) return 0;
	Node* leftChild = node->leftChild;
	Node* rightChild = node->rightChild;
	return getHeight(leftChild) - getHeight(rightChild);  //균형인수:ㅣ왼쪽노드-오른쪽노드ㅣ
}


//AVL트리의 LL회전

Node* rotateLL(Node* node) {
	Node* leftChild = node->leftChild;
	node->leftChild = leftChild->rightChild;
	//기존의 왼쪽노드가 기존의 왼쪽자식의 오른쪽 자식이된다.
	leftChild->rightChild = node;
	//왼쪽자식의 오른쪽자식으로 노드값이 들어간다.
	setHeight(node);
	//회전 이후에 높이를 다시 계산
	return leftChild; 
	//leftChild 는 이후에 setHeight()수행
}


//AVL트리의 RR회전
Node* rotateRR(Node* node) {
	Node* rightChild = node->rightChild;
	node->rightChild = rightChild->leftChild;
	rightChild->leftChild = node;
	setHeight(node);
	//회전 이후에 높이를 다시 계산
	return rightChild;
	//leftChild 는 이후에 setHeight()수행
}


//AVL트리의LR회전
Node* rotateLR(Node* node) {
	Node* leftChild = node->leftChild;
	node->leftChild = rotateRR(leftChild);
	return rotateLL(node);
}

//AVL트리의 RL회전
Node* rotateRL(Node* node) {
	Node* rightChild = node->rightChild;
	node->rightChild = rotateLL(rightChild);
	return rotateRR(node);
}

//AVL트리의 균형잡기

Node* balance(Node* node) {
	int difference = getDifference(node);
	if (difference >= 2) {
		if (getDifference(node->leftChild) >= 1) {
			node = rotateLL(node);
		}
		else{
			node = rotateLR(node);
		}
	}
	else if (difference <= -2) {
		if (getDifference(node->rightChild) <= -1) {
			node = rotateRR(node);
		}
		else {
			node = rotateRL(node);
		}
	}
	setHeight(node);
	return node;
}

//AVL 트리의 삽입

Node* insertNode(Node* node, int data) {
	if (!node) {
		node = (Node*)malloc(sizeof(Node));
		node->data = data;
		node->height = 1;
		node->leftChild = node->rightChild = NULL;
	}
	else if (data < node->data) {
		node->leftChild = insertNode(node->leftChild, data);
		node = balance(node);
	}
	else if (data > node->data) {
		node->rightChild = insertNode(node->rightChild, data);
		node = balance(node);
	}
	else {
		printf("데이터 중복이 발생헀습니다.\n");
	}
	return node;
}

//AVL트리 출력함수

Node* root = NULL;

void display(Node* node, int level) {
	if (node != NULL) {
		display(node->rightChild, level + 1);
		printf("\n");
		if (node == root) {
			printf("Root: ");
		}
		for (int i = 0; i < level && node != root; i++) {
			printf("    ");
		}
		printf("%d(%d)", node->data, getHeight(node));
		display(node->leftChild, level + 1);
	}
}

//AVL트리 이용

int main(void) {
	root = insertNode(root, 17);
	root = insertNode(root, 26);
	root = insertNode(root, 5);
	root = insertNode(root, 10);
	root = insertNode(root, 1); 
	root = insertNode(root, 9);
	root = insertNode(root, 8);
	root = insertNode(root, 12);
	root = insertNode(root, 16);
	root = insertNode(root, 28);
	root = insertNode(root, 23);
	root = insertNode(root, 21);
	root = insertNode(root, 14);
	root = insertNode(root, 55);
	root = insertNode(root, 24);
	root = insertNode(root, 20);
	display(root, 1); printf("\n");
	system("pause");

}

결과값

                    55(1)
                28(2)
            26(3)
                24(1)
        23(4)
                21(2)
                    20(1)
            17(3)
                    16(1)
                14(2)
                    12(1)
Root: 10(5)
            9(2)
                8(1)
        5(3)
            1(1)

 

 

 

 

코드의 길이가 기본 100줄이상 슬슬 넘어가기 시작하니,

구동은 되나, 결과값이 제대로 도출 되지않아 어디부분이 잘못된건지 한참 찾았다..

알파벳 하나 안씀으로 인해, 났다는걸 인지 못한채 암만 봐도 결과값이 제대로 안나와서 매우 많이 해매다가,, 후,,

많은 시간을 삽질 한 만큼,,, 경험치가 쌓였으면 좋겠다,,