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

       

Деревья поиска


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

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

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



Содержание раздела