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

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

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

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

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

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

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

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

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

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

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

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

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

ctRight);

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

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