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

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

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

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

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

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

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

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

Определения

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

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

• пустое множество представляет собой расширенное двоичное дерево
• если T ₁ и T _{2 — расширенные двоичные деревья, то через T 1} • T ₂ обозначим расширенное двоичное дерево, полученное добавлением корня r, соединенного слева с T ₁ и справа с T ₂ ^{[ нужно уточнить, откуда взялось ' r' перейдите в символ 'T ₁ • T ₂ ' ]} , добавляя ребра, когда эти поддеревья не пусты.

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

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

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

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

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

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

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

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

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

• АПолное двоичное дерево (иногда называемое правильным,[^15] плоскостьюилистрогимдвоичным деревом)^[16][17]— это дерево, в котором каждый узел имеет либо 0, либо 2 дочерних элемента. Другой способ определения полного двоичного дерева — эторекурсивное определение. Полное двоичное дерево — это либо:^[11]
  • Одна вершина (один узел в качестве корневого узла).
  • Дерево, корневой узел которого имеет два поддерева, оба из которых являются полными двоичными деревьями.
• АИдеальное бинарное дерево — это бинарное дерево, в котором все внутренние узлы имеют по два дочерних узла, авсе листья имеют одинаковуюглубинуили один и тот жеуровень(уровень узла, определяемый как количество ребер или связей от корневого узла к узлу).^[18]Идеальное двоичное дерево — это полное двоичное дерево.
• АПолное двоичное дерево — это двоичное дерево, в котором каждый уровень,за исключением, возможно, последнего, полностью заполнен, а все узлы на последнем уровне расположены как можно дальше влево.На последнем уровнеhон может иметь от 1 до 2 ^{узлов h} .^[19]Таким образом, совершенное дерево всегда полно, но полное дерево не всегда совершенно. Некоторые авторы вместо этого используют термин «полное»для обозначенияидеальногодвоичного дерева, как оно определено выше, и в этом случае они называют этот тип дерева (с возможным незаполненным последним уровнем)почти полнымдвоичным деревом илипочти полнымдвоичным деревом.^[20][21]Полное двоичное дерево можно эффективно представить с помощью массива.^[19]

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

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

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

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

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

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

$${\displaystyle ((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 . Следовательно, количество бинарных деревьев размера n имеет следующее рекурсивное описание , и для любого положительного целого числа n . Отсюда следует, что это каталонское число индекса n . ${\displaystyle C_{n}}$ ${\displaystyle C_{0}=1}$ ${\displaystyle \textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}}$ ${\displaystyle C_{n}}$

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

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

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

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

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

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

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

Узлы и ссылки

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

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

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

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

Массивы

Двоичные деревья также могут храниться в порядке ширины в виде неявной структуры данных в массивах , и если дерево является полным двоичным деревом, этот метод не теряет места. В этом компактном расположении, если узел имеет индекс i , его дочерние элементы находятся по индексам (для левого дочернего элемента) и (для правого), а его родительский элемент (если таковой имеется) находится по индексу (при условии, что корень имеет нулевой индекс). ). В качестве альтернативы, с массивом с 1 индексом, реализация упрощается: дочерние элементы находятся в и , а родительский элемент находится в . ^[28] Этот метод выигрывает от более компактного хранения и лучшей локальности ссылок , особенно во время обхода предварительного заказа. Однако его рост обходится дорого ^[29] и тратится впустую пространство, пропорциональное ^{[ нужна ссылка ]} 2 ^h - n для дерева глубины h с n узлами. ${\displaystyle 2i+1}$ ${\displaystyle 2i+2}$ ${\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor }$ ${\displaystyle 2i}$ ${\displaystyle 2i+1}$ ${\displaystyle \lfloor i/2\rfloor }$

Этот метод хранения часто используется для двоичных куч . ^[30]

Небольшое полное двоичное дерево, хранящееся в массиве.

Кодировки

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

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

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

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

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

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

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

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

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

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

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

Пример преобразования n-арного дерева в двоичное дерево

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

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

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

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

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

Вставка

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

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

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

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

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

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

Удаление

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

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

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

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

Узел с двумя детьми

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

Обход

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

Предварительный заказ

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

Чтобы

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

Постзаказ

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

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

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

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

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

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

Смотрите также

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

Рекомендации

Цитаты

1. Роуэн Гарнье; Джон Тейлор (2009). Дискретная математика: Доказательства, структуры и приложения, третье издание. ЦРК Пресс. п. 620. ИСБН 978-1-4398-1280-8.
2. Стивен С. Скиена (2009). Руководство по проектированию алгоритмов. Springer Science & Business Media. п. 77. ИСБН 978-1-84800-070-4.
3. Кнут (1997). Искусство компьютерного программирования, Том 1, 3/E . Пирсон Образование. п. 363. ИСБН 0-201-89683-4.
4. Иван Флорес (1971). Система компьютерного программирования/360 . Прентис-Холл. п. 39.
5. Кеннет Розен (2011). Дискретная математика и ее приложения, 7-е издание . МакГроу-Хилл Наука. п. 749. ИСБН 978-0-07-338309-5.
6. Дэвид Р. Мазур (2010). Комбинаторика: экскурсия. Математическая ассоциация Америки. п. 246. ИСБН 978-0-88385-762-5.
7. «Двоичное дерево», Математическая энциклопедия , EMS Press , 2001 [1994]также печатается как Мишель Хазевинкель (1997). Энциклопедия математики. Приложение I. Springer Science & Business Media. п. 124. ИСБН 978-0-7923-4709-5.
8. Л. Р. Фулдс (1992). Приложения теории графов. Springer Science & Business Media. п. 32. ISBN 978-0-387-97599-3.
9. Дэвид Макинсон (2009). Множества, логика и математика для вычислений . Springer Science & Business Media. п. 199. ИСБН 978-1-84628-845-6.
10. Джонатан Л. Гросс (2007). Комбинаторные методы с компьютерными приложениями. ЦРК Пресс. п. 248. ИСБН 978-1-58488-743-0.
11. Кеннет Розен (2011). Дискретная математика и ее приложения. 7-е издание . МакГроу-Хилл Наука. стр. 352–353. ISBN 978-0-07-338309-5.
12. Те Чан Ху; Ман-так Шинг (2002). Комбинаторные алгоритмы . Публикации Courier Dover. п. 162. ИСБН 978-0-486-41962-6.
13. Ли-Синь Сюй; Ченг-Куан Линь (2008). Теория графов и сети взаимосвязей. ЦРК Пресс. п. 66. ИСБН 978-1-4200-4482-9.
14. Дж. Флум; М. Гроэ (2006). Параметризованная теория сложности . Спрингер. п. 245. ИСБН 978-3-540-29953-0.
15. Тамассия, Майкл Т. Гудрич, Роберто (2011). Разработка алгоритмов: основы, анализ и примеры из Интернета (2-е изд.). Нью-Дели: Wiley-Индия. п. 76. ИСБН 978-81-265-0986-7.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
16. «полное двоичное дерево». НИСТ .
17. Ричард Стэнли, Перечислительная комбинаторика, том 2, стр.36
18. «идеальное двоичное дерево». НИСТ .
19. «полное двоичное дерево». НИСТ.
20. «почти полное двоичное дерево». Архивировано из оригинала 4 марта 2016 г. Проверено 11 декабря 2015 г.
21. «Почти полное двоичное дерево» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г.
22. Аарон М. Тененбаум и др. Структуры данных с использованием C, Prentice Hall, 1990 ISBN 0-13-199746-7 
23. Пол Э. Блэк (ред.), запись о структуре данных в Словаре алгоритмов и структур данных . Национальный институт стандартов и технологий США . 15 декабря 2004 г. Онлайн-версия. Архивировано 21 декабря 2010 г. на Wayback Machine , по состоянию на 19 декабря 2010 г.
24. Пармар, Ананд К. (22 января 2020 г.). «Различные типы двоичных деревьев с красочными иллюстрациями». Середина . Проверено 24 января 2020 г.
25. Мехта, Динеш; Сартадж Сахни (2004). Справочник по структурам данных и приложениям . Чепмен и Холл . ISBN 1-58488-435-5.
26. Д. Саманта (2004). Классические структуры данных . PHI Learning Pvt. ООО, стр. 264–265. ISBN 978-81-203-1874-8.
27. Майкл Л. Скотт (2009). Прагматика языков программирования (3-е изд.). Морган Кауфманн. п. 347. ИСБН 978-0-08-092299-7.
28. Введение в алгоритмы . Кормен, Томас Х., Кормен, Томас Х. (2-е изд.). Кембридж, Массачусетс: MIT Press. 2001. с. 128. ИСБН 0-262-03293-7. ОСЛК  46792720.{{cite book}}: CS1 maint: другие ( ссылка )
29. «Массивы обозначений Big O против вставок связанных списков» . Переполнение стека . Проверено 4 июля 2023 г.
30. Лааксо, Микко. «Очередь приоритетов и двоичная куча». Университет Аалто . Проверено 11 октября 2023 г.
31. Демейн, Эрик. «6.897: Расширенные структуры данных, лекция 12, весна 2003 г.» (PDF) . МИТ ЦСАИЛ. Архивировано из оригинала (PDF) 24 ноября 2005 года . Проверено 14 апреля 2022 г.
32. Дунг X. Нгуен (2003). «Двоичная древовидная структура». рис.еду . Проверено 28 декабря 2010 г.
33. Уиттман, Тодд (13 февраля 2015 г.). «Лекция 18: Обход дерева» (PDF) . Архивировано из оригинала (PDF) 13 февраля 2015 г. Проверено 29 апреля 2023 г.

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

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

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

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