avl_extra.c

#include "avl_extra.h"


/*
    Biblioteka zawiera dodatkowe funkcje AVL, które nie są używane w ostatecznym programie, ale są przydatne przy testowaniu.
    Zakładamy, że użytkownik zaimplementował avl_value_write_dot()
*/

/*
    Funkcja pomocnicza do avl_write_dot()
    Wypisuje wierzchołek drzewa do formatu dot
*/
void avl_write_dot_node(FILE* fp, avl_node_t* node, avl_node_t* parent) {
    if (node == NULL) return;
    if (parent != NULL)
        fprintf(fp, "\t\"%p\" -> \"%p\"\n", parent, node);
    fprintf(fp, "\t\"%p\" [label=\"", node);
    avl_value_write_dot(node->value, fp);
    fprintf(fp, "\"];\n");
    avl_write_dot_node(fp, node->left, node);
    avl_write_dot_node(fp, node->right, node);
}

/*
    Funkcja wypisuje drzewo do formatu dot
*/
void avl_write_dot(avl_root_t* root, FILE* fp) {
    fprintf(fp, "digraph avl_tree {\n");
    fprintf(fp, "graph [ordering=\"out\"];\n");
    fprintf(fp, "node [shape=record];\n");
    avl_write_dot_node(fp, root->root, NULL);
    fprintf(fp, "}");
}

avl_extra.h

#ifndef AVL_EXTRA_H
#define AVL_EXTRA_H

#include "avl_tree.h"
#include <stdio.h>


/* Implementowane przez użytkownika */
void avl_value_write_dot(const avl_value_t* v, FILE* fp);

void        avl_write_dot(avl_root_t* root, FILE* fp);

#endif //AVL_EXTRA_H

avl_test.c

#include "avl_tree.h"
#include "avl_extra.h"
#include <stdio.h>
#include <stdlib.h>

struct avl_value {
    int v;
};

void  avl_value_free(avl_value_t* v) {
    free(v);
}

int avl_value_equals(const avl_value_t* v1, const avl_value_t* v2) {
    return v1->v == v2->v;
}
int avl_value_lt(const avl_value_t* v1, const avl_value_t* v2) {
    return v1->v < v2->v;
}
void avl_value_write_dot(const avl_value_t* v, FILE* fp) {
    fprintf(fp, "%d", v->v);
}

#define TESTV(result, predicate, expected)                                          \
  do {                                                                              \
    if (predicate != expected)                                                      \
    printf("\e[31mError:\e[0m %s should be %s, but is: %p: %d, [l=%p, p=%p]\n",     \
    #predicate, #expected, result, result->value->v, result->left, result->right);  \
  } while (0)

const int max_v = 25;

int main() {
    avl_root_t* root = avl_init();
    avl_value_t* v;
    for (int i = 0; i < max_v; i++) {
        v = malloc(sizeof(avl_value_t));
        v->v = i;
        avl_insert(root, v);
    }
    v = malloc(sizeof(avl_value_t));
    v->v = 2;
    avl_node_t* result = avl_find(root, v);
    TESTV(result, result->value->v, 2);
    for (int i = 0; i < max_v; i+=2) {
        v->v = i;
        avl_remove(root, v);
    }
    v->v = 42;
    avl_insert(root, v);
    v = malloc(sizeof(avl_value_t));
    v->v = 0;
    result = avl_find(root, v);
    TESTV(result, result, NULL);
    v->v = 5;
    result = avl_find(root, v);
    TESTV(result, result->value->v, 5);
    v->v = 42;
    avl_insert(root, v);
    FILE* fp = fopen("avltest.dot", "w");
    avl_write_dot(root, fp);
    fclose(fp);
    avl_free(root);
    return 0;
}

avl_tree.c

#include "avl_tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

static avl_node_t* insert_node(avl_node_t* node, avl_value_t* v, int* inserted);
static avl_node_t* create_avl_node_t(avl_value_t* v);
static void free_avl_node_t(avl_node_t* node);
static avl_node_t* remove_node(avl_node_t* node, avl_value_t* v, int* removed);
static avl_node_t* find_min_node(avl_node_t* node);
static avl_node_t* balance_node(avl_node_t* node);
static avl_node_t* rotate_left(avl_node_t* node);
static avl_node_t* rotate_right(avl_node_t* node);
static int get_balance_factor(avl_node_t* node);
static int get_height(avl_node_t* node);

/*
    Inicjalizacja drzewa. Zwraca NULL w przypadku błędu.
*/
avl_root_t* avl_init() {
    avl_root_t* root = malloc(sizeof(avl_root_t));
    if (root == NULL) {
        errno = ENOMEM;
        return NULL;
    }
    root->root = NULL;
    return root;
}

/*
    Funkcja avl_insert dodaje nowy element do drzewa oraz balansuje drzewo.
    Użytkownik ma zadbać, aby v nie było usuwane.
    Parametr funkcji:
        root – wskaźnik na strukturę drzewa,
        v – wskaźnik na strukturę, która ma zostać wstawiona do drzewa.
    Wynik avl_insert:
        1 – jeśli wstawienie się powiodło,
        0 – jeśli element już istniał w drzewie,
       -1 – jeśli dane są błędne
*/
int avl_insert(avl_root_t* root, avl_value_t* v) {
    if (root == NULL || v == NULL) {
        errno = EINVAL;
        return -1;
    }
    int inserted = 0;
    root->root = insert_node(root->root, v, &inserted);
    return inserted;
}

/*
    Funkcja avl_remove usuwa element z drzewa oraz balansuje drzewo.
    Nie gwarantujemy co się stanie z v.
    Parametr funkcji:
        root – wskaźnik na strukturę drzewa,
        v – wskaźnik na strukturę, która ma zostać usunięta.
    Wynik avl_remove:
        0 – jeśli usunięcie się powiodło,
        1 – jeśli element nie istniał w drzewie,
*/
int avl_remove(avl_root_t* root, const avl_value_t* v) {
    if (root == NULL || v == NULL) {
        errno = EINVAL;
        return -1;
    }
    int removed = 0;
    root->root = remove_node(root->root, v, &removed);
    return removed;
}

/*
    Funkcja avl_find wyszukuje element w drzewie.
    Parametr funkcji:
        root – wskaźnik na strukturę drzewa,
        v – wskaźnik na strukturę, która ma zostać wyszukana w drzewie.
    Wynik avl_find:
        wskaźnik na znaleziony element lub NULL, jeśli element nie istnieje.
*/
avl_node_t* avl_find(avl_root_t* root, const avl_value_t* v) {
    avl_node_t* node = root->root;
    while (node != NULL) {
        if (avl_value_equals(node->value, v))
            return node;
        else if (avl_value_lt(v, node->value))
            node = node->left;
        else
            node = node->right;
    }
    return NULL;
}

/*
    Funkcja avl_free przechodzi przez całe drzewo i je usuwa.
    Parametr funkcji:
        root – wskaźnik na strukturę drzewa.
*/
void avl_free(avl_root_t* root) {
    free_avl_node_t(root->root);
    free(root);
}

/*
    Funkcja avl_height zwraca wysokość drzewa.
    Parametr funkcji:
        root – wskaźnik na strukturę drzewa.
*/
int avl_height(avl_root_t* root) {
    if (root == NULL) return 0;
    return get_height(root->root);
}

static avl_node_t* create_avl_node_t(avl_value_t* v) {
    avl_node_t* node = malloc(sizeof(avl_node_t));
    if (node == NULL) {
        errno = ENOMEM;
        return NULL;
    }
    node->value = v;
    node->left = NULL;
    node->right = NULL;
    return node;
}

static avl_node_t* insert_node(avl_node_t* node, avl_value_t* v, int* inserted) {
    if (node == NULL) {
        avl_node_t* new_node = create_avl_node_t(v);
        if (new_node == NULL) {
            *inserted = 0;
            return NULL;
        }
        *inserted = 1;
        return new_node;
    }
    if (avl_value_equals(node->value, v)) {
        *inserted = 0;
        return node;
    }
    if (avl_value_lt(v, node->value))
        node->left = insert_node(node->left, v, inserted);
    else 
        node->right = insert_node(node->right, v, inserted);
    return balance_node(node);
}

static avl_node_t* remove_node(avl_node_t* node, avl_value_t* v, int* removed) {
    if (node == NULL) {
        *removed = 0;
        return NULL;
    }
    if (avl_value_equals(node->value, v)) {
        *removed = 1;
        if (node->left == NULL && node->right == NULL) {
            avl_value_free(node->value);
            free(node);
            return NULL;
        }
        if (node->left == NULL) {
            avl_node_t* right = node->right;
            avl_value_free(node->value);
            free(node);
            return right;
        }
        if (node->right == NULL) {
            avl_node_t* left = node->left;
            avl_value_free(node->value);
            free(node);
            return left;
        }
        avl_node_t* min_node = find_min_node(node->right);
        avl_value_t* min_value = min_node->value;
        node->value = min_value;
        node->right = remove_node(node->right, min_value, removed);
    } else if (avl_value_lt(v, node->value)) {
        node->left = remove_node(node->left, v, removed);
    } else {
        node->right = remove_node(node->right, v, removed);
    }
    return balance_node(node);
}

static avl_node_t* find_min_node(avl_node_t* node) {
    if (node == NULL)
        return NULL;
    while (node->left != NULL)
        node = node->left;
    return node;
}

static avl_node_t* balance_node(avl_node_t* node) {
    int balance_factor = get_balance_factor(node);
    if (balance_factor > 1) {
        if (get_balance_factor(node->left) < 0) {
            node->left = rotate_left(node->left);
        }
        node = rotate_right(node);
    } else if (balance_factor < -1) {
        if (get_balance_factor(node->right) > 0) {
            node->right = rotate_right(node->right);
        }
        node = rotate_left(node);
    }
    return node;
}

/*
    Funkcja get_balance_factor zwraca różnicę wysokości poddrzew lewego i prawego.
    Parametr funkcji:
        node – wskaźnik na strukturę węzła.
    Wynik get_balance_factor:
        różnica wysokości poddrzew lewego i prawego.
*/
static int get_balance_factor(avl_node_t* node) {
    int left_height = get_height(node->left);
    int right_height = get_height(node->right);
    return left_height - right_height;
}

static int get_height(avl_node_t* node) {
    if (node == NULL) return 0;
    
    int left_height = get_height(node->left);
    int right_height = get_height(node->right);
    return 1 + (left_height > right_height ? left_height : right_height);
}

static avl_node_t* rotate_left(avl_node_t* node) {
    avl_node_t* right = node->right;
    avl_node_t* right_left = right->left;
    right->left = node;
    node->right = right_left;
    return right;
}

static avl_node_t* rotate_right(avl_node_t* node) {
    avl_node_t* left = node->left;
    avl_node_t* left_right = left->right;
    left->right = node;
    node->left = left_right;
    return left;
}

static void free_avl_node_t(avl_node_t* node) {
    if (node == NULL) return;
    free_avl_node_t(node->left);
    free_avl_node_t(node->right);
    avl_value_free(node->value);
    free(node);
}

avl_tree.h

#ifndef AVL_TREE_H
#define AVL_TREE_H

/*
    Definicja wartości trzymanej w drzewie.
    Powwina zostać zaimplementowana przez użytkownika.
*/
typedef struct avl_value avl_value_t;

void    avl_value_free(avl_value_t* v);
int     avl_value_equals(const avl_value_t* v1, const avl_value_t* v2);
int     avl_value_lt(const avl_value_t* v1, const avl_value_t* v2);

typedef struct avl_node {
    avl_value_t* value;
    struct avl_node* left;
    struct avl_node* right;
} avl_node_t;

typedef struct {
    avl_node_t* root;
} avl_root_t;

/* Definicje funkcji */
avl_root_t*     avl_init();
int             avl_insert(avl_root_t* root, avl_value_t* v);
int             avl_remove(avl_root_t* root, const avl_value_t* v);
avl_node_t*     avl_find(avl_root_t* root, const avl_value_t* v);
void            avl_free(avl_root_t* root);
int             avl_height(avl_root_t* root);

/* Definicje makr */
#define AVL_FOREACH(root_struct, iterated_symbol, code)                         \
do {                                                                            \
    avl_node_t* iterated_symbol = root_struct->root;                            \
    avl_node_t** stack = calloc(avl_height(root_struct), sizeof(avl_node_t*));  \
    int stack_size = 0;                                                         \
    while (stack_size > 0 || iterated_symbol != NULL) {                         \
        while (iterated_symbol != NULL) {                                       \
            stack[stack_size++] = iterated_symbol;                              \
            iterated_symbol = iterated_symbol->left;                            \
        }                                                                       \
        iterated_symbol = stack[--stack_size];                                  \
        code                                                                    \
        iterated_symbol = iterated_symbol->right;                               \
    }                                                                           \
    free(stack);                                                                \
} while(0)

#endif // AVL_TREE_H