Что такое бинарные деревья?

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

Находящийся на самой вершине узел, является корнем. По отношению к корню, у бинарного дерева есть:

1) потомок, значение которого меньше значения корня;

2) потомок, значение которого больше значения корня.

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

Характеристики бинарных деревьев

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

• уровень (глубина);
• высота вершины.

Уровень вершины –  это расстояние от вершины до корня.

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

Высота дерева –  это высота корневой вершины.

Виды бинарных деревьев

Как и другие деревья, бинарные деревья могут быть:

• полными;
• завершёнными;
• идеальными.

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

Завершённое дерево –  это такое дерево, где каждый уровень является полным, за исключением (возможно) нижнего уровня, где все вершины сдвигаются влево. Одним из хороших примеров использования данного вида деревьев является двоичная куча (binary heap).

Идеальным деревом называют полное дерево, все листья которого находятся на одном уровне. То есть у него присутствуют все вершины, допустимые для его высоты, что гарантирует минимальную высоту такого дерева.

Производительность бинарных деревьев

Производительность бинарных деревьев различна для среднего и худшего случаев. Так, в среднем, для вставки, удаления и поиска элементов оценка будет составлять О(logN), а в худшем случае – O(N).

Деревья поиска

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

Если ты ещё не бросил читать статью и дочитал до этого момента, наверняка ты задаёшься вопросом, зачем нужно столько сложностей? Не проще ли использовать для хранения данных более «простые» структуры данных вроде массивов, списков или словарей? И ответ будет прост – операции с деревом проходят намного быстрее. Например, списки реализуют операции в среднем с O(N) сложностью. Операции с деревом реализуются за O(H), когда H – глубина дерева, т.е. расстояние от корня до вершины. Таким образом, если дерево не является вырожденным (то есть не превращено в линейный список или близкую с ним структуру), а, что ещё лучше, является одним из подвидов деревьев, либо самобалансируется (как, например, красно-чёрное или АВЛ-дерево), сложность операций с ним приближается к O(logN), что более эффективно.

Бинарные деревья широко используется при написании кода, поэтому примеры можно найти и в стандартных библиотеках Java. Так, красно-чёрное дерево можно увидеть как «под капотом» в реализации HashMap, так и в реализации TreeMap/TreeSet классов. C Java 9 в SE-пакете также появился интерфейс BinaryTree.

Ещё больше полезностей о деревьях мы расскажем тебе в наших следующих статьях!

P.S. Полезная статья? Не пожалей ❤ и поделись ей со своими друзьями!