Бинарные деревья и деревья поиска
Деревья являются одной из важнейших структур данных в информатике. Они естественным образом возникают при решении множества задач: от представления иерархической информации (файловые системы, оргструктуры) до организации эффективного поиска и сортировки данных.
В этом разделе мы изучим:
- Бинарные деревья — базовую структуру, где каждый узел имеет не более двух детей
- Обходы деревьев — систематические способы посещения всех узлов
- Двоичные деревья поиска (BST) — деревья, поддерживающие эффективный поиск, вставку и удаление
- Сбалансированные деревья — АВЛ-деревья и красно-чёрные деревья, гарантирующие логарифмическую высоту
- Б-деревья — деревья для работы с внешней памятью
- Деревья отрезков — структуру для эффективных запросов на отрезках
Определение
Дерево — это связный ациклический граф. Связность означает, что из любой вершины можно добраться в любую другую; ацикличность — отсутствие циклов.
Деревья обладают важными свойствами:
Свойства
- В дереве с $n$ вершинами ровно $n-1$ рёбер.
- Между любыми двумя вершинами дерева существует единственный путь.
- При удалении любого ребра дерево становится несвязным.
- При добавлении любого ребра в дереве появляется ровно один цикл.
- 12.1. Бинарные деревья: определения и свойства
- 12.2. Обходы деревьев
- 12.3. Двоичное дерево поиска: операции
- 12.4. BST: анализ сложности
- 12.5. АВЛ-деревья
- 12.6. Красно-чёрные деревья (основы)
- 12.7. Б-деревья
- 12.8. Деревья отрезков (основы) {class=“children children-type-tree children-sort-”}