asyan.org
добавить свой файл
1

Лабораторна робота 5

Бінарне дерево пошуку


Meта: ознайомитись із структурою даних оптимізованою для пошуку — бінарним деревом пошуку деревом.

Хід роботи

Базовий рівень (максимально 10 балів)


1. Реалізуєте бінарне дерево пошуку.

2. Сформуйте 6 наборів даних довжини N=10:

  • набір 1   числа відсортовані за зростанням;

  • набір 2   числа відсортовані за спаданням;

  • набори 3-5   випадкові данні;

  • набір 6   випадкові данні, контрольний набір.

Набори повинні містити цілі числа у діапазони з діапазону [0..1,5*N]

3. Для кожного з наборів 1-5, додайте всі числа з набору у дерево. Обрахуйте кількість операцій, які необхідні щоб знайти кожне з чисел набору 6 у дереві, або впевнитися, що такого числа немає. Данні занесіть в таблицю. Для наборів 3-5 усереднить отримані результати.

4. Повторіть кроки 2 та 3 для N = 100,N=1000, N=10000.

5. Зробіть висновок щодо ефективності використання бінарного дерева пошуку, алгоритмічної складності алгоритму, побудуєте графіки.

Поглиблений рівень (+ 5 балів)


1. Реалізуйте алгоритм видалення елементів з бінарного дерева пошуку.

2. Для кожного з наборів 1-5, додайте всі числа з набору у дерево. Обрахуйте кількість операцій, які необхідні щоб видалити числа з набору 6 із дерева. Данні запишіть у таблицю.

3. Повторіть крок 2 для N = 100, N=1000, N=10000.

4. Зробіть висновки, побудуйте графіки.