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

Помеченное двоичное дерево размером 9 и высотой 3 с корневым узлом, значение которого равно 2. Приведенное выше дерево несбалансировано и не отсортировано.

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

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

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

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

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

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

Определения [ править ]

Рекурсивное определение [ править ]

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

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

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

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

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

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

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

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

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

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

• Совершенное бинарное дерево бинарное дерево , в котором все внутренние узлы имеют двух детей и все листья имеют одинаковую глубину или же уровень . ^[21] Примером совершенного бинарного дерева является (не кровосмесительная) карта происхождения человека до заданной глубины, поскольку у каждого человека ровно два биологических родителя (одна мать и один отец). При условии, что в таблице предков всегда отображаются мать и отец с одной и той же стороны для данного узла, их пол можно рассматривать как аналогию левых и правых детей, причем дети здесь понимаются как алгоритмический термин. Таким образом, идеальное дерево всегда является законченным, но полное дерево не обязательно является идеальным.
• В бесконечном полном двоичном дереве каждый узел имеет двух потомков (и поэтому набор уровней счетно бесконечен ). Множество всех узлов счетно бесконечно, но множество всех бесконечных путей от корня несчетно, имея мощность континуума . Это потому, что эти пути соответствуют сохраняющей порядок биекции точкам множества Кантора или (на примере дерева Штерна – Броко ) множеству положительных иррациональных чисел .
• Сбалансирован бинарное дерево является двоичным структура дерева , в котором левое и правое поддеревья каждого узла различаются по высоте, не более 1. ^[22] Можно также рассматривать бинарные деревья , где нет листьев не намного дальше от корня , чем любой другой лист. (Различные схемы балансировки позволяют по-разному определять «гораздо дальше». ^[23] )
• В вырожденном (или патологическом ) дереве каждый родительский узел имеет только один связанный дочерний узел. ^[24] Это означает, что дерево будет вести себя как структура данных связанного списка .

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

• Количество узлов в полном двоичном дереве не меньше и не больше , где - высота дерева. Дерево, состоящее только из корневого узла, имеет высоту 0.${\ displaystyle n}$${\ displaystyle n = 2h + 1}$${\ Displaystyle п = 2 ^ {ч + 1} -1}$${\ displaystyle h}$
• Количество листовых узлов в идеальном двоичном дереве обусловлено количеством нелистовых (так называемых внутренних) узлов .${\ displaystyle l}$${\ displaystyle l = (n + 1) / 2}$${\ displaystyle nl = \ sum _ {k = 0} ^ {\ log _ {2} (l) -1} 2 ^ {k} = 2 ^ {\ log _ {2} (l)} - 1 = l -1}$
• Это означает, что полное двоичное дерево с листьями имеет узлы.${\ displaystyle l}$${\displaystyle n=2l-1}$
• В сбалансированном полном двоичном дереве (см. Функцию потолка ). ^{[ необходима цитата ]}${\displaystyle h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil }$
• В идеальном полном бинарном дереве, таким образом .${\displaystyle l=2^{h}}$${\displaystyle n=2^{h+1}-1}$
• Количество нулевых ссылок (т. Е. Отсутствующих дочерних узлов) в двоичном дереве из n узлов равно ( n +1).
• Количество внутренних узлов в полном двоичном дереве из n узлов равно .${\displaystyle \lfloor n/2\rfloor }$
• Для любого непустого двоичного дерева с n ₀ листовыми узлами и n ₂ узлами степени 2 n ₀ = n ₂ + 1. ^[25]

Комбинаторика [ править ]

В комбинаторике рассматривается проблема подсчета количества полных двоичных деревьев заданного размера. Здесь деревья не имеют значений, прикрепленных к их узлам (это просто умножит количество возможных деревьев на легко определяемый коэффициент), а деревья различаются только своей структурой; однако левый и правый дочерние элементы любого узла различаются (если это разные деревья, то при их замене будет получено дерево, отличное от исходного). Размер дерева принимается равным количеству 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 .${\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}}$

${\displaystyle ()()(),\qquad ()(()),\qquad (())(),\qquad (()()),\qquad ((()))}$.

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

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

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

Способы хранения двоичных деревьев [ править ]

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

Узлы и ссылки [ править ]

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

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

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

введите  chr_tree  =  Пусто  |  Узел  из  полукокса  *  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 }$, особенно во время обхода предзаказа. Однако это дорогое удовольствие для роста ^{[ необходима цитата ]} и тратит впустую пространство, пропорциональное ^{[ необходимое цитирование ]} 2 ^h - n для дерева глубины h с n узлами.

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

Кодировки [ править ]

Краткие кодировки [ править ]

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

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

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

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

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

Кодирование общих деревьев как двоичных [ править ]

Между общими упорядоченными деревьями и бинарными деревьями существует взаимно однозначное соответствие, которое, в частности, используется Лиспом для представления общих упорядоченных деревьев в виде бинарных деревьев. Чтобы преобразовать общее упорядоченное дерево в двоичное, нам нужно только представить общее дерево в виде левого дочернего правого брата. Результатом этого представления будет автоматически двоичное дерево, если смотреть с другой точки зрения. Каждый узел N в упорядоченном дереве соответствует узлу N ' в двоичном дереве; левый ребенок N « представляет собой узел , соответствующий первый ребенок N , а правый ребенок N» представляет собой узел , соответствующий N«S следующий родственный --- то есть, следующий узел, чтобы среди детей родителя N . Это двоичное представление дерева общего порядка иногда также называют двоичным деревом с левым потомком и правым братом (также известное как дерево LCRS, дерево с двойной цепочкой, цепочка дочерних наследников).

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

Например, в дереве слева A имеет 6 детей {B, C, D, E, F, G}. Его можно преобразовать в двоичное дерево справа.

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

(((NO) IJ) CD ((P) (Q)) F (M))

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

Общие операции [ править ]

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

Вставка [ править ]

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

Листовые узлы [ править ]

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

Внутренние узлы [ править ]

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

Удаление [ править ]

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

Узел с одним или одним дочерним узлом [ править ]

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

Узел с двумя детьми [ править ]

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

Обход [ править ]

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

Приказ в глубину [ править ]

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

Порядок в ширину [ править ]

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

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

См. Также [ править ]

Ссылки [ править ]

Цитаты [ править ]

Библиография [ править ]

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

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме двоичных деревьев .

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