зачем нужно бинарное дерево

Дерево

Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.

Способ представления бинарного дерева:

Корень дерева расположен на уровне с минимальным значением.

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

Остальные элементы – внутренние узлы (узлы ветвления).

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

Имеется много задач, которые можно выполнять на дереве.

Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.

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

Способы обхода дерева

Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.

Существует три способа обхода дерева:

Реализация дерева

Узел дерева можно описать как структуру:

При этом обход дерева в префиксной форме будет иметь вид

Обход дерева в инфиксной форме будет иметь вид

Обход дерева в постфиксной форме будет иметь вид

Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

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

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

Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.

Добавление узлов в дерево

Удаление поддерева

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

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

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

В дереве каждый узел содержит:

Рассмотрим выполнение программы на примере фразы

now is the time for all good men to come to the aid of their party

При этом дерево будет иметь следующий вид

Результат выполнения

Источник

Бинарное (двоичное) дерево поиска, обходы и применение

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

Ещё деревья можно определить рекурсивно: дерево может быть или пустым, или состоять из узла (корня), являющимся родительским узлом для некоторого количества деревьев. Количество дочерних узлов обозначает арность дерева; другими словами, n-арное дерево не может содержать более n дочерних элементов (далее дочерний узел, дочерний элемент и потомок будут иметь один и тот же смысл) для каждого узла. Арность дерева — это тоже самое, что и степень дерева. Если же для каждого узла дерева определяется индивидуальная степень, то говорят только про степень конкретных узлов.

Помимо этого необходимо знать ещё 2 понятия в разговоре о деревьях: путь до вершины (всегда начинаем от корня) и высота дерева (реже — глубина). Путь — это множество переходов в дереве, от корня к необходимому узлу. Число узлов в любом пути называется длиной пути, а максимальная длина пути из всех — высотой дерева. Поскольку дерево — частный случай графа, то такие переходы называют рёбрами, а узлы — вершинами.

Одной из форм записи деревьев «на бумаге» называется скобочной записью:

А для наглядности расставим пробелы и переносы:

А так оно выглядит на самом деле:

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

Деревья полезны, они используются во многих задачах, например:

Важно место в информатике занимают бинарные (или двоичные) деревья, у которых для каждого узла не более 2-х дочерних элементов, это левый и правый наследники. БНФ форма его определения выглядит так:

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

А вот другое — бинарное дерево поиска. Используется для организации хранения данных таким образом, чтобы гарантировать поиск элемента за логарифмическое время:

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

Чтобы работать с деревьями, нужно уметь обходить его элементы. Существуют такие 3 варианта обхода:

Такие обходы называются поиском в глубину, поскольку на каждом шаге итератор пытается продвинуться вертикально вниз по дереву перед тем, как перейти к родственному узлу (узлу на том же уровне). Ещё существует поиск в ширину. Его суть в обходе узлов дерева по уровням, начиная с корня (нужно пройти всего лишь 1 узел) и далее (на втором 2 узла, на третьем 4 узла, ну и т.д.; сколько узлов надо пройти на k-м уровне?).

Реализация поиска в глубину может осуществляться или с использованием рекурсии или с использованием стека, а поиск в ширину реализуется за счёт использования очереди:

Правый потомок заносится первым, так что левый потомок обрабатывается первым

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

Прошитое бинарное дерево поиска

Типичная структура данных одного узла такого дерева выглядит так:

Другой способ обхода дерева заключается в способе хранения информации о связях в массиве. Такой способ позволяет быстро находить дочерние и родительские элементы, производя обычные арифметические операции (а именно — для левого потомка и для правого, где — индекс родительского узла, если считать с 1). Но эффективность заполнения такого массива напрямую зависит от полноты бинарного дерева. Самый худший вариант развития событий произойдёт тогда, когда у дерева есть только один дочерний элемент в каждом узле (не важно, левого или правого). Тогда для хранения узлов потребуется ячеек в массиве.

Использование обхода бинарных деревьев облегчает работу с алгебраическими выражениями. Так, обратная польская нотация для алгебраического выражения получается путём обратного обхода заранее построенного бинарного дерева. Такое дерево называется деревом синтаксического разбора выражения, в котором узлы хранят операнды ( +, –, *, / ), а листья — числовые значения.

Источник

7) Двоичное дерево поиска

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Операция вставки

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

Операции удаления

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

Источник

☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Другие статьи цикла:

Структура данных «Дерево»

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

Древообразная структура DOM (объектной модели документа).

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

Устройство дерева

В отличие от обычных деревьев, структура данных дерево растет сверху вниз – ее корень находится на самом верху – так удобнее изображать.

Кроме двоичных, широкое практическое применение имеют деревья с четырьмя узлами ( дерево квадрантов ). Они используются в геймдеве для организации сетки. Каждый узел в таком дереве представляет одно направление (север-запад, юго-восток и так далее).

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

Деревья – довольно сложные структуры. Для работы с иерархическими данными они должны предоставлять ряд алгоритмов.

Основные операции, которые нам нужны:

При необходимости этот список можно расширить более сложными алгоритмами:

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

Реализация дерева на JavaScript

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

Высота узла ( height ) вычисляется рекурсивно, на основе высоты его дочерних узлов.

Добавление узлов

Первый алгоритм, который мы должны реализовать для дерева, – это вставка новых узлов. Самая простая реализация не предъявляет никаких правил к расположению элементов, поэтому мы можем просто приписать новый узел к существующему как дочерний (с нужной стороны).

При вставке важно обновить все затронутые ссылки: left или right для родительского узла и parent для дочернего. Если у родителя уже был потомок, его свойство parent нужно обнулить.

Создание дерева

Реализация очень простая, но с ее помощью мы уже можем построить настоящее двоичное дерево, например, такое как на картинке:

Двоичное дерево.

Обход дерева

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

Мы разберем два популярных алгоритма обхода дерева:

DFS: Поиск в глубину

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

Визуализация работы алгоритма поиска в глубину.

Запустим перебор для нашего бинарного дерева:

В консоли мы увидим следующее:

Порядок перебора узлов при поиске в глубину

Существует три модификации алгоритма с разным способом перебора узлов:

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

BFS: Поиск в ширину

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

Визуализация работы алгоритма поиска в ширину.

Можно использовать реализацию очереди из предыдущей статьи или воспользоваться простой очередью на базе JavaScript-массива.

Запустим перебор в ширину:

Результат выглядит так:

Порядок перебора узлов при поиске в ширину.

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

Двоичное (бинарное) дерево поиска (binary search tree, BST) – это дерево, в котором элементы размещаются согласно определенному правилу (упорядоченно):

Слова «больше» и «меньше» соответственно означают результат сравнения двух узлов функцией-компаратором.

Пример бинарного дерева поиска.

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

Реализация на JavaScript

Так как бинарное дерево поиска является упорядоченным, нам еще потребуется функция-компаратор для сравнения элементов.

Создадим дерево как на картинке выше:

А теперь обойдем все его элементы, чтобы убедиться, что оно сформировано правильно:

Поиск в бинарном дереве поиска

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

Алгоритм поиска рекурсивно проверяет все узлы, пока не найдет подходящий.

Удаление узлов

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

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

Теперь добавим в класс BinarySearchTree новый метод remove :

Полный код

Полная реализация бинарного дерева поиска на JavaScript:

Эффективность

Временная сложность всех основных операций в бинарном дереве составляет log(n) – это довольно эффективная структура данных.

Сбалансированные бинарные деревья

На картинке изображено валидное бинарное дерево поиска. Для каждого узла соблюдается правило: все узлы в правом поддереве имеют большее значение. Однако такое дерево не позволяет нам пользоваться преимуществами стратегии «разделяй и властвуй», ведь тут нечего отбрасывать. Говорят, что дерево выродилось в список.

Чтобы избежать таких ситуаций, используются более сложные структуры данных – самобалансирующиеся деревья:

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

Легким движением руки несбалансированное дерево поиска превращается в сбалансированное:

Автоматическая балансировка AVL-дерева.

Визуализация самобалансирующихся деревьев:

Двоичная куча

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

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

Пример max-кучи.

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

Пример min-кучи.

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

Каждую кучу можно представить в виде линейного массива:

Представление одних и тех же данных в виде дерева и в виде массива.

Чаще всего используется именно линейная реализация, однако дерево более наглядно демонстрирует принцип распределения.

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

Базовые операции с кучей такие же, как и с очередью:

Реализация

Мы реализуем на JavaScript min-кучу. Для max-кучи нужно только изменить операцию сравнения.

Добавим еще несколько вспомогательных методов для удобных проверок:

Добавление элемента

Сначала новый элемент помещается в самый конец кучи (конец массива), как и в обычной очереди, а затем начинается процесс его поднятия вверх с учетом приоритета. Это рекурсивный алгоритм, который сравнивает элемент с предыдущим и при необходимости меняет их местами.

Получение элемента с максимальным приоритетом

Для получения элемента с начала очереди может быть два метода:

С peek все понятно, нам просто нужно взять нулевой элемент массива. А вот после удаления необходимо перебалансировать дерево. Для этого мы берем самый последний элемент массива, ставим его в начало и начинаем сдвигать вниз, последовательно сравнивая с его дочерними элементами.

Полный код

Заключение

Деревья – довольно сложная (по сравнению с линейными), но очень интересная структура данных. Об одном из самых популярных ее применений (поиске данных) мы уже поговорили.

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

Больше полезной информации вы найдете на наших телеграм-каналах «Библиотека программиста» и «Книги для программистов».

Источник

Двоичное дерево

В этом уроке вы узнаете о разных типах двоичных деревьев и увидите, как их можно реализовать на Си, C++, Java и Python.

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

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

Полное двоичное дерево

Полное двоичное дерево — особый тип бинарных деревьев, в котором у каждого узла либо 0 потомков, либо 2.

Совершенное двоичное дерево

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

Законченное двоичное дерево

Законченное двоичное дерево похоже на совершенное, но есть три большие отличия.

Вырожденное двоичное дерево

Вырожденное двоичное дерево — дерево, в котором на каждый уровень приходится по одной вершине.

Скошенное вырожденное дерево

Скошенное вырожденное дерево — вырожденное дерево, в котором есть либо только левые, либо только правые узлы. Таким образом, есть два типа скошенных деревьев — скошенные влево вырожденные деревья и скошенные вправо вырожденные деревья.

Сбалансированное двоичное дерево

Сбалансированное двоичное дерево — тип бинарного дерева, в котором у каждой вершины количество вершин в левом и правом поддереве различаются либо на 0, либо на 1.

Представление двоичного дерева

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

Источник