Как сделать сбалансированное бинарное дерево

Добавил пользователь Евгений Кузнецов
Обновлено: 04.10.2024

Двоичное дерево поиска. Итеративная реализация.

Д воичные деревья – это структуры данных, состоящие из узлов, которые хранят значение, а также ссылку на свою левую и правую ветвь. Каждая ветвь, в свою очередь, является деревом. Узел, который находится в самой вершине дерева принято называть корнем (root), узлы, находящиеся в самом низу дерева и не имеющие потомков называют листьями (leaves). Ветви узла называют потомками (descendants). По отношению к своим потомкам узел является родителем (parent) или предком (ancestor). Также, развивая аналогию, имеются сестринские узлы (siblings – родные братья или сёстры) – узлы с общим родителем. Аналогично, у узла могут быть дяди (uncle nodes) и дедушки и бабушки ( grandparent nodes). Такие названия помогают понимать различные алгоритмы.

Двоичное дерево. На этом рисунке узел 10 корень, 7 и 12 его наследники. 6, 9, 11, 14 - листья. 7 и 12, также как и 6 и 9 являются сестринскими узлами, 10 - это дедушка узла 6, а 12 - дядя узла 6 и узла 9

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

Двоичное дерево поиска (далее ДДП) – это несбалансированное двоичное дерево, в котором элементы БОЛЬШЕ корневого размещаются справа, а элементы, которые МЕНЬШЕ размещаются слева.

Такое размещение – слева меньше, справа больше – не обязательно, можно располагать элементы, которые меньше, справа. Отношение БОЛЬШЕ и МЕНЬШЕ – это не обязательно естественная сортировка по величине, это некоторая бинарная операция, которая позволяет разбить элементы на две группы.

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

ЗАМЕЧАНИЕ: мы рассматриваем случай, когда в дереве все значения разные и не равны NULL. Деревья с повторяющимися узлами рассмотрим позднее.

Обычно в качестве типа данных мы используем void* и далее передаём функции сравнения через указатели. В этот раз будем использовать пользовательский тип и макросы.

Сначала, как обычно, напишем функцию, которая создаёт новый узел. Она принимает в качестве аргументов значение и указатель на своего родителя. Корневой элемент не имеет родителя, значение указателя parent равно NULL.

Разберёмся со вставкой. Возможны следующие ситуации

1) Дерево пустое. В этом случае новый узел становится корнем ДДП.
2) Новое значение меньше корневого. В этом случае значение должно быть вставлено слева. Если слева уже стоит элемент, то повторяем эту же операцию, только в качестве корневого узла рассматриваем левый узел. Если слева нет элемента, то добавляем новый узел.
3) Новое значение больше корневого. В этом случае новое значение должно быть вставлено справа. Если справа уже стоит элемент, то повторяем операцию, только в качестве корневого рассматриваем правый узел. Если справа узла нет, то вставляем новый узел.

Пусть нам необходимо поместить в ДДП следующие значения

10 7 9 12 6 14 11 3 4

Первое значение становится корнем.

Второе значение меньше десяти, так что оно помещается слева.

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

Число 12 помещается справа от 10.

6 меньше 10 и меньше 7.

Добавляем оставшиеся узлы 14, 3, 4, 11

Функция, добавляющая узел в дерево

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

Проверяем, если дерево пустое, то вставляем корень

Проходим по дереву и ищем место для вставки

Пока не дошли до пустого узла

Если значение больше, чем значение текущего узла

Если при этом правый узел не пустой, то за корень теперь считаем правую ветвь и начинаем цикл сначала

Если правой ветви нет, то вставляем узел справа

Также обрабатываем левую ветвь

Рассмотрим результат вставки узлов в дерево. Очевидно, что структура дерева будет зависеть от порядка вставки элементов. Иными словами, форма дерева зависит от порядка вставки элементов.

Если элементы не упорядочены и их значения распределены равномерно, то дерево будет достаточно сбалансированным, то есть путь от вершины до всех листьев будет одинаковый. В таком случае максимальное время доступа до листа равно log(n), где n – это число узлов, то есть равно высоте дерева.

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

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

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

Поиск в дереве

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

Аналогично, можно найти максимальный элемент

Опять же, если дерево хорошо сбалансировано, то поиск минимума и максимума будет иметь сложность порядка log(n), а в случае плохой балансировки стремится к n.

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

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

С уществует три возможных ситуации.

Объяснение и реализация сбалансированного бинарного дерева поиска (AVL tree) (версия JAVA)

Объяснение и реализация бинарного дерева сбалансированного поиска

Если мы должны эффективно запрашивать данные с конкретным идентификатором в куче данных с идентификаторами, сколько у нас есть способов? Обычно мы все знаем метод двоичного поиска. Метод двоичного поиска действительно является более эффективным алгоритмом поиска, но есть также недостаток использования данных двоичного поиска.Сначала необходимо отсортировать, а для связанного списка нельзя получить прямой доступ к структуре данных дерева в соответствии с координатами, как к массиву.。

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

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

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

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

Бинарное дерево сбалансированного поиска (дерево AVL)

Рассматривая наихудший случай двоичного дерева поиска, предлагается сбалансированное двоичное дерево поиска, которое имеет следующие характеристики:В сбалансированном двоичном дереве поиска разница в высоте между левым и правым поддеревьями любого корневого узла не может быть больше 1.。
Как обеспечить сбалансированность характеристик двоичного дерева?Это требует от нас некоторого баланса и обработки позиций узлов, чтобы поддерживать эту функцию при вставке узлов и удалении узлов.。

Операция по поддержанию этой функции называетсяЛевая и праваяОперация (мы будем работать только с наименьшим диапазоном поддеревьев), мы фактически объясним ниже:

Вращение влево: корневой узел вращается вокруг правого поддерева.

Вращение вправо: корневой узел вращается с левым поддеревом в качестве оси.

Вообще говоря, при вставке нового узла в двоичное дерево появляются следующие четыре типа: тип LL, тип LR, тип RR, тип RL. Ниже приводится введение и баланс этих типов. метод.

Тип LL
Для наименьшего двоичного дерева после вставки узла мы используем тип LLПравая рукаоперационная:

Тип LR
Для наименьшего двоичного дерева после вставки узла мы используем тип LRПоверните налево а затем направооперационная:

Тип RR
Для наименьшего двоичного дерева после вставки узла мы используем тип LLЛевая рукаоперационная:

Тип RL
Для наименьшего двоичного дерева после вставки узла мы используем тип LRПравша, затем левшаоперационная:

AVLTree

Недостатки AVL-деревьев

Хотя эффективность поиска AVL более эффективна, а временная сложность относительно стабильна, благодаря дереву AVLНеобходимость строго поддерживать разницу в высоте между левым и правым поддеревьями потребует много времени для вставки и удаления узла, поэтому деревья AVL редко используются в структуре коллекции Java из-за компромисса между вставкой и поиском., Но брат дерева AVL, красно-черное дерево (строго говоря, красно-черное дерево также является сбалансированным деревом поиска) отказывается от строгой разницы в высоте между левым и правым поддеревьями, так что повышение производительности при вставке и удалении узлов более широко применяется в TreeMap. HashMap (после jdk 1.8).

На этом шаге мы рассмотрим построение идеально сбалансированных бинарных деревьев .

Пусть требуется построить бинарное дерево с n узлами и минимальной высотой (максимально "ветвистое" и "низкое"). Такие деревья имеют большое практическое значение, так как их использование сокращает машинное время, требуемое на выполнение различных алгоритмов. Определение. Бинарное дерево назовем идеально сбалансированным , если для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1 .

Изобразим несколько идеально сбалансированных деревьев:

Рис.1. Примеры идеально сбалансированных бинарных деревьев

Теорема. Длина внутреннего пути в идеально сбалансированном дереве, содержащем n вершин, не превосходит величины: (n+1)[log 2 n] - 2 * 2 [log 2 n] - 2

Доказательство. Ясно, что только одна вершина (а именно корень) может находиться на нулевом расстоянии от корня; не более двух вершин могут находиться на расстоянии 1 от корня; не более четырех вершин могут находиться от корня на расстоянии, равном 2 и т.д. Мы видим, что длина внутреннего пути всегда не больше суммы первых n членов ряда:

Рис.2. Длина внутреннего пути

Взгляните на следующее соотношение:

Теперь легко понять, что сумма первых n членов равна:

символы [ ] - обозначение операции выделения целой части числа.

В [2, с.74] показывается, что:

откуда и следует утверждение теоремы.

Алгоритм построения идеально сбалансированного дерева при известном числе вершин n лучше всего формулируется с помощью рекурсии [1,с.226]. При этом необходимо лишь учесть, что для достижения минимальной высоты при заданном числе вершин, нужно располагать максимально возможное число вершин на всех уровнях, кроме самого нижнего. Это можно сделать очень просто, если распределять все поступающие в дерево вершины поровну слева и справа от каждой вершины.

взять одну вершину в качестве корня.
построить левое поддерево с nl = n DIV 2 вершинами тем же способом.
построить правое поддерево с nr = n-nl-1 вершинами тем же способом.

Оформим описанный алгоритм в виде рекурсивной функции:

Приведем пример программы, иллюстрирующей построение идеально сбалансированного дерева (рекурсивный алгоритм).

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

Предположим, например, что имеется следующий набор ключей для построения дерева с 21 вершиной: 8, 9, 11, 15, 19, 20, 21, 7, 3, 2, 1, 5, 6, 4, 13, 14, 10, 12, 17, 16, 18. Результат работы программы следующий:

Рис.3. Результат работы приложения

Замечание . Идеально сбалансированные деревья изобретены для сокращения времени работы вычислительных алгоритмов, связанных с необходимостью частого прохода по ветвям дерева (напомним, что ветвь - это путь от корня дерева до листа). Одним из примеров подобного рода алгоритмов является поиск информации в дереве. В случае, если дерево является идеально сбалансированным, поиск осуществляется так же быстро, как и при дихотомии, то есть для поиска придется перебрать не более log 2 n вершин, где n - число вершин в дереве.

Одно "но": при формировании идеально сбалансированного дерева ключи необходимо вводить в отсортированном по возрастанию (по убыванию) виде. В этом случае можно построить достаточно простой алгоритм поиска в идеально сбалансированном дереве вершины с заданным ключом. (1) Вирт H. Алгоритмы + структуры данных = программы. - М.: Мир, 1985. - 406 с.
(2) Кнут Д. Искусство программирования для ЭВМ. Т.1: Основные алгоритмы. - M.: Мир, 1976. - 736 с.

Третья часть цикла об алгоритмах и структурах данных в JavaScript посвящена древовидным иерархическим структурам.

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

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

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

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

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

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

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

У корневого элемента (на картинке узел со значением 2) есть несколько дочерних узлов (7 и 5), каждый из которых в свою очередь сам является корнем поддерева. Таких уровней может быть сколько угодно.
Элемент, у которого нет дочерних узлов, называется листом, или терминальным узлом (2, 5, 11, 4). Все остальные узлы (кроме корневого), у которых есть потомки, называются внутренними.
Каждый узел дерева имеет только одного родителя, не больше. Кроме корневого узла, у которого родителей нет вообще.
Высота дерева – длина самой длинной ветви (количество ребер). У дерева на картинке она равна 3 – ветка от корня 2 до листа 5. Высоту также можно найти для любого внутреннего узла, например, для узла 6 высота равна 1.

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

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

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

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

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

Добавление нового узла ( add );
Удаление узла по его значению ( remove );
Поиск узла по значению ( find );
Обход всех элементов ( traverse ).

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

Вставка/удаление поддерева;
Вставка/удаление ветви;
Вставка элемента в определенную позицию;
Поиск наименьшего общего предка для двух узлов.

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

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

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

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

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

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

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

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

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

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

Обход дерева

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

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

поиск в глубину (depth-first search);
поиск в ширину (breadth-first search).

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

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

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

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

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

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

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

обход в прямом порядке , или предупорядоченный обход (pre-order walk). Перебор начинается с родительского узла и идет вниз, к дочерним.
обход в обратном порядке , или поступорядоченный (post-order walk). Сначала перебираем левого и правого потомков, а потом родителя.
симметричный обход . Начинаем с левого потомка, потом родитель, потом правый потомок.

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

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

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

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

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

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

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

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

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

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

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

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

Каждый узел должен быть "больше" любого элемента в своем левом поддереве.
Каждый узел должен быть "меньше" любого элемента в своем правом поддереве.

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

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

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

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

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

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

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

Метод insert , сравнивает значение нового элемента со значением узла и определяет, в какое поддерево его нужно поместить.

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

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

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

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

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

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

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

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

Есть три сценария:

У удаляемого узла нет потомков (листовой узел).
У удаляемого узла один потомок (левый или правый).
У удаляемого узла два потомка.

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

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

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

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

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

Полный код

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

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

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

Индексация	Поиск	Вставка	Удаление
O(log(n))	O(log(n))	O(log(n))	O(log(n))

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

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

Вырожденное бинарное дерево поиска.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

найти элемент с максимальным приоритетом (максимальный элемент в max-куче или минимальный элемент в min-куче);
удалить элемент с максимальным приоритетом;
добавить в очередь новый элемент.

Реализация

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

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

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

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

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

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

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

peek – просмотр без удаления;
pop – получение элемента и удаление его из очереди.

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

Полный код

Заключение

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

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

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

Читайте также: