В информатике , А бинарное дерево представляет собой древовидную структуру данных , в которой каждый узел имеет не более двух детей , которые упоминаются каклевый ребенок иправильный ребенок . Рекурсивное определениеиспользованием толькотеории множествпонятий является точто (непустое) бинарное дерево являетсякортеж(L,S,R), гдеLиRявляются бинарные деревья илипустое множествоаSпредставляет собойодноэлементный наборсодержащий корень. [1] Некоторые авторы допускают, чтобы двоичное дерево также было пустым множеством. [2]
С точки зрения теории графов , бинарные (и K-арные) деревья, как определено здесь, являются древовидными . [3] Таким образом, двоичное дерево можно также назвать ветвлением ветвления [3] - термин, который появился в некоторых очень старых книгах по программированию [4] до того, как стала преобладать современная терминология информатики. Кроме того , можно интерпретировать , как бинарное дерево неориентированного , а не ориентированного графа , в этом случае бинарное дерево представляет собой приказ , корневое дерево . [5] Некоторые авторы используют корневое двоичное дерево вместо двоичного, чтобы подчеркнуть тот факт, что дерево является корневым, но, как определено выше, двоичное дерево всегда является корневым. [6] Бинарное дерево - это частный случай упорядоченного K-арного дерева , где k равно 2.
В математике то, что называют двоичным деревом, может значительно отличаться от автора к автору. Некоторые используют определение, обычно используемое в информатике [7], но другие определяют его как каждый не-лист, имеющий ровно двух дочерних элементов, и не обязательно упорядочивают (как левый / правый) дочерние элементы. [8]
В вычислениях бинарные деревья используются двумя разными способами:
- Во-первых, как средство доступа к узлам на основе некоторого значения или метки, связанной с каждым узлом. [9] Двоичные деревья, помеченные таким образом, используются для реализации двоичных деревьев поиска и двоичных куч , а также для эффективного поиска и сортировки . Обозначение некорневых узлов как левых или правых дочерних узлов, даже если присутствует только один дочерний элемент, имеет значение в некоторых из этих приложений, в частности, в деревьях двоичного поиска. [10] Однако расположение конкретных узлов в дереве не является частью концептуальной информации. Например, в обычном двоичном дереве поиска размещение узлов почти полностью зависит от порядка, в котором они были добавлены, и может быть переупорядочено (например, путем балансировки ) без изменения смысла.
- Во-вторых, как представление данных с соответствующей разветвляющейся структурой. В таких случаях конкретное расположение узлов под и / или слева или справа от других узлов является частью информации (т. Е. Изменение его приведет к изменению значения). Общие примеры встречаются с кодированием Хаффмана и кладограммами . Ежедневное деление документов на главы, разделы, абзацы и так далее - аналогичный пример с n-арными, а не бинарными деревьями.
Определения
Рекурсивное определение
Чтобы фактически определить двоичное дерево в целом, мы должны учитывать возможность того, что только один из дочерних элементов может быть пустым. Для этого нужен артефакт, который в некоторых учебниках называется расширенным двоичным деревом . Таким образом, расширенное двоичное дерево рекурсивно определяется как: [11]
- пустое множество является расширенным бинарным деревом
- если T 1 и T 2 являются расширенными двоичными деревьями, то обозначим через T 1 • T 2 расширенное двоичное дерево, полученное добавлением корня r, соединенного слева с T 1 и справа с T 2 [ требуется пояснение, откуда взялось ' r 'войдите в символ ' T 1 • T 2 ' ] , добавив ребра, когда эти поддеревья не пусты.
Другой способ представить эту конструкцию (и понять терминологию) - рассмотреть вместо пустого множества другой тип узла - например, квадратные узлы, если обычные являются кругами. [12]
Использование концепций теории графов
Бинарное дерево - это корневое дерево , которое также является упорядоченным деревом (также известным как плоское дерево), в котором каждый узел имеет не более двух дочерних элементов. У корневого дерева естественным образом возникает понятие уровней (расстояние от корня), таким образом, для каждого узла может быть определено понятие дочерних узлов как узлов, связанных с ним уровнем ниже. Упорядочивание этих детей (например, рисование их на плоскости) позволяет отличить левого ребенка от правого ребенка. [13] Но это по-прежнему не отличает узел с левым, но не правым потомком, от узла с правым, но без левого потомка.
Необходимое различие можно сделать, сначала разбив ребра, т. Е. Определив двоичное дерево как тройку (V, E 1 , E 2 ), где (V, E 1 ∪ E 2 ) - корневое дерево (эквивалентно древовидности) и E 1 ∩ E 2 пусто, а также требует, чтобы для всех 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.
- Количество листовых узлов в совершенном двоичном дереве потому что количество нелистовых (так называемых внутренних) узлов .
- Это означает, что полное двоичное дерево с листья узлы.
- В сбалансированном полном двоичном дереве(см. функцию потолка ). [ необходима цитата ]
- В идеальном полном двоичном дереве таким образом .
- Количество нулевых ссылок (т. Е. Отсутствующих дочерних узлов) в двоичном дереве из n узлов равно ( n +1).
- Количество внутренних узлов в полном двоичном дереве из n узлов равно.
- Для любого непустого двоичного дерева с n 0 листовыми узлами и n 2 узлами степени 2 n 0 = n 2 + 1. [25]
Комбинаторика
В комбинаторике рассматривается проблема подсчета количества полных двоичных деревьев заданного размера. Здесь деревья не имеют значений, прикрепленных к их узлам (это просто умножит количество возможных деревьев на легко определяемый коэффициент), а деревья различаются только своей структурой; однако левый и правый дочерние элементы любого узла различаются (если это разные деревья, то при их замене будет получено дерево, отличное от исходного). Размер дерева принимается равным количеству n внутренних узлов (с двумя дочерними узлами); остальные узлы являются листовыми, и их n + 1 . Количество таких двоичных деревьев размера n равно количеству способов заключить в круглые скобки строку из n + 1 символов (представляющих листья), разделенных n двоичными операторами (представляющими внутренние узлы), для определения подвыражений аргументов каждого оператора. Например, для n = 3 нужно заключить в скобки строку вида, что возможно пятью способами:
Соответствие бинарным деревьям должно быть очевидным, а добавление избыточных скобок (вокруг уже заключенного в скобки выражения или вокруг полного выражения) запрещено (или, по крайней мере, не считается созданием новой возможности).
Существует уникальное двоичное дерево размера 0 (состоящее из одного листа), а любое другое двоичное дерево характеризуется парой его левого и правого потомков; если они имеют размеры i и j соответственно, полное дерево имеет размер i + j + 1 . Следовательно, числобинарных деревьев размера n имеет следующее рекурсивное описание, а также для любого натурального n . Следует, чтоэто число Каталонский индекса п .
Вышеупомянутые строки в скобках не следует путать с набором слов длиной 2 n в языке Дейка , которые состоят только из круглых скобок таким образом, чтобы они были правильно сбалансированы. Количество таких строк удовлетворяет одному и тому же рекурсивному описанию (каждое слово Дика длины 2 n определяется подсловом Дика, заключенным в начальную букву '(' и совпадающим с ним ')' вместе с подсловом Дика, оставшимся после этой закрывающей скобки, длина которого 2 i и 2 j удовлетворяют i + j + 1 = n ); поэтому это число также является каталонским.. Итак, есть еще пять слов Дайка длины 6:
- () () (), () (()), (()) (), (() ()), ((()))
Эти слова Дика не соответствуют двоичным деревьям таким же образом. Вместо этого они связаны следующей рекурсивно определенной биекцией: слово Дика, равное пустой строке, соответствует двоичному дереву размера 0 только с одним листом. Любое другое слово Дика можно записать как (), где ,сами являются (возможно, пустыми) словами Дика, и в них совпадают две написанные круглые скобки. Тогда биекция определяется тем, что слова а также соответствуют бинарным деревьям, которые являются левым и правым потомками корня.
Биективное соответствие также можно определить следующим образом: заключите слово Дика в дополнительную пару круглых скобок, чтобы результат можно было интерпретировать как выражение списка Лиспа (с пустым списком () как только встречающимся атомом); тогда выражение пары точек для этого правильного списка является выражением в круглых скобках (с NIL в качестве символа и '.' в качестве оператора), описывающим соответствующее двоичное дерево (которое, по сути, является внутренним представлением правильного списка).
Возможность представлять бинарные деревья в виде цепочек символов и скобок подразумевает, что бинарные деревья могут представлять элементы свободной магмы на единичном наборе.
Способы хранения двоичных деревьев
Бинарные деревья могут быть построены из примитивов языка программирования несколькими способами.
Узлы и ссылки
В языке с записями и ссылками бинарные деревья обычно строятся с использованием структуры узла дерева, которая содержит некоторые данные и ссылки на его левый дочерний элемент и его правый дочерний элемент. Иногда он также содержит ссылку на своего уникального родителя. Если у узла менее двух дочерних узлов, некоторые из дочерних указателей могут быть установлены на специальное нулевое значение или на специальный контрольный узел .
Этот метод хранения двоичных деревьев расходует изрядное количество памяти, поскольку указатели будут нулевыми (или указывать на стража) более чем в половине случаев; более консервативной альтернативой представления является двоичное дерево с нитями . [26]
В языках с помеченными объединениями, такими как ML , узел дерева часто представляет собой помеченное объединение двух типов узлов, один из которых представляет собой трехкортежный набор данных, левый дочерний и правый дочерний, а другой из которых является «листом». "узел, который не содержит данных и функционирует подобно нулевому значению в языке с указателями. Например, следующая строка кода в OCaml (диалект ML) определяет двоичное дерево, в котором хранится символ в каждом узле. [27]
введите chr_tree = Пусто | Узел из полукокса * chr_tree * chr_tree
Массивы
Двоичные деревья также могут храниться в порядке ширины в виде неявной структуры данных в массивах , и если дерево является полным двоичным деревом, этот метод не тратит впустую места. В этом компактном расположении, если узел имеет индекс i , его дочерние элементы находятся в индексах (для левого ребенка) и (справа), а его родитель (если есть) находится по индексу (при условии, что корень имеет нулевой индекс). В качестве альтернативы, с 1-индексированным массивом реализация упрощается с дочерними элементами, найденными в а также , и родитель найден в . [28] Этот метод выигрывает от более компактного хранения и лучшей локализации ссылок , особенно во время обхода перед заказом. Однако это дорогое удовольствие для роста [ необходима цитата ] и тратит впустую пространство, пропорциональное [ необходимое цитирование ] 2 h - n для дерева глубины h с n узлами.
Этот метод хранения часто используется для двоичных куч . [ необходима цитата ]
Кодировки
Краткие кодировки
Сжатое структура данных является одним который занимает близко к минимально возможному пространству, как установлено информационных теоретических нижних границ. Количество различных бинарных деревьев на узлы , то й каталонское число (при условии, что мы рассматриваем деревья с идентичной структурой как идентичные). Для больших, речь идет о ; таким образом, нам нужно как минимум околобиты для его кодирования. Таким образом, сжатое двоичное дерево заняло бы биты.
Одно простое представление, которое соответствует этой границе, - это посещение узлов дерева в предварительном порядке, вывод «1» для внутреннего узла и «0» для листа. [1] Если дерево содержит данные, мы можем просто одновременно сохранить их в последовательном массиве в предварительном порядке. Эта функция выполняет это:
функция EncodeSuccinct ( узел n, структура цепочки битов , данные массива ) { если n = nil, то добавить 0 в структуру; еще добавить 1 в структуру; добавить данные к данным; EncodeSuccinct (n. Слева, структура, данные); EncodeSuccinct (число справа, структура, данные);}
В строковой структуре есть только биты в конце, где - количество (внутренних) узлов; нам даже не нужно хранить его длину. Чтобы показать, что информация не теряется, мы можем преобразовать вывод обратно в исходное дерево следующим образом:
функция 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 = ⌊log 2 ( i +1) ⌋), а рассматриваемый узел не является самим корнем ( d > 0 ). Когда индекс ширины маскируется битом d - 1, значения битов 0 и 1 означает шаг влево или вправо соответственно. Процесс продолжается последовательной проверкой следующего бита справа, пока он не закончится. Самый правый бит указывает на окончательный переход от нужного родителя узла к самому узлу. Существует пространственно-временный компромисс между итерацией полного двоичного дерева таким образом по сравнению с каждым узлом, имеющим указатель / с на своего брата / с.
Смотрите также
- 2–3 дерева
- 2–3–4 дерева
- Дерево AA
- Анентафель
- Дерево AVL
- B-дерево
- Разделение двоичного пространства
- Дерево Хаффмана
- K-арное дерево
- Неравенство Крафт
- Оптимальное двоичное дерево поиска
- Случайное двоичное дерево
- Рекурсия (информатика)
- Красно-черное дерево
- Веревка (информатика)
- Самобалансирующееся двоичное дерево поиска
- Splay tree
- Номер Strahler
- Дерево примитивных пифагоровых троек # Альтернативные методы построения дерева
- Некорневое двоичное дерево
Рекомендации
Цитаты
- ^ Роуэн Гарнье; Джон Тейлор (2009). Дискретная математика: доказательства, структуры и приложения, третье издание . CRC Press. п. 620. ISBN 978-1-4398-1280-8.
- ^ Стивен С Скиена (2009). Руководство по разработке алгоритмов . Springer Science & Business Media. п. 77. ISBN 978-1-84800-070-4.
- ^ а б Кнут (1997). Искусство программирования, том 1, 3 / E . Pearson Education. п. 363. ISBN. 0-201-89683-4.
- ^ Иван Флорес (1971). Система компьютерного программирования / 360 . Прентис-Холл. п. 39.
- ^ Кеннет Розен (2011). Дискретная математика и ее приложения, 7-е издание . McGraw-Hill Science. п. 749. ISBN 978-0-07-338309-5.
- ^ Дэвид Р. Мазур (2010). Комбинаторика: экскурсия . Математическая ассоциация Америки. п. 246. ISBN. 978-0-88385-762-5.
- ^ а б "Двоичное дерево" , Энциклопедия математики , EMS Press , 2001 [1994] также в печати как Мишель Хазевинкель (1997). Энциклопедия математики. Дополнение I . Springer Science & Business Media. п. 124. ISBN 978-0-7923-4709-5.
- ^ Л. Р. Фулдс (1992). Приложения теории графов . Springer Science & Business Media. п. 32. ISBN 978-0-387-97599-3.
- ^ Дэвид Макинсон (2009). Наборы, логика и математика для вычислений . Springer Science & Business Media. п. 199. ISBN 978-1-84628-845-6.
- ^ Джонатан Л. Гросс (2007). Комбинаторные методы с компьютерными приложениями . CRC Press. п. 248. ISBN 978-1-58488-743-0.
- ^ а б Кеннет Розен (2011). Дискретная математика и ее приложения 7-е издание . McGraw-Hill Science. С. 352–353. ISBN 978-0-07-338309-5.
- ^ Те Чан Ху; Ман-так Шинг (2002). Комбинаторные алгоритмы . Courier Dover Publications. п. 162. ISBN. 978-0-486-41962-6.
- ^ Лих-Син Сюй; Ченг-Куан Линь (2008). Теория графов и взаимосвязанные сети . CRC Press. п. 66. ISBN 978-1-4200-4482-9.
- ^ J. Flum; М. Гроэ (2006). Параметризованная теория сложности . Springer. п. 245. ISBN 978-3-540-29953-0.
- ^ Тамассия, Майкл Т. Гудрич, Роберто (2011). Разработка алгоритмов: основы, анализ и примеры в Интернете (2-е изд.). Нью-Дели: Вили-Индия. п. 76. ISBN 978-81-265-0986-7.
- ^ «полное двоичное дерево» . NIST .
- ^ Ричард Стэнли, Перечислительная комбинаторика, том 2, стр. 36
- ^ а б «полное двоичное дерево» . NIST.
- ^ «почти полное двоичное дерево» . Архивировано из оригинала на 2016-03-04 . Проверено 11 декабря 2015 .
- ^ «почти полное двоичное дерево» (PDF) .
- ^ «идеальное двоичное дерево» . NIST .
- ^ Аарон М. Тененбаум и др. Структуры данных с использованием C, Прентис Холл, 1990 г. ISBN 0-13-199746-7
- ^ Пол Э. Блэк (редактор), запись о структуре данных в Словаре алгоритмов и структур данных . США Национальный институт стандартов и технологий . 15 декабря 2004 г. Онлайн-версия. Архивировано 21 декабря 2010 г. на Wayback Machine, доступ осуществлен 19 декабря 2010 г.
- ^ Пармар, Ананд К. (22 января 2020 г.). «Различные типы двоичного дерева с красочными иллюстрациями» . Средний . Проверено 24 января 2020 .
- ^ Мехта, Динеш; Сартадж Сахни (2004). Справочник по структурам данных и приложениям . Чепмен и Холл . ISBN 1-58488-435-5.
- ^ Д. Саманта (2004). Классические структуры данных . PHI Learning Pvt. Ltd. С. 264–265. ISBN 978-81-203-1874-8.
- ^ Майкл Л. Скотт (2009). Прагматика языка программирования (3-е изд.). Морган Кауфманн. п. 347. ISBN 978-0-08-092299-7.
- ^ Введение в алгоритмы . Кормен, Томас Х., Кормен, Томас Х. (2-е изд.). Кембридж, Массачусетс: MIT Press. 2001. с. 128. ISBN 0-262-03293-7. OCLC 46792720 .CS1 maint: другие ( ссылка )
- ^ а б Дунг X. Нгуен (2003). «Двоичная древовидная структура» . ris.edu . Проверено 28 декабря 2010 года .
Библиография
- Дональд Кнут . Искусство программирования, том 1. Фундаментальные алгоритмы , третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89683-4 . Раздел 2.3, особенно подразделы 2.3.1–2.3.2 (стр. 318–348).
Внешние ссылки
- запись двоичных деревьев в базе данных FindStat
- Доказательство двоичного дерева по индукции
- Сбалансированное двоичное дерево поиска в массиве Как создать восходящий список Анентафеля или сбалансированное двоичное дерево поиска в массиве
- Бинарные деревья и их реализация с примерами рабочего кода
- Реализация JavaScript двоичного дерева с исходным кодом