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.

			Справочное описание GLib
Начало \| Описание