Бинарное (двоичное) дерево поиска, обходы и применение
Дерево — это один из абстрактных типов данных, а также любая структура данных, которая этот тип реализует. Деревья моделируют иерархичную древовидную структуру (ну например, семейное древо), в котором существует только один корень (корневой элемент) и узлы (другие элементы), связанные отношениями потомок — родитель, где любой отдельно взятый элемент имеет только одного родителя (кроме корня, у него-то родителей нет).
Ещё деревья можно определить рекурсивно: дерево может быть или пустым, или состоять из узла (корня), являющимся родительским узлом для некоторого количества деревьев. Количество дочерних узлов обозначает арность дерева; другими словами, 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). Но эффективность заполнения такого массива напрямую зависит от полноты бинарного дерева. Самый худший вариант развития событий произойдёт тогда, когда у дерева есть только один дочерний элемент в каждом узле (не важно, левого или правого). Тогда для хранения узлов потребуется ячеек в массиве.
Использование обхода бинарных деревьев облегчает работу с алгебраическими выражениями. Так, обратная польская нотация для алгебраического выражения получается путём обратного обхода заранее построенного бинарного дерева. Такое дерево называется деревом синтаксического разбора выражения, в котором узлы хранят операнды ( +, –, *, / ), а листья — числовые значения.
Источник
Деревья поиска
Дерево — одна из наиболее распространенных структур данных в программировании.
Деревья состоят из набора вершин (узлов, нод) и ориентированных рёбер (ссылок) между ними. Вершины связаны таким образом, что от какой-то одной вершины, называемой корневой (вершина 8 на рисунке), можно дойти до всех остальных единственным способом.
- Родитель вершины $v$ — вершина, из которой есть прямая ссылка в $v$.
- Дети (дочерние элементы, сын, дочь) вершины $v$ — вершины, в которые из $v$ есть прямая ссылка.
- Предки — родители родителей, их родители, и так далее.
- Потомки — дети детей, их дети, и так далее.
- Лист (терминальная вершина) — вершина, не имеющая детей.
- Поддерево — вершина дерева вместе со всеми её потомками.
- Степень вершины — количество её детей.
- Глубина вершины — расстояние от корня до неё.
- Высота дерева — максимальная из глубин всех вершин.
Деревья чаще всего представляются в памяти как динамически создаваемые структуры с явными указателями на своих детей, либо как элементы массива связанные отношениями, неявно определёнными их позициями в массиве.
Деревья также используются в контексте графов.
Бинарные деревья поиска
Бинарное дерево поиска (англ. binary search tree, BST) — дерево, для которого выполняются следующие свойства:
- У каждой вершины не более двух детей.
- Все вершины обладают ключами, на которых определена операция сравнения (например, целые числа или строки).
- У всех вершин левого поддерева вершины $v$ ключи не больше, чем ключ $v$.
- У всех вершин правого поддерева вершины $v$ ключи больше, чем ключ $v$.
- Оба поддерева — левое и правое — являются двоичными деревьями поиска.
Более общим понятием являются обычные (не бинарные) деревья поиска — в них количество детей может быть больше двух, и при этом в «более левых» поддеревьях ключи должны быть меньше, чем «более правых». Пока что мы сконцентрируемся только на двоичных, потому что они проще.
Чаще всего бинарные деревья поиска хранят в виде структур — по одной на каждую вершину — в которых записаны ссылки (возможно, пустые) на правого и левого сына, ключ и, возможно, какие-то дополнительные данные.
Как можно понять по названию, основное преимущество бинарных деревьев поиска в том, что в них можно легко производить поиск элементов:
Эта функция — как и многие другие основные, например, вставка или удаление элементов — работает в худшем случае за высоту дерева. Высота бинарного дерева в худшем случае может быть $O(n)$ («бамбук»), поэтому в эффективных реализациях поддерживаются некоторые инварианты, гарантирующую среднюю глубину вершины $O(\log n)$ и соответствующую стоимость основных операций. Такие деревья называются сбалансированными.
Источник