Дерево поиска
-
Определение дерева поиска
- Дерево поиска — древовидная структура данных для поиска ключей в наборе.
- Ключ для каждого узла должен быть больше ключей в поддеревьях слева и меньше ключей в поддеревьях справа.
-
Преимущества деревьев поиска
- Эффективное время поиска при условии сбалансированности дерева.
- Возможность эффективного вставки и удаления элементов при поддержании баланса дерева.
- Часто используются для реализации ассоциативного массива.
-
Виды деревьев поиска
- Бинарное дерево поиска: каждый узел содержит ключ и два поддерева, левое и правое.
- B-дерево: переменное количество поддеревьев в каждом узле, не обязательно заполнены данными.
- (a,b)-дерево: все листья имеют одинаковую глубину, каждый узел имеет от a до b дочерних элементов.
- Троичное дерево поиска: каждый узел хранит один символ, дерево упорядочено как бинарное, но может иметь третий узел.
-
Алгоритмы поиска
- Поиск определенного ключа: рекурсивный и повторяющийся алгоритмы.
- Поиск минимального и максимального значений: минимум в самом дальнем левом узле, максимум в самом дальнем правом узле.