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


         

Написать не рекурсивный алгоритм, который


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



  • Содержание  Назад  Вперед