Двоичное дерево - Binary tree

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

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

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

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

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

Родословная схема , которая может быть сопоставлена с совершенным 4 уровня бинарного дерева.

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

Полное двоичное дерево (не полное)

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

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

Количество узлов в полном двоичном дереве не меньше и не больше , где - высота дерева. Дерево, состоящее только из корневого узла, имеет высоту 0. ${\ displaystyle n}$ ${\ displaystyle 2h + 1}$ ${\ displaystyle 2 ^ {h + 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 п = 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 п = 2 ^ {ч + 1} -1}$
Количество нулевых ссылок (т. Е. Отсутствующих дочерних узлов) в двоичном дереве из n узлов равно ( n +1).
Количество внутренних узлов в полном двоичном дереве из n узлов равно . ${\ Displaystyle \ lfloor п / 2 \ rfloor}$
Для любого непустого двоичного дерева с n ₀ листовыми узлами и n ₂ узлами степени 2 n ₀ = n ₂ + 1.

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

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

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

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

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

Узлы и ссылки

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

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

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

type chr_tree = Empty | Node of char * chr_tree * chr_tree

Массивы

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

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

Кодировки

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

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

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

function EncodeSuccinct(node n, bitstring structure, array data) {
    if n = nil then
        append 0 to structure;
    else
        append 1 to structure;
        append n.data to data;
        EncodeSuccinct(n.left, structure, data);
        EncodeSuccinct(n.right, structure, data);
}

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

function DecodeSuccinct(bitstring structure, array data) {
    remove first bit of structure and put it in b
    if b = 1 then
        create a new node n
        remove first element of data and put it in n.data
        n.left = DecodeSuccinct(structure, data)
        n.right = DecodeSuccinct(structure, data)
        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 назначает своего родителя в качестве нового узла.

Удаление

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

Узел с нулем или одним потомком

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

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

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

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

Обход

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

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

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

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

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

В полном двоичном дереве индекс ширины узла ( i - (2 ^d - 1)) может использоваться как инструкции обхода от корня. Поразрядное чтение слева направо, начиная с бита d - 1, где d - это расстояние узла от корня ( d = ⌊log ₂ ( 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).

Languages

In other projects