37 просмотров

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Статья в тему:  У кого самая опасная ядерная бомба

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

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

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

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

Операция поиска

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

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

Псевдокод для поиска в BST:

поиск(элемент, корень) если !root возвращает -1 если root.value == элемент возвращает 1 если root.value < элемент поиск(элемент, корень.право) иначе поиск(элемент, корень.левый)

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

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

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

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

Псевдокод для вставки узла в BST:

вставка (элемент, корень) Узел x = корень Узел y = NULL, тогда как x: y = x, если x.value < element.value x = x.right else x = x.left, если y.value < элемент y.right = элемент иначе y.left = элемент

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

Для удаления узла из 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 Удаление узла будет происходить на основе правила преемника по порядку, что означает, что самый большой элемент в правом поддереве из 12 заменит его.
  3. 3 Удалите узел 12 и замените его на 19, так как это наибольшее значение в правом поддереве.
  4. 4 Просмотрите новую структуру BST после удаления 12

Псевдокод для удаления узла:

delete (value, root): Node x = root Node y = NULL # поиск узла while x: y = x if x.value < value x = x.right else if x.value >value x = x.left else if value == x break # если узел не нулевой, то заменить его преемником, если y.left или y.right: newNode = GetInOrderSuccessor(y) root.value = newNode.value # После копирования значения преемника в корень #мы удаляем преемник free(newNode) else free(y)

Важные условия

  • Вставить: вставляет элемент в дерево/создает дерево.
  • Поиск: поиск элемента в дереве.
  • Предварительный обход: обход дерева в предварительном порядке.
  • Inorder Traversal: обход дерева по порядку.
  • Обход в обратном порядке: обход дерева в обратном порядке.
Статья в тему:  Как переработка предотвращает глобальное потепление

Резюме

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

Вы могли бы:

  • Жадный алгоритм на примере: что это такое, метод и подход
  • Алгоритм поиска в ширину (BFS) с ПРИМЕРОМ
  • Алгоритм бинарного поиска с ПРИМЕРОМ
  • Деревья AVL: повороты, вставка, удаление на примере C++
  • Учебник DAA в формате PDF: разработка и анализ алгоритмов
голоса
Рейтинг статьи
Ссылка на основную публикацию
Статьи c упоминанием слов:

0
Оставьте комментарий! Напишите, что думаете по поводу статьи.x