Основы офисного программирования и язык VBA


Класс BinTree - часть 2


Написать не рекурсивный алгоритм, который обходил бы все узлы дерева некоторым заданным образом не так то просто. Другое дело рекурсивное определение. Действительно базисное решение очевидно, - когда дерево пусто, то ничего и делать не надо. Если же оно не пусто, то у нас есть корень дерева, а у него два потомка, которые в свою очередь являются деревьями. Поэтому для обхода всего дерева достаточно посетить корень, а затем обойти (рекурсивно) оба поддерева. Меняя порядок посещения корня и поддеревьев, получаем три различных способа обхода дерева. Заметим, именно благодаря тому, что сама структура данных рекурсивна, рекурсивные алгоритмы естественным образом описывают решения задач по обработке таких данных. Рекурсивные определения просты и понятны, но напоминают некоторый фокус. Наиболее сложно воспроизвести вычисления, выполняемые рекурсивным алгоритмом.
  • Для простоты в методе SearchAndInsert мы совместили две операции поиска элемента по заданному ключу и вставки нового элемента. Если в дереве найден элемент с заданным ключом, то предполагается, что речь идет о поиске и возвращается информация из информационного поля этого элемента. Если в дереве нет элемента с таким ключом, то создается новый узел дерева. Заметьте, что наше решение не позволяет производить замену элемента, а в процессе поиска не уведомляет об отсутствии элемента с заданным ключом
  • Удаление элемента из дерева поиска осложняется тем, что нужно поддерживать структуру дерева поиска. В тех случаях, когда нужно удалить элемент, у которого есть два потомка, вызывается специальная процедура ReplaceAndDelete. Эта процедура ищет кандидата, который мог бы заменить удаляемый элемент, сохраняя структуру дерева.
  • Недостатком деревьев поиска является то, что они могут быть плохо сбалансированы и могут иметь относительно длинные ветви. Так, если при создании дерева поиска, ключи будут поступать в отсортированном порядке, то дерево будет представлено одной ветвью. Работа с этой структурой данных предполагает, что при создании и добавлении элементов в дерево ключи поступают в случайном порядке, хорошо перемешанные.Эта структура особенно применима в тех случаях, когда в процессе работы над данными широко используются все операции - поиск, вставка и удаление.
  • Мы не стали писать реализацию этого класса, оперирующего с данными, хранящимися в списках Excel или базе данных Access, поскольку это выходит за рамки этой лекции.



  • Начало  Назад  Вперед



    Книжный магазин