Двоичное дерево поиска (BST) - это древовидная структура данных, в которой каждый узел имеет не более двух дочерних элементов, которые называются левым и правым дочерними элементами, а самый верхний узел в дереве называется корнем. Он дополнительно удовлетворяет свойству двоичного поиска, которое гласит, что ключ в каждом узле должен быть больше или равен любому ключу, хранящемуся в левом поддереве, и меньше или равен любому ключу, хранящемуся в правом поддереве.

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

В этом посте мы перечислили часто задаваемые вопросы интервью по дереву двоичного поиска:

  1. Вставка в BST
  2. Искать заданный ключ в BST
  3. Удаление из BST (двоичного дерева поиска)
  4. Построить сбалансированный BST из заданных ключей
  5. Определить, является ли данное двоичное дерево BST или нет
  6. Проверить, представляют ли данные ключи одни и те же BST или нет, без построения BST
  7. Найти предшественника в порядке для данного ключа в BST
  8. Найти наименьшего общего предка (LCA) двух узлов в BST
  9. Найти k наименьший и k наибольший элемент в BST
  10. Найти пол и потолок в двоичном дереве поиска
  11. Преобразование двоичного дерева в BST с сохранением его исходной структуры
  12. Удалить узлы из BST, ключи которых находятся за пределами допустимого диапазона
  13. Найти пару с заданной суммой в BST
  14. Найти k-й наименьший узел в дереве двоичного поиска (BST)
  15. Найти преемника в порядке для данного ключа в BST
  16. Замените каждый элемент массива наименьшим большим элементом справа
  17. Исправить двоичное дерево, которое всего в одном свопе от того, чтобы стать BST
  18. Обновить каждый ключ в BST, чтобы он содержал сумму всех больших ключей
  19. Проверить, представляет ли данная последовательность предварительный обход BST
  20. Построить двоичное дерево поиска на основе постзаказной последовательности
  21. Построить двоичное дерево поиска из последовательности предварительного заказа
  22. Подсчитайте поддеревья в BST, узлы которых лежат в заданном диапазоне
  23. Найдите размер самого большого BST в двоичном дереве
  24. Распечатать полное двоичное дерево поиска (BST) в порядке возрастания
  25. Распечатать двоичную древовидную структуру с ее содержимым на C ++
  26. Найти оптимальную стоимость построения бинарного дерева поиска
  27. Структура данных Treap
  28. Реализация структуры данных Treap (вставка, поиск и удаление)
  29. Объединить два BST в двусвязный список в отсортированном порядке
  30. Постройте сбалансированный по высоте BST из несбалансированного BST
  31. Построить BST со сбалансированной высотой из отсортированного двусвязного списка
  32. Найти тройку с заданной суммой в БСТ
  33. Преобразование двоичного дерева поиска в минимальную кучу

Благодарим за прочтение.