Блок задач

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

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

Задача «Красно-черное дерево»

Реализовать модуль для работы с классическими красно-черными деревьями или с левосторонними красно-черными деревьями.

typedef void * Pointer;

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

typedef struct tRBTreeNode {
    Pointer data;
    /* ... */
} RBTreeNode;

typedef struct tRBTree {
    RBTreeNode *root;
    CmpFunc cmp_func; /* all data comparisons should be done
                         with help of this func! */
    /* ... */
} RBTree;

// Create empty tree
RBTree * rb_create(CmpFunc cmp_func);

// Clear tree but do not destroy tree struct
void rb_clear(RBTree *tree);

// Completely destroy tree
void rb_destroy(RBTree *tree);

size_t rb_size(RBTree *tree);

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

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

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

Дополнение

В качестве дополнительного задания можно реализовать функцию удаления элементов из дерева, самостоятельно изучив, как это делается.

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

Применение

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

typedef struct tEntry {
    Pointer key;
    Pointer value;
}

Примечание

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

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

На каждом шаге такого теста необходимо проверять корректность Красно-черного дерева:

  • Корень — чeрный.
  • Оба потомка каждого красного узла — черные.
  • Красный узел всегда черный.
  • Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.

Для этого можно добавить в модуль соответствующую функцию:

// Return whether Red-Black tree is correct
int rb_check(RBTree *tree);