Бинарное дерево поиска в C++

Бинарное дерево поискаДвоичное или бинарное дерево поиска или BST, как его обычно называют, представляет собой двоичное дерево, которое подходит под следующие условия:

  1. Узлы, которые меньше корневого узла, который помещается как левый дочерний элемент BST.
  2. Узлы, которые больше, чем корневой узел, размещенный как правый дочерний элемент BST.
  3. Левое и правое поддеревья, в свою очередь, являются бинарными деревьями поиска.

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

Пример BST показан ниже:

Пример BST

Бинарные деревья поиска также называют «упорядоченными двоичными деревьями» из-за такого особого порядка узлов.

Из приведенного выше BST видно, что в левом поддереве есть узлы меньше корня, то есть 45, а в правом поддереве есть узлы больше 45.

Теперь давайте обсудим некоторые основные операции BST.

Основные операции

1) Вставка

Операция вставки добавляет новый узел в бинарное дерево поиска.

Алгоритм операции вставки бинарного дерева поиска приведен ниже:

Как показано в приведенном выше алгоритме, мы должны убедиться, что узел размещен в соответствующей позиции, чтобы не нарушать порядок BST:

Порядок BST

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

2) Удаление

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

Следовательно, в зависимости от того, какой узел мы должны удалить, у нас есть следующие случаи удаления в BST:

Читать также:  Приоритетная очередь в STL

1) Когда узел является конечным узлом

Когда удаляемый узел является конечным узлом, мы удаляем узел напрямую:

Удаляемый узел является конечным узлом

2) Когда у узла есть только один дочерний элемент

Когда у удаляемого узла есть только один дочерний узел, мы копируем дочерний узел и удаляем дочерний узел:

У удаляемого узла есть только один дочерний узел

3) Когда у узла есть два потомка — преемника

Если удаляемый узел имеет двух дочерних элементов, то мы находим неупорядоченный преемник для узла, а затем копируем неупорядоченный преемник в узел. Позже мы удаляем преемника по порядку:

Удаляемый узел имеет двух дочерних элементов

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

3) Поиск

Операция поиска BST ищет конкретный элемент, идентифицированный как «ключ» в BST. Преимущество поиска элемента в BST состоит в том, что нам не нужно искать все дерево. Вместо этого из-за порядка в BST мы просто сравниваем ключ с корнем.

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

Ниже приведен алгоритм операции поиска в BST:

Алгоритм поиска в BST

Если мы хотим найти ключ со значением 6 в приведенном выше дереве, то сначала мы сравниваем ключ с корневым узлом, т.е. если (6==7) => Нет, если (6<7) =Да; это означает, что мы будем опускать правое поддерево и искать ключ в левом поддереве.

Читать также:  Структура данных очереди в C++

Далее спускаемся к левому поддереву. Если (6 == 5) => Нет.

Если (6 < 5) => Нет; это означает, что 6>5, и мы должны двигаться вправо.

Если (6==6) => Да; ключ найден.

4) Обходы

Мы уже обсуждали обходы бинарного дерева. В случае BST мы также можем пройти по дереву, чтобы получить последовательность inOrder, preorder или postOrder. Фактически, когда мы проходим BST в последовательности Inorder01, мы получаем отсортированную последовательность:

Проходим BST

Обходы для вышеуказанного дерева следующие:

  • Обход в порядке (lnr): 3 5 6 7 8 9 10
  • Обход в предварительном порядке (nlr): 7 5 3 6 9 8 10
  • Обход после заказа (lrn): 3 6 5 8 10 9 7

Демонстрация

Давайте создадим бинарное дерево поиска из данных, приведенных ниже.

45 30 60 65 70

Возьмем первый элемент в качестве корневого узла.

№1) 45

45

На последующих шагах мы будем размещать данные в соответствии с определением дерева бинарного поиска, т.е. если данные меньше, чем родительский узел, то они будут помещены в левый дочерний узел, а если данные больше, чем родительский узел, то они будут правым дочерним узлом.

Эти шаги показаны ниже.

2) 30

30-45

3) 60

60

4) 65

65

5) 70

70

Когда мы выполняем неупорядоченный обход только что созданного BST, последовательность действий следующая:

Неупорядоченный обход

Теперь видно, что последовательность обхода имеет элементы, расположенные в порядке возрастания:

Реализация бинарного дерева поиска C++

Давайте рассмотрим BST и его операции, используя реализацию C++:

Вывод данных:

Создано бинарное дерево поиска (обход в порядке):
30 40 60 65 70
Удалить узел 40
Неупорядоченный обход модифицированного бинарного дерева поиска:
30 60 65 70

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

Преимущества BST

1) Поиск очень эффективен

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

Читать также:  Функции IOMANIP в C++: setprecision и setw

Нам просто нужно сравнить корневой узел с элементом, который мы ищем, а затем мы решаем, нужно ли нам искать в левом или правом поддереве.

2) Эффективная работа по сравнению с массивами и связными списками

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

3) Быстрая вставка и удаление

Операции вставки и удаления также выполняются быстрее по сравнению с другими структурами данных, такими как связные списки и массивы.

Применения BST

Вот некоторые из основных применений BST:

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

Итог

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

Неупорядоченный обход BST дает нам отсортированную последовательность элементов в порядке возрастания. Когда для поиска используются BST, то поиск происходит очень эффективно и выполняется в кратчайшие сроки. BST также используются в кодировании Хаффмана, многоуровневых индексаций в базах данных и т. д.

В следующей нашей статье мы поговорим о деревьях AVL и структурах данных кучи в C++.

С Уважением, МониторБанк

Добавить комментарий