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


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


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



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