Balanced Binary Trees

Balanced Binary Trees — Отсортированная коллекция пар ключ/значение оптимизированная для поиска и пересечения в определённом порядке.

Краткое описание

#include <glib.h> GTree; GTree* g_tree_new (GCompareFunc key_compare_func); GTree* g_tree_new_with_data (GCompareDataFunc key_compare_func, gpointer key_compare_data); GTree* g_tree_new_full (GCompareDataFunc key_compare_func, gpointer key_compare_data, GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func); void g_tree_insert (GTree *tree, gpointer key, gpointer value); void g_tree_replace (GTree *tree, gpointer key, gpointer value); gint g_tree_nnodes (GTree *tree); gint g_tree_height (GTree *tree); gpointer g_tree_lookup (GTree *tree, gconstpointer key); gboolean g_tree_lookup_extended (GTree *tree, gconstpointer lookup_key, gpointer *orig_key, gpointer *value); void g_tree_foreach (GTree *tree, GTraverseFunc func, gpointer user_data); void g_tree_traverse (GTree *tree, GTraverseFunc traverse_func, GTraverseType traverse_type, gpointer user_data); gboolean (*GTraverseFunc) (gpointer key, gpointer value, gpointer data); enum GTraverseType; gpointer g_tree_search (GTree *tree, GCompareFunc search_func, gconstpointer user_data); gboolean g_tree_remove (GTree *tree, gconstpointer key); gboolean g_tree_steal (GTree *tree, gconstpointer key); void g_tree_destroy (GTree *tree);

Описание

Структура GTree и связанные с ней функции обеспечивают отсортированную коллекцию пар ключ/значение оптимизированную для поиска и пересечения в определённом порядке.

Для создания новой GTree используйте g_tree_new().

Для вставки пары ключ/значение в GTree используйте g_tree_insert().

Для поиска значения соответствующего полученному ключу, используйте g_tree_lookup() и g_tree_lookup_extended().

Для определения количества ветвей в GTree, используйте g_tree_nnodes(). Для определения высоты GTree, используйте g_tree_height().

Для пересечения GTree, вызывая функцию для каждой ветви посещаемой при пересечении, используйте g_tree_foreach().

Для удаления пар ключ/значение используйте g_tree_remove().

Для уничтожения GTree, используйте g_tree_destroy().

Детали

GTree

typedef struct _GTree GTree;

Структура GTree это непрозрачная структура данных представляющая Balanced Binary Tree. Доступ к ней разрешён только функциям перечисленным ниже.


g_tree_new ()

GTree* g_tree_new (GCompareFunc key_compare_func);

Создаёт новую GTree.

key_compare_func : функция используемая для упорядочивания ветвей в GTree. Она должна возвращать значения подобно стандартной функции strcmp() - 0 если два аргумента равны, отрицательное значение если первый аргумент располагается перед вторым, или положительное значение если первый аргумент располагается после второго.
Возвращает : новая GTree.

g_tree_new_with_data ()

GTree* g_tree_new_with_data (GCompareDataFunc key_compare_func, gpointer key_compare_data);

Создаёт новую GTree при помощи функции сравнения которая принимает пользовательские данные. Смотрите g_tree_new() для подробностей.

key_compare_func : функция сравнения в стиле qsort().
key_compare_data : данные помещаемые в функцию сравнения.
Возвращает : новая GTree.

g_tree_new_full ()

GTree* g_tree_new_full (GCompareDataFunc key_compare_func, gpointer key_compare_data, GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func);

Создаёт новую GTree подобно g_tree_new() и позволяет указать функцию освобождающую память распределяемую для ключей и значений которые получены при удалении элементов из GTree.

key_compare_func : функция сравнения в стиле qsort().
key_compare_data : данные помещаемые в функцию сравнения.
key_destroy_func : функция освобождающая память распределённую для ключей используемых при удалении элементов из GTree или NULL если вы не хотите указывать такую функцию.
value_destroy_func : функция освобождающая память распределённую для значений используемых при удалении элементов из GTree или NULL если вы не хотите использовать такую функцию.
Возвращает : новая GTree.

g_tree_insert ()

void g_tree_insert (GTree *tree, gpointer key, gpointer value);

Вставляет пару ключ/значение в GTree. Если полученный ключ уже существует в GTree соответствующее ему значение устанавливается в новое значение. Если вы указали value_destroy_func при создании GTree, старое значение освободится с помощью этой функции. Если вы указали key_destroy_func при создании GTree, помещаемый ключ освобождается с помощью этой функции.

Дерево автоматически сбалансировано, так как новые пары ключ/значение добавляются таким образом, чтобы расстояние от корня до листьев было минимальным на сколько это возможно.

tree : GTree.
key : вставляемый ключ.
value : значение соответствующее ключу.

g_tree_replace ()

void g_tree_replace (GTree *tree, gpointer key, gpointer value);

Вставляет новый ключ и значение в GTree подобно g_tree_insert(). Отличие в том, что если ключ уже существует в GTree, он переписывается новым ключом. Если вы указали value_destroy_func при создании GTree, старое значение освобождается с помощью этой функции. Если вы указали key_destroy_func при создании GTree, старый ключ освобождается при помощи этой функции.

Дерево автоматически сбалансировано, так как новые пары ключ/значение добавляются таким образом, чтобы расстояние между корнем и листьями было минимально возможным.

tree : GTree.
key : ключ для вставки.
value : значение соответствующее ключу.

g_tree_nnodes ()

gint g_tree_nnodes (GTree *tree);

Определяет номер узла в GTree.

tree : GTree.
Возвращает : номер узла в GTree.

g_tree_height ()

gint g_tree_height (GTree *tree);

Определяет высоту GTree.

Если GTree не содержит ветвей, высота равна 0. Если GTree содержит только корневую ветвь, высота равна 1. Если корневая ветвь имеет дочернюю, высота равна 2, и т.д..

tree : GTree.
Возвращает : высота GTree.

g_tree_lookup ()

gpointer g_tree_lookup (GTree *tree, gconstpointer key);

Определяет значение соответствующее полученному ключу. Так как GTree автоматически балансируется при добавлении пар ключ/значение, ключ находится очень быстро.

tree : GTree.
key : ключ для поиска.
Возвращает : значение соответствующее ключу, или NULL если ключ был найден.

g_tree_lookup_extended ()

gboolean g_tree_lookup_extended (GTree *tree, gconstpointer lookup_key, gpointer *orig_key, gpointer *value);

Находит ключ в GTree, возвращает оригинальный ключ, связанное с ним значение и gboolean которое TRUE если ключ был найден. Это полезно если вам необходимо освободить память связанную с оригинальным ключом, например перед вызовом g_tree_remove().

tree : GTree.
lookup_key : разыскиваемый ключ.
orig_key : возвращаемый оригинальный ключ.
value : возвращает значение связанное с ключом.
Возвращает : TRUE если ключ найден в GTree.

g_tree_foreach ()

void g_tree_foreach (GTree *tree, GTraverseFunc func, gpointer user_data);

Вызывает указанную функцию для каждой пары ключ/значение в GTree. В функцию помещаются ключ и значение для каждой пары, а также полученный параметр data. Дерево пересекается в порядке сортировки.

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

tree : GTree.
func : функция вызываемая для каждой посещаемой ветви. Если эта функция возвращает TRUE, пересечение останавливается.
user_data : пользовательские данные помещаемые в функцию.

g_tree_traverse ()

void g_tree_traverse (GTree *tree, GTraverseFunc traverse_func, GTraverseType traverse_type, gpointer user_data);

Внимание

g_tree_traverse устарела начиная с версии 2.2 и не должна использоваться во вновь создаваемом коде. Порядок сбалансированного дерева несколько произволен. Если вы просто хотите посетить все ветви в сортировочном порядке, используйте g_tree_foreach(). Если вы действительно нуждаетесь в посещении ветвей в другом порядке, рассмотрите использование N-ary Tree.

Вызывает полученную функцию для каждой ветви в GTree.

tree : GTree.
traverse_func : функция вызываемая для каждой посещаемой ветви. Если эта функция возвращает TRUE, пересечение прекращается.
traverse_type : порядок в котором посещаются ветви, один из G_IN_ORDER, G_PRE_ORDER и G_POST_ORDER.
user_data : пользовательские данные помещаемые в функцию.

GTraverseFunc ()

gboolean (*GTraverseFunc) (gpointer key, gpointer value, gpointer data);

Определяет тип функции помещаемой в g_tree_traverse(). Она помещает пару ключ/значение для каждой ветви, вместе с параметром user_data помещаемым в g_tree_traverse(). Если функция вернула TRUE, пересечение прекращается.

key : ключ GTree ветви.
value : значение соответствующее ключу.
data : пользовательские данные помещаемые в g_tree_traverse().
Возвращает : TRUE для остановки пересечения.

enum GTraverseType

typedef enum { G_IN_ORDER, G_PRE_ORDER, G_POST_ORDER, G_LEVEL_ORDER } GTraverseType;

Определяет тип функции пересечения g_tree_traverse(), g_node_traverse() и g_node_find().

G_IN_ORDER сначала посещает левую дочернюю ветвь, затем саму ветвь, затем правую дочернюю ветвь. Используйте это если вам нужен вывод сортированный согласно функции сравнения.
G_PRE_ORDER посещает ветвь, затем дочерние.
G_POST_ORDER посещает дочерние ветви, затем саму ветвь.
G_LEVEL_ORDER не реализовано для Balanced Binary Trees. Для N-ary Trees, первой посещается корневая ветвь, затем её дочерние ветви, затем их дочерние, и так далее. Помните что это менее эффективно чем другие порядки.

g_tree_search ()

gpointer g_tree_search (GTree *tree, GCompareFunc search_func, gconstpointer user_data);

Находит GTree используя search_func.

search_func вызывается с указателем на ключ пары ключ/значение в дереве, переданном в user_data. Если search_func возвращает 0 для пары ключ/значение, то g_tree_search_func() вернёт значение этой пары. Если search_func возвращает -1, то поиск продолжается среди пар ключ/значение, которые имеют меньший ключ; если search_func возвращает 1, поиск продолжается среди пар ключ/значение которые имеют больший ключ.

tree : GTree.
search_func : функция используемая для поиска GTree.
user_data : данные помещаемые как второй аргумент в функцию search_func.
Возвращает : значение соответствующее найденному ключу, или NULL если ключ был найден.

g_tree_remove ()

gboolean g_tree_remove (GTree *tree, gconstpointer key);

Удаляет пару ключ/значение из GTree.

Если GTree создана с использованием g_tree_new_full(), ключ и значение освобождаются используя указанную функцию уничтожения, иначе вы должны убедиться что освободили все динамически распределённые значения самостоятельно. Если ключ не существует в GTree, функция ничего не делает.

tree : GTree.
key : удаляемый ключ.
Возвращает : TRUE если ключ найден (до версии 2.8, эта функция ничего не возвращала)

g_tree_steal ()

gboolean g_tree_steal (GTree *tree, gconstpointer key);

Удаляет ключ со связанным с ним значением из GTree без вызова функции уничтожения ключа и значения.

Если ключ не существует в GTree, функция ничего не делает.

tree : GTree.
key : удаляемый ключ.
Возвращает : TRUE если ключ найден (до версии 2.8, эта функция ничего не возвращала)

g_tree_destroy ()

void g_tree_destroy (GTree *tree);

Уничтожает GTree. Если ключ и/или значение распределены динамически, вы должны либо освобождать их первыми либо создать GTree используя g_tree_new_full(). В последнем случае функция уничтожения указанная вами будет вызвана для всех ключей и значений перед уничтожением GTree.

tree : GTree.