[알고리즘] 트리5 - 균형 이진 탐색 트리(AVL)

알고리즘

[알고리즘] 트리5 - 균형 이진 탐색 트리(AVL)

sundori 2023. 11. 14. 21:50

2023.11.13 - [알고리즘] - [알고리즘] 트리 4 - 이진 탐색 트리

[알고리즘] 트리4 - 이진 탐색 트리

이진 탐색 트리 이진트리는 트리를 효율적으로 구현하고 관리하기 위해서 일정한 조건으로 정의한 것이며, 이진트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정해둔

sun-dori.tistory.com

균형 이진 탐색 트리

이진 탐색 트리에서 좌우 균형이 올바르다면 탐색을 할 때 성능이 좋고 이 성능은 탐색 트리의 높이와 밀접한 상관관계를 가진다.

높이가 3인 (a) 트리에서는 17을 탐색하려면 루트 노드 8에서 비교 연산을 4번을 수행해야 하지만...

높이가 5인 (b) 트리에서는 17을 탐색하려면 (a) 트리보다 더 많은 비교 연산이 필요하다..

n개의 노드를 가진 이진 탐색 트리에서 비교 연산 횟수는 최소 높이를 가진 경우에는 $0(\log_{2} n)$가 되지만... (b) 같은 트리의 최고 높이를 가진 트리는 $0(n)$이 된다. 따라서 한쪽으로 치우치지 않고 균형을 이루도록 맞춰주면 탐색 성능을 높일 수 있다.
이러한 원리로 균형 조건을 추가한 트리를 균형 이진 탐색 트리(Balanced Binary Search Tree) 또는 균형 트리(Balanced Tree)라 함.

AVL 트리의 개념과 유형

이 트리는 Adelson-Velskii. Landis Tree의 줄임말인데 그냥 아델슨 아저씨와 란디스 아저씨가 제안한 대표적인 균형 이진트리이다.

각 노드에서 왼쪽 서브 트리의 높이 hL( height of Left subtree )과 오른쪽 서브 트리의 높이 hR( height of Right subtree )의 차이가 1 이하인 균형 트리로서 밑에와 같은 특징을 가진다.

왼쪽 서브 트리 < 부모 노드 < 오른쪽 서브 트리 순의 크기 관계를 가진다.
각 노드의 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이 (hL-hR)인 노드의 균형 인수(BF: Balance Factor)를 관리한다.
각 노드의 균형 인수로 {-1, 0, +1}의 값만 가지게 해서 왼쪽 서브 트리와 오른쪽 서브 트리의 균형을 유지한다.

BF = hL - hR

AVL 트리의 회전 연산

불균형의 유형과 원인	해결 방법
LL유형: 불균형 발생 노드의 왼쪽 자식 노드와 자식의 왼쪽 사직 노드에 의해 왼쪽으로 치우친 현상.	LL회전: 치우친 구간 중 상위 구간을 오른쪽으로 회전
RR유형: 불균형 발생 노드의 오른쪽 자식 노드와 자식의 오른쪽 자식 노드에 의해 오른쪽으로 치우친 현상.	RR회전: 치우친 구간 중 상위 구간을 왼쪽으로 회전
LR유형: 불균형 발생 노드의 왼쪽 자식 노드와 자식의 오른쪽 자식 노드에 의해 왼족 서브 트리가 치우친 현상	LR회전: 치우친 구간 중 하위 구간을 왼쪽으로 1차 회전 후 2차적으로 LL회전을 적용
RL유형: 불균형 발생 노드의 오른쪽 자식 노드와 자식의 왼쪽 자식 노드에 의해 오른쪽 서브 트리가 치우친 현상	RL회전: 치우친 구간 중 하위 구간을 오른쪽으로 1차 회전 후 2차적으로 RR회전을 적용

LL 회전 연산

LL 회전 또는 Left_Left 회전은 삽입/삭제 연산 후에 AVL 트리에 불균형이 생겼을 때 적용하는데...

// LL 회전
treeNode* LL_rotate(treeNode* parent) {
    treeNode* child = parent->left;  // 부모의 왼쪽 자식을 가져온다.
    parent->left = child->right;     // 부모의 왼쪽 자식을 child의 오른쪽 자식으로 연결
    child->right = parent;           // child의 오른쪽 자식을 부모로 만든다.
    return child;                    // 회전된 서브트리의 새로운 루트 노드인 child를 반환
}

RR 회전 연산

RR 회전 또는 Right_Right 회전은 삽입/삭제 연산 후에 AVL 트리에 불균형이 생겼을 때 적용하는데...

// RR 회전
treeNode* RR_rotate(treeNode* parent) {
    treeNode* child = parent->right; // 부모의 오른쪽 자식을 가져온다.
    parent->right = child->left;     // 부모의 오른쪽 자식을 child의 왼쪽 자식으로 연결
    child->left = parent;            // child의 왼쪽 자식을 부모로 만든다.
    return child;                    // 회전된 서브트리의 새로운 루트 노드인 child를 반환
}

LR 회전 연산

LR 회전 또는 Left_Right 회전은 삽입/삭제 연산 후에 AVL 트리에 불균형이 생겼을 때 적용하는데...

// LR 회전
treeNode* LR_rotate(treeNode* parent) {
    treeNode* child = parent->left;  // 부모의 왼쪽 자식을 가져온다
    parent->left = RR_rotate(child); // 왼쪽 자식에 RR 회전을 적용하여 균형을 잡는다
    return LL_rotate(parent);        // 부모 노드에 LL 회전을 적용하여 균형을 잡고 새로운 루트를 반환
}

RL 회전 연산

RL 회전 또는 Right_Left 회전은 삽입/삭제 연산 후에 AVL 트리에 불균형이 생겼을 때 적용하는데...

// RL 회전
treeNode* RL_rotate(treeNode* parent) {
    treeNode* child = parent->right; // 부모의 오른쪽 자식을 가져온다
    parent->right = LL_rotate(child); // 오른쪽 자식에 LL 회전을 적용하여 균형을 잡는다
    return RR_rotate(parent);        // 부모 노드에 RR 회전을 적용하여 균형을 잡고 새로운 루트를 반환
}

AVL 트리의 구현

본 코드는 이진 탐색 트리(BST)와 균형 이진 탐색 트리(AVL)의 연산 횟수를 비교하기 위해 작성하였다.

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

#define MAX(a,b) ((a>b)?a:b)
typedef int element; // 이진 탐색 트리 element의 자료형 정의

typedef struct treeNode {
    element key;                // 노드에 저장될 키 값
    struct treeNode* left;      // 왼쪽 서브트리를 가리키는 포인터
    struct treeNode* right;    // 오른쪽 서브트리를 가리키는 포인터
} treeNode;

// LL 회전
treeNode* LL_rotate(treeNode* parent) {
    treeNode* child = parent->left;  // 부모의 왼쪽 자식을 가져옵니다.
    parent->left = child->right;     // 부모의 왼쪽 자식을 child의 오른쪽 자식으로 연결
    child->right = parent;           // child의 오른쪽 자식을 부모로 만듭니다.
    return child;                    // 회전된 서브트리의 새로운 루트 노드인 child를 반환
}

// RR 회전
treeNode* RR_rotate(treeNode* parent) {
    treeNode* child = parent->right; // 부모의 오른쪽 자식을 가져옵니다.
    parent->right = child->left;     // 부모의 오른쪽 자식을 child의 왼쪽 자식으로 연결
    child->left = parent;            // child의 왼쪽 자식을 부모로 만듭니다.
    return child;                    // 회전된 서브트리의 새로운 루트 노드인 child를 반환
}

// LR 회전
treeNode* LR_rotate(treeNode* parent) {
    treeNode* child = parent->left;  // 부모의 왼쪽 자식을 가져온다
    parent->left = RR_rotate(child); // 왼쪽 자식에 RR 회전을 적용하여 균형을 잡는다
    return LL_rotate(parent);        // 부모 노드에 LL 회전을 적용하여 균형을 잡고 새로운 루트를 반환
}

// RL 회전
treeNode* RL_rotate(treeNode* parent) {
    treeNode* child = parent->right; // 부모의 오른쪽 자식을 가져온다
    parent->right = LL_rotate(child); // 오른쪽 자식에 LL 회전을 적용하여 균형을 잡는다
    return RR_rotate(parent);        // 부모 노드에 RR 회전을 적용하여 균형을 잡고 새로운 루트를 반환
}

// 높이 반환
int getHeight(treeNode* p) {
    int height = 0;
    if (p != NULL) height = MAX(getHeight(p->left), getHeight(p->right)) + 1; // 노드의 높이를 재귀적으로 계산
    return height;
}

// 균형 인수(Balance Factor) 반환
int getBF(treeNode* p) {
    if (p == NULL) return 0;
    return getHeight(p->left) - getHeight(p->right); // 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이를 반환
}

// 균형 잡기
treeNode* rebalance(treeNode** p) {
    int BF = getBF(*p); // 노드의 균형 인수를 가져온다
    if (BF > 1) {       // 왼쪽 서브트리가 오른쪽 서브트리보다 높게 나타날 때
        if (getBF((*p)->left) > 0)
            *p = LL_rotate(*p); // LL 회전을 적용
        else *p = LR_rotate(*p); // LR 회전을 적용
    }
    else if (BF < -1) { // 오른쪽 서브트리가 왼쪽 서브트리보다 높게 나타날 때
        if (getBF((*p)->right) < 0)
            *p = RR_rotate(*p); // RR 회전을 적용
        else *p = RL_rotate(*p); // RL 회전을 적용
    }
    return *p; // 새로운 루트 노드를 반환
}

// AVL 트리에 노드 삽입
treeNode* insertAVLNode(treeNode** root, element x) {
    if (*root == NULL) {
        *root = (treeNode*)malloc(sizeof(treeNode));
        (*root)->key = x;
        (*root)->left = NULL;
        (*root)->right = NULL;
    }
    else if (x < (*root)->key) {
        (*root)->left = insertAVLNode(&((*root)->left), x); // 왼쪽 서브트리에 삽입하고 균형을 잡는다
        *root = rebalance(root);
    }
    else if (x > (*root)->key) {
        (*root)->right = insertAVLNode(&((*root)->right), x); // 오른쪽 서브트리에 삽입하고 균형을 잡는다
        *root = rebalance(root);
    }
    else {
        printf("\n 중복된 값이 존재합니다!\n");
        exit(1);
    }
    return *root; // 새로운 루트 노드를 반환
}

// 이진 탐색 트리에서 노드 탐색
treeNode* searchBST(treeNode* root, element x) {
    treeNode* p;
    int count = 0;
    p = root;
    while (p != NULL) {
        count++;
        if (x < p->key) p = p->left;
        else if (x == p->key) {
            printf("%3d회 검색 : 키를 찾았습니다.", count);
            return p;
        }
        else p = p->right;
    }
    count++;
    printf("%3d회 검색 : 키를 찾지 못했습니다.", count);
    return p;
}

// 이진 탐색 트리에 노드 삽입
treeNode* insertBSTNode(treeNode* p, element x) {
    treeNode* newNode;
    if (p == NULL) {
        newNode = (treeNode*)malloc(sizeof(treeNode));
        newNode->key = x;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    else if (x < p->key)  p->left = insertBSTNode(p->left, x);
    else if (x > p->key)  p->right = insertBSTNode(p->right, x);
    else  printf("\n 중복된 값이 존재합니다!\n");

    return p;
}

// 이진 탐색 트리에서 노드 삭제
void deleteBSTNode(treeNode* root, element key) {
    treeNode* parent, * p, * succ, * succ_parent;
    treeNode* child;

    parent = NULL;
    p = root;
    while ((p != NULL) && (p->key != key)) {  // 키를 찾거나 리프 노드까지 이동
        parent = p;
        if (key < p->key) p = p->left;
        else p = p->right;
    }

    // 키가 존재하지 않을 때
    if (p == NULL) {
        printf("\n 키가 존재하지 않습니다.");
        return;
    }

    // 리프 노드 삭제
    if ((p->left == NULL) && (p->right == NULL)) {
        if (parent != NULL) {
            if (parent->left == p) parent->left = NULL;
            else parent->right = NULL;
        }
        else root = NULL;
    }

    // 자식이 하나인 노드 삭제
    else if ((p->left == NULL) || (p->right == NULL)) {
        if (p->left != NULL) child = p->left;
        else child = p->right;

        if (parent != NULL) {
            if (parent->left == p) parent->left = child;
            else parent->right = child;
        }
        else root = child;
    }

    // 자식이 둘인 노드 삭제
    else {
        succ_parent = p;
        succ = p->left;
        while (succ->right != NULL) { // 왼쪽 서브트리에서 가장 큰 값을 찾는다.
            succ_parent = succ;
            succ = succ->right;
        }
        if (succ_parent->left == succ)  succ_parent->left = succ->left;
        else succ_parent->right = succ->left;
        p->key = succ->key;
        p = succ;
    }
    free(p); // 노드 메모리 해제
}

// 중위 순회로 노드 출력
void displayInorder(treeNode* root) {
    if (root) {
        displayInorder(root->left);
        printf("%d_", root->key); // 노드의 키를 출력
        displayInorder(root->right);
    }
}

int main(void) {
	treeNode* root_AVL = NULL;
	treeNode* root_BST = NULL;
	//////////////////////////////////////////////////////////////////
	root_AVL = insertAVLNode(&root_AVL, 50); // AVL 트리 만들기
	insertAVLNode(&root_AVL, 60);
	insertAVLNode(&root_AVL, 70);
	insertAVLNode(&root_AVL, 90);
	insertAVLNode(&root_AVL, 80);
	insertAVLNode(&root_AVL, 75);
	insertAVLNode(&root_AVL, 73);
	insertAVLNode(&root_AVL, 72);
	insertAVLNode(&root_AVL, 78);
	printf("\n ******* AVL 트리 출력 ****************** \n\n");
	displayInorder(root_AVL); //중위순회 경로 출력
	printf("\n\n AVL 트리에서 70 탐색 : ");
	searchBST(root_AVL, 70);
	printf("\n\n AVL 트리에서 72 탐색 : ");
	searchBST(root_AVL, 72);
	printf("\n\n AVL 트리에서 76 탐색 : ");
	searchBST(root_AVL, 76);

	/////////////////////////////////////////////////////////////////////////////
	root_BST = insertBSTNode(root_BST, 50); //BST 만들기
	insertBSTNode(root_BST, 60);
	insertBSTNode(root_BST, 70);
	insertBSTNode(root_BST, 90);
	insertBSTNode(root_BST, 80);
	insertBSTNode(root_BST, 75);
	insertBSTNode(root_BST, 73);
	insertBSTNode(root_BST, 72);
	insertBSTNode(root_BST, 78);
	printf("\n\n\n ******* BST 출력 ************************ \n\n");
	displayInorder(root_BST);  //중위순회 경로 출력
	printf("\n\n BST에서 70 탐색 : ");
	searchBST(root_BST, 70);
	printf("\n\n BST에서 72 탐색 : ");
	searchBST(root_BST, 72);
	printf("\n\n BST에서 76 탐색 : ");
	searchBST(root_BST, 76);
	getchar(); return 0;
}
--------------------------------------------------
 ******* AVL 트리 출력 ****************** 

50_60_70_72_73_75_78_80_90_

 AVL 트리에서 70 탐색 :   1회 검색 : 키를 찾았습니다.

 AVL 트리에서 72 탐색 :   4회 검색 : 키를 찾았습니다.

 AVL 트리에서 76 탐색 :   5회 검색 : 키를 찾지 못했습니다.


 ******* BST 출력 ************************ 

50_60_70_72_73_75_78_80_90_

 BST에서 70 탐색 :   3회 검색 : 키를 찾았습니다.

 BST에서 72 탐색 :   8회 검색 : 키를 찾았습니다.

 BST에서 76 탐색 :   8회 검색 : 키를 찾지 못했습니다.

728x90

'알고리즘' 카테고리의 다른 글

[알고리즘] 그래프 1 - 그래프의 개념 (1)	2023.12.05
[알고리즘] 트리6 - 히프 트리(Heap) (2)	2023.11.20
[알고리즘] 트리4 - 이진 탐색 트리 (0)	2023.11.13
[알고리즘] 트리3 - 스레드 이진 트리 (1)	2023.11.13
[알고리즘] 트리2 - 이진 트리의 순회 (0)	2023.11.10

현재글[알고리즘] 트리5 - 균형 이진 탐색 트리(AVL)

낭만을 찾아서 개발자의 길에 오르기 시작하다.

java, 추상 클래스, 자료구조, 프로그래머스, IntStream, C/C++, 코딩 기초 트레이닝, 임베디드시스템, Lv.0, 트리, 극동대학교 AI컴퓨터, 자바, 극동대학교, Atmega128보드, 태양계, 알고리즘, LV0, 스위치를 이용한 LED 컨트롤, 극동대, CodeVisionAVR,

Today :
Yesterday :

일	월	화	수	목	금	토
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

sundori DevStory