Бинарные свойства

Двоичное дерево поиска обладает следующими свойствами:

  • Левое поддерево узла содержит только узлы с ключами меньше ключа узла.
  • Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла.
  • Не должно быть повторяющихся узлов.

Поиск ключа

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

Вставка ключа

Новый ключ всегда вставляется в лист. Мы начинаем поиск ключа от корня, пока не наткнемся на конечный узел. Как только конечный узел найден, новый узел добавляется как дочерний элемент конечного узла.

Удалить ключ

При удалении узла есть три возможности:

  • Удаляемый узел является листом: просто удалите его из дерева.
  • У удаляемого узла есть только один дочерний элемент: скопируйте дочерний элемент в узел и удалите его.
  • У узла, который нужно удалить, есть два потомка: Найти преемника узла по порядку. Скопируйте содержимое неупорядоченного преемника в узел и удалите неупорядоченного преемника. Обратите внимание, что предшественник также может быть использован.

https://gist.github.com/nerohoop/9b3eb3be59c88e93a92f1a8753ef94ea

Временная сложность операции удаления в наихудшем случае составляет O(h), где h — высота двоичного дерева поиска. В худшем случае нам, возможно, придется путешествовать от корня к самому глубокому конечному узлу. Высота перекошенного дерева может стать n, а временная сложность операции удаления может стать O(n).

Преимущества BST перед Hash Table

  1. Мы можем получить все ключи в отсортированном порядке, просто выполнив Inorder Traversal BST. Это не естественная операция в хеш-таблицах и требует дополнительных усилий.
  2. Выполнение статистики порядка, поиск ближайших меньших и больших элементов, выполнение запросов диапазона легко сделать с помощью BST. Как и сортировка, эти операции не являются естественными операциями с хеш-таблицами.
  3. BST легко реализовать по сравнению с хешированием, мы можем легко реализовать свой собственный BST. Для реализации хеширования мы обычно полагаемся на библиотеки, предоставляемые языками программирования.
  4. С самобалансирующимся BST все операции гарантированно выполняются за время O(Logn). Но при хешировании Θ(1) — это среднее время, и некоторые конкретные операции могут быть дорогостоящими, особенно когда происходит изменение размера таблицы.

Строительство и преобразование

Построить BST из заданного обхода предварительного заказа

Хитрость заключается в том, чтобы установить диапазон {min .. max} для каждого узла. Инициализируйте диапазон как {INT_MIN .. INT_MAX}. Первый узел обязательно будет в пределах досягаемости, поэтому создайте корневой узел. Чтобы построить левое поддерево, установите диапазон как {INT_MIN …root-›data}. Если значения находятся в диапазоне {INT_MIN .. root-›data}, значения являются частью левого поддерева. Чтобы построить правильное поддерево, установите диапазон как {root-›data..max .. INT_MAX}.

Построить BST из заданного обхода предварительного порядка Итеративный

  1. Создайте пустой стек.
  2. Сделайте первое значение корневым. Поместите его в стек.
  3. Продолжайте извлекать, пока стек не пуст, а следующее значение больше, чем верхнее значение стека.
  4. Сделайте это значение правым дочерним элементом последнего извлеченного узла. Поместите новый узел в стек.
  5. Если следующее значение меньше верхнего значения стека, сделайте это значение левым дочерним элементом верхнего узла стека. Поместите новый узел в стек.

Преобразование двоичного дерева в двоичное дерево поиска

  1. Создайте временный массив, в котором хранится неупорядоченный обход дерева.
  2. Отсортируйте временный массив.
  3. Копировать элементы массива в узлы дерева один за другим.

Сбалансированное дерево

Как определить, сбалансировано ли бинарное дерево по высоте?

Пустое дерево сбалансировано по высоте. Непустое бинарное дерево T сбалансировано, если

  1. Левое поддерево T сбалансировано
  2. Правое поддерево T сбалансировано
  3. Разница между высотами левого и правого поддеревьев не более 1.

Мы можем оптимизировать реализацию, вычислив высоту в той же рекурсии, а не вызывая функцию высоты отдельно.

Отсортированный массив в сбалансированный BST

  1. Получите середину массива и сделайте его корневым.
  2. Рекурсивно сделайте то же самое для левой половины и правой половины.
  3. Получите середину левой половины и сделайте ее левым дочерним элементом
  4. Получите середину правой половины и сделайте ее правильным ребенком

Отсортированный связанный список для сбалансированного BST

  1. Получите середину связанного списка и сделайте его корневым.
  2. Рекурсивно сделайте то же самое для левой половины и правой половины.
  3. Получите середину левой половины и сделайте ее левым дочерним элементом
  4. Получите середину правой половины и сделайте это правильно, ребенок

Преобразование BST в Min-Heap

Если нам разрешено использовать дополнительное пространство, мы можем выполнить неупорядоченный обход дерева и сохранить ключи в вспомогательном массиве. Поскольку мы выполняем неупорядоченный обход BST, массив будет отсортирован.

Если нам нужно сделать это без дополнительного места, нам нужно сначала преобразовать двоичное дерево поиска в отсортированный связанный список. Мы можем сделать это, обходя BST по порядку.

Построить BST из заданного обхода порядка уровней

Идея состоит в том, чтобы использовать очередь для построения дерева. Нам нужна подробная информация об узле, связанная с каждым узлом, которая указывает диапазон. Все подузлы текущего узла должны находиться в этом диапазоне.

Проверка и наименьший/наибольший элемент

Проверьте, является ли бинарное дерево BST или нет

Выполните обход заданного дерева по порядку и сохраните результат во временном массиве. Проверяем, отсортирован ли временный массив по возрастанию, если да, то дерево BST.

Проверьте, есть ли у каждого внутреннего узла BST ровно один дочерний узел.

Учитывая предварительный обход BST, проверьте, есть ли у каждого нелистового узла только один дочерний узел. Предположим, что BST содержит уникальные записи.

При обходе в прямом порядке потомки каждого узла появляются после узла. Если у корневого узла есть только один потомок, то все потомки либо меньше, либо больше корня.

  1. Найдите следующего преемника (или потомка) узла в предварительном порядке.
  2. Найдите последнего преемника в предварительном порядке (последний элемент в pre[]) узла.
  3. Если оба преемника меньше текущего узла или оба преемника больше текущего узла, продолжаем. В противном случае верните ложь.

Найдите k-й наименьший элемент в BST

Мы можем легко получить отсортированные элементы, используя неупорядоченный обход. Этот метод принимает O (n).

Другой метод заключается в поддержании ранга каждого узла. Мы можем отслеживать элементы в дереве при его построении. Поскольку нам нужен K-й наименьший элемент, мы можем поддерживать количество элементов левого поддерева в каждом узле.

K-й по величине элемент в BST, когда модификация BST не разрешена

Идея состоит в том, чтобы выполнить обход BST в обратном порядке. Обход в обратном порядке обходит все узлы в порядке убывания. Выполняя обход, мы отслеживаем количество посещенных узлов. Когда count становится равным k, мы останавливаем обход и печатаем ключ.