Двоичное дерево поиска (BST) - это древовидная структура данных, в которой каждый узел имеет не более двух дочерних элементов, которые называются левым и правым дочерними элементами, а самый верхний узел в дереве называется корнем. Он дополнительно удовлетворяет свойству двоичного поиска, которое гласит, что ключ в каждом узле должен быть больше или равен любому ключу, хранящемуся в левом поддереве, и меньше или равен любому ключу, хранящемуся в правом поддереве.
Деревья двоичного поиска позволяют быстро искать, добавлять и удалять элементы. Они хранят свои ключи в отсортированном порядке, поэтому поиск и другие операции могут использовать принцип двоичного поиска: при поиске ключа в дереве (или места для вставки нового ключа) они перемещаются по дереву от корня к листу. , сравнивая ключи, хранящиеся в узлах дерева, и на основе сравнения решая продолжить поиск в левом или правом поддеревьях. В среднем это означает, что каждое сравнение позволяет операциям пропускать примерно половину дерева, так что каждый поиск, вставка или удаление занимает время, пропорциональное логарифму количества элементов, хранящихся в дереве. Это намного лучше, чем линейное время, необходимое для поиска элементов по ключу в (несортированном) массиве, но медленнее, чем соответствующие операции с хеш-таблицами.
В этом посте мы перечислили часто задаваемые вопросы интервью по дереву двоичного поиска:
- Вставка в BST
- Искать заданный ключ в BST
- Удаление из BST (двоичного дерева поиска)
- Построить сбалансированный BST из заданных ключей
- Определить, является ли данное двоичное дерево BST или нет
- Проверить, представляют ли данные ключи одни и те же BST или нет, без построения BST
- Найти предшественника в порядке для данного ключа в BST
- Найти наименьшего общего предка (LCA) двух узлов в BST
- Найти k наименьший и k наибольший элемент в BST
- Найти пол и потолок в двоичном дереве поиска
- Преобразование двоичного дерева в BST с сохранением его исходной структуры
- Удалить узлы из BST, ключи которых находятся за пределами допустимого диапазона
- Найти пару с заданной суммой в BST
- Найти k-й наименьший узел в дереве двоичного поиска (BST)
- Найти преемника в порядке для данного ключа в BST
- Замените каждый элемент массива наименьшим большим элементом справа
- Исправить двоичное дерево, которое всего в одном свопе от того, чтобы стать BST
- Обновить каждый ключ в BST, чтобы он содержал сумму всех больших ключей
- Проверить, представляет ли данная последовательность предварительный обход BST
- Построить двоичное дерево поиска на основе постзаказной последовательности
- Построить двоичное дерево поиска из последовательности предварительного заказа
- Подсчитайте поддеревья в BST, узлы которых лежат в заданном диапазоне
- Найдите размер самого большого BST в двоичном дереве
- Распечатать полное двоичное дерево поиска (BST) в порядке возрастания
- Распечатать двоичную древовидную структуру с ее содержимым на C ++
- Найти оптимальную стоимость построения бинарного дерева поиска
- Структура данных Treap
- Реализация структуры данных Treap (вставка, поиск и удаление)
- Объединить два BST в двусвязный список в отсортированном порядке
- Постройте сбалансированный по высоте BST из несбалансированного BST
- Построить BST со сбалансированной высотой из отсортированного двусвязного списка
- Найти тройку с заданной суммой в БСТ
- Преобразование двоичного дерева поиска в минимальную кучу
Благодарим за прочтение.