Методические указания для выполнения лабораторных работ по дисциплине "Структуры и алгоритмы обработки данных"

Страницы работы

17 страниц (Word-файл)

Фрагмент текста работы

  1. Дополнительная операция - определение критерия сбалансированности для узлов дерева (нерекурсивная форма).
  2. Алгоритмы операций АТД реализуются в нерекурсивной форме. Дополнительная операция - определение К –го по порядку значения ключа в дереве (рекурсивная форма).
  3. Алгоритмы операций АТД реализуются в рекурсивной форме. Дополнительная операция - вставка элемента в корень дерева.
  4. Алгоритмы операций АТД реализуются в нерекурсивной форме. Дополнительная операция - объединение двух поддеревьев (рекурсивная форма).
  5. Алгоритмы операций АТД реализуются в рекурсивной форме. Дополнительная операция - горизонтальное инвертирование дерева (нерекурсивная форма).
  6. Алгоритмы операций АТД реализуются в нерекурсивной форме. Дополнительная операция - вывод данных всех узлов, расположенных на заданном уровне дерева (рекурсивная форма).
  7. Алгоритмы операций АТД реализуются в рекурсивной форме. Дополнительная операция - вывод ключей всех узлов, расположенных в поддереве заданного элемента в порядке «снизу - вверх.» (нерекурсивная форма).
  8. Алгоритмы операций АТД реализуются в нерекурсивной форме. Дополнительная операция - вывод ключей всех узлов, расположенных в поддереве заданного элемента в порядке «снизу - вверх.» (рекурсивная форма).
  9. Алгоритмы операций АТД реализуются в рекурсивной форме. Дополнительная операция - вывод ключей всех узлов, расположенных в поддереве заданного элемента в порядке «сверху - вниз.» (нерекурсивная форма).
  10. Алгоритмы операций АТД реализуются в нерекурсивной форме. Дополнительная операция - вывод ключей всех узлов, расположенных в поддереве заданного элемента в порядке «сверху - вниз.» (рекурсивная форма).
    Лабораторная работа № 4.

"Нелинейные коллекции данных - сбалансированные деревья поиска".

Задание: На базе двоичного дерева поиска спроектировать,  реализовать и провести тестовые испытания АТД для нелинейной коллекции - "Сбалансированное дерево поиска".

Операции АТД "Сбалансированное дерево поиска":

·  опрос количества узлов в дереве Size,

·  проверка пустого дерева Еmpty,

·  поиск элемента в дереве Find,

·  опрос высоты дерева,

·  очистка дерева Clear

·  включение нового элемента по ключу в дерево Insert,

·  удаление элемента по ключу из дерева Delete,

Методические указания к лабораторной работе:

  1. Рандомизированное дерево, АВЛ - дерево и Красно - Черное дерево (RB - дерево) реализовать как модификацию АТД "Дерево двоичного поиска" с помощью технологии наследования классов.
  2. АТД "2-3 дерево" реализовать, как самостоятельный класс.
  3. Получить оценки эффективности операций Find, Insert, Delete относительно количества узлов в дереве, выраженные в средней на операцию глубине пути в дереве.
  1. Трудоемкость операций измеряется в средней на операцию длине пути в дереве.
  2. При тестировании рассмотреть варианты худшего и среднего случаев работы операций.

Варианты заданий:

1.  АТД "АВЛ - дерево" - модификация АТД "Рекурсивное дерево двоичного поиска.

2.  АТД "АВЛ - дерево" - модификация АТД "Нерекурсивное дерево двоичного поиска.

3.  , АТД " RB - дерево" - модификация АТД "Рекурсивное дерево двоичного поиска.

4.  , АТД " RB - дерево" - модификация АТД "Нерекурсивное дерево двоичного поиска.

5.  АТД "Рекурсивное 2-3 дерево".

6.  АТД "Нерекурсивное 2-3 дерево".

7.  АТД " Рандомизированное дерево" - модификация АТД "Рекурсивное дерево двоичного поиска.

8.  АТД "Рандомизированное дерево" - модификация АТД "Нерекурсивное

Похожие материалы

Информация о работе