Бинарное (двоичное) дерево поиска, обходы и применение
Дерево — это один из абстрактных типов данных, а также любая структура данных, которая этот тип реализует. Деревья моделируют иерархичную древовидную структуру (ну например, семейное древо), в котором существует только один корень (корневой элемент) и узлы (другие элементы), связанные отношениями потомок — родитель, где любой отдельно взятый элемент имеет только одного родителя (кроме корня, у него-то родителей нет).
Ещё деревья можно определить рекурсивно: дерево может быть или пустым, или состоять из узла (корня), являющимся родительским узлом для некоторого количества деревьев. Количество дочерних узлов обозначает арность дерева; другими словами, n-арное дерево не может содержать более n дочерних элементов (далее дочерний узел, дочерний элемент и потомок будут иметь один и тот же смысл) для каждого узла. Арность дерева — это тоже самое, что и степень дерева. Если же для каждого узла дерева определяется индивидуальная степень, то говорят только про степень конкретных узлов.
Помимо этого необходимо знать ещё 2 понятия в разговоре о деревьях: путь до вершины (всегда начинаем от корня) и высота дерева (реже — глубина). Путь — это множество переходов в дереве, от корня к необходимому узлу. Число узлов в любом пути называется длиной пути, а максимальная длина пути из всех — высотой дерева. Поскольку дерево — частный случай графа, то такие переходы называют рёбрами, а узлы — вершинами.
Одной из форм записи деревьев «на бумаге» называется скобочной записью:
А для наглядности расставим пробелы и переносы:
А так оно выглядит на самом деле:
Деревья полезны, они используются во многих задачах, например:
- парсеры и трансляторы используют синтаксическое дерево;
- при работе со строками используются суффиксные деревья;
- бинарные деревья используются в большом количестве задач: от сортировки и поиска, до создания на их базе других, более сложных структур данных.
Важно место в информатике занимают бинарные (или двоичные) деревья, у которых для каждого узла не более 2-х дочерних элементов, это левый и правый наследники. БНФ форма его определения выглядит так:
Существуют множество разных бинарных деревьев, например, двоичная куча (или сортирующее дерево). Оно используется в пирамидальной сортировке и при реализации приоритетных очередей. Для этого на обычное бинарное дерево нужно всего лишь наложить такие ограничения:
- Значение в любой вершине не меньше, чем значения её потомков.
- Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой.
- Последний слой заполняется слева направо без «дырок».
А вот другое — бинарное дерево поиска. Используется для организации хранения данных таким образом, чтобы гарантировать поиск элемента за логарифмическое время:
- Оба поддерева — левое и правое — являются двоичными деревьями поиска.
- У всех узлов левого поддерева для произвольного узла значения ключей меньше значения ключа этого узла.
- У всех узлов правого поддерева для произвольного узла значения ключей больше либо равны значения ключа этого узла.
Поиск элемента с заданным значением в таком дереве происходит очевидным образом: начиная с корня сравниваем текущее значение узла с заданным; если они равны, то значение найдено, иначе сравниваем значения и выбираем следующий узел для проверки: левый или правый.
Чтобы работать с деревьями, нужно уметь обходить его элементы. Существуют такие 3 варианта обхода:
- Прямой обход (КЛП): корень → левое поддерево → правое поддерево.
- Центрированный обход (ЛКП): левое поддерево → корень → правое поддерево.
- Обратный обход (ЛПК): левое поддерево → правое поддерево → корень
Такие обходы называются поиском в глубину, поскольку на каждом шаге итератор пытается продвинуться вертикально вниз по дереву перед тем, как перейти к родственному узлу (узлу на том же уровне). Ещё существует поиск в ширину. Его суть в обходе узлов дерева по уровням, начиная с корня (нужно пройти всего лишь 1 узел) и далее (на втором 2 узла, на третьем 4 узла, ну и т.д.; сколько узлов надо пройти на k-м уровне?).
Реализация поиска в глубину может осуществляться или с использованием рекурсии или с использованием стека, а поиск в ширину реализуется за счёт использования очереди:
preorder(node) if (node = null) return visit(node) preorder(node.left) preorder(node.right)
iterativePreorder(node) s ← empty stack s.push(node) while (not s.isEmpty()) node ← s.pop() visit(node) if (node.right ≠ null) s.push(node.right) if (node.left ≠ null) s.push(node.left)
Правый потомок заносится первым, так что левый потомок обрабатывается первым
levelorder(root) q ← empty queue q.enqueue(root) while (not q.isEmpty()) node ← q.dequeue() visit(node) if (node.left ≠ null) q.enqueue(node.left) if (node.right ≠ null) q.enqueue(node.right)
Чтобы реализовать центрированный обход, не обязательно использовать рекурсии или стек. Для этого добавляют новые связи (полученное дерево будет называться прошитым бинарным деревом), где каждому левому потомку, у которого нет своего левого потомка, назначают указатель на предыдущий элемент в порядке центрированного обхода, а для правых по тем же причинам — следующий.
Прошитое бинарное дерево поиска
Типичная структура данных одного узла такого дерева выглядит так:
Другой способ обхода дерева заключается в способе хранения информации о связях в массиве. Такой способ позволяет быстро находить дочерние и родительские элементы, производя обычные арифметические операции (а именно — для левого потомка и для правого, где — индекс родительского узла, если считать с 1). Но эффективность заполнения такого массива напрямую зависит от полноты бинарного дерева. Самый худший вариант развития событий произойдёт тогда, когда у дерева есть только один дочерний элемент в каждом узле (не важно, левого или правого). Тогда для хранения узлов потребуется ячеек в массиве.
Использование обхода бинарных деревьев облегчает работу с алгебраическими выражениями. Так, обратная польская нотация для алгебраического выражения получается путём обратного обхода заранее построенного бинарного дерева. Такое дерево называется деревом синтаксического разбора выражения, в котором узлы хранят операнды ( +, –, *, / ), а листья — числовые значения.
Источник
Бинарное дерево. Для чего? Конкретный пример из жизни, пожалуйста! Буду очень признателен.
Здравствуйте! Недавно я затронул тему бинарного дерева и очень хочу разобраться, для чегО онО нужнО?
Нет, ну правда, препод мне сказал расплывчато: «Иногда случается так, что необходимо именно такое структурирование при хранении данных, есть определенные «возможности» и некоторая «весьма существенная» выгода. и так далее и тому подобное. Такое ощущение. что он то ли сам не знал, накой хрен онО нужнО, то ли считал это очевидным, то ли подумал, что для меня это сложно и ненужно.
Помогите мне понять, для чего нужно бинарное дерево.
Дайте мне хотя бы три Конкретных примера из жизни, лучше с указаниями и описаниями и ссылками на экземпляр, использующий его, постараясь как можно меньше говорить общие пространные термины, за которыми ничего конкретное не кроется.
Буду Вам очень признателен, если поможете.
Бинарное дерево нужно для быстрого поиска (логарифмическая сложность) для быстрой вставки и быстрого удаления. При обходе всего дерева можно получить строгую упорядоченную последовательность — то есть его можно использовать для сортировки.
Чебуратор Мыслитель (8452) Пожалуйста 🙂 Вообще-то препод должен был знать это и объяснить — иначе гнать такого препода ссаными тряпками 🙂 Есть множество разновидностей двоичного дерева — обычное бинарное дерево не всегда дает высокую производительность поиска, вставки и удаления — так как это дерево не балансируется и одна ветка дерева может быть сильно больше чем вторая — поэтому и требуется больше времени для обхода. Для решения этих проблем используются так называемые самобалансирующиеся деревья в которых обе ветки почти одинаковы по высоте — соответственно поиск, вставка и удаление происходит всегда за логарифмическую сложность.
к примеру. есть 1024 новобранца, которые встали по росту. рост от 202 до 160 см. тебе надо найти типа с ростом 183 см.
Последоательный поиск. Ты идёшь от первого и спрашиваешь рост каждого. может так получится, что вообще нет типа с таким ростом. ты спросишь максимум 1024 раза
Бинарный поиск Ты спрашиваешь среднего и в зависимости от его роста ты вбираешь, идти в меньшую или большую сторону. здесь ты максимум 10 раз спросишь.
Но это относится к упорядоченным множествам. Но что делать с неупорядоченными?
Бинарное дерево организует логику хранения и работы с данными таким образом, чтоб при добавлении, удалении, поиске тебе было необходимо выполнять меньшее кол-во операций. время работы — логарифмическое. (в отдельных видах бинарного дерева своя скорость, ф где дольше удаление где вставка.)
+ бинарное дерево позволяет организовывать словарь.
Есть ещё теорема, согласно которой любое дерево представимо в виде бинарного. Т. е. это ещё и универсальное представление любой иерархии.
Источник