4.1. Структуры bst - деревьев

Для хранения BST-деревьев используются две альтернативные структуры – массив элементов дерева и связная структура дерева на базе адресных указателей.

Массив элементов используется в случае, если задано предельное количество элементов (размер дерева), которые будут размещены в BST-дереве. В этом случае для хранения дерева выделяется массив заданного размера, тип которого совпадает с типом элементов множества, хранящегося в дереве. Корень дерева размещается в элементе массива с индексом 0, а его левый и правый сыновья – с индексом 1 и 2 соответственно. По индексу любого элемента легко вычислить индексы его сыновей и родителя в массиве. Если некоторый элемент имеет индекс i, то его левый сын расположен по индексу 2i+1, а правый сын – по индексу 2i+2. Индекс родителя вычисляется, как целая часть от деления (i-1)/2 (рис.17).

Рис. 17. Схема размещения BST-дерева в массиве.

Как видно из примера, приведенного на рис. 15, хранение дерева приводит к неэффективному использованию памяти массива. Поэтому использовать массив рекомендуется для хранения полных деревьев, в которых каждый узел имеет двух сыновей.

Наиболее распространённой формой для хранения деревьев является связная структура на базе адресных указателей. Каждый узел дерева размещается в динамической памяти и содержит помимо ключа и данных два указателя на левого и правого сыновей. Таким образом, структура через указатели на сыновей обеспечивает спуск по дереву от корня к местоположению узла с заданным значением ключа. Для некоторых операций требуется подъём от некоторого узла к родительскому узлу и далее к корню. Для этого в структуру узла можно ввести дополнительный указатель на родителя. Но это приводит к неоправданным затратам памяти на дополнительные указатели в узлах. Поэтому эти указатели используются только в отдельных разновидностях деревьев. Как правило, естественное поведение алгоритма операции, обеспечивает возврат по ранее пройденному пути в дереве.

В дерево вводится вспомогательный указатель, содержащий адрес корневого узла. Если дерево пусто, то указатель содержит значение nil (рис. 18).

Р ис. 18. Связная структура BST-дерева.

4.2. Задание к лабораторной работе

1. Спроектировать, реализовать и провести тестовые испытания АТД «BST-дерево» для коллекции, содержащей данные произвольного типа. Тип коллекции задаётся клиентской программой.

Двоичное дерево поиска (Binary Search Tree – BST) представляет упорядоченное, иерархическое, ассоциативное множество элементов, между которыми существуют структурные отношения «предки – потомки».

Интерфейс АТД «BST-дерево» включает следующие операции:

• опрос размера дерева,

• очистка дерева,

• проверка дерева на пустоту,

• доступ к данным с заданным ключом,

• включение данных с заданным ключом,

• удаление данных с заданным ключом,

• обход узлов дерева по схеме, заданной в варианте задания,

• дополнительная операция, заданная в варианте задания.

• итератор для доступа к данным в дереве с операциями:

• установка на первый узел в дереве с минимальным ключом,

• установка на последний узел в дереве с максимальным ключом,

• проверка состояния итератора,

• доступ по чтению и записи к данным текущего узла в дереве,

• переход к следующему по значению ключа узлу в дереве,

• переход к предыдущему по значению ключа узлу в дереве,

Для тестирования коллекции интерфейс АТД «BST – дерево» включает дополнительные операции:

• вывод структуры дерева на экран,

• опрос числа просмотренных операцией узлов дерева.

2. Выполнить отладку и тестирование всех операций АТД «BST-дерево» с помощью меню операций.

3. Выполнить тестирование средней трудоёмкости операций поиска, вставки и удаления элементов для вырожденного и случайного BST-дерева.

4. Провести сравнительный анализ экспериментальных показателей трудоёмкости операций.

5. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

1. пункты 1 – 5 (см. раздел 2.2),

6. описание методики тестирования трудоёмкости операций,

7. таблицы и графики с полученными оценками трудоёмкости операций для вырожденного и случайного BST-дерева. Должны быть приведены графики среднего числа пройденных узлов для операций поиска, вставки и удаления (графики совмещены в одной системе координат),

8. сравнительный анализ теоретических и экспериментальных оценок трудоёмкости для операций BST-дерева,

9. сравнительный анализ экспериментальных оценок трудоёмкости для различных операций BST-дерева,

10. пункты 10 – 12 (см. раздел 2.2),