[C] AVL Tree

 

 

AVL Tree

• Binary Tree의 한 종류

 

• Left-Subtree와 Right-Subtree의 균형을 유지
  • 임의의 node의 subtree height 차이는 2이하

 

• BF(Balance Factor) 통해서 Tree 균형 유지
  • BF = "Left_SubTree_Height" - "Right_SubTree_Height"
  • BF =  -1 ~ +1 사이의 값을 유지

 

• Left/Right Rotation과 recursive로 구현

---

 

Rotate Operation

 

---

• Balance가 무너진 4가지의 경우 및 수정 방법 (LL, RR, LR, RL) 

 

---

 

 

Insert

• 이진 탐색을 통해서 신규 node를 위치시키고, 4가지 규칙 중 하나를 적용하여 Tree 수정

 

 

---

 

 

Delete

• 지우려는 node의 child 갯수에 따라서 처리 (0개, 1개, 2개)

 

Child 갯수 == 0

: 해당 node를 지우고, root로 이동하면서 Balance 유지 작업수행

 

Child 갯수 == 1

: 자식을 해당 위치로 이동시킴, root로 이동하면서 Balance 유지 작업수행

 

Child 갯수 == 2

: 우측 subtree에서 최솟값을 찾아서 해당 node로 이동시킴, root로 이동하면서 Balance 유지 작업 수행

---

 

 

구현 / Source Code

avl_tree.h

#ifndef _AVL_TREE_H_
#define _AVL_TREE_H_

typedef struct node_t node_t;
struct node_t {
    void* data;

    node_t* parent;
    node_t* left;
    node_t* right;

    /* height */
    int h;
};

typedef struct avl_tree_t avl_tree_t;
struct avl_tree_t {
    node_t* root;

    /*
     * if (a > b)
     *  return +1;
     * if (a < b)
     *  return -1;
     * if (a == b)
     *  return 0;
     */
    int (*compare)(void* a, void* b);
};

void avl_tree_init(avl_tree_t* tree, int (*compare)(void* a, void* b));
void avl_insert(avl_tree_t* tree, void* data);
void avl_delete(avl_tree_t* tree, void* data);
void avl_tree_destroy(avl_tree_t* tree);

void avl_for_each_inorder(avl_tree_t* tree, void (*probe)(void* data));
void avl_for_each_postorder(avl_tree_t* tree, void (*probe)(void* data));

void* avl_leftmost(avl_tree_t* tree);
void* avl_rightmost(avl_tree_t* tree);

#endif

avl_tree.c

#include <stdlib.h>

#include "avl_tree.h"

static int height(node_t* n)
{
    if (n == NULL)
        return 0;

    return n->h;
}

static int get_bf(node_t* n)
{
    if (n == NULL)
        return 0;

    return height(n->left) - height(n->right);
}

/* Rotating relative to y, return new top of subtree */
static node_t* right_rotate(node_t* y)
{
    node_t* x = y->left;
    node_t* t = x->right;

    x->right = y;
    y->left = t;

    x->parent = y->parent;
    y->parent = x;

    if (t)
        t->parent = y;

    y->h = max(height(y->right), height(y->left)) + 1;
    x->h = max(height(x->right), height(x->left)) + 1;

    return x;
}

/* Rotating relative to x, return new top of subtree */
static node_t* left_rotate(node_t* x)
{
    node_t* y = x->right;
    node_t* t = y->left;

    x->right = t;
    y->left = x;

    y->parent = x->parent;
    x->parent = y;

    if (t)
        t->parent = x;

    x->h = max(height(x->left), height(x->right)) + 1;
    y->h = max(height(y->left), height(y->right)) + 1;

    return y;
}

static node_t* avl_alloc_node(void* data)
{
    node_t* n = (node_t*)malloc(sizeof(node_t));

    if (!n)
        return NULL;

    n->data = data;
    n->left = NULL;
    n->right = NULL;
    n->h = 1;

    return n;
}

static void avl_free_node(node_t* n)
{
    free(n);
}

static node_t* __avl_insert(avl_tree_t *tree, node_t *node, void* data)
{
    int bf;

    if (!node)
        return avl_alloc_node(data);

    if (tree->compare(node->data, data) > 0)
        node->left = __avl_insert(tree, node->left, data);
    else
        node->right = __avl_insert(tree, node->right, data);

    node->h = max(height(node->right), height(node->left)) + 1;

    bf = get_bf(node);

    if (bf > 1) {
        if (tree->compare(node->left->data, data) > 0)
            return right_rotate(node);
        else if (tree->compare(data, node->left->data) > 0) {
            node->left = left_rotate(node->left);
            return right_rotate(node);
        }
    }

    if (bf < -1) {
        if (tree->compare(data, node->right->data) > 0)
            return left_rotate(node);
        else if (tree->compare(node->right->data, data) > 0) {
            node->right = right_rotate(node->right);
            return left_rotate(node);
        }
    }

    return node;
}

void avl_insert(avl_tree_t* tree, void* data)
{
     tree->root = __avl_insert(tree, tree->root, data);
}

static node_t* avl_min_node(node_t* n)
{
    node_t* current = n;

    while (current->left)
        current = current->left;

    return current;
}

static node_t* __avl_delete(avl_tree_t* tree, node_t* n, void* data)
{
    int bf;

    if (!n)
        return NULL;

    if (tree->compare(n->data, data) > 0)
        n->left = __avl_delete(tree, n->left, data);
    else if (tree->compare(n->data, data) < 0)
        n->right = __avl_delete(tree, n->right, data);
    else {
        if (!n->left || !n->right) {
            node_t* temp = n->left ? n->left : n->right;

            if (!temp) {
                temp = n;
                n = NULL;
            } else
                *n = *temp;

            avl_free_node(temp);
            
        } else {
            node_t* temp = avl_min_node(n->right);
            n->data = temp->data;
            n->right = __avl_delete(tree, n->right, temp->data);
        }
    }

    if (!n)
        return NULL;

    n->h = max(height(n->left), height(n->right)) + 1;
    bf = get_bf(n);

    if (bf > 1) {
        if (get_bf(n->left) >= 0)
            return right_rotate(n);
        else {
            n->left = left_rotate(n->left);
            return right_rotate(n);
        }
    }

    if (bf < -1) {
        if (get_bf(n->right) <= 0)
            return left_rotate(n);
        else {
            n->right = right_rotate(n->right);
            return left_rotate(n);
        }
    }

    return n;
}

void avl_delete(avl_tree_t* tree, void* data)
{
    __avl_delete(tree, tree->root, data);
}

void avl_tree_init(avl_tree_t* tree, int (*compare)(void* a, void* b))
{
    tree->root = NULL;
    tree->compare = compare;
}

static void __avl_for_each__inorder(avl_tree_t* tree, node_t* node, void (*probe)(void* data))
{
    if (!node)
        return;

    __avl_for_each__inorder(tree, node->left, probe);
    probe(node->data);
    __avl_for_each__inorder(tree, node->right, probe);
}

void avl_for_each_inorder(avl_tree_t* tree, void (*probe)(void* data))
{
    node_t* node = tree->root;
    __avl_for_each__inorder(tree, node, probe);
}

static void __avl_for_each__postorder(avl_tree_t* tree, node_t* node, void (*probe)(void* data))
{
    if (!node)
        return;

    __avl_for_each__postorder(tree, node->left, probe);
    __avl_for_each__postorder(tree, node->right, probe);
    probe(node->data);
}

void avl_for_each_postorder(avl_tree_t* tree, void (*probe)(void* data))
{
    node_t* node = tree->root;
    __avl_for_each__postorder(tree, node, probe);
}

void* avl_leftmost(avl_tree_t* tree)
{
    node_t* current = tree->root;

    while (current->left)
        current = current->left;

    return current->data;
}

void* avl_rightmost(avl_tree_t* tree)
{
    node_t* current = tree->root;

    while (current->right)
        current = current->right;

    return current->data;
}

static void __avl_destroy(avl_tree_t* tree, node_t* node)
{
    if (!node)
        return;

    __avl_destroy(tree, node->left);
    __avl_destroy(tree, node->right);
    avl_free_node(node);
}

void avl_tree_destroy(avl_tree_t* tree)
{
    __avl_destroy(tree, tree->root);
}

 

main.c

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

#include "avl_tree.h"

/* user defined data and operator */
struct data_t {
    int key;
};

struct data_t* alloc_data(void)
{
    return (struct data_t*)malloc(sizeof(struct data_t));
}

void free_data(void* data)
{
    free(data);
}

/*
 * if (a > b)
 *  return +1;
 * if (a < b)
 *  return -1;
 * if (a == b)
 *  return 0;
 */
int data_compare(void* a, void* b)
{
    struct data_t* _a = (struct data_t*)a;
    struct data_t* _b = (struct data_t*)b;

    return _a->key - _b->key;
}

void data_print(void* d)
{
    struct data_t* data = (struct data_t*)d;
    printf("%d ", data->key);
}

/* main */
enum menu_e {
    INSERT = 1,
    DELETE,
    MINIMUM,
    MAXIMUM,
    PRINT_IN_ORDER,
    EXIT = 99,
};

void print_main_menu(void)
{
    printf("::: MENU :::\n");
    printf("%d. insert\n", INSERT);
    printf("%d. delete\n", DELETE);
    printf("%d. minimum\n", MINIMUM);
    printf("%d. maximum\n", MAXIMUM);
    printf("%d. print(in order)\n", PRINT_IN_ORDER);
    printf("------------\n");
    printf("%d. exit\n", EXIT);
    printf("------------\n");
}

int main()
{
    struct avl_tree_t avl_tree;
    avl_tree_init(&avl_tree, data_compare);

    while (1) {
        int select;

        print_main_menu();
        scanf("%d", &select);

        switch (select)
        {
        case INSERT:
        {
            int key;
            printf("input value : ");
            scanf("%d", &key);
            struct data_t* data = alloc_data();
            if (data) {
                data->key = key;
                avl_insert(&avl_tree, data);
            }
            else
                printf("memory alloc fail\n");
        }
        break;
        case DELETE:
        {
            int key;
            printf("input value : ");
            scanf("%d", &key);
            struct data_t* data = alloc_data();
            if (data) {
                data->key = key;
                avl_delete(&avl_tree, data);
                free_data(data);
            }
            else
                printf("memory alloc fail\n");
        }
        break;
        case MINIMUM:
        {
            struct data_t* data = avl_leftmost(&avl_tree);
            if (data)
                printf("minimum = %d\n", data->key);
        }
        break;
        case MAXIMUM:
        {
            struct data_t* data = avl_rightmost(&avl_tree);
            if (data)
                printf("maximum = %d\n", data->key);
        }
        break;
        case PRINT_IN_ORDER:
        {
            printf("print in order : \n");
            avl_for_each_inorder(&avl_tree, data_print);
            printf("\n");
        }
        break;
        case EXIT:
        {
            goto out;
        }
        break;
        default:
            break;
        }
        printf("\n");
    }
out:
    avl_for_each_postorder(&avl_tree, free_data);
    avl_tree_destroy(&avl_tree);
}

---

 

참고 및 출처

https://www.programiz.com/dsa/avl-tree

AVL Tree

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

AVL Tree Visualzation

https://code-lab1.tistory.com/61

[자료구조] AVL트리란? AVL트리 쉽게 이해하기, AVL트리 시뮬레이터

https://blog.csdn.net/weixin_44024891/article/details/104910691

AVLtree（平衡二叉树）_GlorygloryGlory的博客-CSDN博客_avltree

https://github.com/xieqing/avl-tree

GitHub - xieqing/avl-tree: An AVL Tree Implementation In C

.