Dvoichnye-Derevya-Poiska (1) (1)

1.

Двоичные Деревья
Поиска
Двоичное дерево поиска — это структура данных, которая хранит
элементы в упорядоченном виде, позволяя эффективно выполнять поиск,
вставку и удаление элементов.

2.

Основные Свойства
Двоичного Дерева Поиска
1
Упорядоченность
2
Рекурсивность
Для любого узла значение в
Каждое поддерево также
левом поддереве меньше,
является двоичным деревом
чем значение в узле, а
поиска.
значение в правом
поддереве больше.
3
Отсутствие дубликатов
В дереве не может быть узлов с одинаковыми значениями.

3.

Эффективность Операций в
Двоичном Дереве Поиска
Операция
Средняя Сложность
Худшая Сложность
Поиск
O(log n)
O(n)
Вставка
O(log n)
O(n)
Удаление
O(log n)
O(n)

4.

Поиск Элемента в Двоичном Дереве Поиска
Начальная Точка
Начинаем с корневого узла дерева.
Сравнение
Сравниваем значение искомого элемента с текущим узлом.
Перемещение
Если значение меньше, переходим к левому поддереву; если больше, переходим к правому поддереву.
Повторение
Повторяем шаги 2-3, пока не найдем искомый элемент или не достигнем пустого узла.

5.

Вставка Элемента в Двоичное
Дерево Поиска
1
Поиск Места
Используем алгоритм поиска, чтобы найти место для вставки
нового узла.
2
Создание Узла
Создаем новый узел, содержащий вставляемое значение.
3
Подключение Узла
Подключаем новый узел к дереву в найденное место,
соблюдая порядок.

6.

Удаление Элемента из Двоичного Дерева Поиска
Случай 1: Лист
Случай 2: Один Потомок
Случай 3: Два Потомка
Просто удаляем узел.
Заменяем узел единственным
Заменяем узел своим преемником
потомком.
(наименьшим значением в правом
поддереве).

7.

Применение Двоичных Деревьев
Поиска
Базы Данных
Компиляторы
Используются для организации и поиска
Используются для хранения
данных в таблицах.
символьной таблицы, которая
отображает имена переменных на их
значения.
Алгоритмы
Операционные Системы
Используются в алгоритмах сортировки,
Используются для управления
поиска и других задачах, где требуется
файловой системой и процессами.
упорядоченность.