Фундаментальные алгоритмы и структуры данных в Delphi

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

Желательно разработать метод, с помощью которого можно было бы непосредственно определить, в какую группу должно помещаться хеш-значение. Предположим, что имеет место следующая ситуация: разрядная глубина каталога равна 3, но разрядная глубина группы равна 2. Записи 4 и 5 каталога указывают на группу A, которая заполнена, а записи 6 и 7 - на пустую группу B. Куда Должно быть помещено данное хеш-значение? Прежде всего, следует осознать, что группа А содержит только те хеш-значения, последними разрядами которых являются 001, 101, 011 или 111 (чтобы убедиться в этом, проинвертируйте разряды для получения записей 4, 5, 6 и 7 каталога). Если хеш-значение имеет окончание 001 или 101, оно будет помещено в группу A. Если оно имеет окончание 011 или 111, оно будет помещено в группу B. Все еще не понятно, не так ли? Что ж, первые две комбинации заканчиваются разрядами 01, в то время как две вторые комбинации - разрядами 11. Почему учитываются только два разряда? Вспомним, что разрядная глубина группы равна 2. Идея состоит в том, чтобы вычислить запись каталога, соответствующую началу диапазона (которое нам известно), проинвертировать разряды, соответствующие разрядной глубине каталога, и выполнить операцию AND для полученного результата и маски, которая была сгенерирована из значения разрядной глубины группы. Затем эту маску можно использовать для разбиения хеш-значений по категориям. Именно эти действия и выполняются в среднем разделе подпрограммы.

Все остальные действия являются тривиальными и особого интереса не представляют - выполняется проверка правильности значений счетчиков групп, добавление новой группы, обновление исходной группы и обеспечение того, чтобы записи каталога, которые требуют изменения, указывали на новую группу.

Полный код класса TtdHashTableExtendible можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshExt.pas.

Резюме

В этой главе были рассмотрены хеш-таблицы - структуры данных, которые пытаются предоставить максимально быстрый доступ к своим элементам, при этом они подпадают под категорию O(1).

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

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

Глава 8. Бинарные деревья.

Подобно массивам и связным спискам, деревья того или иного вида - это структуры данных, которые используются программистами практически повсеместно. В главе 3 были рассмотрены односвязные списки, в которых существовала единственная связь, соединяющая узлы друг с другом (двухсвязные списки имели также связь, указывающую в противоположном направлении). Обычно связные списки рассматриваются как горизонтальные структуры (в целях экономии места на бумаге!), в которых начальный узел располагается слева, а сам связный список простирается направо. Теперь представим, что этот связный список повернут на 90 градусов по часовой стрелке, чтобы начальный узел располагался вверху, а конечный внизу. Этот случай представляет собой особый пример многопутевого дерева, в котором каждый узел имеет только один дочерний узел, расположенный непосредственно под ним. Аналогично, каждый узел имеет один родительский узел, который расположен непосредственно над ним. Естественно, такая классификация охватывает целое семейство деревьев. Примем соглашение, что самый нижний узел имеет нулевую связь, т.е. не имеет дочернего узла. Поскольку каждый узел имеет максимум один дочерний узел, односвязный список можно было бы называть унарным деревом.

Многопутевое дерево является обобщением этой концепции. Оно представляет собой коллекцию узлов, организованных так, чтобы все узлы кроме корневого (мы будем называть узел в верхушке дерева корневым, а узел, который не имеет дочерних узлов - листовым, или просто листом) имели только один родительский узел и могли иметь ноль или больше дочерних узлов. Таким образом, связный список - это особое многопутевое дерево, в котором каждый узел (кроме самого нижнего) имеет только один дочерний узел. Если каждый узел может иметь максимум n дочерних узлов, такое дерево называется n-арным деревом.

Рисунок 8.1. Бинарное дерево

Теперь рассмотрим случай, когда каждый узел имеет до двух дочерних узлов. Иначе говоря, для каждого узла существует максимум две связи с узлами следующего нижнего уровня. Эта структура называется бинарным деревом. Согласно принятому соглашению, два дочерних узла данного узла называются левым и правым дочерними узлами, поскольку при рисовании дерева с расположением его корня в вершине, дочерние узлы выстраиваются горизонтально под ним, один левее от другого. Классическое представление бинарного дерева показано на рис. 8.1.

Из приведенных рассуждений ясно, что при определении используемого узла бинарного дерева в Delphi-программе нам требуются две связи (т.е. указатели) с его дочерними узлами, связь с его родительским узлом (эта связь необязательна, но, как мы увидим, ее применение упрощает некоторые алгоритмы, работающие с деревьями) и фактические данные, которые должны храниться в узле. С целью упрощения задачи примем, что данные в узле могут быть представлены указателем, подобно TList и структурам данных, которые уже были рассмотрены в этой книге. Поскольку узел имеет фиксированный размер, мы снова воспользуемся описанным в главе 3 диспетчером узлов, когда дело дойдет до создания класса бинарного дерева. Код, приведенный в листинге 8.1, определяет расположение записей узлов.

Листинг 8.1. Расположение узлов в бинарном дереве type

TtdChildType = ( {типы дочерних узлов}

ctLeft, {.. левый дочерний узел}

ctRight);

{.. правый дочерний узел}

TtdRBColor = ( {цвета для красно-черного дерева}

rbBlack, {..черный}

rbRed);

{..красный}

PtdBinTreeNode = ^TtdBinTreeNode;

TtdBinTreeNode = packed record btParent : PtdBinTreeNode;

btChild : array [TtdChildType] of PtdBinTreeNode;

btData : pointer;

case boolean of

false : (btExtra : longint);

true : (btColor : TtdRBColor);

end;

Обратите внимание, что две дочерние связи мы определили в виде двухэлементного массива. На первый взгляд, это может показаться излишним, но когда дело дойдет до реализации операций с бинарным деревом, такое определение существенно упростит нашу задачу. Кроме того, узел бинарного дерева объявляет дополнительное поле, которое не требуется для обычных бинарных деревьев, однако упрощает задачу для красно-черного варианта дерева бинарного поиска.

Создание бинарного дерева

Само по себе создание бинарного дерева тривиально. В простейшем случае корневой узел бинарного дерева определяет все бинарное дерево.

var

MyBinaryTree : PtBinTreeNode;

Если MyBinaryTree равен nil, никакого бинарного дерева не существует, поэтому это значение служит начальным значением бинарного дерева.

{инициализировать бинарное дерево}

MyBinaryTree :=nil;

На практике принято использовать фиктивный узел, аналогичный фиктивному заглавному узлу односвязного списка, чтобы каждый реальный узел дерева, включая корневой, имел родительский узел. Корневой узел может быть как левым, так и правым дочерним узлом фиктивного узла, но для определенности примем, что он является левым.