Бинарное дерево

Не путать с двоичным деревом поиска , B-деревом или B+ деревом .

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

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

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

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

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

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

Определения

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

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

• пустое множество представляет собой расширенное двоичное дерево
• если T ₁ и T ₂ — расширенные двоичные деревья, то через T ₁ • T ₂ обозначим расширенное бинарное дерево, полученное добавлением корня r , соединенного слева с T ₁ и справа с T ₂ добавляя ребра, когда эти поддеревья не пусты.

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

графов

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

Необходимое различие можно провести, сначала разделив края; т. е. определение бинарного дерева как тройки (V, E ₁ , E ₂ ), где (V, E ₁ ∪ E ₂ ) — корневое дерево (эквивалентно древовидности), а E ₁ ∩ E ₂ пусто, а также требование, чтобы для все j ∈ { 1, 2 }, каждый узел имеет не более одного дочернего элемента E _j . Более неформальный способ провести различие — сказать, цитируя Энциклопедию математики , что «каждый узел имеет левого дочернего элемента, правого дочернего элемента, ни одного из них или оба» и указать, что это «все разные» двоичные деревья.

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

Терминология деревьев недостаточно стандартизирована и поэтому различается в литературе.

• А корневое двоичное дерево имеет корневой узел , и каждый узел имеет не более двух дочерних элементов.

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

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

• А полное называемое двоичное дерево ( иногда плоскость или строгое двоичное дерево) — это дерево, в котором каждый узел имеет либо 0, либо 2 потомка. Другой способ определения полного двоичного дерева — это рекурсивное определение . Полное двоичное дерево — это либо:
  • Одна вершина (один узел в качестве корневого узла).
  • Дерево, корневой узел которого имеет два поддерева, оба из которых являются полными двоичными деревьями.
• А Идеальное бинарное дерево — это бинарное дерево, в котором все внутренние узлы имеют по два дочерних узла , а все листья имеют одинаковую глубину или один и тот же уровень (уровень узла, определяемый как количество ребер или связей от корневого узла к узлу). Идеальное двоичное дерево — это полное двоичное дерево.
• А Полное двоичное дерево — это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего , полностью заполнен, а все узлы на последнем уровне расположены как можно дальше влево. Может иметь от 1 до 2 ^час узлы на последнем уровне h . Таким образом, совершенное дерево всегда полно, но полное дерево не всегда совершенно. Некоторые авторы вместо этого используют термин «полное» для обозначения идеального двоичного дерева, как оно определено выше, и в этом случае они называют этот тип дерева (с возможным незаполненным последним уровнем) почти полным двоичным деревом или почти полным двоичным деревом. Полное двоичное дерево можно эффективно представить с помощью массива.

Полное двоичное дерево (которое не является полным)

• В бесконечном полном двоичном дереве есть дерево с ${\aleph _{0}}$ уровни, где для каждого уровня d количество существующих узлов на уровне d равно 2 ^д . Кардинальное число множества всех уровней равно ${\aleph _{0}}$(счетная бесконечность). Кардинальное число множества всех путей («листьев», так сказать) несчетно, имея мощность континуума .
• Сбалансированное . бинарное дерево — это бинарная древовидная структура, в которой левое и правое поддеревья каждого узла различаются по высоте (количество ребер от самого верхнего узла до самого дальнего узла в поддереве) не более чем на 1 (или перекос) не больше 1). Можно также рассмотреть бинарные деревья, в которых ни один лист не находится намного дальше от корня, чем любой другой лист. (Различные схемы балансировки допускают разные определения понятия «намного дальше». )
• ) дерево Вырожденное (или патологическое — это дерево, в котором каждый родительский узел имеет только один связанный дочерний узел. Это означает, что дерево будет вести себя как структура данных связанного списка . В этом случае преимущество использования двоичного дерева значительно снижается, поскольку по сути это связанный список, временная сложность которого равна O( n ) ( n как количество узлов), и он имеет больше места для данных, чем связанный список, из-за двух сложность O(log ₂ n ) для поиска данных в сбалансированном двоичном дереве. указателей на узел, в то время как обычно ожидается

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

• Количество узлов $n$ в полном двоичном дереве не менее $2h+1$ и самое большее $2^{h+1}-1$ (т. е. количество узлов в идеальном двоичном дереве), где $h$это высота дерева. Дерево, состоящее только из корневого узла, имеет высоту 0. Наименьшее количество узлов получается путем добавления только двух дочерних узлов на каждую добавленную высоту, поэтому $2h+1$(1 для подсчета корневого узла). Максимальное количество узлов получается при полном заполнении узлов на каждом уровне, т. е. это идеальное дерево. Для идеального дерева количество узлов равно $1+2+4+\ldots +2^{h}=2^{h+1}-1$, где последнее равенство взято из суммы геометрической прогрессии .
• Количество листовых узлов $l$ в идеальном двоичном дереве $l=(n+1)/2$ (где $n$ — количество узлов в дереве), поскольку $n={{2}^{h+1}}-1$ (с использованием вышеуказанного свойства), а количество листьев равно $2^{h}$ так $n=2\cdot {{2}^{h}}-1=2l-1\to l=\left(n+1\right)/2$. Это также означает, что $n=2l-1$. По высоте дерева $h$, $l=(2^{h+1}-1+1)/2=2^{h}$.
• Для любого непустого двоичного дерева с $l$ листовые узлы и $i_{2}$ узлы степени 2 (внутренние узлы с двумя дочерними узлами), $l=i_{2}+1$. Доказательство состоит в следующем. Для идеального двоичного дерева общее количество узлов равно $n=2^{h+1}-1$ (Идеальное двоичное дерево — это полное двоичное дерево.) и $l=2^{h}$, так $i=n-l=(2^{h+1}-1)-2^{h}=2^{h}-1=l-1\to l=i+1$. Чтобы сделать полное двоичное дерево из идеального двоичного дерева, пару двух родственных узлов удаляют один за другим. Это приводит к тому, что «два листовых узла удаляются», «один внутренний узел удаляется» и «удаленный внутренний узел становится листовым узлом», поэтому один листовой узел и один внутренний узел удаляются при удалении двух родственных узлов. Как результат, $l=i+1$справедливо и для полного двоичного дерева. Чтобы создать двоичное дерево с листовым узлом без его родственного узла, из полного двоичного дерева удаляется один листовой узел, затем «удаляется один листовой узел» и «удаляется один внутренний узел с двумя дочерними узлами», поэтому $l=i+1$тоже держит. Теперь это отношение охватывает все непустые двоичные деревья.
• С учетом $n$ узлов, минимально возможная высота дерева равна $h_{min}=\log _{2}(n+1)-1$с которым дерево является сбалансированным полным деревом или совершенным деревом. С заданной высотой $h$, количество узлов не может превышать $2^{h+1}-1$как количество узлов в идеальном дереве. Таким образом $n\leq 2^{h+1}-1\to h\geq \log _{2}(n+1)-1$.
• Бинарное дерево с $l$ листья имеют по крайней мере высоту $h_{m}=\log _{2}(l)$. С заданной высотой $h$, количество листьев на этой высоте не может превышать $2^{h}$как количество листьев на высоте у идеального дерева. Таким образом $l\leq 2^{h}\to h\geq \log _{2}(l)$.
• В непустом двоичном дереве, если $n$ общее количество узлов и $e$ общее количество ребер, тогда $e=n-1$. Это очевидно, поскольку каждому узлу требуется одно ребро, за исключением корневого узла.
• Количество нулевых ссылок (т. е. отсутствующих дочерних элементов узлов) в двоичном дереве из n узлов равно ( n + 1).
• Число внутренних узлов в полном двоичном дереве из n узлов равно $\lfloor n/2\rfloor$.

Комбинаторика

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

$$((X*X)*X)*X,\qquad (X*(X*X))*X,\qquad (X*X)*(X*X),\qquad X*((X*X)*X),\qquad X*(X*(X*X)).$$

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

Существует уникальное двоичное дерево размера 0 (состоящее из одного листа), а любое другое двоичное дерево характеризуется парой своих левых и правых дочерних элементов; если они имеют размеры i и j соответственно, полное дерево имеет размер i + j + 1 . Следовательно, число $C_{n}$ бинарных деревьев размера n имеет следующее рекурсивное описание $C_{0}=1$, и $\textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$для любого положительного целого числа n . Следует, что $C_{n}$ — каталонское число индекса n .

Вышеупомянутые строки в скобках не следует путать с набором слов длиной 2 n в языке Дайка , которые состоят только из круглых скобок таким образом, что они правильно сбалансированы. Число таких строк удовлетворяет одному и тому же рекурсивному описанию (каждое слово Дика длиной 2 n определяется подсловом Дика, заключенным в начальную букву '(' и соответствующее ей ')' вместе с подсловом Дика, оставшимся после закрывающей скобки, длина которой 2 i и 2 j удовлетворяют условию i + j + 1 = n ); следовательно, это число также является каталонским номером $C_{n}$. Итак, есть также пять слов Дика длины 6:

()()(),     ()(()),     (())(),     (()()),     ((()))

Эти слова Дика не соответствуют двоичным деревьям таким же образом. Вместо этого они связаны следующей рекурсивно определенной биекцией: слово Дика, равное пустой строке, соответствует двоичному дереву размера 0 только с одним листом. Любое другое слово Дейка можно записать как ( $w_{1}$) $w_{2}$, где $w_{1}$, $w_{2}$сами являются (возможно, пустыми) словами Дика и в них совпадают две письменные скобки. Тогда биекция определяется, позволяя словам $w_{1}$ и $w_{2}$ соответствуют двоичным деревьям, которые являются левыми и правыми дочерними элементами корня.

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

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

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

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

Узлы и ссылки

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

Этот метод хранения двоичных деревьев тратит впустую немало памяти, поскольку указатели будут иметь значение null (или указывать на дозорный элемент) более чем в половине случаев; более консервативная альтернатива представления — бинарное дерево с резьбой .

В языках с теговыми объединениями, таких как ML , узел дерева часто представляет собой тегированное объединение двух типов узлов, один из которых представляет собой тройку данных, левый дочерний и правый дочерний элементы, а другой является «листом». "узел, который не содержит данных и функционирует так же, как нулевое значение в языке с указателями. Например, следующая строка кода в OCaml (диалект ML) определяет двоичное дерево, в каждом узле которого хранится символ.

введите   chr_tree   =   Пусто   |    Узел   char  ​   *   chr_tree   *   chr_tree 

Массивы

Двоичные деревья также могут храниться в порядке ширины как неявная структура данных в массивах , и если дерево является полным двоичным деревом, этот метод не тратит места зря. В этом компактном расположении, если узел имеет индекс i , его дочерние элементы находятся по индексам $2i+1$ (для левого ребенка) и $2i+2$ (справа), а его родительский элемент (если есть) находится по индексу $\left\lfloor {\frac {i-1}{2}}\right\rfloor$(при условии, что корень имеет нулевой индекс). Альтернативно, при использовании массива с 1 индексом реализация упрощается, когда дочерние элементы находятся по адресу $2i$ и $2i+1$и родительский элемент найден по адресу $\lfloor i/2\rfloor$.

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

A small complete binary tree stored in an array

Кодировки

Краткие кодировки

Краткая структура данных — это структура, которая занимает пространство, близкое к минимально возможному, как это установлено теории информации нижними границами . Количество различных бинарных деревьев на $n$ узлы это $\mathrm {C} _{n}$, $n$каталонское число (при условии, что мы считаем деревья одинаковой структуры идентичными). Для больших $n$, речь идет о $4^{n}$; таким образом, нам нужно как минимум около $\log _{2}4^{n}=2n$бит для его кодирования. Таким образом, краткое двоичное дерево будет занимать $2n+o(n)$ биты.

Одним из простых представлений, соответствующих этой границе, является посещение узлов дерева в предварительном порядке с выводом «1» для внутреннего узла и «0» для листа. Если дерево содержит данные, мы можем просто одновременно хранить их в последовательном массиве в предварительном порядке. Эта функция выполняет это:

function  EncodeSuccinct(  узел  n,  битовой строки  структура  , данные массива  ) { 
      если  n =  ноль   , то 
          добавить 0 в структуру; 
      еще 
          добавить 1 к структуре; 
          добавить n.data к данным; 
          EncodeSuccinct (n.left, структура, данные); 
          EncodeSuccinct (n.right, структура, данные); 
  } 
 

Строковая структура имеет только $2n+1$ биты в конце, где $n$— количество (внутренних) узлов; нам даже не нужно хранить его длину. Чтобы показать, что никакая информация не потеряна, мы можем преобразовать выходные данные обратно в исходное дерево следующим образом:

function  DecodeSuccinct (  битовой строки  структура  , данные массива  ) { 
      удалите первый бит  структуры  и поместите его в  b 
     , если  b = 1  , то 
          создать новый узел  n 
          удалите первый элемент данных и поместите его в n.data 
          n.left = DecodeSuccinct (структура, данные) 
          n.right = DecodeSuccinct(структура, данные) 
          вернуть  н 
      иначе 
         вернуть  ноль 
  } 
 

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

Кодирование упорядоченных деревьев как двоичных деревьев

Между упорядоченными и двоичными деревьями существует естественное взаимно однозначное соответствие. Он позволяет однозначно представить любое упорядоченное дерево в виде двоичного дерева и наоборот:

Пусть T — узел упорядоченного дерева, и пусть B обозначает образ T в соответствующем двоичном дереве. Тогда дочерний элемент B левый представляет первого дочернего элемента T , а правый дочерний элемент B представляет T. следующего родственного брата

Например, упорядоченное дерево слева и двоичное дерево справа соответствуют:

An example of converting an n-ary tree to a binary tree

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

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

Общие операции

Вращение дерева — очень распространенная внутренняя операция в самобалансирующихся двоичных деревьях .

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

Вставка

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

Листовые узлы

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

Внутренние узлы

Процесс вставки узла в двоичное дерево

Вставка на внутренних узлах немного сложнее, чем на листовых узлах. Скажем, что внутренний узел — это узел A, а узел B — дочерний узел A. (Если вставка заключается в вставке правого дочернего элемента, то B является правым дочерним элементом A, и аналогично вставке левого дочернего элемента.) A назначает свой дочерний элемент новому узлу, и новый узел назначает своего родителя A. Затем новый узел назначает своего дочернего узла B, а B назначает своего родителя новым узлом.

Удаление

Удаление — это процесс удаления узла из дерева. Только определенные узлы бинарного дерева могут быть удалены однозначно.

Узел с нулем или одним дочерним элементом

Процесс удаления внутреннего узла в бинарном дереве

Предположим, что удаляемый узел — это узел A. Если у A нет дочерних узлов, удаление выполняется путем установки дочернего узла родительского узла A в значение null . Если у A есть один дочерний элемент, установите родительский элемент дочернего элемента A в родительский элемент A и установите дочерний элемент родительского элемента A в дочерний элемент A.

Узел с двумя потомками

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

Обход

Основная статья: Обход дерева

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

Предзаказ

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

В порядке

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

Пост-заказ

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

Порядок в глубину

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

Порядок в ширину

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

В полном двоичном дереве индекс ширины узла ( i − (2 ^д − 1)) могут использоваться как инструкции обхода от корня. Побитовое чтение слева направо, начиная с бита d - 1, где d - расстояние узла от корня ( d = ⌊log ₂ ( i +1)⌋), а рассматриваемый узел не является самим корнем ( d > 0). ). Когда индекс ширины маскируется в бите d - 1, значения битов 0 и 1 означает шаг влево или вправо соответственно. Процесс продолжается последовательной проверкой следующего бита справа, пока его не останется. Самый правый бит указывает на окончательный переход от родителя желаемого узла к самому узлу. Существует компромисс во времени и пространстве между итерацией полного двоичного дерева таким образом и каждым узлом, имеющим указатель(и) на его родственного(-ых) брата(-ов).

См. также

• 2–3 дерева
• 2–3–4 дерево
• АА-дерево
• Родословная
• АВЛ-дерево
• B-дерево
• Разделение двоичного пространства
• Дерево Хаффмана
• K-арное дерево
• Неравенство Крафта
• Оптимальное двоичное дерево поиска
• Случайное двоичное дерево
• Рекурсия (информатика)
• Красно-черное дерево
• Веревка (информатика)
• Самобалансирующееся двоичное дерево поиска
• Распространение дерева
• Номер прожектора
• Дерево примитивных троек Пифагора#Альтернативные методы создания дерева
• Некорневое двоичное дерево

Ссылки

Библиография

• Дональд Кнут . Искусство компьютерного программирования, том 1. Фундаментальные алгоритмы , третье издание. Аддисон-Уэсли, 1997. ISBN   0-201-89683-4 . Раздел 2.3, особенно подразделы 2.3.1–2.3.2 (стр. 318–348).

Внешние ссылки

• бинарные деревья. Архивировано 23 сентября 2020 г. в записи Wayback Machine в FindStat. базе данных
• Доказательство двоичного дерева по индукции
• Сбалансированное двоичное дерево поиска в массиве. Как создать восходящий список Анентафеля или сбалансированное двоичное дерево поиска в массиве.
• Двоичные деревья и их реализация с примерами рабочего кода.
• Реализация двоичного дерева на JavaScript с исходным кодом