Блок задач

3. Структуры данных

Темы
Сложность 8

Задача «AVL-дерево»

Реализовать модуль для работы с АВЛ-деревьями (подробнее можно посмотреть в лекции и в вики).

typedef void * Pointer;

typedef int (*CmpFunc)(Pointer data1, Pointer data2);

typedef struct tAVLTreeNode {
    Pointer data;
    /* ... */
} AVLTreeNode;

typedef struct tAVLTree {
    AVLTreeNode *root;
    CmpFunc cmp_func; /* all data comparisons should be done
                         with help of this func! */
    /* ... */
} AVLTree;

// Create empty tree
AVLTree * avl_create(CmpFunc cmp_func);

// Clear tree but do not destroy tree struct
void avl_clear(AVLTree *tree);

// Completely destroy tree
void avl_destroy(AVLTree *tree);

size_t avl_size(AVLTree *tree);

// Find element with equal data and return its data if any else NULL
Pointer avl_find(AVLTree *tree, Pointer data);

// Return data which was replaced by this insertion if any else NULL
Pointer avl_insert(AVLTree *tree, Pointer data);

// Delete node with equal data and return its data if any else NULL
Pointer avl_delete(AVLTree *tree, Pointer data);

// Call foreach_func for every node's data in tree passing given extra_data
void avl_foreach(AVLTree *tree,
                 void (*foreach_func)(Pointer data, Pointer extra_data),
                 Pointer extra_data);

Применение

Для лучшего понимания можно реализовать абстрактный тип данных ассоциативный массив (отображение, словарь, map) с использованием данного дерева. В таком случае в дереве будут храниться указатели на Entry, содержащие ключ, по которому работает функция сравнения, и некоторое значение, соответствующее ключу.

typedef struct tEntry {
    Pointer key;
    Pointer value;
}

Примечание

Каждая функция модуля должна быть протестирована с помощью assert.

Также предусмотреть нагрузочное тестирование: добавление большого числа случайных элементов в дерево, затем извлечение всех элементов, которые были добавлены.

На каждом шаге такого теста необходимо проверять корректность АВЛ-дерева: для каждой его вершины высота её двух поддеревьев должны различается не более чем на 1. Для этого можно добавить в модуль соответствующую функцию:

// Return whether AVL-tree is correct
int avl_check(AVLTree *tree);