Введение

Ограниченная форма древовидной структуры данных.

В информатике, двоичное дерево — это древовидная структура данных, в которой каждый узел имеет не более двух потомков, называемых левым и правым потомками. То есть, это k-арное дерево. Рекурсивное определение с использованием теории множеств гласит, что двоичное дерево является кортежем (L, S, R), где L и R — двоичные деревья или пустое множество, а S — одноэлементное множество, содержащее корень. С точки зрения теории графов, двоичные деревья, как определено здесь, являются арборесценциями. Таким образом, двоичное дерево также может называться бифуркационной арборесценцией, до того как преобладала современная терминология информатики. Также возможно интерпретировать двоичное дерево как неориентированный, а не ориентированный граф, в этом случае двоичное дерево является упорядоченным, укорененным деревом. Некоторые авторы используют термин «укорененное двоичное дерево» вместо «двоичное дерево», чтобы подчеркнуть, что дерево укоренено, но, как определено выше, двоичное дерево всегда укоренено. В математике то, что называется двоичным деревом, может существенно различаться у разных авторов. Некоторые используют определение, обычно используемое в информатике.

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

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

Рекурсивное определение

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

Использование концепций теории графов

Двоичное дерево — это корневое дерево, которое также является упорядоченным деревом (также известным как плоское дерево), в котором каждый узел имеет не более двух потомков. Корневое дерево естественным образом подразумевает понятие уровней (расстояние от корня); таким образом, для каждого узла понятие потомков может быть определено как узлы, связанные с ним на уровень ниже. Упорядочение этих потомков (например, при изображении их на плоскости) позволяет различать левого и правого потомка. Однако это всё ещё не позволяет отличить узел с левым, но без правого потомка, от узла с правым, но без левого потомка. Необходимое различие можно сделать, сначала разделив рёбра, то есть определив двоичное дерево как тройку (V, E1, E2), где (V, E1 ∪ E2) является корневым деревом (эквивалентно, древовидной структурой), а E1 ∩ E2 пусто, и дополнительно требуя, чтобы для всех j ∈ {1, 2} у каждого узла было не более одного потомка из Ej. Более неформальный способ провести различие — сказать, цитируя Энциклопедию математики, что "каждый узел имеет левого потомка, правого потомка, ни одного из них или обоих", и указать, что все эти варианты — различные двоичные деревья.

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

Терминология деревьев не является хорошо стандартизированной и поэтому варьируется в различных источниках. Укорененное двоичное дерево имеет корневой узел, и каждый узел имеет не более двух дочерних узлов. Полное двоичное дерево (иногда называемое правильным, плоским или строгим двоичным деревом) — это дерево, в котором каждый узел имеет либо 0, либо 2 дочерних узла. Другой способ определения полного двоичного дерева — рекурсивное определение. Полное двоичное дерево может быть:
Одной вершиной (один узел, являющийся корневым узлом).
Деревом, у которого корневой узел имеет два поддерева, оба из которых являются полными двоичными деревьями.
Идеальное (или совершенное) двоичное дерево — это двоичное дерево, в котором все внутренние узлы имеют два дочерних узла, а все листья находятся на одинаковой глубине или уровне (уровень узла определяется как количество ребер или связей от корневого узла к этому узлу). Идеальное двоичное дерево является полным двоичным деревом.
Полное двоичное дерево — это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены максимально слева. На последнем уровне h может быть от 1 до 2h узлов. Следовательно, идеальное дерево всегда является полным, но полное дерево не всегда является идеальным. Некоторые авторы используют термин «полное» для обозначения идеального двоичного дерева, как определено выше, и в этом случае называют дерево с возможно неполным последним уровнем почти полным двоичным деревом или близким к полному двоичному дереву. Полное двоичное дерево может быть эффективно представлено с помощью массива. Также можно рассматривать двоичные деревья, в которых ни один лист не находится значительно дальше от корня, чем любой другой лист. (Различные схемы балансировки допускают различные определения «значительно дальше»). Вырожденное (или патологическое) дерево — это дерево, в котором каждый родительский узел имеет только один дочерний узел. Это означает, что дерево будет вести себя как структура данных связного списка. В этом случае преимущество использования двоичного дерева значительно снижается, поскольку по сути это связный список, временная сложность которого составляет O(n) (где n — количество узлов), и оно требует большего объема памяти, чем связный список, из-за двух указателей на узел, в то время как сложность O(log2n) для поиска данных в сбалансированном двоичном дереве обычно ожидается.

Свойства двоичных деревьев

Количество узлов в полном двоичном дереве составляет от до (т. е., количество узлов в совершенном двоичном дереве), где — высота дерева. Дерево, состоящее только из корневого узла, имеет высоту 0. Минимальное количество узлов получается при добавлении только двух дочерних узлов при увеличении высоты (1 для учёта корневого узла). Максимальное количество узлов получается при полном заполнении узлов на каждом уровне, то есть это совершенное дерево. Для совершенного дерева число узлов равно , где последнее равенство следует из суммы геометрической прогрессии. Число листовых узлов в совершенном двоичном дереве равно (где — число узлов в дереве), поскольку (используя вышеуказанное свойство), а число листьев равно , следовательно, также верно, что с точки зрения высоты дерева , для любого непустого двоичного дерева с листовыми узлами и узлами степени 2 (внутренними узлами с двумя дочерними узлами) доказательство следующее: для совершенного двоичного дерева общее число узлов равно (совершенное двоичное дерево является полным двоичным деревом) и , следовательно, чтобы получить полное двоичное дерево из совершенного, удаляются попарно два соседних узла. Это приводит к удалению двух листовых узлов и одного внутреннего узла, а также к тому, что удалённый внутренний узел становится листовым, то есть при удалении пары соседних узлов удаляется один листовой узел и один внутренний узел. В результате, это свойство также выполняется для полного двоичного дерева. Чтобы получить двоичное дерево с листовым узлом без его соседа, из полного двоичного дерева удаляется один листовой узел, что приводит к удалению одного листового узла и одного внутреннего узла с двумя детьми, следовательно, это свойство также выполняется. Таким образом, это соотношение охватывает все непустые двоичные деревья. При заданном числе узлов минимально возможная высота дерева равна , при которой дерево является сбалансированным полным или совершенным деревом. При заданной высоте число узлов не может превышать как число узлов в совершенном дереве. Таким образом, . Двоичное дерево с листьями имеет высоту не менее . При заданной высоте число листьев на этой высоте не может превышать как число листьев на этой высоте в совершенном дереве. Таким образом, . В непустом двоичном дереве, если — общее число узлов, а — общее число рёбер, то . Это очевидно, поскольку каждому узлу требуется одно ребро, за исключением корневого узла. Число нулевых ссылок (т. е. отсутствующих дочерних элементов узлов) в двоичном дереве из n узлов равно (n + 1). Число внутренних узлов в полном двоичном дереве из n узлов равно .

Комбинаторная теория

В комбинаторике рассматривается задача подсчета числа полных двоичных деревьев заданного размера. Здесь деревья не имеют значений, привязанных к их узлам (это лишь умножает количество возможных деревьев на легко определяемый фактор), и деревья различаются только по своей структуре; однако левый и правый потомок любого узла различаются (если это разные деревья, то их перестановка приведет к дереву, отличному от исходного). Размер дерева определяется как число *n* внутренних узлов (узлов с двумя потомками); остальные узлы – листья, и их количество равно *n* + 1. Количество таких двоичных деревьев размера *n* равно числу способов полной расстановки скобок в строке из *n* + 1 символов (представляющих листья), разделенных *n* бинарными операторами (представляющих внутренние узлы), чтобы определить подвыражения-аргументы каждого оператора. Например, для *n* = 1 необходимо расставить скобки в выражении вида X*X*X*X, что можно сделать пятью способами:

Соответствие между скобочными выражениями и двоичными деревьями должно быть очевидным, а добавление избыточных скобок (вокруг уже заключенного в скобки выражения или вокруг всего выражения) не допускается (или, по крайней мере, не рассматривается как создание новой возможности). Существует единственное двоичное дерево размера 0 (состоящее из одного листа), а любое другое двоичное дерево характеризуется парой его левого и правого потомков; если размеры этих потомков равны *i* и *j* соответственно, то полное дерево имеет размер *i* + *j* + 1. Следовательно, число двоичных деревьев размера *n* имеет следующее рекурсивное описание: , и для любого положительного целого числа *n*. Отсюда следует, что это число Каталана с индексом *n*.

Вышеуказанные скобочные выражения не следует путать с множеством слов длины 2*n* в языке Дайка, которые состоят только из скобок, правильно сбалансированных между собой. Количество таких строк удовлетворяет тому же рекурсивному описанию (каждое слово Дайка длины 2*n* определяется подсловом Дайка, заключенным в начальную '(' и соответствующую ей ')', вместе с оставшимся после закрывающей скобки подсловом Дайка, длины которого 2*i* и 2*j* удовлетворяют соотношению ); таким образом, это число также является числом Каталана. Существует также пять слов Дайка длины 6:

Эти слова Дайка не соответствуют двоичным деревьям тем же образом. Вместо этого они связаны следующим рекурсивно определенным биективным соответствием: слово Дайка, равное пустой строке, соответствует двоичному дереву размера 0, состоящему только из одного листа. Любое другое слово Дайка можно записать как , где и сами являются (возможно, пустыми) словами Дайка, и где две заключенные в скобки скобки соответствуют друг другу. Тогда биекция определяется тем, что словам и соответствуют двоичные деревья, являющиеся левым и правым потомками корня. Биективное соответствие также можно определить следующим образом: заключить слово Дайка в дополнительную пару скобок, чтобы результат можно было интерпретировать как выражение списка Lisp (с пустым списком как единственным атомом); тогда выражение с точками для этого собственного списка является полностью заключенным в скобки выражением (с NIL в качестве символа и '.' в качестве оператора), описывающим соответствующее двоичное дерево (которое, по сути, является внутренним представлением собственного списка). Возможность представления двоичных деревьев в виде строк символов и скобок подразумевает, что двоичные деревья могут представлять элементы свободной магмы на одноэлементном множестве.

Методы хранения двоичных деревьев

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

Массивы

Двоичные деревья также могут храниться в порядке обхода в ширину как неявная структура данных в массивах, и если дерево является полным двоичным деревом, этот метод не приводит к потерям памяти. В этой компактной организации, если узел имеет индекс i, его дочерние элементы находятся по индексам (для левого дочернего элемента) и (для правого), а родительский элемент (если он есть) – по индексу (при условии, что корень имеет индекс ноль). В качестве альтернативы, при использовании массива с индексацией, начиная с 1, реализация упрощается: дочерние элементы находятся по индексам и , а родительский элемент – по индексу . Этот метод обеспечивает более компактное хранение и лучшую локальность ссылок, особенно при обходе в прямом порядке. Однако его расширение требует значительных затрат, и он расходует память пропорционально 2^h - 1 для дерева глубины h с n узлами. Этот метод хранения часто используется для бинарных куч.