topic_11.md

Бинарное дерево поиска (Binary Search Tree, BST)

Определение бинарного дерева поиска

Бинарное дерево поиска (BST) — это структура данных, где:

1. Все узлы в левом поддереве текущего узла имеют значения меньше, чем значение текущего узла.
2. Все узлы в правом поддереве текущего узла имеют значения больше, чем значение текущего узла.

Особенности

• Поддерживает быстрые операции поиска, вставки и удаления.
• Средняя сложность: ( O(\log n) ).
• Худшая сложность (несбалансированное дерево): ( O(n) ).

---

Алгоритм операции удаления ключа из дерева

Удаление узла в бинарном дереве поиска включает три варианта:

1. Удаление узла без потомков (лист):

   • Узел удаляется, разрывается связь с родительским узлом.

2. Удаление узла с одним потомком:

   • Удаляемый узел заменяется своим потомком.

3. Удаление узла с двумя потомками:

   • Находится минимальный элемент в правом поддереве (преемник).
   • Значение преемника копируется в удаляемый узел.
   • Преемник удаляется.

---

Методы обхода дерева

Обход дерева — это процесс посещения всех узлов дерева в определённом порядке.

Основные виды обхода:

1. Обход в глубину (DFS):

   • Прямой (Pre-order): сначала обрабатывается корень, затем левое и правое поддеревья.
   • Симметричный (In-order): сначала левое поддерево, затем корень, затем правое поддерево.
   • Обратный (Post-order): сначала левое и правое поддеревья, затем корень.

2. Обход в ширину (BFS):

   • Узлы обрабатываются уровнями, начиная с корня.

---

Назначение обходов дерева

1. Прямой обход (Pre-order):

   • Используется для копирования структуры дерева или создания префиксной записи выражений.

2. Симметричный обход (In-order):

   • Применяется для извлечения значений из BST в отсортированном порядке.

3. Обратный обход (Post-order):

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

4. Обход в ширину (BFS):

   • Используется для поиска узлов на определённом уровне или проверки свойств уровня дерева.