[c언어] AVL 트리

26 Dec 2023

c언어

AVL 트리는 이진 탐색 트리(Binary Search Tree, BST)의 변형으로, 트리의 균형을 유지하여 삽입, 삭제, 검색 연산의 시간 복잡도를 최적화하는 자료 구조입니다. c언어로 AVL 트리를 구현하여 보겠습니다.

AVL 트리란 무엇인가요?

AVL 트리는 Adelson-Velsky 와 Landis의 이름에서 따온 트리로, 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 항상 1 이하여야 합니다. 이를 통해, 트리의 높이를 최소로 유지하여 연산의 시간 복잡도를 O(log n)으로 보장합니다.

AVL 트리의 구현

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

typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
    int height;
} Node;

int max(int a, int b) {
    return (a > b) ? a : b;
}

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

int getBalance(Node *N) {
    if (N == NULL) {
        return 0;
    }
    return height(N->left) - height(N->right);
}

Node *newNode(int key) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return node;
}

Node *rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
    return x;
}

Node *leftRotate(Node *x) {
    Node *y = x->right;
    Node *T2 = y->left;
    y->left = x;
    x->right = T2;
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
    return y;
}

이 외에도 AVL 트리의 삽입, 삭제 연산 및 데이터 검색 관련 함수를 구현하고, 테스트 코드를 작성하여 실제 동작을 확인할 수 있습니다.

마치며

c언어를 사용하여 AVL 트리를 구현하는 방법에 대해 알아보았습니다. AVL 트리는 데이터의 동적인 추가, 삭제 및 검색에 있어서 효율적인 연산을 보장해주는 자료 구조로, 실제 프로젝트에서 활용될 수 있는 가치 있는 구현체입니다.