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

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

Размеченное двоичное дерево размером 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 ₂ являются расширенными бинарными деревьями, то обозначим через T ₁ • T ₂ расширенное бинарное дерево, полученное путем добавления корня r, соединенного слева с T ₁ и справа с T ₂ ^{[ необходимо разъяснение , куда делась буква «r» в символе «T ₁ • T ₂ » ),} путем добавления ребер, когда эти поддеревья непустые.

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

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

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

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

Типы бинарных деревьев

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

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

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

Диаграмма родословной , которую можно сопоставить с идеальным 4-уровневым бинарным деревом.

• Аполное бинарное дерево (иногда называемоеправильным,^[15] плоскимилистрогимбинарным деревом)^[16][17]— это дерево, в котором каждый узел имеет либо 0, либо 2 потомка. Другой способ определения полного бинарного дерева —рекурсивное определение. Полное бинарное дерево — это либо:^[11]
  • Одна вершина (один узел в качестве корневого узла).
  • Дерево, корневой узел которого имеет два поддерева, оба из которых являются полными бинарными деревьями.
• АИдеальное бинарное дерево — это бинарное дерево, в котором все внутренние узлы имеют двух потомков, авсе листья имеют одинаковуюглубинуили один и тот жеуровень(уровень узла определяется как количество ребер или связей от корневого узла до узла).^[18]Идеальное бинарное дерево — это полное бинарное дерево.
• АПолное бинарное дерево — это бинарное дерево, в котором каждый уровень,за исключением, возможно, последнего, полностью заполнен, а все узлы на последнем уровне находятся как можно дальше влево. Оно может иметь от 1 до 2 ^h узлов на последнем уровне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 в языке Dyck , которые состоят только из скобок таким образом, что они должным образом сбалансированы. Количество таких строк удовлетворяет тому же рекурсивному описанию (каждое слово Dyck длины 2 n определяется подсловом Dyck, заключенным в начальную скобку '(' и соответствующую ей ')' вместе с подсловом Dyck, оставшимся после этой закрывающей скобки, длины которых 2 i и 2 j удовлетворяют i + j + 1 = n ); это число, следовательно, также является каталонским числом . Таким образом, существует также пять слов Dyck длины 6: ${\displaystyle C_{n}}$

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

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

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

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

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

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

Узлы и ссылки

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

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

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

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

Массивы

Двоичные деревья также могут храниться в порядке «в ширину» как неявная структура данных в массивах , и если дерево является полным двоичным деревом, этот метод не тратит место впустую. В этом компактном расположении, если узел имеет индекс i , его потомки находятся по индексам (для левого потомка) и (для правого), в то время как его родитель (если есть) находится по индексу (предполагая, что корень имеет нулевой индекс). В качестве альтернативы, с 1-индексированным массивом реализация упрощается с потомками, найденными по и , и родителем, найденным по . ^[28] ${\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 }$

Этот метод выигрывает от более компактного хранения и лучшей локальности ссылок , особенно во время обхода в прямом порядке. Он часто используется для двоичных куч . ^[29]

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

Кодировки

Сжатые кодировки

Сжатая структура данных — это та, которая занимает близкое к минимально возможному пространство, как установлено теоретическими нижними границами информации . Количество различных двоичных деревьев на узлах равно , y каталонскому числу (предполагая, что мы рассматриваем деревья с одинаковой структурой как идентичные). Для больших это около ; таким образом, нам нужно по крайней мере около бит для его кодирования. Сжатое двоичное дерево, следовательно, будет занимать бит. ${\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» для листа. ^[30] Если дерево содержит данные, мы можем просто одновременно сохранить их в последовательном массиве в прямом порядке. Эта функция выполняет это:

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

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

функция 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 назначает своего родителя в качестве нового узла.

Удаление

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

Узел с нулевым или одним дочерним узлом

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

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

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

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

Прохождение

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

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

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

Чтобы

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

Пост-заказ

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

Глубинный порядок

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

Широтный порядок

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

В полном бинарном дереве индекс ширины узла ( 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). Дискретная математика: доказательства, структуры и приложения, третье издание. CRC Press. стр. 620. ISBN 978-1-4398-1280-8.
2. Стивен С. Скиена (2009). Руководство по разработке алгоритмов. Springer Science & Business Media. стр. 77. ISBN 978-1-84800-070-4.
3. Knuth (1997). Искусство программирования, том 1, 3/E . Pearson Education. стр. 363. ISBN 0-201-89683-4.
4. Иван Флорес (1971). Компьютерная система программирования/360 . Prentice-Hall. стр. 39.
5. Кеннет Розен (2011). Дискретная математика и ее приложения, 7-е издание . McGraw-Hill Science. стр. 749. ISBN 978-0-07-338309-5.
6. Дэвид Р. Мазур (2010). Комбинаторика: Экскурсия. Математическая ассоциация Америки. стр. 246. ISBN 978-0-88385-762-5.
7. "Двоичное дерево", Энциклопедия математики , EMS Press , 2001 [1994]также в печати как Michiel Hazewinkel (1997). Encyclopaedia of Mathematics. Приложение I. Springer Science & Business Media. стр. 124. ISBN 978-0-7923-4709-5.
8. LR Foulds (1992). Приложения теории графов. Springer Science & Business Media. стр. 32. ISBN 978-0-387-97599-3.
9. Дэвид Макинсон (2009). Множества, логика и математика для вычислений . Springer Science & Business Media. стр. 199. ISBN 978-1-84628-845-6.
10. Джонатан Л. Гросс (2007). Комбинаторные методы с компьютерными приложениями. CRC Press. стр. 248. ISBN 978-1-58488-743-0.
11. Kenneth Rosen (2011). Дискретная математика и ее приложения 7-е издание . McGraw-Hill Science. стр. 352–353. ISBN 978-0-07-338309-5.
12. Те Чианг Ху; Ман-так Шинг (2002). Комбинаторные алгоритмы . Courier Dover Publications. стр. 162. ISBN 978-0-486-41962-6.
13. Ли-Хсин Хсу; Чэн-Куан Линь (2008). Теория графов и сети взаимосвязей. CRC Press. стр. 66. ISBN 978-1-4200-4482-9.
14. J. Flum; M. Grohe (2006). Параметризованная теория сложности . Springer. стр. 245. ISBN 978-3-540-29953-0.
15. Тамассиа, Майкл Т. Гудрич, Роберто (2011). Разработка алгоритмов: основы, анализ и примеры Интернета (2-е изд.). Нью-Дели: Wiley-India. стр. 76. ISBN 978-81-265-0986-7.{{cite book}}: CS1 maint: multiple names: authors list (link)
16. "полное двоичное дерево". NIST .
17. Ричард Стэнли, Перечислительная комбинаторика, том 2, стр. 36
18. "идеальное бинарное дерево". NIST .
19. "полное двоичное дерево". NIST.
20. "почти полное двоичное дерево". Архивировано из оригинала 2016-03-04 . Получено 2015-12-11 .
21. "почти полное двоичное дерево" (PDF) . Архивировано (PDF) из оригинала 2022-10-09.
22. Аарон М. Тененбаум и др. Структуры данных с использованием C, Prentice Hall, 1990 ISBN 0-13-199746-7 
23. Пол Э. Блэк (ред.), статья о структуре данных в Словаре алгоритмов и структур данных . Национальный институт стандартов и технологий США . 15 декабря 2004 г. Онлайн-версия. Архивировано 21 декабря 2010 г. на Wayback Machine . Доступно 19 декабря 2010 г.
24. Пармар, Ананд К. (2020-01-22). "Различные типы двоичного дерева с красочными иллюстрациями". Medium . Получено 2020-01-24 .
25. Мехта, Динеш; Сартадж Сахни (2004). Справочник по структурам данных и приложениям . Чепмен и Холл . ISBN 1-58488-435-5.
26. Д. Саманта (2004). Классические структуры данных . PHI Learning Pvt. Ltd. стр. 264–265. ISBN 978-81-203-1874-8.
27. Майкл Л. Скотт (2009). Прагматика языка программирования (3-е изд.). Морган Кауфманн. стр. 347. ISBN 978-0-08-092299-7.
28. Введение в алгоритмы . Кормен, Томас Х., Кормен, Томас Х. (2-е изд.). Кембридж, Массачусетс: MIT Press. 2001. стр. 128. ISBN 0-262-03293-7. OCLC  46792720.{{cite book}}: CS1 maint: others (link)
29. Лааксо, Микко. «Очередь приоритетов и двоичная куча». Университет Аалто . Проверено 11 октября 2023 г.
30. Демейн, Эрик. "6.897: Advanced Data Structures Spring 2003 Lecture 12" (PDF) . MIT CSAIL. Архивировано из оригинала (PDF) 24 ноября 2005 г. . Получено 14 апреля 2022 г. .
31. Dung X. Nguyen (2003). "Двоичная структура дерева". rice.edu . Получено 28 декабря 2010 г.
32. Wittman, Todd (2015-02-13). "Lecture 18: Tree Traversals" (PDF) . Архивировано из оригинала (PDF) 2015-02-13 . Получено 2023-04-29 .

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

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

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

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