Алгоритм поиска элемента двоичного дерева по ключу

1. Если дерево пусто, сообщить, что узел не найден, и остановиться.

2. Иначе сравнить K со значением ключа корневого узла X.

2.1. Если K=X, выдать ссылку на этот узел и остановиться

2.1.1. Иначе, если K>X, рекурсивно искать ключ K в правом поддереве Т.

2.1.2. Иначе (если K<X) рекурсивно искать ключ K в левом поддереве Т.

 

Поиск элемента В дерева

 

Благодаря структуре этого дерева и постоянно поддерживаемому балансу, поиск осуществляется за логарифмическое время от количества элементов. Сам алгоритм описывается следующим образом. Пусть ищется значение X в заданном В -дереве.

Алгоритм поиска элемента В дерева

1. Начинаем от корня

2. Если X –один из ключей текущего узла, то СТОП, ключ найден.

Иначе находим пару соседних ключей Y, Z, таких что X лежит в интервале от Y до Z.

3. Переходим к потомку между Y и Z.

4. Возврат к шагу 2.

5. Если дошли до листа и Х нет среди ключей, то СТОП, ключ и элемент не найден.

 

Порядок выполнения лабораторной работы

 

Подготовка к работе

 

Подготовка предполагает выполнение следующих этапов.

1. Знакомство со всеми разделами руководства.

2. Разработка алгоритма и программы построения двоичного дерева поиска.

3. Разработка алгоритма и программы построения В+ дерева.

Последовательность выполнения лабораторной работы

 

1. Разработать алгоритм и программу построения двоичного дерева поиска:

a) Получить у преподавателя задание на величину диапазона значений ключей и размер их массива n.

b) Сформировать массив ключей, значения которых задаются с помощью датчика случайных чисел.

c) По заданию преподавателя упорядочить значения ключей по возрастанию (убыванию).

d) Приняв за корень элемент с ключом из середины массива (ключ с номером n / 2), построить двоичное дерево поиска. Информационные поля узлов дерева можно оставить пустыми.

e) Вывести значения ключей по уровням дерева.

2. Разработать алгоритм и программу построения В+ дерева:

a) Получить у преподавателя задание на количество ярусов, величину диапазона значений ключей и размер их массива n на каждом ярусе.

b) Сформировать массив ключей, значения которых задаются с помощью датчика случайных чисел.

c) По заданию преподавателя упорядочить значения ключей по возрастанию (убыванию).

d) Приняв за корень элемент с ключом из середины массива (ключ с номером n / 2), построить В+ дерево. Информационные поля узлов дерева можно оставить пустыми.

e) Вывести значения ключей по уровням дерева.

3. Разработать алгоритм и программу поиска заданного преподавателем типа (по совпадению, интервалу или близости) на двоичном и В+ дереве.

4. Оценить сложность разработанных алгоритмов.

 

Содержание отчета о выполненной работе

 

Отчет должен содержать следующее.

· Название и цель работы, а также исходные данные.

· Пошаговые алгоритмы построения двоичного и В+ дерева, а также тексты их программ.

· Распечатки результатов, полученных с помощью ЭВМ.

· Пошаговые алгоритмы поиска на двоичном и В+ дереве, а также тексты их программ.

· Выводы о сложности разработанных алгоритмов.

 

Контрольные вопросы

 

1. Для каких задач предпочтительными являются древовидные структуры данных?

2. Какие типы деревьев используются в программировании?

3. Что представляет собой двоичное дерево?

4. Чем отличается упорядоченное двоичное дерево от обычного?

5. Что представляет собой узел дерева?

6. Что такое поддерево?

7. Как задаются связи между узлами дерева?

8. Какие характеристики имеют деревья?

9. Чем отличается В+ дерево от двоичного?

10. Какие основные операции выполняются над деревьями?

11. Как строится двоичное дерево?

12. Как может быть выполнен обход узлов дерева?

13. Какие типы операций поиска существуют?

14. Чем отличается поиск по совпадению от поиска по близости?

15. Как выполняется поиск на двоичном дереве?

16. Как выполняется поиск на В+ дереве?

 

Библиографический список

 

1. Никлаус Вирт Алгоритмы и структуры данных. Новая версия для Оберона [Электронный ресурс]/ Никлаус Вирт— Электрон. текстовые данные.— М.: ДМК Пресс, 2010.— 272 c.

2. Синюк В.Г. Алгоритмы и структуры данных [Электронный ресурс]: лабораторный практикум. Учебное пособие/ Синюк В.Г., Рязанов Ю.Д.— Электрон. текстовые данные.— Белгород: Белгородский государственный технологический университет им. В.Г. Шухова, ЭБС АСВ, 2013.— 204 c.

3. Иванов И.П. Сборник задач по курсу «Алгоритмы и структуры данных» [Электронный ресурс]: методические указания/ Иванов И.П., Голубков А.Ю., Скоробогатов С.Ю.— Электрон. текстовые данные.— М.: Московский государственный технический университет имени Н.Э. Баумана, 2013.— 36 c.

4. Комлева Н.В. Структуры и алгоритмы компьютерной обработки данных [Электронный ресурс]: учебное пособие/ Комлева Н.В.— Электрон. текстовые данные.— М.: Евразийский открытый институт, Московский государственный университет экономики, статистики и информатики, 2004.— 140 c.

Приложение 1

Типы алгоритмов,
исследуемых в лабораторной работе 1

1. Составить программу, которая формирует одномерный массив из n случайных чисел. Определить среднее арифметическое этих чисел. Значение n меняется в пределах от 10 до 50 миллионов.

2. Составить программу, которая формирует одномерный массив из n случайных чисел. Получить из него два новых массива: один из четных чисел, а другой из нечетных. Значение n меняется в пределах от 10 до 50 миллионов.

3. Составить программу, которая формирует одномерный массив из n случайных чисел. Определить сумму отрицательных чисел и отдельно сумму остальных. Значение n меняется в пределах от 10 до 50 миллионов.

4. Составить программу, которая формирует одномерный массив из n случайных чисел. Определить количество четных чисел и количество нечетных чисел. Значение n меняется в пределах от 10 до 50 миллионов.

5. Составить программу, которая формирует одномерный массив из n случайных чисел. Отдельно определить произведение четных чисел, и произведение нечетных чисел. Значение n меняется в пределах от 10 до 50 миллионов.

6. Составить программу, которая формирует матрицу из n*n случайных чисел. Определить произведение чисел, лежащих на главной диагонали матрицы. Значение n меняется в пределах от 5 до 10 тысяч.

7. Составить программу, которая формирует матрицу из n*n случайных чисел. Определить произведение чисел, лежащих на побочной диагонали матрицы. Значение n меняется в пределах от 5 до 10 тысяч.

8. Составить программу, которая формирует матрицу из n*n случайных чисел. Определить сумму чисел, лежащих выше главной диагонали матрицы. Значение n меняется в пределах от 5 до 10 тысяч.

9. Составить программу, которая формирует матрицу из n*n случайных чисел. Определить произведение всех чисел в матрице. Значение n меняется в пределах от 5 до 10 тысяч.

10. Составить программу, которая формирует матрицу из n*n случайных чисел. Определить сумму отрицательных чисел и отдельно сумму остальных. Значение n меняется в пределах от 5 до 10 тысяч.

11. Составить программу, которая формирует матрицу из n*n случайных чисел. Определить количество четных чисел и количество нечетных. Значение n меняется в пределах от 5 до 10 тысяч.

 

Приложение 2

Типы алгоритмов,
исследуемых в лабораторной работе 2

1. Разработать алгоритм и программу простого линейного поиска с циклом For. В качестве исходных данных использовать строку текста, из которой необходимо выделить слова. Аргумент поиска – слово.

2. Разработать алгоритм и программу ускоренного линейного поиска. В качестве исходных данных использовать строку текста, из которой необходимо выделить слова. Аргумент поиска – слово.

3. Разработать алгоритм и программу дихотомического поиска. В качестве исходных данных использовать массив целых чисел, который вводится с клавиатуры. Аргумент поиска – число.

4. Разработать алгоритм и программу дихотомического поиска. В качестве исходных данных использовать массив целых чисел, который формируется с помощью датчика случайных чисел с диапазоном от 0 до 100. Аргумент поиска – число.

5. Разработать алгоритм и программу интерполирующего поиска. В качестве исходных данных использовать массив целых чисел, который вводится с клавиатуры. Аргумент поиска – число.

6. Разработать алгоритм и программу интерполирующего поиска. В качестве исходных данных использовать массив целых чисел, который формируется с помощью датчика случайных чисел с диапазоном от 0 до 100. Аргумент поиска – число.

7. Разработать алгоритм и программу простого линейного поиска с циклом For. В качестве исходных данных использовать строку текста, из которой необходимо выделить слова. Затем слова упорядочить по алфавиту. Аргумент поиска – слово.

8. Разработать алгоритм и программу ускоренного линейного поиска. В качестве исходных данных использовать строку текста, из которой необходимо выделить слова. Затем слова упорядочить по алфавиту. Аргумент поиска – слово.

Приложение 3

Типы алгоритмов,
исследуемых в лабораторной работе 3

Разработать следующие алгоритмы и программы с использованием рекурсии.

1. Линейного поиска целочисленного значения ключа в заданном массиве и вывода этого массива.

2. Линейного поиска слова в заданном массиве и вывода этого массива.

3. Дихотомического поиска целочисленного значения ключа в заданном массиве и вывода этого массива.

4. Интерполирующего поиска целочисленного значения ключа в заданном массиве и вывода этого массива.

5. Вычисления целой степени целого числа.

6. Вычисления целой степени вещественного числа.

7. Перевода целого числа, введенного с клавиатуры, в двоичную систему счисления.

8. Перевода целого числа, введенного с клавиатуры, в систему счисления с основанием q.

9. Ввода одномерного массива и линейного поиска целочисленного значения ключа в нем.

10. Ввода одномерного массива слов и линейного поиска заданного слова в нем.

11. Ввода одномерного массива и дихотомического поиска целочисленного значения ключа в нем.

12. Ввода одномерного массива и интерполирующего поиска целочисленного значения ключа в нем.

 

 

Приложение 4

Типы алгоритмов,
исследуемых в лабораторной работе 4

1. Составить две программы, которые реализуют алгоритмы простой сортировки «пузырьком» и вставками. Исходные данные задавать с помощью датчика случайных чисел.

2. Составить две программы, которые реализуют алгоритмы простой сортировки «пузырьком» и выбором. Исходные данные задавать с помощью датчика случайных чисел.

3. Составить две программы, которые реализуют алгоритмы простой сортировки «пузырьком» и шейкером. Исходные данные задавать с помощью датчика случайных чисел.

4. Составить две программы, которые реализуют алгоритмы простой сортировки «пузырьком» и слиянием. Исходные данные задавать с помощью датчика случайных чисел.

5. Составить две программы, которые реализуют алгоритмы простой сортировки «пузырьком» и быстрой сортировки. Исходные данные задавать с помощью датчика случайных чисел.

6. Составить две программы, которые реализуют алгоритмы простой сортировки «пузырьком» и сортировки Шелла. Исходные данные задавать с помощью датчика случайных чисел.

7. Составить две программы, которые реализуют алгоритмы простой сортировки «пузырьком» и методом Боуза- Нельсона. Исходные данные задавать с помощью датчика случайных чисел.

8. Составить две программы, которые реализуют алгоритмы ускоренной сортировки «пузырьком» и вставками. Исходные данные задавать с помощью датчика случайных чисел.

9. Составить две программы, которые реализуют алгоритмы ускоренной сортировки «пузырьком» и выбором. Исходные данные задавать с помощью датчика случайных чисел.

10. Составить две программы, которые реализуют алгоритмы ускоренной сортировки «пузырьком» и шейкером. Исходные данные задавать с помощью датчика случайных чисел.

11. Составить две программы, которые реализуют алгоритмы ускоренной сортировки «пузырьком» и слиянием. Исходные данные задавать с помощью датчика случайных чисел.

12. Составить две программы, которые реализуют алгоритмы ускоренной сортировки «пузырьком» и быстрой сортировки. Исходные данные задавать с помощью датчика случайных чисел.

13. Составить две программы, которые реализуют алгоритмы ускоренной сортировки «пузырьком» и сортировки Шелла. Исходные данные задавать с помощью датчика случайных чисел.

14. Составить две программы, которые реализуют алгоритмы ускоренной сортировки «пузырьком» и методом Боуза- Нельсона. Исходные данные задавать с помощью датчика случайных чисел.

 

 

Приложение 5

Типы деревьев,
исследуемых в лабораторной работе 5

 

Вариант 1

1. Построить двоичное дерево, содержащее n = 15 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 100.

2. Построить В+ дерево, содержащее n = 15 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 100.

3. Обеспечить обход деревьев «сверху вниз».

4. Выполнить поиск значения ключа по совпадению.

 

Вариант 2

1. Построить двоичное дерево, содержащее n = 16 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 150.

2. Построить В+ дерево, содержащее n = 16 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 150.

3. Обеспечить обход деревьев «снизу вверх».

4. Выполнить поиск значения ключа по близости снизу.

 

Вариант 3

1. Построить двоичное дерево, содержащее n = 12 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 80.

2. Построить В+ дерево, содержащее n = 12 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 80.

3. Обеспечить симметричный обход деревьев.

4. Выполнить поиск значения ключа по близости сверху.

Вариант 4

1. Построить двоичное дерево, содержащее n = 20 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 180.

2. Построить В+ дерево, содержащее n = 20 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 180.

3. Обеспечить обход деревьев «сверху вниз».

4. Выполнить поиск значения ключа по совпадению.

 

Вариант 5

1. Построить двоичное дерево, содержащее n = 20 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 180.

2. Построить В+ дерево, содержащее n = 20 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 180.

3. Обеспечить обход деревьев «снизу вверх».

4. Выполнить поиск значения ключа по близости снизу.

 

Вариант 6

1. Построить двоичное дерево, содержащее n = 20 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 200.

2. Построить В+ дерево, содержащее n = 20 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 200.

3. Обеспечить симметричный обход деревьев.

4. Выполнить поиск значения ключа по близости сверху.

 

 

Вариант 7

1. Построить двоичное дерево, содержащее n = 18 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 160.

2. Построить В+ дерево, содержащее n = 18 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 160.

3. Обеспечить обход деревьев «сверху вниз».

4. Выполнить поиск значения ключа по совпадению.

 

Вариант 8

1. Построить двоичное дерево, содержащее n = 14 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 120.

2. Построить В+ дерево, содержащее n = 14 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 120.

3. Обеспечить обход деревьев «снизу вверх».

4. Выполнить поиск значения ключа по близости снизу.

 

Вариант 9

1. Построить двоичное дерево, содержащее n = 15 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 140.

2. Построить В+ дерево, содержащее n = 15 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 140.

3. Обеспечить симметричный обход деревьев.

4. Выполнить поиск значения ключа по близости сверху.

 

 

Вариант 10

1. Построить двоичное дерево, содержащее n = 20 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 200.

2. Построить В+ дерево, содержащее n = 20 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 200.

3. Обеспечить обход деревьев «сверху вниз».

4. Выполнить поиск значения ключа по совпадению.

 

Вариант 11

1. Построить двоичное дерево, содержащее n = 18 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 160.

2. Построить В+ дерево, содержащее n = 18 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 160.

3. Обеспечить обход деревьев «снизу вверх».

4. Выполнить поиск значения ключа по близости снизу.

 

Вариант 12

1. Построить двоичное дерево, содержащее n = 16 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 120.

2. Построить В+ дерево, содержащее n = 16 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 120.

3. Обеспечить симметричный обход деревьев.

4. Выполнить поиск значения ключа по близости сверху.

 

 

Вариант 13

1. Построить двоичное дерево, содержащее n = 12 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 100.

2. Построить В+ дерево, содержащее n = 12 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 100.

3. Обеспечить обход деревьев «сверху вниз».

4. Выполнить поиск значения ключа по совпадению.

 

Вариант 14

1. Построить двоичное дерево, содержащее n = 18 узлов. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 160.

2. Построить В+ дерево, содержащее n = 18 узлов и имеющее степень m = 5. Значения ключей в узлах задавать с помощью датчика случайных чисел с диапазоном D от 0 до 160.

3. Обеспечить обход деревьев «снизу вверх».

4. Выполнить поиск значения ключа по близости снизу.

 

 

 

 

ОГЛАВЛЕНИЕ

 

Лабораторная работа №1 Изучение методов оценки алгоритмов 1

 

Лабораторная работа №2 Исследование и оценка алгоритмов поиска 13

 

Лабораторная работа № 3 Разработка рекурсивных алгоритмов 23

 

Лабораторная работа №4 Исследование и оценка алгоритмов сортировки 29

 

Лабораторная работа №5 Исследование и оценка алгоритмов поиска на деревьях 47

 

Библиографический список 67

 

Приложения 68