Дерево двоичного поиска (BST) с примером

Содержание:

Anonim

Что такое двоичное дерево поиска?

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

В этом руководстве по структуре данных вы узнаете:

  • Что такое двоичное дерево поиска?
  • Атрибуты двоичного дерева поиска
  • Зачем нам нужно двоичное дерево поиска?
  • Типы двоичных деревьев
  • Как работает двоичное дерево поиска?
  • Важные термины

Атрибуты двоичного дерева поиска

BST состоит из нескольких узлов и состоит из следующих атрибутов:

  • Узлы дерева представлены в родительско-дочерних отношениях.
  • Каждый родительский узел может иметь ноль дочерних узлов или максимум два подузла или поддерева слева и справа.
  • Каждое поддерево, также известное как двоичное дерево поиска, имеет дочерние ветви справа и слева от себя.
  • Все узлы связаны парами ключ-значение.
  • Ключи узлов, представленных в левом поддереве, меньше ключей их родительского узла.
  • Точно так же ключи узлов левого поддерева имеют меньшие значения, чем ключи их родительского узла.

  1. Есть главный узел или родительский уровень 11. Под ним находятся левый и правый узлы / ветви со своими собственными ключевыми значениями.
  2. Правое поддерево имеет значения ключей больше, чем у родительского узла.
  3. Левое поддерево имеет значения, чем родительский узел

Зачем нам нужно двоичное дерево поиска?

  • Двумя основными факторами, которые делают двоичное дерево поиска оптимальным решением любых реальных проблем, являются скорость и точность.
  • Из-за того, что двоичный поиск выполняется в формате ветвления с отношениями родитель-потомок, алгоритм знает, в каком месте дерева нужно искать элементы. Это уменьшает количество сравнений "ключ-значение", которые программа должна выполнить, чтобы найти нужный элемент.
  • Кроме того, в случае, если элемент для поиска больше или меньше родительского узла, этот узел знает, на какой стороне дерева искать. Причина в том, что левое поддерево всегда меньше родительского узла, а правое поддерево всегда имеет значения, равные или превышающие значения родительского узла.
  • BST обычно используется для реализации сложного поиска, надежной игровой логики, автозаполнения действий и графики.
  • Алгоритм эффективно поддерживает такие операции, как поиск, вставка и удаление.

Типы двоичных деревьев

Три вида бинарных деревьев:

  • Полное двоичное дерево: все уровни в деревьях полны возможных исключений последнего уровня. Точно так же все узлы заполнены, направляя крайнее левое положение.
  • Полное двоичное дерево: все узлы имеют 2 дочерних узла, кроме листа.
  • Сбалансированное или идеальное двоичное дерево: в дереве все узлы имеют двух дочерних элементов. Кроме того, у каждого подузла одинаковый уровень.

Как работает двоичное дерево поиска?

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

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

BST в первую очередь предлагает следующие три типа операций для вашего использования:

  • Поиск: ищет элемент в двоичном дереве.
  • Вставить: добавляет элемент в двоичное дерево
  • Удалить: удалить элемент из двоичного дерева

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

Поисковая операция

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

  1. Элемент для поиска - 10
  2. Сравните элемент с корневым узлом 12, 10 <12, поэтому вы переместитесь в левое поддерево. Нет необходимости анализировать правое поддерево
  3. Теперь сравните 10 с узлом 7, 10> 7, так что перейдите к правому поддереву.
  4. Затем сравните 10 со следующим узлом, который равен 9, 10> 9, посмотрите в правое дочернее поддерево
  5. 10 совпадает со значением в узле, 10 = 10, возвращает значение пользователю.

Вставить операцию

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

  1. Существует список из 6 элементов, которые необходимо вставить в BST в порядке слева направо.
  2. Вставьте 12 в качестве корневого узла и сравните следующие значения 7 и 9 для вставки соответственно в правое и левое поддерево
  3. Сравните оставшиеся значения 19, 5 и 10 с корневым узлом 12 и разместите их соответственно. 19> 12 поместите его как правого дочернего элемента 12, 5 <12 & 5 <7, следовательно, поместите его как левого дочернего элемента 7.
    1. Теперь сравните 10, 10 равно <12, 10 равно> 7 и 10 равно> 9, поместите 10 как правое поддерево 9.

Удалить операции

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

  • Случай 1 - Узел с нулевыми дочерними элементами: это самая простая ситуация, вам просто нужно удалить узел, у которого нет других дочерних элементов справа или слева.
  • Случай 2 - Узел с одним дочерним элементом: после удаления узла просто соедините его дочерний узел с родительским узлом удаленного значения.
  • Случай 3 Узел с двумя детьми: это самая сложная ситуация, и она работает по следующим двум правилам.
    • 3a - В порядке предшественника: вам нужно удалить узел с двумя дочерними элементами и заменить его наибольшим значением в левом поддереве удаленного узла.
    • 3b - В порядке преемника: вам нужно удалить узел с двумя дочерними элементами и заменить его наибольшим значением в правом поддереве удаленного узла.

  1. Это первый случай удаления, при котором вы удаляете узел, не имеющий дочерних элементов. Как вы можете видеть на диаграмме, у 19, 10 и 5 нет потомков. Но мы удалим 19.
  2. Удалите значение 19 и удалите ссылку из узла.
  3. Посмотреть новую структуру BST без 19

  1. Это второй случай удаления, при котором вы удаляете узел, у которого есть 1 дочерний элемент, как вы можете видеть на диаграмме, что у 9 есть один дочерний элемент.
  2. Удалите узел 9 и замените его дочерним узлом 10 и добавьте ссылку с 7 на 10.
  3. Посмотреть новую структуру BST без 9

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

  1. 1 Удалите узел 12, у которого есть два дочерних элемента
  2. 2 Удаление узла будет происходить на основе правила In Order Successor, что означает, что самый большой элемент в правом поддереве из 12 заменит его.
  3. 3 Удалите узел 12 и замените его на 19, так как это наибольшее значение в правом поддереве
  4. 4 Просмотрите новую структуру BST после удаления 12

Важные термины

  • Вставить - вставляет элемент в дерево / создает дерево.
  • Поиск - поиск элемента в дереве.
  • Preorder Traversal - Обходит дерево в порядке предварительного заказа.
  • Inorder Traversal - Обходит дерево по порядку.
  • Postorder Traversal - Обходит дерево в режиме пост-заказа.

Резюме

  • BST - это алгоритм продвинутого уровня, который выполняет различные операции на основе сравнения значений узла с корневым узлом.
  • Любая из точек в иерархии родитель-потомок представляет узел. По крайней мере, один родительский или корневой узел остается постоянно.
  • Есть левое поддерево и правое поддерево. Левое поддерево содержит значения, меньшие, чем у корневого узла. Однако правое поддерево содержит значение, превышающее значение корневого узла.
  • У каждого узла может быть ноль, один или два дочерних элемента.
  • Дерево двоичного поиска облегчает выполнение основных операций, таких как поиск, вставка и удаление.
  • Удаление, являющееся наиболее сложным, имеет несколько случаев, например, узел без дочернего элемента, узел с одним дочерним элементом и узел с двумя дочерними элементами.
  • Алгоритм используется в реальных решениях, таких как игры, автозаполнение данных и графика.