Блок задач

1. Разгон

Сложность 3

Задача «Двоичное дерево»

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

Примерный интерфейс:

#include <stdbool.h> // bool
#include <stddef.h>  // size_t

typedef
struct BTreeItem
{
    const void * key;
    void * value;
}
BTreeItem;


void * btree_create(
    size_t keySize, size_t valueSize, 
    int(*compare)( const void *, const void * )
);
void btree_destroy(void * btree, void(*destroy)( void * ));

void * btree_init(
    void * btree, 
    size_t keySize, size_t valueSize, 
    int(*compare)( const void *, const void * )
);
void btree_clear(void * btree, void(*destroy)( void * ));

size_t btree_count(const void * btree);
void * btree_item(const void * btree, const void * key);
void * btree_insert(void * btree, const void * key, bool * createFlag);
void btree_remove(void * btree, const void * key, void(*destroy)( void * ));

size_t btree_first(const void * btree);
size_t btree_last(const void * btree);
size_t btree_next(const void * btree, size_t item_id);
size_t btree_prev(const void * btree, size_t item_id);
size_t btree_stop(const void * btree);
void * btree_current(const void * btree, size_t item_id);
void btree_erase(void * btree, size_t item_id, void(*destroy)( void * ));
  • struct btreeItem -- элемент двоичного дерева, содержащий в себе указатели на ключ и значение.
  • btree_create -- Создать новое пустое двоичное дерево. Размер ключа -- keySize, размер значения элемента -- valueSize, для упорядочивания элементов по ключу использовать функцию сравнения compare.
  • btree_destroy -- Удалить существующее двоичное дерево. Если указана функция destroy, то вызвать её для каждого удаляемого элемента btreeItem.
  • btree_init -- Инициализировать двоичное дерево. Размер ключа -- keySize, размер значения элемента -- valueSize, для упорядочивания элементов по ключу использовать функцию сравнения compare.
  • btree_clear -- Удалить все элементы из двоичного дерева. Если указана функция destroy, то вызвать её для каждого удаляемого элемента btreeItem.
  • btree_count -- Количество элементов в дереве.
  • btree_item -- Получить значение по заданному ключу. В случае наличия искомого ключа в дереве, функция возвращает указатель на значение связанное с этим ключом, иначе -- NULL.
  • btree_insert -- Добавить значение по заданному ключу. В случае успеха, функция возвращает указатель на связанное с искомым ключом значение, иначе -- NULL. Если задан указатель createFlag, то при создании нового элемента дерева этот флаг будет установлен в true, при доступе к значению уже существовавшего элемента -- в false.
  • btree_remove -- Найти по ключу и удалить элемент из двоичного дерева. Если указана функция destroy, то вызвать её для удаляемого элемента btreeItem.
  • btree_first -- Идентификатор для первого элемента двоичного дерева. Идентификатор может стать невалидным при модификации дерева.
  • btree_last -- Идентификатор для последнего элемента двоичного дерева. Идентификатор может стать невалидным при модификации дерева.
  • btree_next -- По идентификатору текущего элемента получить идентификатор следующего элемента дерева.
  • btree_prev -- По идентификатору текущего элемента получить идентификатор предыдущего элемента дерева.
  • btree_stop -- Идентификатор, получаемый при попытке обратиться к элементу за пределами дерева.
  • btree_current -- Получить элемент BTreeItem по его идентификатору.
  • btree_extract -- Удаление элемента двоичного дерева по его идентификатору. Если указана функция destroy, то вызвать её для удаляемого элемента btreeItem. После удаления элемента, идентификаторы любых элементов из этого дерева могут стать невалидным.