Продолжается подписка на наши издания! Вы не забыли подписаться?

Вы когда-нибудь задавали себе вопрос – как устроены индексы в СУБД? А может быть, у вас возникала потребность в применении высокопроизводительных алгоритмов доступа к данным? На эти и некоторые другие вопросы призван ответить ряд статей под общим названием «Высокопроизводительные алгоритмы». В этом цикле речь пойдет о деревьях, хешах и тому подобному. Первая статья посвящена деревьям. Вернее, бинарным деревьям.

Как известно, для ускорения доступа к информации применяется индексы. Есть много типов индексов битовые, кластерные хеш-индексы, но, наверное, самым популярным и распространенным являются индексы на основе бинарных деревьев.

Деревья

Массивы и связанные списки определяют коллекции объектов, доступ к которым осуществляется последовательно. Такие структуры данных называют линейными (linear) списками, поскольку они имеют уникальные первый и последний элементы и у каждого внутреннего элемента есть только один наследник. Линейный список является абстракцией, позволяющей манипулировать данными, представляемыми различным образом — массивами, стеками, очередями и связанными списками.

Во многих приложениях обнаруживается нелинейный порядок объектов, где элементы могут иметь нескольких наследников. Например, в фамильном дереве родитель может иметь нескольких потомков (детей). На Рис. 1 показаны три поколения семьи. Такое упорядочение называют иерархическим.

Рис.1.

В этой статье мы рассмотрим нелинейную структуру, называемую деревом (tree), которая состоит из узлов и ветвей и имеет направление от корня к внешним узлам, называемым листьями. Эти структуры подобны коммуникационной сети, показанной на Рис. 2, требуют особых алгоритмов и применяются в специальных приложениях.

Рис. 2

Терминология деревьев

Древовидная структура характеризуется множеством узлов (nodes), происходящих от единственного начального узла, называемого корнем (root). На Рис. 3 корнем является узел А. В терминах генеалогического дерева узел можно считать родителем (parent), указывающим на 0, 1 или более узлов, называемых сыновьями (children). Например, узел В является родителем сыновей E и F. Родитель узла H - узел D. Дерево может представлять несколько поколений семьи. Сыновья узла и сыновья их сыновей называются потомками (descendants), а родители и прародители – предками (ancestors) этого узла. Например, узлы E, F, I, J – потомки узла B. Каждый некорневой узел имеет только одного родителя, и каждый родитель имеет 0 или более сыновей. Узел, не имеющий детей (E, G, H, I, J), называется листом (leaf).

Каждый узел дерева является корнем поддерева (subtree), которое определяется данным узлом и всеми потомками этого узла. Узел F есть корень поддерева, содержащего узлы F, I и J. Узел G является корнем поддерева без потомков. Это определение позволяет говорить, что узел A есть корень поддерева, которое само оказывается деревом.

Рис.3.

Переход от родительского узла к дочернему и к другим потомкам осуществляется вдоль пути (path). Например, на Рис. 4 путь от корня A к узлу F проходит от A к B и от B к F. Тот факт, что каждый некорневой узел имеет единственного родителя, гарантирует, что существует единственный путь из любого узла к его потомкам. Длина пути от корня к этому узлу есть уровень узла. Уровень корня равен 0. Каждый сын корня является узлом 1-го уровня, следующее поколение – узлами 2-го уровня и т.д. Например, на Рис. 4 узел F является узлом 2-го уровня с длиной пути 2.

Глубина (depth) дерева есть его максимальный уровень. Понятие глубины также может быть описано в терминах пути. Глубина дерева есть длина самого длинного пути от корня до узла. На Рис. 4 глубина дерева равна 3.

Рис.4. Уровень узла и длина пути

Бинарные деревья

Хотя деревья общего вида достаточно важны, мы сосредоточимся на ограниченном классе деревьев, где каждый родитель имеет не более двух сыновей (Рис. 5). Такие бинарные деревья (binary trees) имеют унифицированную структуру, допускающую разнообразные алгоритмы прохождения и эффективный доступ к элементам. Изучение бинарных деревьев дает возможность решать наиболее общие задачи, связанные с деревьями, поскольку любое дерево общего вида можно представить эквивалентным ему бинарным деревом.

У каждого узла бинарного дерева может быть 0, 1 или 2 сына. По отношению к узлу слева будем употреблять термин левый сын (left child), а по отношению к узлу справа – правый сын (right child). Наименования "левый" и "правый" относятся к графическому представлению дерева. Бинарное дерево является рекурсивной структурой. Каждый узел – это корень своего собственного поддерева. У него есть сыновья, которые сами являются корнями деревьев, называемых левым и правым поддеревьями соответственно. Таким образом, процедуры обработки деревьев рекурсивны. Вот рекурсивное определение бинарного дерева:

Бинарное дерево - это такое множество узлов B, что

а) B является деревом, если множество узлов пусто (пустое дерево – тоже дерево);

б) B разбивается на три непересекающихся подмножества:

  • {R} корневой узел

  • {L1, L2,..., Lm} левое поддерево R

  • {R1, R2,..., Rm} правое поддерево R

На любом уровне n бинарное дерево может содержать от 1 до 2n узлов. Число узлов, приходящееся на уровень, является показателем плотности дерева. Интуитивно плотность есть мера величины дерева (число узлов) по отношению к глубине дерева. На Рис. 5 дерево А содержит 8 узлов при глубине 3, в то время как дерево B содержит 5 узлов при глубине 4. Последний случай является особой формой, называемой вырожденным (degenerate) деревом, у которого есть единственный лист (E) и каждый нелистовой узел имеет только одного сына. Вырожденное дерево эквивалентно связанному списку.

Рис.5. Бинарные деревья

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

Вырожденные деревья являются крайней мерой плотности. Другая крайность – законченные бинарные деревья (complete binary tree) глубины N, где каждый уровень 0...N - 1 имеет полный набор узлов, и все листья уровня N расположены слева. Законченное бинарное дерево, содержащее 2N узлов на уровне N, является полным. На Рис. 6 показаны законченное и полное бинарные деревья.

Законченные и полные бинарные деревья дают интересные математические факты. На нулевом уровне имеется 20 узлов, на первом — 21, на втором — 22 и т.д. На первых k-1 уровнях имеется 2k-1 узлов.

1 + 2 + 4 +... + 2k-1 = 2k-1

На уровне k количество дополнительных узлов колеблется от 1 до 2k (полное). В полном дереве число узлов равно

1 + 2 + 4 +... + 2k-1 + 2k = 2k-1 - 1

Число узлов законченного бинарного дерева удовлетворяет неравенству

2k< N < 2k-1 - 1 < 2k-1

Решая его относительно k, имеем

k < log2 (N) < k+1

Например, полное дерево глубины 3 имеет

24 - 1 = 15 узлов

Рис.6. Классификация бинарных деревьев

Структура бинарного дерева

Структура бинарного дерева состоит из узлов. Как и в связанном списке, эти узлы содержат поля данных и указатели на другие узлы в коллекции. В этом разделе мы определим узлы дерева и операции для его построения и прохождения. Объявим класс TreeNode, реализующий функциональность узла дерева, и разработаем ряд функций, позволяющих создавать бинарные деревья и осуществлять прохождение по их узлам.

Узел дерева содержит поле данных и два поля с указателями. Поля указателей называются левым указателем (left) и правым указателем (right), поскольку они указывают на левое и правое поддерево, соответственно. Значение NULL является признаком пустого дерева.

Корневой узел определяет входную точку дерева, а поля указателей – узлы следующего уровня. Листовой узел содержит NULL в полях правого и левого указателей (Рис. 7).

Проектирование класса TreeNode

В этом разделе мы разберем разработку класса TreeNode, в котором объявляются объекты-узлы бинарного дерева. Узел состоит из поля данных, которое является открытым (public) элементом, т.е. к которому можно обращаться непосредственно. Это позволяет читать или обновлять данные во время прохождения дерева, а также допускает возвращение ссылки на данные. Последняя особенность используется более сложными структурами данных, например, словарями. Два поля с указателями являются закрытыми (private) элементами, доступ к которым осуществляется посредством функций Left() и Right().

Спецификация класса TreeNode
ОБЪЯВЛЕНИЕ

ОПИСАНИЕ
// Следующее объявление понадобится // нам в дальнейшем template <class T> class BinSTree; // объявление объекта для узла бинарного дерева template <class T> class TreeNode { private: // указатели левого и правого дочерних узлов TreeNode<T> left; TreeNode<T> right; public: // открытый элемент, допускающий обновление T data; // конструктор инициализирует поля данных и указателей // значение NULL соответствует пустому поддереву TreeNode(const T& item, TreeNode<T> lptr, TreeNode<T> rptr):data(item), left(lptr), right(rptr) { } // методы доступа к полям указателей TreeNode<T> Left(void) const; TreeNode<T> Right(void) const; // сделать класс BinSTree дружественным, поскольку // необходим доступ к полям left и right friend class BinSTree<T>; };

Конструктор инициализирует поля данных и указателей. Если задать вместо обоих указателей NULL, узел будет инициализирован как лист.

Если в параметр lptr или rptr конструктора поместить указатели на другой объект TreeNode, конструктор присоединяет этот объект как левого или правого сына нового узла.

Методы доступа Left и Right возвращают соответствующий указатель. Класс BinSTree объявляется дружественным классу TreeNode и может модифицировать указатели. Другие клиенты должны использовать конструктор для создания указателей и методы Left и Right для прохождения дерева.

ПРИМЕР 
// указатели целочисленных узлов дерева TreeNode<int> root, lchild, rchild; TreeNode<int> p; // создать листья, содержащие // 20 и 30 в качестве данных lchild = new TreeNode<int> (20); rchild = new TreeNode<int> (30); // создать корень, содержащий число // 10 и двух сыновей root = new TreeNode<int> (10, lchild, rchild);

root->data = 50; // присвоить корню 50

Методы Left и Right возвращают значения полей левого и правого указателей. Благодаря этому клиент имеет доступ к левому и правому сыновьям узла.

Построение бинарного дерева

Бинарное дерево состоит из коллекции объектов TreeNode, связанных между собой посредством полей Left и Right. Объект TreeNode создается динамически с помощью функции new.

TreeNode<int> p; // объявление указателя // на узел дерева

p = new TreeNode(item); // левый и правый указатели равны NULL

Вызов функции new обязательно должен включать значение данных, и необязательно указатели на правое и/или левое поддерево. Определим функцию GetTreeNode, принимающую данные, и ноль или более указателей на объект TreeNode для создания и инициализации узла бинарного дерева. При недостаточном количестве доступной памяти программа прекращается сразу после выдачи сообщения об ошибке.

// создать объект TreeNode с указательными полями lptr и rptr. // по умолчанию указатели содержат NULL. template <class T> TreeNode<T> GetTreeNode(T item, TreeNode<T> lptr = NULL, TreeNode<T> rptr = NULL) { TreeNode<T> p; // вызвать new для создания нового узла // передать туда параметры lptr и rptr p = new TreeNode<T> (item, lptr, rptr); // если памяти недостаточно, завершить // программу сообщением об ошибке if (p == NULL) { cerr << “Ошибка при выделении памяти!\n"; exit(1); } // вернуть указатель на выделенную системой память return p; }

Функция FreeTreeNode принимает указатель на объект TreeNode и освобождает занимаемую узлом память, вызывая оператор С++ delete.

// освободить динамическую память, занимаемую данным узлом template <class t> void FreeTreeNode(TreeNode<T> p) { delete p; }

Функция GetTreeNode может быть использована для явного построения каждого узла дерева и, следовательно, всего дерева. Это было продемонстрировано на дереве с тремя узлами, содержащими 10, 20 и 30. Для более крупного экземпляра процесс будет немного утомительным, так как вы должны поместить в дерево все значения данных и указателей.

Создадим функцию MakeCharTree, строящую три дерева, узлы которых содержат символьные элементы данных. Эти деревья будут использоваться для иллюстрации методов TreeNode в следующем разделе. Параметры функции включают в себя ссылку на корень дерева и число n (0 < n < 2), которое служит для обозначения дерева. Следующие объявления создают указатель на объект TreeNode, с именем root, и назначают его корнем дерева Tree_2.

// объявить указатель на корень TreeNode<char> root; // сформировать на этом корне дерево tree_2 MakeCharTree(root,2);

На рисунке 8 показаны три дерева, построенных этим методом. Мы не приводим здесь кода этой функции ввиду ее примитивности, потренируйтесь сами.

Рис. 8. Дерево MakeCharTree

Разработка функций класса TreeNode

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

Алгоритмы прохождения существенно влияют на эффективность использования дерева. В первую очередь мы разработаем методы рекурсивного прохождения, а затем на их основе создадим алгоритмы прохождения, копирования и удаления, а также определения глубины дерева.

Наша реализация метода прохождения предусматривает передачу указателя на функцию в качестве параметра (visit). Эта функция осуществляет доступ к содержащимся в узле данным. Передавая в качестве параметра указатели на разные функции, можно добиться выполнения различных действий при прохождении каждого узла в процессе прохождения дерева. В языках С++ и С (по крайней мере, в современных реализациях С) имя функции является указателем на эту функцию. Это значит, что вместо синтаксиса <имя> можно использовать просто имя функции. Таким образом, при задании функции в качестве параметра другой функции можно пользоваться упрощенным синтаксисом. Наш метод прохода можно записать так:

template <class T> void <Метод_прохода> (TreeNode<T> t, void visit(T& item));

Всякий раз при вызове метода клиент должен передавать имя функции, выполняющей некоторое действие с данными, имеющимися в узле. По мере того как метод перемещается от узла к узлу, вызывается эта функция и выполняется предусмотренное действие.

Чтобы определить аргумент некоторой функции как указатель на функцию, необходима в описание параметра поместить описание передаваемой функции Пусть, например, функция G имеет параметр — функцию f. В этом параметре указывается имя функции (f), список параметров (int x) и возвращаемый тип (int).

int G(int t, int f(int x)) // параметр-функция f { // вычислить f(t) с помощью функции f и параметра t. // возвратить произведение этого значения и t return t f(t); }

Вызывая функцию G, клиент должен передать функцию для f с той же структурой. Пусть в нашем примере клиент определил функцию XSquared, вычисляющую x2.

// XSquared - целочисленная функция // с целочисленным параметром x int XSquared(int x) { return xx; }

Клиент вызывает функцию G с целочисленным параметром t и параметром-функцией XSquared. Оператор

Y = G(3, XSquared)

вызывает функцию G, которая в свою очередь вызывает функцию XSquared с параметром 3. Оператор:

cout << G(3.0, XSquared) << endl;

печатает результат 27.

Рекурсивные методы прохождения деревьев

Рекурсивное определение бинарного дерева определяет эту структуру как корень с двумя поддеревьями, которые идентифицируются полями левого и правого указателей в корневом узле. Сила рекурсии проявляется в методах прохождения деревьев. Каждый алгоритм прохождения дерева выполняет в узле три действия: заходит в узел и рекурсивно спускается по левому и правому поддеревьям. Спустившись к поддереву, алгоритм определяет, что он находится в узле, и может выполнить те же три действия. Спуск прекращается по достижении пустого дерева (указатель == NULL). Различные алгоритмы рекурсивного прохождения отличаются порядком, в котором они выполняют свои действия в узле. Мы изложим симметричный и обратный методы, в которых сначала осуществляется спуск по левому поддереву, а затем по правому. Другие методы оставляем вам в качестве упражнений.

Симметричный метод прохождения дерева

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

Итак, порядок операций при симметричном методе следующий:

  1. Прохождение левого поддерева.

  2. Посещение узла.

  3. Прохождение правого поддерева.

Мы называем такое прохождение LNR (left, node, right).

При симметричном методе прохождения дерева Tree_0 выполняются следующие операции.

Действие

Прохождение

Замечания

Спуститься от A к B:

 

Левый сын узла B равен NULL

Посетить B;

B

 

Спуститься от B к D:

 

D -листовой узел

Посетить D;

D

Конец левого поддерева узла A

Посетить корень A:

A

 

Спуститься от A к C:

   

Спуститься от C к E:

 

E - листовой узел

Посетить E;

E

 

Посетить C;

C

Готово!

Узлы посещаются в порядке B D A E C. Рекурсивная функция сначала спускается по левому дереву [t ->Left()], а затем посещает узел. Второй шаг рекурсии спускается по правому дереву [t ->Right()].

// симметричное рекурсивное прохождение узлов дерева template <class T> void Inorder (TreeNode<T> t, void visit(T& item)) { // рекурсивное прохождение завершает-ся на пустом поддереве if (t!= NULL) { // спуститься по левому поддереву Inorder(t->Left(), visit); // посетить узел visit(t->data); // спуститься по правому поддереву Inorder(t->Right(), visit); } }

Обратный метод прохождения дерева

При обратном прохождении посещение узла откладывается до тех пор, пока не будут рекурсивно пройдены оба его поддерева. Порядок операций дает так называемое LRN (left, right, node) сканирование.

  1. Прохождение левого поддерева.

  2. Прохождение правого поддерева.

  3. Посещение узла.

При обратном прохождении дерева Tree_0 узлы посещаются в порядке D B E C A.

Действие Прохождение  Замечания Спуститься от A к B:   Левый сын узла B равен NULL Спуститься от B к D:   D - листовой узел Посетить D; D Все сыновья узла B пройдены Посетить B; B Левое поддерево узла A пройдено Спуститься от A к C:     Спуститься от C к E:   E - листовой узел Посетить E; E Левый сын узла C Посетить C; C Правый сын узла A Посетить корень A: A Готово!

Функция сканирует дерево снизу вверх. Мы спускаемся вниз по левому дереву [t->Left()], а затем вниз по правому [t->Right()]. Последней операцией является посещение узла.

// обратное рекурсивное прохождение узлов дерева template <class T> void Postorder (TreeNode<T> t, void visit (T& item)) { // рекурсивное прохождение завершается на пустом поддереве if (t!= NULL) { // спуститься по левому поддереву Postorder(t->Left(), visit); // спуститься по правому поддереву Postorder(t->Right(), visit); // посетить узел visit(t->data); } }

Прямой метод прохождения определяется посещением узла в первую очередь и последующим прохождением сначала левого, а потом правого его поддеревьев (NLR).

Ясно, что префиксы pre, in и post в названиях функций показывают, когда происходит посещение узла. В каждом случае сначала осуществлялось прохождение по левому поддереву, а уже потом по правому. Фактически существуют еще три алгоритма, которые выбирают сначала правое поддерево и потом левое. Алгоритмы прохождения посещают каждый узел дерева. Они дают эквивалент последовательного сканирования массива или связанного списка.

Покажем на примере результаты использования различных методов прохождения. Для изображенного на Рис. 8 дерева Tree_2 имеет место следующий порядок посещения узлов.

Прямой: A B D G C E H I F Симметричный: D G B A H E I C F Обратный: G D B H I E F C A

Использование алгоритмов прохождения деревьев

На рекурсивных алгоритмах прохождения деревьев основаны многие приложения. Эти алгоритмы обеспечивают упорядоченный доступ к узлам. Здесь мы продемонстрируем использование алгоритмов прохождения для подсчета количества листьев на дереве и глубины дерева. В каждом случае для посещения узлов мы должны применять ту или иную стратегию прохождения.

Посещение узлов дерева

Для многих приложений требуется просто обойти узлы дерева, неважно в каком порядке. В этих случаях клиент волен выбрать любой алгоритм прохождения. В данном приложении функция CountLeaf проходит дерево с целью подсчета его листьев. При распознавании очередного листа происходит приращение параметра count.

// эта функция использует обратный метод прохождения. // при посещении узла проверяется, является ли он листовым template CountLeaf (<TreeNode<T> t, int& count) { // Использовать обратный метод прохождения if (t!= NULL) { CountLeaf(t->Left(), count); // пройти левое поддерево CountLeaf(t->Right(), count); // пройти правое поддерево // Проверить, является ли данный узел листом. // Если да, то произвести приращение переменной count if (t->Left() == NULL && t->Right() == NULL) count++; } }

Функция Depth использует обратный метод прохождения для вычисления глубины бинарного дерева. В каждом узле вычисляется глубина его левого и правого поддеревьев. Итоговая глубина на единицу больше максимальной глубины поддеревьев.

// Эта функция использует обратный метод прохождения // для вычисления глубины левого и правого поддеревьев // узла и возвращает результирующее значение глубины, // равное 1 + max(depthLeft, depthRight). Глубина пустого дерева равна -1 template <class T> void Depth (TreeNode<T> t) { int depthLeft, depthRight, depthval; if (t == NULL) depthval = -1; else { depthLeft = Depth(t->Left()); depthRight = Depth(t->Right()); depthval = 1 + (depthLeft > depthRight depthLeft : depthRight); } return depthval; }

Копирование и удаление деревьев

Процедуры копирования и удаления всего дерева вводят новые понятия и подготавливают нас к проектированию класса деревьев, который требует деструктор и конструктор копирования. Функция CopyTree принимает исходное дерево и создает его дубликат. Процедура DeleteTree удаляет каждый узел дерева, включая корень, и высвобождает занимаемую узлами память.

Копирование дерева

Функция CopyTree использует для посещения узлов обратный метод прохождения. Этот метод гарантирует, что мы спустимся по дереву на максимальную глубину, прежде чем начнем операцию посещения, которая создает узел для нового дерева. Функция CopyTree строит новое дерево снизу вверх. Сначала создаются сыновья, а затем они присоединяются к своим родителям, как только те будут созданы. Этот подход вы должны были использовать в функции MakeCharTree. Например, порядок операций для дерева Tree_0 (Рис. 8) следующий:

d = GetTreeNode('D'); e = GetTreeNode('E'); b = GetTreeNode('B', NULL, d); c = GetTreeNode('C', e, NULL); a = GetTreeNode('A', b, c); root = a;

Сначала мы создаем сына D, который затем присоединяется к своему родителю B при создании узла. Создается узел E и присоединяется к своему родителю C во время рождения (или создания) последнего. Наконец, создается корень и присоединяется к своим сыновьям B и C.

Алгоритм копирования дерева начинает работать с корня и в первую очередь строит левое поддерево узла, а затем - правое его поддерево. Только после этого создается новый узел. Тот же рекурсивный процесс повторяется для каждого узла. Соответственно узлу t исходного дерева создается новый узел с указателями newlptr и newrptr.

При обратном методе прохождения сыновья посещаются перед их родителями. В результате в новом дереве создаются поддеревья, соответствующие t->Left() и t->Right(). Сыновья присоединяются к своим родителям в момент создания последних.

newlptr = CopyTree(t->Left()); newrptr = CopyTree(t->Right()); // создать родителя и присоединить к нему его сыновей newnode = GetTreeNode(t->data, newlptr, newrptr);

Суть посещения узла t в исходном дереве заключается в создании нового узла на дереве-дубликате.

Проиллюстрируем рекурсивную функцию CopyTree на примере символьного дерева Tree_0. Предположим, что главная процедура определяет корни root1 и root2 и создает дерево Tree_0. Функция CopyTree создает новое дерево с корнем root2. Проследим алгоритм и проиллюстрируем процесс создания пяти узлов на дереве-дубликате.

TreeNode<char> root1, root2; // объявить два дерева MakeCharTree(root1, 0); // root1 указывает на Tree_0 root2 = CopyTree(root1); // создать копию дерева Tree_0
  1. Пройти потомков узла A, начиная с левого поддерева (узла B и далее к узлу D, который является правым поддеревом узла B). Создать новый узел с данными, равными D, и левым и правым указателями, равными NULL.

  2. Сыновья узла B пройдены. Создать новый узел с данными, равными B, левым указателем, равным NULL, и правым указателем, указывающим на копию узла D.

  3. Поскольку левое поддерево узла A пройдено, начать прохождение его правого поддерева и дойти до узла E. Создать новый узел с данными из узла E и полями указателей, равными NULL.

  4. После обработки E перейти к его родителю и создать новый узел с данными из C. В поле правого указателя поместить NULL, а левому указателю присвоить ссылку на копию дочернего узла E.

  5. Последний шаг выполняется в узле A. Создать новый узел с данными из A и присоединить к нему копии сына B слева и сына C справа. Копирование дерева завершено.

Функция CopyTree возвращает указатель на вновь созданный узел. Это возвращаемое значение используется родителем, когда тот создает свой собственный узел и присоединяет к нему своих сыновей. Функция возвращает корень вызывающей программе.

// создать дубликат дерева t и возвра-тить корень нового дерева template <class T> TreeNode<T> CopyTree(TreeNode<T> t) { // переменная newnode указывает на новый узел, создаваемый // посредством вызова GetTreeNode и присоединяемый в дальнейшем // к новому дереву. указатели newlptr и newrptr адресуют сыновей // нового узла и передаются в качест-ве параметров в GetTreeNode TreeNode<T> newlptr, newrptr, newnode; // остановить рекурсивное прохождение при достижении пустого дерева if (t == NULL) return NULL; // CopyTree строит новое дерево в процессе прохождения // узлов дерева t. в каждом узле это-го дерева функция // CopyTree проверяет наличие левого сына. если он есть, // создается его копия. в противном случае возвращается // NULL. CopyTree создает копию узла с помощью GetTreeNode // и подвешивает к нему копии сыно-вей. if (t->Left()!= NULL) newlptr = CopyTree(t->Left()); else newlptr = NULL; if (t->Right()!= NULL) newrptr = CopyTree(t->Right()); else newrptr = NULL; // построить новое дерево снизу вверх, сначала создавая // двух сыновей, а затем их родителя newnode = GetTreeNode(t->data, newlptr, newrptr); // вернуть указатель на вновь создан-ное дерево return newnode; }

Удаление дерева

Когда в приложении используется такая динамическая структура, как дерево, ответственность за освобождение занимаемой памяти ложится на программиста. Разработаем функцию DeleteTree, в которой применяется обратный метод прохождения бинарного дерева. Использование обратного метода прохождения гарантирует, что мы посетим всех сыновей родительского узла, прежде чем удалим его. Операция посещения заключается в вызове функции FreeTreeNode, удаляющей узел.

// использовать обратный алгоритм для прохождения узлов дерева // и удалить каждый узел при его посещении template <class T> void DeleteTree(TreeNode<T> t) { if(t!= NULL) { DeleteTree(t->Left()); DeleteTree(t->Right()); FreeTreeNode(t); } }

Разработаем также функцию ClearTree, которая удаляет все узлы дерева и сбрасывает корень. Функция вызывает DeleteTree для удаления узлов дерева и присваивает указателю на корень значение NULL.

// вызвать функцию DeleteTree для удаления узлов дерева. // затем сбросить указатель на его корень в NULL template &lt;class T&gt; void ClearTree(TreeNode&lt;T&gt; &t) { DeleteTree(t); t = NULL; // теперь корень пуст }

Бинарные деревья поиска

Обычное бинарное дерево может содержать большую коллекцию данных и все же обеспечивать быстрый поиск, добавление или удаление элементов. Одним из наиболее важных приложений деревьев является построение классов коллекций. Для линейных структур сложность алгоритма, реализующего последовательный поиск равна O(N), что неэффективно для больших коллекций. В общем случае древовидные структуры обеспечивают значительно большую производительность, так как путь к любым данным не превышает глубины дерева. Эффективность поиска максимальна при законченном бинарном дереве и составляет O(log2N). Например, в списке из 10000 элементов предполагаемое число сравнений при последовательном поиске равно 5000. Поиск же на законченном дереве потребовал бы не более 14 сравнений. Бинарное дерево представляет большие потенциальные возможности в качестве структуры хранения списка.

Чтобы запомнить элементы в виде дерева с целью эффективного доступа, мы должны разработать поисковую структуру, которая указывает путь к элементу. Эта структура, называемая бинарным деревом поиска (binary search tree), упорядочивает элементы посредством оператора отношения "<". Чтобы сравнить узлы дерева, мы подразумеваем, что часть или все поле данных определено в качестве ключа и оператор "<" сравнивает ключи, когда добавляет элемент. Бинарное дерево поиска строится по следующему правилу:

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

Рис. 9. Бинарное дерево поиска

На Рис. 9 показан пример бинарного поискового дерева. Это дерево называется поисковым потому, что в поисках некоторого элемента (ключа) мы можем идти лишь по совершенно конкретному пути. Начав с корня, мы сканируем левое поддерево, если значение ключа меньше текущего узла. В противном случае сканируется правое поддерево. Такой метод создания дерева позволяет осуществлять поиск элемента по кратчайшему пути от корня. Например, поиск числа 37 требует четырех сравнений, начиная с корня.

Текущий узел

Действие

Корень = 50

Сравнить ключ = 37  и 50

поскольку 37 < 50, перейти в левое поддерево

Узел = 30

Сравнить ключ = 37  и 30

поскольку 37 >= 30, перейти в правое поддерево

Узел = 35

Сравнить ключ = 37  и 35

поскольку 37 >= 35, перейти в правое поддерево

Узел = 37

Сравнить ключ = 37  и 37. Элемент найден.

На Рис. 10 показаны различные бинарные деревья поиска.

Ключ в узле бинарного дерева поиска

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

Номер социальной страховки (9-символьная строка) Имя студента (строка) Средний балл (число с плавающей точкой) ключевое поле   struct Student { String ssn; String name; float gpa; }

Рис. 10. Примеры деревьев бинарного поиска

На Рис. 10 узлы содержат единственное целочисленное значение, которое и является ключом. В этом случае узел 25 имеет ключ 25, и мы сравниваем два узла путем сравнения целых чисел. Сравнение производится с помощью целочисленных операторов отношения "<" и "==". Для студента университета ключом является ssn, и мы сравниваем две символьные строки. Это делается с помощью перегрузки операций. Например, следующий код реализует отношение "<" для двух объектов Student:

int operator < (const Student& s, const Student& t) { return s.ssn < t.ssn; // сравнить ключи ssn }

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

Работа с бинарным деревом поиска

Бинарное дерево поиска является нелинейной структурой для хранения множества элементов. Как и любая списковая структура, дерево должно допускать вставку, удаление и поиск элементов. Для поискового дерева требуется такая операция вставки, которая правильно располагает новый элемент. Рассмотрим, например, вставку узла 8 в дерево BinSTree_1. Начав с корневого узла 25, определяем, что узел 8 должен быть в левом поддереве узла 25 (8<25). В узле 10 определяем, что место узла 8 должно быть в левом поддереве узла 10, которое в данный момент пусто. Узел 8 вставляется в дерево в качестве левого сына узла 10.

До каждого вставляемого в дерево узла существует конкретный путь. Тот же путь может использоваться для поиска элемента. Поисковый алгоритм берет ключ и ищет его в левом или в правом поддереве каждого узла, составляющего путь. Например, поиск элемента 30 на дереве BinSTree_1 (Рис. 10) начинается в корневом узле 25 и переходит в правое поддерево (30 > 25), а затем в левое поддерево. (30 < 37). Поиск прекращается на третьем сравнении, когда ключ совпадает с числом 30, хранящемся в узле.

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

На первый взгляд напрашивается решение выбрать сына узла 25 — скажем, 37 — и заменить его родителя. Однако это простое решение терпит неудачу, так как некоторые узлы оказываются не с той стороны корня. Поскольку данное дерево относительно невелико, мы можем установить, что 15 или 30 являются допустимой заменой корневому узлу.

Класс BinSTree

BinSTree – это класс, реализующий функциональность бинарного поискового дерева. Он содержит деструктор, конструктор копирования и перегруженные операторы присваивания, позволяющие инициализировать объекты и играющие роль операторов присваивания. Деструктор отвечает за очистку списка. Он и операторы присваивания вместе с методом ClearList вызывают скрытый метод DeleteTree. Мы также включили сюда скрытый метод CopyTree для использования в конструкторе копирования и перегруженном операторе "=".

Спецификация класса BinSTree

ОБЪЯВЛЕНИЕ
#include <iostream.h> #include <stdlib.h> #include "treenode.h" template <class T> class BinSTree { protected: // требуется для наследо-вания // указатели на корень и на текущий узел TreeNode<T> root; TreeNode<T> current; // число элементов дерева int size; // распределение/освобождение памяти TreeNode<T> GetTreeNode(const T& item, TreeNode<T> lptr, TreeNode<T> rptr); void FreeTreeNode(TreeNode<T> p); // используется конструктором копирования // и оператором присваивания void DeleteTree(TreeNode<T> t); // используется деструктором, оператором присваивания // и функцией ClearList TreeNode<T> FindNode(const T& item, TreeNode<T> & parent) const; public: // конструкторы и деструктор BinSTree(void); BinSTree(const BinSTree<T>& tree); BinSTree(void); // оператор присваивания BinSTree<T>& operator= (const BinSTree<T>& rhs); // стандартные методы обработки списков // Осуществляет поиск путем сравнения элемента // с данными, хранящимися в узле. // После выполнения текущая позиция соответствует // совпавшему узлу. int Find(T& item); // Находит подходящее для вставки место и добавляет // новый элемент данных. После выполнения этого метода // текущая позиция соответствует новому узлу. void Insert(const T& item); // Находит соответствующий узел, удаляет его и // связывает все его поддеревья так, чтобы сохранить // структуру бинарного дерева поиска. void Delete(const T& item); void ClearList(void); int ListEmpty(void) const; int ListSize(void) const; // методы, специфичные для деревьев // Если ключ в текущей позиции совпадает с ключом // элемента данных, присваивает значение элемента данных // узлу. В противном случае вставляет элемент данных в // дерево. void Update(const T& item); // Возвращает указатель на корень. TreeNode<T> GetRoot(void) const; }
ОПИСАНИЕ

Этот класс имеет защищенные данные. Переменная root указывает на корневой узел дерева. Указатель current ссылается на точку последнего изменения в списке. Например, current указывает положение нового узла после операции вставки, а метод Find заносит в current ссылку на узел, совпавший с элементом данных.

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

ПРИМЕР
BinSTree<int> T; // дерево с целочисленными данными T.Insert(50); // создать дерево с четырьмя узлами (A) T.Insert(40); T.Insert(70); T.Insert(45); T.Delete(40); // удалить узел 40 (B) T.ClearList(); // удалить узлы дерева // дерево univInfo содержит информацию о студентах. // Поле ssn является ключевым BinSTree<Student> univInfo; Student stud; // назначить ключ "9876543789" и найти его на дереве stud.ssn = "9876543789"; if (univInfo.Find(stud)) { // студент найден. присвоить новый средний балл и обновить узел stud.gpa = 3.86; univInfo.Update(stud); } else cout << "Студент отсутствует в базе данных." << endl;

Использование
бинарных деревьев поиска

Класс BinSTree — мощная структура данных, которая используется для обработки динамических списков. Перед рассмотрением примера практической задачи построения конкорданса рассмотрим несколько более простых примеров. Под конкордансом здесь понимается алфавитный список всех слов заданного текста с указателями на места их появлений. Рассмотрим ряд простых программ, где применяются деревья поиска.

Создание примеров деревьев поиска.

В разделе «Структура бинарного дерева» функция MakeCharTree использовалась для создания ряда бинарных деревьев с символьными данными. Создадим похожую функцию MakeSearchTree, строящую бинарные деревья поиска с целочисленными данными, применяя метод Insert. Первое дерево SearchTree_0 создается на базе массива arr0. В этом примере переменная Т имеет тип BinSTree.

int arr0[6] = {30, 20, 45, 5, 10, 40}; for (i = 0; i < 6; i++) T.Insert(arr0[i]); // добавить элемент к дереву

Еще два дерева, SearchTree_1 и SearchTree_2, создайте сами. Первое из них должно быть восьмиэлементным деревом, а второе – деревом с десятью случайными числами из диапазона 10-99 (Рис. 11). Номер создаваемого дерева должен передаваться функции MakeSearchTree в качестве параметра. В качестве другого параметра функция должна получать указатель на переменную типа BinSTree.


 Рис. 11. Деревья, создаваемые с помощью функции MakeSearchTree

Симметричный метод прохождения

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

Дублированные узлы

Бинарное дерево поиска может иметь дублированные узлы. В операции вставки мы продолжаем сканировать правое поддерево, если наш новый элемент совпадает с данными в текущем узле. В результате в правом поддереве совпавшего узла возникают дублированные узлы. Например, следующее дерево генерируется из списка 50 70 25 90 30 55 25 15 25.

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

Реализация класса BinSTree

Класс BinSTree описывает нелинейный список и базовые операции вставки, удаления и поиска элементов. Помимо методов обработки списков важную роль при реализации класса играет управление памятью. Скрытые методы CopyTree и DeleteTree используются конструктором, деструктором и оператором присваивания для размещения и уничтожения узлов списка.

Элементы данных класса BinSTree

Бинарное дерево поиска определяется своим указателем корня, который используется в операциях вставки (Insert), поиска (Find) и удаления (Delete). Класс BinSTree содержит элемент данных root, являющийся указателем корня и имеющий начальное значение NULL. Доступ к root осуществляется посредством метода GetRoot, разрешающего вызовы внешних функций прохождения. Второй указатель, current, определяет на дереве место для обновлений. Операция Find устанавливает current на совпавший узел, и этот указатель используется функцией Update для обновления данных. Методы Insert и Delete переустанавливают current на новый узел или на узел, заменивший удаленный. Объект BinSTree является списком, размер которого все время изменяется функциями Insert и Delete. Текущее число элементов в списке хранится в закрытом элементе данных size.

// Указатели на корень и на текущий узел TreeNode<T> root; TreeNode<T> current; // Число элементов дерева int size;

Управление памятью

Размещение и уничтожение узлов для методов Insert и Delete, а также для утилит CopyTree и DeleteTree выполняется посредством GetTreeNode и FreeTreeNode. Метод GetTreeNode аналогичен обсуждавшемуся выше. Он распределяет память и инициализирует поля данных и указателей в узле. FreeTreeNode непосредственно вызывает оператор удаления для освобождения памяти.

Конструктор, деструктор и оператор присваивания

Класс содержит конструктор, который инициализирует элементы данных. Конструктор копирования и перегруженный оператор присваивания с помощью метода CopyTree создают новое бинарное дерево поиска для текущего объекта. Алгоритм функции CopyTree был разработан нами для класса TreeNode в разделе, посвященном алгоритмам прохождения деревьев. В том же разделе мы рассматривали алгоритм удаления узлов дерева, который реализован в классе BinSTree функцией DeleteTree и используется как деструктором, так и методом ClearList.

Перегружаемый оператор присваивания копирует объект, стоящий справа, в текущий объект. После проверки того, что объект не присваивается самому себе, функция очищает текущее дерево и с помощью CopyTree создает дубликат присваиваемого дерева (rhs). Указателю current присваивается указатель root, копируется размер списка и возвращается ссылка на текущий объект.

// оператор присваивания template <class T> BinSTree<T>& BinSTree<T>::operator = (const BinSTree<T>& rhs) { // нельзя копировать дерево в само себя if (this == &rhs) return this; // очистить текущее дерево. скопировать новое дерево // в текущий объект ClearList(); root = CopyTree(tree.root); // присвоить текущему указателю значение корня и задать // размер дерева current = root; size = tree.size; // возвратить ссылку на текущий объект return this; }

Операции обработки списков

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

Операция Find (поиск)

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

// искать элемент данных на дереве. если найден, возвратить // адрес совпавшего узла и указатель на его родителя. иначе // возвратить NULL template <class T> TreeNode<T> BinSTree<T>::FindNode(const T& item, TreeNode<T> & parent) const { // пробежать по узлам дерева, начиная с корня TreeNode<T> t = root; // у корня нет родителя parent = NULL; // прерваться на пустом дереве while (t!== NULL) { // остановиться при совпадении if (item == t->data) break; else { // обновить родительский указатель // и идти направо или налево parent = t; if (item < t->data) t = t->left; else t = t->right; } } // возвратить указатель на узел; NULL, // если не найден return t; }

Информация о родителе используется операцией Delete (удаление). В методе Find нас интересует только установление текущей позиции на совпавший узел и присвоение ссылки на этот узел параметру item. Метод Find возвращает True (1) показывая тем самым, что поиск удался, или False (0) — в противном случае. Для сравнения данных в узлах методу Find требуются операторы отношения "==" и "<". Эти операторы должны быть перегруженными, если они не определены для этого базового типа данных.

// искать item. если найден, присвоить данные узла параметру item template <class T> int BinSTree<T>::Find(T& item) { // мы используем FindNode, который принимает параметр parent TreeNode<T> parent; // искать item. назначить совпавший узел текущим current = FindNode (item, parent); // если найден, скопировать данные уз-ла и возвратить True if (current!= NULL) { item = current->data; return 1; } else // item не найден. возвратить False return 0; }
Операция Insert (вставка)

Метод Insert принимает в качестве параметра новый элемент данных и вставляет его в подходящее место на дереве. Эта функция итеративно проходит путь вдоль левых и правых поддеревьев, пока не найдет точку вставки. На каждом шаге этого пути алгоритм сохраняет запись текущего узла (t) и родителя этого узла (parent). Процесс прекращается по достижении пустого поддерева (t == NULL), которое показывает, что мы нашли место для вставки нового элемента. В этом месте новый узел вставляется в качестве сына данного родителя. Например, следующие шаги вставляют число 32 в дерево, изображенное на Рис. 12.

  1. Метод начинает работу в корневом узле и сравнивает 32 с корневым значением 25 [Рис. 12 (A)]. Поскольку 32 > 25, переходим к правому поддереву и рассматриваем узел 35.
    t = узел 35; parent = узел 25

  2. Считая узел 35 корнем своего собственного поддерева, сравниваем 32 и 35 и переходим к левому поддереву узла 35 [Рис. 12 (B)].
    t = NULL; parent = 35

  3. С помощью GetTreeNode мы создаём листовой узел, содержащий значение 32, а затем вставляем новый узел в качестве левого сына узла 35 [Рис. 12 (C)]:

// присвоение left возможно, т.к. BinSTree // является дружественным по отноше-нию к TreeNode newNode = GetTreeNode(item, NULL, NULL); parent->left = newNode;

Указатели parent и t являются локальными переменными, изменяющимися по мере нашего продвижения по пути в поисках точки вставки.

// вставить item в дерево поиска template <class T> void BinSTree<T>::Insert(const T& item) { // t - текущий узел, parent - предыду-щий узел TreeNode<T> t = root, parent = NULL, newNode; // закончить на пустом дереве while(t!= NULL) { // обновить указатель parent и идти направо или налево parent = t; if (item < t->data) t = t->left; else t = t->right; } // если родителя нет, вставить в каче-стве корневого узла if (parent == NULL) root = newNode; // если item меньше родительского уз-ла, вставить в качестве левого сына else if (item < parent->data) parent->left = newNode; else // если item больше или равен роди-тельскому узлу, // вставить в качестве правого сына parent->right = newNode; // присвоить указателю current адрес нового узла и увеличить size на единицу current = newNode; size++; }
Операция Delete (удаление)

Операция Delete удаляет из дерева узел с заданным ключом. Сначала с помощью метода FindNode устанавливается место этого узла на дереве и определяется указатель на его родителя. Если искомый узел отсутствует, операция удаления завершается.

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

Функция Findnode возвращает указатель DNodePtr на узел D, подлежащий удалению. Второй указатель, PNodePtr, идентифицирует узел P – родителя удаляемого узла. Метод Delete "пытается" подыскать заменяющий узел R, который будет присоединен к родителю и, следовательно, займет место удаленного узла. Заменяющий узел R идентифицируется указателем RNodePtr.

Алгоритм поиска заменяющего узла должен рассмотреть четыре случая, зависящие от числа сыновей удаляемого узла. Заметьте, что если указатель на родителя равен NULL, то удаляется корень. Эта ситуация учитывается нашими четырьмя случаями и тем дополнительным фактором, что корень должен быть обновлен. Поскольку класс BinSTree является другом класса TreeNode, у нас есть доступ к закрытым элементам left и right.

Ситуация A: Узел D не имеет сыновей, т.е. является листом.

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

Обновление совершается путем установки RNodePtr в NULL. Когда мы присоединяем NULL-узел, родитель указывает на NULL.

RNodePtr = DNodePtr->left;... PNodePtr->right = RNodePtr;

Ситуация B: Узел D имеет только левого сына.

Присоединить левое поддерево узла D к его родителю.

Обновление совершается путем присвоения указателя на левого сына узла D в RNodePtr и последующего присоединения узла R к родителю.

RNodePtr = DNodePtr->right;... PNodePtr->left = RNodePtr;

Ситуация C: Узел D имеет правого сына, но не имеет левого сына.

Присоединить правое поддерево узла D к его родителю.

Как и в ситуации B, обновление может быть совершено путем присвоения RNodePtr указателя на правого сына узла D и последующего присоединения узла R к родителю.

RNodePtr = DNodePtr->right;... PNodePtr->left = RNodePtr;

Ситуация D: Удаление узла с двумя сыновьями.

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

Удалив узел 30, мы создали два "осиротевших" поддерева, которые должны быть вновь присоединены к дереву. Для этого требуется стратегия выбора заменяющего узла из оставшейся совокупности узлов. Результирующее дерево должно удовлетворять определению бинарного дерева поиска. Применим max-min-принцип.

Выберите в качестве заменяющего самый правый узел левого поддерева. Это — максимальный из узлов, меньших, чем удаляемый. Отсоедините этот узел (R) от дерева, присоедините его левое поддерево к его родителю в качестве правого поддерева, а затем поставьте R на место удаляемого узла. В демонстрационном дереве заменяющим является узел 28. Мы присоединяем его левого сына (26) к его родителю (25) и заменяем удаленный узел (30) заменяющим (28).

Для отыскания самого правого узла левого поддерева используется следующий простой алгоритм.

Шаг 1: Поскольку заменяющий узел R меньше, чем удаляемый узел D, перейти к левому поддереву узла D. Спуститься к узлу 25.

Шаг 2: Поскольку R является максимальным узлом левого поддерева, найти его значение, спустившись вниз по правому поддереву. Во время спуска следите за предшествующим узлом PofRNodePtr. В нашем примере спуститесь к узлу 28. PofRNodePtr указывает на узел 25.

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

1. Если правое поддерево пусто, то текущая точка — заменяющий узел R и PofRNodePtr указывает на удаляемый узел D. Мы присоединяем правое поддерево узла D в качестве правого поддерева узла R, а родителя (P) удаляемого узла присоединяем к R.

RNodePtr->right = DNodePtr->right; PNodePtr->left = RNodePtr;

2. Если правое поддерево непусто, мы идем до листового узла или узла, имеющего только левое поддерево.

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

() PofRNodePtr->right = PofR-NodePtr->left;

1. R является листом (см. рисунок выше). Отсоединить его от дерева. Поскольку RNodePtr->left равен NULL, оператор () устанавливает правого сына узла PofRNodePtr в NULL.

2. R имеет левое поддерево. Оператор () присоединяет это поддерево в качестве правого сына узла PofRNodePtr.

Алгоритм заканчивается заменой удаляемого узла узлом R. Сначала сыновья узла D присоединяются в качестве сыновей узла R. Затем узел R замещает узел D как корень поддерева, образованного узлом D.

() PofRNodePtr->right = PofRNodePtr->left;

Завершите присоединение к родительскому узлу (Р).

// удаление корневого узла. // назначение нового корня if (PNodePtr == NULL) root = RNodePtr; // присоединить R к P с правильной стороны else if (DNodePtr->data < PNodePtr->data) PNodePtr->left = RNodePtr; else PNodePtr->right = RNodePtr;

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

Метод Delete
// если элемент находится на дереве, удалить его template <class T> void BinSTree<T>::Delete(const T& item) { // DNodePtr - указатель на удаляемый узел D // PNodePtr - указатель на родительский узел P узла D // RNodePtr - указатель на узел R, замещающий узел D TreeNode<T> DNodePtr, PNodePtr, RNodePtr; // найти узел, данные в котором совпадают с item. // получить его адрес и адрес его родителя if ((DNodePtr = FindNode (item, PNodePtr)) == NULL return; // если узел D имеет NULL-указатель, то заменяющим // узлом является тот, что находится на другой ветви if (DNodePtr->right == NULL) RNodePtr = DNodePtr->left; else if (DNodePtr->left == NULL) RNodePtr = DNodePtr->right; // узел D имеет двух сыновей else { // найти и отсоединить заменяющий узел R для узла D. // в левом поддереве узла D найти максимальный узел // из всех узлов, меньших чем узел D. // отсоединить этот узел от дерева. // PofRNodePtr - указатель на родителя заменяющего узла TreeNode<T> PofRNodePtr = DNodePtr; // первой возможной заменой является левый сын узла D RNodePtr = DNodePtr->left; // спуститься вниз по правому поддереву левого сына узла D, // сохраняя указатель на текущий узел и его родителя. // остановившись, мы будем иметь заменяющий узел while (RNodePtr->right!= NULL) { PofRNodePtr = RNodePtr; RNodePtr = RNodePtr->right; } if (PofRNodePtr == DNodePtr) // левый сын удаляемого узла является заменяющим // присоединить правое поддерево узла D к узлу R RNodePtr->right = DNodePtr->right; else { // мы спустились вниз по правой ветви как минимум на один узел. // удалить заменяющий узел из дерева, // присоединив его правую ветвь к родительскому узлу PofRNodePtr->right = RNodePtr->left; } } // завершить присоединение к родительскому узлу. // удалить корневой узел. назначить новый корень. if (RNodePtr == NULL) root = RNodePtr; // присоединить узел R к узлу P с правильной стороны else if (DNodePtr->data < PNodePtr->data) PNodePtr->left = RNodePtr; else PNodePtr->right = RNodePtr; // удалить узел из памяти и уменьшить размер списка FreeTreeNode(DNodePtr); size—; }
Метод Update

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

// если текущий узел определен и элемент данных (item) совпал // с данными в этом узле, скопировать элемент данных в узел. // иначе вставить item в дерево template <class T> void BinSTree<T>::Update( const T& item) { if (current!= NULL && current->data == item) current->data = item; else Insert(item); }

Практическая задача: конкорданс

Обычной проблемой анализа текстов является определение частоты и расположения слов в документе. Эта информация запоминается в конкордансе, где различные слова перечислены в алфавитном порядке и каждое слово снабжено ссылками на строки текста, в которых оно встречается. Рассмотрим следующую цитату.

Peter Piper picked a peck of pickled peppers. A peck of pickled peppers Peter Piper picked. If Peter Piper picked a peck of pickled peppers, where is the peck that Peter Piper picked?

Слово "piper" встречается здесь 4 раза в строках 1, 2 и 3. Слово "pickled" встречается 3 раза в строках 1 и 3.

В этой задаче создается конкорданс для текстового файла следующим образом:

Вход: Открыть документ как текстовый файл и ввести текст по словам, отслеживая текущую строку.

Действие: Определить запись, которая состоит из слова, счетчика появлений и списка номеров строк, содержащих это слово. При первой встрече некоторого слова в тексте создать запись и вставить ее в дерево. Если слово уже есть в дереве, обновить частоту его появления и список номеров строк.

Выход: После ввода файла распечатать слова в алфавитном порядке вместе со счетчиками частоты и упорядоченными списками строк, где встречается каждое слово.

Структуры данных

Данными каждого узла является объект Word, содержащий символьную цепочку, счетчик частоты появлений и связанный список номеров строк текста. Объект Word содержит также номер строки, где данное слово встретилось последний раз. Это гарантирует, что мы сможем обработать несколько случаев появлений слова в строке и только один раз занести номер этой строки в список.

Функции-члены класса Word перегружают операторы отношения "==" и "<" и стандартные операторы потокового ввода/вывода.

class Word { private: // wordText - слово из текста; count - его частота String wordText; int count; // счетчик строк разделяется всеми объектами Word static int lineno; // номер последней строки, где встретилось данное слово. // используется для того, чтобы знать, когда вставлять // номер строки в lineNumbers int lastLineNo; LinkedList<int> lineNumbers; public: // конструктор Word(void); // открытые операции класса void CountWord (void); String& Key(void); // операторы сравнения, используемые классом BinSTree int operator== (const Word& w) const; int operator< (const Word& w) const; // операторы потокового ввода/вывода friend istream& operator >> (istream& istr, Word& w); friend ostream& operator << (ostream& ostr, Word& w); };

Реализация класса Word

Для каждого слова конструктор устанавливает начальное значение частоты в 0 и номер последней строки в -1. Перегружаемые операторы отношения "<" и "==" необходимы для операций вставки и поиска и реализуются путем сравнения строк двух объектов, содержащих слова.

В этом классе объявляется скрытая переменная lineno, доступная только элементам класса и друзьям. Word::lineno является статическим членом класса, и поэтому доступна всем экземплярам класса. И это правильно, так как всем этим объектам нужен доступ к номеру текущей строки входного файла. Статические элементы данных более предпочтительны, чем глобальные переменные.

Оператор ввода ">>".

Оператор ввода считывает данные из потока по одному слову за раз. Слово должно начинаться с буквы, за которой необязательно идет последовательность букв или цифр. Ввод слова начинается с чтения и выбрасывания всех небуквенных символов. Это гарантирует, что все межсловные промежутки и знаки пунктуации будут пропущены. Процесс ввода прекращается по достижении конца файла. Если встречается символ конца строки, происходит увеличение переменной lineno на единицу.

// пропустить все предшествующие пробелы и небуквенные символы while (istr.get(c) &&!isalpha(c)) // если встретился конец строки, увеличить счетчик строк текста if (c == '\n') w.lineno++;

Когда распознается начало слова, оператор ">>" накапливает символы, читая буквы и цифры до тех пор, пока не встретится не алфавитно-цифровой символ. Буквы слова преобразуются в строчные и запоминаются в локальной переменной wd. Это позволяет сделать наш конкорданс нечувствительным к регистру букв, из которых состоит слово. Если после очередного слова следует символ конца строки, он снова помещается в поток и обнаруживается во время ввода следующего слова. Функция завершается копированием переменной wd в wordText, сбросом счетчика count и присвоением переменной lastLineNo значения lineno.

// если не конец файла, ввести слово if (!istr.eof()) { // преобразовать первую букву в строчную, занести ее в wd c = tolower(c); wd[i++] = c; // последовательно считывать буквы или цифры, преобразуя их в строчные while (istr.get(c) && (isalpha(c) || isdigit(c))) wd[i++] = tolower(c); // завершить строку нулем wd[i] = '

2-й ряд. Перебрасываем кромочную петлю на рабочую спицу и провязываем 1 изнаночную.

'; // если после текущего слова встретился конец строки, // возвратить его обратно в поток для следующего слова if (c == '\n') istr.putback(c); // заключительные установки w.wordText = wd; w.count = 0; w.lastLineNo = w.lineno; }

Функция CountWord

После считывания слова из текста вызывается функция CountWord, которая обновляет значение частоты и список номеров строк. В начале функции значение счетчика count увеличивается на единицу. Если count = 1, то слово — новый элемент дерева, и номер строки, где впервые встретилось это слово, добавляется в список. Если слово уже есть в списке, то проверяется, изменился ли номер строки с момента последнего появления данного слова. Если да, то номер текущей строки заносится в список и используется для обновления lastLineNo.

// записать случай вхождения слова void Word::CountWord (void) { // увеличить частоту вхождения слова count++; // если это слово встретилось впервые или на новой строке, // вставить его в список и присвоить переменной lastLineNo // номер текущей строки. if (count == 1 || lastLineNo!= lineno) { lineNumbers.InsertRear(lineno); lastLineNo = lineno; } }

Оператор вывода "<<"

Оператор потокового вывода распечатывает слово и частоту, вслед за которыми идет упорядоченный список номеров строк, где это слово встречается.

<слово>......................<частота>: n1, n2, n3,... // вывести объект класса Word в поток ostream& operator<< (ostream& ostr, Word& w) { // вывести слово ostr << w.wordText; // вывести выровненный вправо счетчик частоты. // заполнить промежуток точками. ostr.fill('.'); ostr << setw(25-w.wordText.Length()) << w.count << ": "; ostr.fill(' '); // снова назначить пробел символом-заполнителем // пройтись по списку и распечатать номера строк for(w.lineNumbers.Reset();!w.lineNumbers.EndOfList(); w.lineNumbers.Next()) ostr << w.lineNumbers.Data() << " "; ostr << endl; return ostr; }

Программа подсчета вхождений слов (Конкорданс)

В программе определено бинарное дерево поиска concordTree, в котором хранятся объекты класса Word. После открытия текстового файла concord.txt оператор ввода потока считывает слова, пока не встретится конец файла. Каждое слово либо включается в дерево, либо используется для обновления информации о себе, если оно уже встречалось ранее. После того как все слова обработаны, выполняется симметричное прохождение, в процессе которого слова распечатываются в алфавитном порядке.

#include <iostream.h> #include <fstream.h> #include <stdlib.h> #include "word.h" // класс Word #include "bstree.h" // класс BinSTree #include "treescan.h" // метод Inorder // используется функцией Inorder void PrintWord(Word& w) { cout << w; } void main(void) { // объявить дерево объектов Word; читать из потока fin BinSTree<Word> concordTree; ifstream fin; Word w; // открыть файл concord.txt fin.open("concord.txt", ios::in | ios::nocreate); if (!fin) { cerr << "Не могу открыть concord.txt" << endl; exit(1); } // читать объекты Word из потока fin, пока не встретится конец файла while(fin >> w) { // найти w на дереве if (concordTree.Find(w) == 0) { // w нет на дереве. обновить частоту слова и включить его в дерево w.CountWord(); concordTree.Insert(w); } else { // w на дереве. обновить информацию о слове w.CountWord(); concordTree.Update(w); } } // распечатать дерево в алфавитном порядке Inorder(concordTree.GetRoot(), Print-Word); }

Файл concord.txt выглядит так:

Peter Piper picked a peck of pickled peppers. A peck of pickled peppers Peter Piper picked. If Peter Piper picked a peck of pickled peppers, where is the peck that Peter Piper picked?

Если выполнить программу с файлом concord.txt в качестве параметра, результаты будут выглядеть так:

a.............................3: 1 2 if............................1: 2 is............................1: 3 of............................3: 1 2 peck..........................4: 1 2 3 peppers.......................3: 1 2 3 peter.........................4: 1 2 3 picked........................4: 1 2 3 pickled.......................3: 1 3 piper.........................4: 1 2 3 that..........................1: 3 the...........................1: 3 where.........................1: 3

Более сложные нелинейные структуры

До сих пор мы рассматривали деревья, представляемые в виде динамически порождаемых узлов. Теперь мы опишем деревья, которые моделируют массивы в виде законченных бинарных деревьев. Они используются в приложениях, связанных с пирамидальными структурами и турнирной сортировкой. Мы подробно остановимся на пирамидах и рассмотрим их применение в пирамидальной сортировке.

Деревья бинарного поиска реализуют списки и обеспечивают среднее время поиска порядка O(log2n). Однако на несбалансированных деревьях эффективность поисковых алгоритмов снижается. В следующем номере мы рассмотрим новый тип деревьев, называемых сбалансированными или AVL-деревьями, (по фамилиям их изобретателей Г. М. Адельсона-Вельского и Е. М. Ландиса. Прим. ред.), в которых поддерживаются неизменно хорошие поисковые характеристики бинарного дерева.

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

Бинарные деревья, представляемые массивами

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

Вспомним, что законченное бинарное дерево глубины n содержит все возможные узлы на уровнях до n-1, а узлы уровня n располагаются слева направо подряд (без дыр). Массив A есть последовательный список, элементы которого могут представлять узлы законченного бинарного дерева с корнем A[0]; потомками первого уровня A[1] и A[2]; потомками второго уровня A[3], A[4], A[5] и A[6] и т.д. Корневой узел имеет индекс 0, а всем остальным узлам индексы назначаются в порядке, определяемом поперечным (уровень за уровнем) методом прохождения. На рис. 13 показано законченное бинарное дерево для массива A из десяти элементов.

int A[10] = {5, 1, 3, 9, 6, 2, 4, 7, 0, 8}

Рис. 13 Законченное бинарное дерево для 10-элементного массива А

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


Бинарные деревья


Эквивалентное представление в виде массива

Преимущества представляемых массивами деревьев обнаруживаются тогда, когда требуется прямой доступ к узлам. Индексы, идентифицирующие сыновей и родителя данного узла, вычисляются просто. В таблице, расположенной ниже, представлено дерево, изображенное на рис. 13. Здесь для каждого уровня указаны узлы, а также их родители и сыновья.

Для каждого узла A[i] в N-элементном массиве индекс его сыновей вычисляется по формулам:

Индекс левого сына = 2i (неопределен при 2i+1 > N) Индекс правого сына = 2i + 2 (не определен при 2i + 2 > N)

Уровень

Родитель

Значение

Левый сын

Правый сын

0

0

A[0] = 5

1

2

1

A[1] = 1

2

4

 

2

A[2] = 3

5

6

 

3

A[3] = 9

7

8

 

4

A[4] = 6

9

10=NULL

 

5

A[5] = 2

11=NULL

12=NULL

 

6

A[6] = 4

13=NULL

14=NULL

 

7

A[7] = 7

 

 

 

8

A[8] = 0

 

 

 

9

A[9] = 8

 

 

 

Поднимаясь от сыновей к родителю, мы замечаем, что родителем узлов A[3] и A[4] является A[1], родителем A[5] и A[6] — A[2] и т.д. Общая формула для вычисления родителя узла A[i] следующая:

Индекс родителя = (i-1)/2 (не определен при i=0)

Турнирная сортировка

Бинарные деревья находят важное применение в качестве деревьев принятия решения, в которых каждый узел представляет ситуацию, имеющую два возможных исхода. В частности, для представления спортивного турнира, проводимого по схеме с выбываниями. Каждый нелистовой узел соответствует победителю встречи между двумя игроками. Листовые узлы дают стартовый состав участников и распределение их по парам. Например, победителем теннисного турнира является Дэвид, выигравший финальную встречу с Доном. Оба спортсмена вышли в финал, выиграв предварительные матчи. Дон победил Алана, а Дэвид Мэнни. Все игры турнира и их результаты могут быть записаны в виде дерева.

В турнире с выбыванием победитель определяется очень скоро. Например, для четырех игроков понадобится всего три матча, а для 24 = 16 участников – 24 - 1 = 15 встреч.

Турнир выявляет победителя, но со вторым лучшим игроком пока не все ясно. Поскольку Дон проиграл финал победителю турнира, он может и не оказаться вторым лучшим игроком. Нам нужно дать шанс Мэнни, так как тот играл матч первого круга с, быть может, единственным игроком, способным его победить. Чтобы выявить второго лучшего игрока, нужно исключить Дэвида и реорганизовать турнирное дерево, устроив матч между Доном и Мэнни.

Как только определится победитель этого матча, мы сможем правильно распределить места.

Выиграл Мэнни: Места Дэвид Мэнни Дон Алан Выиграл Дон: Места Дэвид Дон Мэнни Алан

Турнирное дерево может использоваться для сортировки списка из N элементов. Рассмотрим эффективный алгоритм, использующий дерево, представленное в виде массива. Пусть имеется последовательно представленное дерево, содержащее N элементов листовых узлов в нижнем ряду. Эти элементы запоминаются на уровне k, где 2k > N. Предположим, что список сортируется по возрастанию. Мы сравниваем каждую пару элементов и запоминаем меньший из них (победителя) в родительском узле. Процесс продолжается до тех пор, пока наименьший элемент (победитель турнира) не окажется в корневом узле. Например, приведенное ниже дерево задает следующее начальное состояние массива из N = 8 целых чисел. Элементы запоминаются на уровне 3, где 23 = 8.

A[8] = {35, 25, 50, 20, 15, 45, 10, 40}

Со второго уровня начинаются "игры" — в родительские узлы помещаются наименьшие значения в парах. Например, "игру" между элементами Tree[7] и Tree[8] выигрывает меньший из них, и значение 25 записывается в Tree[3]. Подобные сравнения проводятся также на втором и первом уровнях. В результате последнего сравнения наименьший элемент попадает в корень дерева на уровне 0.

Как только наименьший элемент оказывается в корневом узле, он удаляется со своего старого места и копируется в массив. В первый раз в A[0] записывается 10, а затем дерево обновляется для поиска следующего наименьшего элемента. В турнирной модели некоторые матчи должны быть сыграны повторно. Поскольку число 10 изначально было в Tree[13], проигравший в первом круге Tree[14] = 40 должен снова участвовать в турнире. Tree[14] копируется в свой родительский узел Tree[6], а затем снова проводятся матчи в индексе 6 (15 побеждает 40) и в индексе 2 (15 побеждает 20). В результате 15 попадает в корень и становится вторым наименьшим элементом списка. Корень копируется в A[1], и процесс продолжается.

Процесс продолжается до тех пор, пока все листья не будут удалены. В нашем примере последний (наибольший) узел играет серию матчей, в которых побеждает всех по умолчанию. После копирования числа 50 в A[7] мы получаем отсортированный список.

Вычислительная эффективность. Эффективность турнирной сортировки составляет O(n log2n). В массиве, содержащем n = 2k элементов, для выявления наименьшего элемента требуется n-1 сравнений. Это становится ясным, когда мы замечаем, что половина участников выбывает после каждого круга по мере продвижения к корню. Общее число матчей равно

2k-1 + 2k-2 +... + 21 + 1 = n-1

Дерево обновляется, и оставшиеся n-1 элементов обрабатываются посредством k-1 сравнений вдоль пути, проходящего через родительские узлы. Общее число сравнений равно

(n-1) + (k-1)(n-1) = (n-1) + (n-1)(log2n-1) = (n-1) log2n

Хотя количество сравнений в турнирной сортировке составляет O(n log2n), использование пустот значительно менее эффективно. Дереву требуется 2n-1 узлов, чтобы вместить k-1 кругов соревнования.

Алгоритм TournamentSort. Для реализации турнирной сортировки определим класс DataNode и создадим представленное массивом дерево из объектов этого типа. Членами класса являются элемент данных, его место в нижнем ряду дерева и флажок, показывающий, участвует ли еще этот элемент в турнире. Для сравнения узлов используется перегруженный оператор "<=".

template <class T> class DataNode { public: // элемент данных, индекс в массиве, логический флажок T data; int index; int active; friend int operator <= (const DataNode<T> &x, const DataNode<T> &y); };

Сортировка реализуется с помощью функций TournamentSort и UpdateTree.

// сформировать последовательное дерево, скопировать туда элементы массива; // отсортировать элементы и скопировать их обратно в массив template <class T> void TournamentSort (T a[], int n) { DataNode<T> tree; // корень дерева DataNode<T> item; // минимальная степень двойки, большая или равная n int bottomRowSize; // число узлов в полном дереве, нижний ряд которого // имеет bottomRowSize узлов int treesize; // начальный индекс нижнего ряда узлов int loadindex; int i, j; // определить требуемый размер памяти для нижнего ряда узлов bottomRowSize = PowerOfTwo(n); // вычислить размер дерева и динамически создать его узлы treesize = 2 bottomRowSize - 1; tree = new DataNode<T>[treesize]; loadindex = treesize - bottomRowSize // скопировать массив в дерево объектов типа DataNode j = 0; for (i=loadindex; i<treesize; i++) { item.index = i; if (j < n) { item.active = 1; item.data = a[j++]; } else item.active = 0; tree[i] = item; } // выполнить начальные сравнения для определения наименьшего элемента i = loadindex; while (i > 0) { j = i; while (j < 2i); // обработать пары соревнующихся { // проведение матча. сравнить tree[j] с его соперником tree[j+1] // скопировать победителя в родительский узел if (!tree[j+1].active || tree[j] < tree[j+1]) tree[(j-1)/2] = tree[j]; else tree[(j-1)/2] = tree[j+1]; j += 2; // перейти к следующей паре } // обработать оставшиеся n-1 элементов. скопировать победителя // из корня в массив. сделать победителя неактивным. обновить // дерево, разрешив сопернику победителя снова войти в турнир for (i=0; i<n-1; i++) { a[i] = tree[0].data; tree[tree[0].index].active = 0; UpdateTree(tree, tree[0].index); } // скопировать значение в массив a[n-1] = tree[0].data; }

В функцию UpdateTree передается индекс i, указывающий исходное положение наименьшего текущего элемента в нижнем ряду дерева. Это — удаляемый узел (становится неактивным). Значению, которое "проиграло" предварительный раунд последнему победителю (наименьшему значению), разрешается снова войти в турнир.

// параметр i есть начальный индекс текущего наименьшего элемента // в списке (победителя турнира) template <class T> void UpdateTree(DataNode<T> tree, int i) { int j; // определить соперника победителя. позволить ему продолжить // турнир, копируя его в родительский узел. if (i % 2 == 0) tree [(i-1)/2] = tree[i-1]; // соперник левый узел else tree [(i-1)/2] = tree[i+1]; // соперник правый узел // переиграть те матчи, в которых принимал участие // только что исключенный из турнира игрок i = (i-1)/2; while (i > 0) { // соперником является правый или левый узел? if (i % 2 == 0) j = i-1; else j = i+1; // проверить, является ли соперник активным if (!tree[i].active ||!tree[j].active) if (tree[i].active) tree[(i-1)/2] = tree[i]; else tree[(i-1)/2] = tree[j]; // устроить соревнование. // победителя скопировать в родительский узел else if (tree[i] < tree[j]) tree[(i-1)/2] = tree[i]; else tree[(i-1)/2] = tree[j]; // перейти к следующему кругу соревнования (родительский уровень) i = (i-1)/2; } // Турнир с новым соперником закончен. // очередное наименьшее значение находится в корневом узле }

Пирамиды

Представляемые массивами деревья находят применение в имеющих большое значение приложениях с пирамидами (heaps), являющимися законченными бинарными деревьями, имеющими упорядочение узлов по уровням. В максимальной пирамиде (maximum heap) родительский узел больше или равен каждому из своих сыновей. В минимальной пирамиде (minimum heap) родительский узел меньше или равен каждому из своих сыновей. Эти ситуации изображены на рис. 14. В максимальной пирамиде корень содержит наибольший элемент, а в минимальной — наименьший.

Пирамида как список

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


Рис. 14. Максимальные и минимальные пирамиды

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

Обсудим внутреннюю организацию пирамиды в нашем классе Heap. Алгоритмы вставки и удаления элементов представляются в реализации методов Insert и Delete.

Класс Heap

Как и любой линейный или нелинейный список, класс пирамид имеет операции вставки и удаления элементов, а также операции, которые возвращают информацию о состоянии объекта, например, размер списка.

Спецификация класса Heap
ОБЪЯВЛЕНИЕ
#include <iostream.h> #include <stdlib.h> template <class T> class Heap { private: // hlist указывает на массив, который может быть динамически создан // конструктором (inArray == 0) или передан как параметр (inArray == 1) T hlist; int inArray; // максимальный и текущий размеры пирамиды int maxheapsize; int heapsize; // определяет конец списка // функция вывода сообщений об ошибке void error(char errmsg[]); // утилиты восстановления пирамидальной структуры void FilterDown(int i); void FilterUp(int i); public: // конструкторы и деструктор Heap (int maxsize); // создать пустую пирамиду Heap (const Heap<T>& H); // конструктор копирования Heap (T arr[], int n); // преобразовать arr в пирамиду Heap(void); // деструктор // перегруженные операторы: "=", "[]" Heap<T> operator= (const Heap<T>& rhs); const T& operator[] (int i); // методы обработки списков int ListSize(void) const; int ListEmpty(void) const; int ListFull(void) const; void Insert(const T& item); T Delete(void); void ClearList(void); };
ОПИСАНИЕ

Первый конструктор принимает параметр maxsize и использует его для динамического выделения памяти под массив. В исходном состоянии пирамида пуста, и новые элементы вставляются в нее с помощью метода Insert. Деструктор, конструктор копирования и оператор присваивания управляют выделением и освобождением памяти. Третий конструктор принимает в качестве параметра массив и преобразует его в пирамиду. Таким образом, клиент может навязать пирамидальную структуру любому существующему массиву и воспользоваться свойствами пирамиды.

Перегруженный оператор индекса "[]" позволяет клиенту обращаться к объекту типа heap как к массиву. Поскольку этот оператор возвращает константнyю ссылку на данные, доступ к ним осуществляется лишь в режиме "только чтение".

Методы ListEmpty, ListSize и ListFull возвращают информацию о текущем состоянии пирамиды.

Метод Delete всегда удаляет из пирамиды первый (наименьший) элемент. Метод Insert вставляет элемент в список и обеспечивает пирамидальное упорядочение.

ПРИМЕР
Heap<int> H(4); // четырехэлементная пирамида целых чисел int A[] = {15, 10, 40, 30}; // четырехэлементный массив Heap<int> K(A, 4); // преобразовать массив A в пирамиду K H.Insert(85); // вставить 85 в пирамиду H H.Insert(40); // вставить 40 в пирамиду H cout << H.Delete(); // напечатать 40 - наименьший элемент в H // распечатать пирамиду, созданную по массиву A for (int i=0; i<4; i++) cout << K[i] << " "; // напечатать 10 15 40 30 K[0] = 99; // недопустимый оператор

Реализация класса Heap

Здесь мы подробно обсудим операции вставки и удаления для пирамид, а также методы FilterUp и FilterDown. Эти вспомогательные методы отвечают за реорганизацию пирамиды при ее создании или изменении.

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

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

H.Insert(8); // вставить элемент 8 в пирамиду

Вставить 8 в A[9]. Вставить новый элемент в конец пирамиды. Эта позиция определяется индексом heapsize, хранящим текущее число элементов в пирамиде.

Отправить значение 8 на вышестоящий уровень пирамиды (по пути предков J ). Сравнить 8 с родителем 20. Поскольку сын меньше своего родителя, поменять их значения местами (см. ниже рис. A). Продолжить движение вверх. Теперь элемент 8 меньше своего родителя H[1]=10 и поэтому меняется с ним местами. Процесс завершается, так как следующий родитель удовлетворяет условию пирамидальности.

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

Чтобы поместить узел в правильную позицию, операция вставки использует метод FilterUp.

// функция для восстановления пирамиды. Начиная с индекса i, // подниматься вверх по дереву, переходя от родителя к родителя. // Менять элементы местами, если сын меньше родителя template <class T> void Heap<T>::FilterUp (int i) { int currentpos, parentpos; T target; // currentpos индекс текущего уровня в пирамиде. target вставляемое значение, // для которого выбирается правильная позиция в пирамиде currentpos = i; parentpos = (i-1)/2; target = hlist[i]; // подниматься к корню while (currentpos!= 0) { // если родитель <= target, то все в порядке. if (hlist[parentpos] <= target) break; else // поменять местами родителя с сыном и обновить индексы // для проверки следующего родителя { // переместить данные из родительской позиции в текущую. // назначить родительскую позицию текущей. проверить следующего родителя hlist[currentpos] = hlist[parentpos]; currentpos = parentpos; parentpos = (currentpos-1)/2; } } // правильная позиция найдена. поместить туда target hlist[currentpos] = target; }

Открытый метод Insert проверяет сначала заполненность пирамиды, а затем начинает операцию вставки. После записи элемента в конец пирамиды вызывается FilterUp для ее реорганизации.

// вставить в пирамиду новый элемент и восстановить ее структуру template <class T> void Heap<T>::Insert(const T& item) { // проверить, заполнена ли пирамида и выйти, если да if (heapsize == maxheapsize) error ("Пирамида заполнена"); // записать элемент в конец пирамиды и увеличить heapsize. // вызвать FilterUp для восстановления пирамидального упорядочения hlist[heapsize] = item; FilterUp(heapsize); heapsize++; }

Удаление из пирамиды. Данные удаляются всегда из корня дерева. После такого удаления корень остается ничем не занятым и сначала заполняется последним элементом пирамиды. Однако такая замена может нарушить условие пирамидальности. Поэтому требуется пробежать по всем меньшим потомкам и найти подходящее место для только что помещенного в корень элемента. Если он больше любого своего сына, мы должны поменять местами этот элемент с его наименьшим сыном. Движение по пути меньших сыновей продолжается до тех пор, пока элемент не займет правильную позицию в качестве родителя или пока не будет достигнут конец списка. В последнем случае элемент помещается в листовой узел. Например, в нижеприведенной пирамиде удаляется корневой узел 5.

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

Передвигать число 22 от корня вниз по пути, проходящему через меньших сыновей. Сравнить корень 22 с его сыновьями. Наименьший из двух, сын H[1], меньше, чем 22, поэтому следует поменять их местами (cм. ниже рис. A). Находясь на первом уровне, новый родитель сравнивается со своими сыновьями H[3] и H[4]. Наименьший из них имеет значение 11 и поэтому должен поменяться местами со своим родителем (cм. ниже рис. В). Теперь дерево удовлетворяет условию пирамидальности.

Метод Delete. Чтобы поместить узел в правильную позицию, операция удаления использует метод FilterDown. Эта функция получает в качестве параметра индекс i, с которого начинается сканирование. В данном случае метод FilterDown вызывается с параметром 0, так как замещающее значение копируется из последнего элемента пирамиды в ее корень. Метод FilterDown используется также конструктором для построения пирамиды.

// Функция для восстановления пирамиды. Начиная с индекса i, // менять местами родителя и сына так, чтобы поддерево, // начинающееся в узле i, было пирамидой template <class T> void Heap<T>::FilterDown (int i) { int currentpos, childpos; T target; // начать с узла i и присвоить его значение переменной target currentpos = i; target = hlist[i]; // вычислить индекс левого сына и начать движение вниз по пути, // проходящему через меньших сыновей до конца списка childpos = 2 i + 1; while (childpos < heapsize) // пока не конец списка { // Индекс правого сына равен child-pos+1. Присвоить переменной // childpos индекс наименьшего из двух сыновей if ((childpos+1 < heapsize) && (hlist[childpos+1] <= hlist[childpos])) childpos = childpos + 1; // Если родитель меньше сына, пирамида в порядке. Выход. if (target <= hlist[childpos]) break; else { // Переместить значение меньшего сына в родительский узел. // Теперь позиция меньшего сына не занята hlist[currentpos] = hlist[childpos]; // обновить индексы и продолжить сканирование currentpos = childpos; childpos = 2 currentpos + 1; } } // поместить target в только что ставшую свободной позицию hlist[currentpos] = target; }

Открытый метод Delete копирует значение из корневого узла во временную переменную, а затем замещает корень последним элементом пирамиды. После этого heapsize уменьшается на единицу. FilterDown реорганизует пирамиду. Значение, сохраненное во временной переменной, возвращается клиенту.

// возвратить значение корневого элемента и обновить пирамиду. // попытка удаления элемента из пустой пирамиды влечет за собой // выдачу сообщения об ошибке и прекращение программы template <class T> T Heap<T>::Delete(void) { T tempitem; // проверить, пуста ли пирамида if (heapsize == 0) error ("Пирамида пуста"); // копировать корень в tempitem. заменить корень последним элементом // пирамиды и уменьшить на единицу значение переменной heapsize tempitem = hlist[0]; hlist[0] = hlist[heapsize-1]; heapsize—; // вызвать FilterDown для установки нового значения корня FilterDown(0); // возвратить исходное значение корня return tempitem; }

Преобразование массива в пирамиду. Один из конструкторов класса Heap использует существующий массив в качестве входного параметра и преобразует его в пирамиду. Ко всем нелистовым узлам применяется метод FilterDown. Индекс последнего элемента пирамиды равен n-1. Индекс его родителя равен

currentpos = ((n - 1) - 1) / 2 = (n - 2) / 2

и определяет последний нелистовой узел пирамиды. Этот индекс является начальным для преобразования массива. Если применить метод FilterDown ко всем индексам от currentpos до 0, то можно гарантировать, что каждый родительский узел будет удовлетворять условию пирамидальности. В качестве примера рассмотрим целочисленный массив

int A[10] = {9, 12, 17, 30, 50, 20, 60, 65, 4, 19} Индексы листьев: 5, 6,..., 9 Индексы родительских узлов: 4, 3,..., 0

Приведенные ниже рисунки иллюстрируют процесс преобразования пирамиды. Для всех вызовов FilterDown соответствующее поддерево выделено на рисунках треугольником.

FilterDown(4). Родитель H[4] = 50 больше своего сына H[9] = 19 (см. исходный список) и поэтому должен поменяться с ним местами (см. рис. A).


(A)

FilterDown(3). Родитель H[3] = 30 больше своего сына H[8] = 4 и поэтому должен поменяться с ним местами (см. рис. B).


(B)

На уровне 2 родитель H[2] = 17 уже удовлетворяет условию пирамидальности, поэтому вызов FilterDown(2) не производит никаких перестановок.

FilterDown(1). Родитель H[1] = 12 больше своего сына H[3] = 4 и поэтому должен поменяться с ним местами (C).

FilterDown(0). Процесс прекращается в корневом узле. Родитель H[0] = 9 должен поменяться местами со своим сыном H[1]. Результирующее дерево является пирамидой (D).

(C)

(D)

КОНСТРУКТОР
// конструктор преобразует исходный массив в пирамиду. // массив и его размер передаются в качестве параметров template <class T> Heap<T>::Heap(T arr[], int n) { int j, currentpos; // n <= 0 является недопустимым размером массива if (n <= 0) error ("Неправильный размер массива"); // использовать n для установки размера пирамиды и максимального размера // пирамиды. Копировать массив arr в список пирамиды maxheapsize = n; heapsize = n; hlist = arr; // присвоить переменной currentpos индекс последнего родителя. // вызывать FilterDown в цикле с индексами currentpos..0 currentpos = (heapsize-2)/2; while (currentpos >= 0) { FilterDown(currentpos); currentpos—-; } // присвоить флажку inArray значение True inArray = 1; }

Пирамидальная сортировка

Пирамидальная сортировка имеет эффективность O(n log2n). Алгоритм использует тот факт, что наименьший элемент находится в корне (индекс 0) и что метод Delete возвращает это значение.

Для осуществления пирамидальной сортировки массива A объявите объект типа Heap с массивом A в качестве параметра. Конструктор преобразует A в пирамиду. Сортировка осуществляется последовательным удалением A[0] и вставкой его в A[N-1], A[N-2],..., A[1]. Вспомните, что с момента исключения элемента из пирамиды элемент больше не является частью пирамиды, а элемент, бывший до этого хвостовым, замещает корневой. Мы имеем возможность скопировать удаленный элемент в освободившуюся позицию массива. В процессе пирамидальной сортировки очередные наименьшие элементы удаляются и последовательно запоминаются в хвостовой части массива. Таким образом, массив A сортируется по убыванию.

Пирамидальная сортировка пятиэлементного массива A осуществляется посредством следующих действий:

int A[] = {50, 20,75, 35, 25}

исходная пирамида

Удалить 20 и запомнить в A[4] Удалить 25 и запомнить в A[3]

Удалить 35 и запомнить в A[2] Удалить 50 и запомнить в A[1]

Поскольку единственный оставшийся элемент 75 является корнем, массив отсортирован: A = 75 50 35 25 20.

Ниже приводится реализация алгоритма пирамидальной сортировки.

Функция HeapSort
#include "heap.h" // класс Heap template <class T> // отсортировать массив A по убыванию void HeapSort (T A[], int n) { // преобразуем A в пирамиду Heap<T> H(A, n); T elt; // цикл заполнения элементов A[n-1]... A[1] for (int i=n-1; i>=1; i--) { // исключить наименьший элемент из пирамиды и запомнить его в A[i] elt = H.Delete(); A[i] = elt; } }

Вычислительная эффективность пирамидальной сортировки. Массив, содержащий n элементов соответствует законченному бинарному дереву глубиной k = log2n. Начальная фаза преобразования массива в пирамиду требует n/2 операций FilterDown. Каждой из них требуется не более k сравнений. На второй фазе сортировки операция FilterDown выполняется n-1 раз. В худшем случае она требует k сравнений. Объединив обе фазы, получим худший случай сложности пирамидальной сортировки:

k n/2 + k (n - 1) = k (3n/2 - 1) = log2n (3n/2 - 1)

Итак, сложность алгоритма имеет порядок O(n log2n).

Пирамидальная сортировка не требует никакой дополнительной памяти, поскольку производится на месте. Турнирная сортировка является алгоритмом порядка O(n log2n), но требует создания последовательно представляемого массивом дерева из 2(k+1) узлов, где k наименьшее целое, при котором n < 2k. Некоторые O(n log2n) сложные сортировки дают O(n2) в худшем случае. Пирамидальная сортировка всегда имеет сложность O(n log2n) независимо от исходного распределения данных.

Сравнение методов сортировки

Массив A, содержащий 2000 случайных целых чисел, сортируется с помощью функции HeapSort (пирамидальная сортировка). В целях сравнения массивы B и C заполняются теми же элементами и сортируются с помощью функций TournamentSort (турнирная сортировка) и ExchangeSort (обменная сортировка). Функция обменной сортировки ExchangeSort:

// поменять значения двух переменных целого типа х и у void Swap(int & х, int & у) { int temp == х; // сохранить первоначальное значение х х = у; // заменить х на у у = temp; // присвоить переменной у } // сортировать целый массив п-элементов а в возрастающем порядке void ExchangeSort(int a[], int n) { int i, j; // реализовать n — 1 проходов.найти правильные значения в а[],...,a[n-2]. for(i = 0; i < n-1; i++) // поместить минимум из a[n+l]...а[п-1] в a[i] for(j = i+1; j < n; j++) // поменять местами, если a[i] > a[j] if (a[i] > a[j]) Swap(a[i], a[j]) ; }

Сортировки хронометрируются функцией TickCount, которая возвращает число 1/60 долей секунды, прошедших с момента старта системы. Сортировка обменом, имеющая сложность O(n2), позволит четко представить быстродействие турнирного и пирамидального методов, имеющих сложность O(n log2n). Функция PrintFirst_Last распечатывает первые и последние пять элементов массива. Код этой функции не включен в листинг программы.

#include <iostream.h> #include "random.h" #include "toursort.h" #include "heapsort.h" #include "ticks.h" enum SortType {heap, tournament, exchange}; void TimeSort (int A, int n, char sortName, SortType sort) { long tcount; // TickCount системная функция. возвращает число 1/60 долей // секунды с момента старта системы cout << "Испытывается " << sortName << ":" << endl; // засечь время. отсортировать массив А. подсчитать затраченное // время в 1/60 долях секунды tcount = TickCount(); switch(sort) { case heap: HeapSort(A,n); break; case tournament: Tournament-Sort(A, n); break; case exchange: ExchangeSort(A, n); break; } tcount = TickCount() - tcount; // распечатать 5 первых и 5 последних элементов отсортированного массива for (int i=0; i<5; i++) cout << A[i] << " "; cout << "..."; for (i=n-5; i<<n; i++) cout << A[i] << " "; cout << endl; cout << "Продолжительность " << tcount << "\n\n"; } void main(void) { // указатели массивов A, B и C int A, B, C; RandomNumber rnd; // динамическое выделение памяти и загрузка массивов A = new int [2000]; B = new int [2000]; C = new int [2000]; // загрузить в массивы одни и те же 2000 случайных чисел for (int i=0; i<2000; i++) A[i] = B[i] = C[i] = rnd.Random(10000); TimeSort(A, 2000, "пирамидальная сортировка ", heap); delete [] A; TimeSort(B, 2000, "турнирная сортировка ", heap); delete [] B; TimeSort(C, 2000, "сортировка обменом ", heap); delete [] C; } / <Прогон программы> Испытывается пирамидальная сортировка : 9999 9996 9996 9995 9990... 11 10 9 6 3 Продолжительность 16 Испытывается турнирная сортировка : 3 6 9 10 11... 9990 9995 9996 9996 9999 Продолжительность 36 Испытывается сортировка обменом : 3 6 9 10 11... 9990 9995 9996 9996 9999 Продолжительность 818 /

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

Copyright © 1994-2016 ООО "К-Пресс"


Источник: http://www.k-press.ru/cs/2000/3/trees/trees.asp


Закрыть ... [X]

Как сделать украшение на свадебную машину своими руками (фото) Вязать кофту из кос спицами

Схема плетения славянский пояс Схема плетения славянский пояс Схема плетения славянский пояс Схема плетения славянский пояс Схема плетения славянский пояс Схема плетения славянский пояс Схема плетения славянский пояс