Работа с двоичными деревьями: построение, поиск, удаление, включение и обход

     Рисунок 4.6 – Функция walk() 

     Функция walk() в качестве аргумента принимает указатель на node двоичного дерева поиска. Функция распечатывает  в отсортированном виде содержимое дерева, корнем которого является узел node.

     Код этой функции прост. Если node является нулевым указателем, то печатать нечего. В противном случае печатается левое поддерево узла node, затем значение самого узла и правое поддерево.

     Теперь  нужно определить открытую функцию, которая будет использовать функцию walk() (см. Рисунок 4.7). 

     void bin_walk(const struct bin_tree *tree)

     {

           assert(tree != NULL);

           walk(tree->root);

     }

     Рисунок 4.7 – Функция bin_walk() 

     Эта функция не требует объяснений. Она  проверяет, не является ли аргумент tree нулевым, и вызывает функцию walk(), которая и выводит элементы двоичного дерева на печать.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

5 Описание программной реализации 

      5.1 Функциональная схема программы 

      На  рисунке 5.1 представлена обобщённая схема, показывающая последовательность выполнения функциональных блоков программы.

 

 

 
 

 

 
 
 
 

 
 
 

      Рисунок 5.1 – Схема функциональных блоков программы 

     5.2 Комплект поставки и порядок  инсталляции  

     Для инсталляции программного продукта необходимо запустить с дискеты файл Install.exe, после чего будет выбрана директория установки и произведён запуск программы.

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

• WBT.exe – демонстрационная программа;
• 1h.txx, 2h.txx – файлы, содержащие теоретические сведения по материалу;
• N.txx, Y.txx – файлы интерфейса программы;

 

6 АНАЛИЗ  ЭФФЕКТИВНОСТИ РЕАЛИЗУЕМОГО МЕТОДА

 

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

     6.1 Общая оценка поиска в двоичном  дереве 

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

     Максимальное  время поиска по двоичному дереву зависит от его высоты. Если высота дерева равна 5, тогда для определения того, содержится ли искомый элемент в дереве, требуется в наихудшем случае выполнить пять сравнений. Двоичное дерево с n узлами будет иметь высоту не менее log₂n, а максимальная высота может оказаться n, если дерево сконструировано небрежно. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

7 АНАЛИЗ  РЕЗУЛЬТАТА 

     Пример  работы с двоичным деревом. 

     

     

     

       

       
 

       
 

     Рисунок 7.1 – Двоичное дерево 

     Прежде  всего нужно создать дерево. Для  создания дерева необходимо отвести под него какую-то область памяти. Сделать это можно с помощью функции malloc() (см. п. 4.4).

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

     Пусть искомым значением будет 15. В функцию  поиска bin_search()     (см. п. 4.5, рис. 4.3) в качестве параметров передаём наше дерево tree и значение item, равное 15. Проверяем аргументы с помощью функции Assert() (см.    п. 4.5, рис. 4.3). Удостоверяемся, что tree не является нулевым указателем и начинаем поиск с самого начала(т.е. с корня дерева). Функция содержит бесконечный цикл, в котором происходит сравнение искомого значения 15 с значениями, имеющимися в дереве. Алгоритм поиска основан на том, что точно известно, что в левом поддереве содержатся меньшие значения, а в правом – большие значения.

     Первая  проверка if(node == NULL) на существование дальнейших элементов даёт положительный результат. Далее сравниваем значения корня с искомым элементом 15. 8<15, поэтому все значения, содержащиеся в левом поддереве, не могут иметь значение 15. Поэтому функция присвоит элементу node значение 14 правого поддерева. Смотрим: 14<15, значит, опять переходим вправо, на значение 20. 20>15, поэтому переходим влево от значения 20 на значение 15. 15=15, поэтому процедура возвратит значение 1, возвещающее о том, что искомое значение найдено.

     Допустим, мы ищем значение 2. Смотрим корень: 8>2, поэтому, если значение 2 есть в дереве, то оно может быть только в левом поддереве. 5>2, поэтому переходим влево, но там нет элемента, поэтому срабатывает проверка (if node == NULL) и функция возвращает значение 0, возвещающее о том, что искомое значение не найдено.

     Теперь  пошаговое описание того, как было сформировано дерево на    рис. 7.1.

     При нажатии клавиши Ins в ПП программа  запрашивает значение, которое передаётся как параметр в функцию bin_insert() (см. п. 4.6 рис. 4.4). Аналогичная функции поиска проверка аргументов. Затем инициализируем node значением корня дерева и присваиваем переменной new адрес указателя на корень дерева. Корнем дерева стало значение 8. Основной цикл повторяется для каждого уровня дерева. При этом выполняются проверки, аналогичные тем, которые происходят в функции поиска bin_search(), за исключением лишь того, что если подобного элемента в дереве нет, то он добавляется.

     Далее добавляем значение 5. Смотрим: 5<8, значит нужно сформировать левое  поддерево. Поэтому левый указатель  из корня будет указывать на 5, а правый указатель так и останется NULL. Добавляем 7. Смотрим сначала: 7<8, поэтому оно должно пойти влево, но там уже содержится 5, поэтому сравниваем: 5<7, и оба указателя (хотя нас интересует только правый) у 5 равны NULL, значит, 7 пойдёт вправо от 5. Оба указателя у 7 равны NULL, а правый указатель у 5 указывает на 7. Далее добавляем элемент 14. Смотрим: 14>8, значит, 14 уйдёт вправо. Правый указатель у 8 равен NULL, поэтому смело ориентируем его на 14. Добавляем элемент 20: 8<20, переходим вправо на 14. 14<20, поэтому 20 идёт вправо. Правый указатель у 14 указывает на 20. Добавляем 15: 8<15, 14<15, 20>15, поэтому 15 идёт влево от 20. Добавляем 10: 10>8, 14>10, поэтому 10 идёт влево от 14. Оба указателя у 14 заняты:  левый указывает на 10, а правый – на 20.

     Затем проверим ситуацию с одинаковыми элементами: допустим, пользователь по-ошибке решил опять добавить элемент 5. Смотрим: 5<8, поэтому идём влево, но там уже есть элемент с таким же значением, поэтому функция возвращает значение 2, возвещающее о том, что элемент уже существует.

     Рассмотрим  удаление элемента из дерева. При нажатии  клавиши Del в ПП программа запрашивает  значение, которое передаётся как  параметр в функцию bin_delete() (см. п. 4.6 рис. 4.5). В функции происходит раннее упомянутая проверка аргументов и уже известный алгоритм поиска элемента. Допустим, что мы удаляем элемент 0. Если функция не находит такого значения, то она возвращает значение 0, возвещающее о том, что такого элемента в дереве нет. Удаляем 10. Цикл в начале функции и есть алгоритм поиска, и если значение item найдено, то вместо выполнения вставки, как в функции bin_insert(), цикл просто завершается. После завершения цикла точно известно присутствие удаляемого элемента, а указатель z указывает на узел, который необходимо удалить, а q – на указатель, который привёл нас в узел z. Итак, смотрим: корень 8<10, поэтому 10 может содержаться только в правом поддереве. Дальше: 14<10, значит, уходим влево и находим искомый элемент, чем обуславливаем выход из цикла. Теперь, чтобы удалить значение z, нужно рассмотреть три случая:

     а) У узла z нет правого дочернего  узла, значит, узел z можно заменить его левым дочерним узлом. Указатель  на z(*q) заменяется указателем на левый дочерний узел. Если же узел z не имеет и левого указателя (т.е. и левый, и правый указатели равны NULL), то значение *q заменяется на NULL.

     В нашем случае, при удалении 10, у 10 нет дочерних узлов, поэтому это  самый простой случай. Левый указатель 14 заменяем на NULL.

     б) У узла z есть правый дочерний узел, но у того нет левого дочернего узла (см. Рис 7.2).

     

     

     

     

     

     

       

       
 
 

     Рисунок 7.2 – Удаление (2 случай) 

     Правый  дочерний узел узла z (его значение равно 12) получает левое поддерево узла z (левое поддерево в данном случае состоит всего из одного элемента 9). Затем он заменяет собой узел z.

     в) У узла z есть правый дочерний узел, и у правого дочернего узла есть левый дочерний узел (см. рис. 7.3). 

     

     

     

       

     

     

     

     

     

     

       

       
 

     Рисунок 7.3 – Удаление (3 случай)

     Итак, удаляемый узел 0. У 10 есть правый дочерний узел 15, а у 15 есть левый дочерний узел 14, поэтому проходим по левому дочернему узлу от 15 до тех пор, пока не встретится последний левый элемент в этом поддереве. В нашем случае он равен 13. 13 заменяет собой 10, а вся остальная структура остаётся прежней.