Поиск в бинарных деревьях


Содержание
Илон Маск рекомендует:  Insert cursor (blob)

Поиск в бинарных деревьях

В разделе 1 мы использовали двоичный поиск для поиска данных в массиве. Этот метод чрезвычайно эффективен, поскольку каждая итерация вдвое уменьшает число элементов, среди которых нам нужно продолжать поиск. Однако, поскольку данные хранятся в массиве, операции вставки и удаления элементов не столь эффективны. Двоичные деревья позволяют сохранить эффективность всех трех операций — если работа идет с «случайными» данными. В этом случае время поиска оценивается как O(lg n). Наихудший случай — когда вставляются упорядоченные данные. В этом случае оценка время поиска — O(n). Подробности вы найдете в работе Кормена [1990].

Илон Маск рекомендует:  Что такое код udm_crc32

Теория

Двоичное дерево — это дерево, у которого каждый узел имеет не более двух наследников. Пример бинарного дерева приведен на рис. 3.2. Предполагая, что k содержит значение, хранимое в данном узле, мы можем сказать, что бинарное дерево обладает следующим свойством: у всех узлов, расположенных слева от данного узла, значение соответствующего поля меньше, чем k, у всех узлов, расположенных справа от него, — больше. Вершину дерева называют его корнем, узлы, у которых отсутствуют оба наследника, называются листьями. Корень дерева на рис. 3.2 содержит 20, а листья — 4, 16, 37 и 43. Высота дерева — это длина наидлиннейшего из путей от корня к листьям. В нашем примере высота дерева равна 2.

Рис. 3.2: Двоичное дерево

Чтобы найти в дереве какое-то значение, мы стартуем из корня и движемся вниз. Например, для поиска числа 16, мы замечаем, что 16 7, и потому мы движемся вправо. Третья попытка успешна — мы находим элемент с ключом, равным 16.

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

Рис. 3.3: Несбалансированное бинарное дерево

Вставка и удаление

Чтобы лучше понять, как дерево становится несбалансированным, посмотрим на процесс вставки пристальнее. Чтобы вставить 18 в дерево на рис. 3.2 мы сначала должны найти это число. Поиск приводит нас в узел 16, где благополучно завершается. Поскольку 18 > 16, мы попросту добавляет узел 18 в качестве правого потомка узла 16 (рис. 3.4).

На этом примере хорошо видно, как возникает несбалансированность дерева. Если данные поступают в возрастающем порядке, каждый новый узел добавляется справа от последнего вставленного. Это приводит к одному длинному списку. Обратите внимание: чем более «случайны» поступающие данные, тем более сбалансированным получается дерево.

Удаления производятся примерно так же — необходимо только позаботиться о сохранении структуры дерева. Например, если из дерева на рис. 3.4 удаляется узел 20, его сначала нужно заменить на узел 37. Это даст дерево, изображенное на рис. 3.5. Рассуждения здесь примерно следующие. Нам нужно найти потомка узла 20, справа от которого расположены узлы с большими значениями. Таким образом, нам нужно выбрать узел с наименьшим значением, расположенный справа от узла 20. Чтобы найти его, нам и нужно сначала спуститься на шаг вправо (попадаем в узел 38), а затем на шаг влево (узел 37); эти двухшаговые спуски продолжаются, пока мы не придем в концевой узел, лист дерева.

Рис. 3.4: Бинарное дерево после добавления узла 18

Рис. 3.5: Бинарное дерево после удаления узла 20

Реализация

В реализации алгоритма на Си операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в дереве. Каждый узел Node содержит указатели left, right на левого и правого потомков, а также указатель parent на предка. Собственно данные хранятся в поле data. Адрес узла, являющегося корнем дерева хранится в укзателе root, значение которого в самом начале, естественно, NULL. Функция insertNode запрашивает память под новый узел и вставляет узел в дерево, т.е. устанавливает нужные значения нужных указателей. Функция deleteNode, напротив, удаляет узел из дерева (т.е. устанавливает нужные значения нужных указателей), а затем освобождает память, которую занимал узел. Функция findNode ищет в дереве узел, содержащий заданное значение.

Дерево

Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.

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

Способ представления бинарного дерева:

  • A — корень дерева
  • В — корень левого поддерева
  • С — корень правого поддерева

Корень дерева расположен на уровне с минимальным значением.

Узел D , который находится непосредственно под узлом B , называется потомком B . Если D находится на уровне i , то B – на уровне i-1 . Узел B называется предком D .

Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой .

Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.

Остальные элементы – внутренние узлы (узлы ветвления).

Число потомков внутреннего узла называется его степенью . Максимальная степень всех узлов есть степень дерева.

Число ветвей, которое нужно пройти от корня к узлу x , называется длиной пути к x . Корень имеет длину пути равную 0 ; узел на уровне i имеет длину пути равную i .

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

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

Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.

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

Способы обхода дерева

Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.

Существует три способа обхода дерева:

  • Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
  • Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
  • Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.
Реализация дерева

Узел дерева можно описать как структуру:

При этом обход дерева в префиксной форме будет иметь вид

Обход дерева в инфиксной форме будет иметь вид

Обход дерева в постфиксной форме будет иметь вид

Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

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

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

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

Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.

Бинарные деревья поиска

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

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

Бинарным деревом поисканазывается такое бинарное дерево, у которого для каждой вершиныAвсе значения вершин левого поддереваAне превышают значенияA, а все значения вершин правого поддереваAне меньше, чем значениеA.

Илон Маск рекомендует:  Краткое пособие по языку sql

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

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

Опишем структуры данных для представления таблицы в виде бинарного дерева.

left, right: Tree;

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

Var t: Tree;

X: KeyType;

Var found: Boolean

if t = nil then begin

else if t^.key x then

TreeSearch := TreeSearch(t^.left, x, found)

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

Если функция выполнит вставку новой вершины, то исходное дерево изменится, однако оно сохранит свойства дерева поиска.

Время работы функции определяется числом шагов спуска по дереву выполненных при поиске. Время выполнения вставки не зависит от размеров дерева, поэтому оно не повлияет на оценку в смысле O-большое.

Максимальное число шагов спуска ограничено высотой дерева поиска. Как связана высота hс числом вершин дереваn? Это зависит от распределения вершин в дереве.

Наиболее предпочтительным для поиска видом деревьев являются идеально сбалансированные деревья (ИС-деревья). Это такие бинарные деревья, у которых для каждой вершины количества вершин в ее левом и правом поддеревьях различаются не больше, чем на 1. Легко доказать, что длины всех ветвей ИС-дерева также различаются не более, чем на 1.

Примеры ИС-деревьев поиска с разным числом вершин показаны на рис. 4.1.

Рис. 4.1. Примеры идеально сбалансированных деревьев поиска

Нетрудно доказать, что ИС-дерево высоты hможет иметь от2 h–1 до2 h – 1вершин. Отсюда можно получить и обратную зависимость – оценку высоты для данного числа вершин:h log2n + 1. Получается, что время поиска по ИС-дереву имеет логарифмическую оценку:T(n) = O(log(n)), аналогично бинарному поиску в сортированном массиве.

Проблема заключается в том, что сбалансированность дерева обеспечить трудно. Предположим, что на вход программы, строящей бинарное дерево поиска с помощью функции TreeSearch, поступает монотонно возрастающая последовательность ключей. Нетрудно видеть, что в этом случае каждая новая вершина будет включаться в дерево как правый сын предыдущей вершины, а левых сыновей в этом дереве не будет вовсе. Результатом будет крайне несбалансированноевырожденноедерево, по сути представляющее собой линейный список. Для вырожденного дерева его высота равна числу вершин, а стало быть,T(n) = O(n).

С другой стороны, пусть нам удалось каким-то образом построить ИС-дерево из nвершин. Если затем в это дерево будет добавлено еще хотя бы 1-2 вершины, то его балансировка может быть нарушена и для ее восстановления придется заново строить все дерево, затратив на это время порядкаO(n).

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

Разумеется, вырожденное дерево – это заведомо худший случай. В среднем дело обстоит не так плохо. Доказано, что если вершины добавляются в случайном порядке, то математическое ожидание высоты получившегося дерева будет иметь логарифмическую оценку и лишь примерно на 40 % превысит высоту ИС-дерева с тем же количеством вершин.

Ситуация напоминает ту, которая характерна для алгоритма QuickSort: в среднем все очень хорошо, но не исключен и худший случай, когда все становится плохо.

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

Рис. 4.2. Удаление вершин из дерева поиска

На рис. 4.2, апоказано удаление вершиныA, не имеющей сыновей. Здесь проблем не возникает.

На рис. 4.2, биллюстрируется удаление вершиныB, имеющей одного сына. При этом у отца удаляемой вершины освобождается одна связь, к которой и присоединяется «осиротевший внук». Очевидно, что сортированность дерева поиска при этом сохраняется.

На рис. 4.2, впоказан самый сложный случай – удаление вершиныC, имеющей двух сыновей. Чтобы при этом не развалить дерево и сохранить его сортированность, поступают следующим образом. Для удаляемой вершины ищется ближайшая к ней слева вершина. Для этого нужно сначала перейти отCк ее левому сыну, а затем спускаться направо, пока не попадем в вершину, не имеющую правого сына. В данном примере это вершинаD. Далее следует поменять местами удаляемую вершинуCи ее левого соседаD(это можно сделать либо путем манипуляций указателями, либо просто обменяв записи таблицы, связанные с вершинами). На новом месте вершинаCимеет не более одного сына (ибо правого сына она не имеет), а потому может быть удалена, как в случаеаилиб. Легко видеть, что сортированность дерева не будет нарушена после этих операций.

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

Можно ли при работе с бинарными деревьями поиска гарантировать оценку T(n) = O(log(n))для поиска и вставки не только в среднем, но и в худшем случае? Ответ положительный. Однако для этого следует выбрать подходящий класс деревьев. Для произвольных бинарных деревьев операция вставки выполняется просто и быстро, но поиск может быть долгим в случае вырождения. ИС-деревья гарантируют быстрый поиск, но много времени уходит на поддержание баланса при вставке и удалении. Желательно найти какой-то «средний» тип деревьев, чтобы они были не намного хуже, чем идеально сбалансированные, но вставка выполнялась значительно быстрее.

Было предложено несколько подобных типов деревьев. Среди них АВЛ-деревья [1, 5], 2-3-деревья [3, 5], красно-черные деревья [4]. Мы рассмотрим только АВЛ-деревья, которые были названы в честь предложивших их советских математиков Г.М.Адельсона-Вельского и Е.М.Ландиса и которые до настоящего времени остаются одним из лучших средств решения задачи поиска со вставкой.

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

Легко видеть, что всякое ИС-дерево поиска является АВЛ-деревом. Обратное, вообще говоря, неверно.

На рис. 4.3показаны примеры самых худших (т.е. наиболее разбалансированных, «перекошенных») АВЛ-деревьев для различных значений высоты. Как видно из рисунка, даже в худшем случае АВЛ-деревья далеки от вырожденности. Это становится все более заметно при увеличении высоты. Можно доказать, что высота АВЛ-дерева превышает высоту ИС-дерева с тем же количеством вершин не более, чем на 45 %. Таким образом, логарифмическая зависимость высоты от числа вершин сохраняется даже в худшем случае.

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

Рис. 4.3. Наихудшие АВЛ-деревья разной высоты

Прежде всего, надо выяснить, каким образом вообще обнаруживается нарушение сбалансированности при вставке. Наиболее удобное решение – хранить в каждой вершине АВЛ-дерева дополнительное поле bal(баланс), которое может принимать одно из трех значений:

t^.bal = –1, если левое поддерево вершиныtвыше, чем правое;

t^.bal = 0, если оба поддерева одинаковы по высоте;

t^.bal = +1, если правое поддеревоtвыше, чем левое.

При выполнении вставки сначала происходит рекурсивный спуск по дереву, затем новая вершина добавляется как лист (и для нее, естественно, устанавливается начальное значение bal= 0), а затем, в процессе возврата вверх, для всех вершин соответствующей ветви дерева выполняется корректировка значений поляbal, если вставка новой вершины вызвала увеличение высоты левого или правого поддерева.

Пусть при возврате вверх после вставки выяснилось, что для некоторой вершины Cбаланс нарушен: левое поддеревоCтеперь оказалось на 2 единицы выше, чем правое (случай перекоса вправо рассматривается аналогично). При этом для вершин, лежащих нижеC, баланс остается в пределах нормы (от –1 до +1). В этой ситуации возможны два существенно разных случая, проиллюстрированных на рис.4.4.

Рис. 4.4. Нарушение баланса при вставке в АВЛ-дерево

Буквой Aобозначен левый сын вершиныC. Высота поддереваAмогла увеличиться либо при вставке в левое поддеревоA(случай 1), либо при вставке в правое поддерево (случай 2). Прямоугольники 1, 2, 3, 4 обозначают поддеревья произвольной сложности, а перечеркнутый квадрат – добавленную вершину. Во втором случае показаны два возможных положения добавленной вершины, одно из них – пунктиром. Можно доказать, что в случае 1 высоты поддеревьев 1, 2 и 3 равны одной и той же величинеh, а в случае 2 высоты поддеревьев 1 и 4 на единицу больше, чем 2 и 3.

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

Рис. 4.5. Восстановление баланса АВЛ-дерева

Такие преобразования АВЛ-дерева принято называть его поворотами.

Прежде всего заметим, что повороты не нарушают упорядоченность дерева поиска (например, в случае 1 и до поворота, и после него ключи в различных частях дерева упорядочены следующим образом: 1 A  2  C  3). При этом восстанавливается баланс вершин дерева.

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

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

Структуры даных. Бинарное дерево поиска

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

Что такое дерево? Дерево является связным графом ( да-да, про графы я еще напишу ) , который не содержит циклы, ребра графа не ориентированны и не взвешенны.

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

Допустим у нас есть следующее дерево:

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

Тоже самое с самым большим значением — оно всегда самое правое:

Поиск элемента тоже очень прост:

  1. Как обычно начинаем с корневого элемента.
  2. Проверяем или даный элемент — тот который нам нужен. Если да — возвращаем
  3. Если нет: смотрим или он больше даного, или меньше. Идем к соответствующему листу
  4. Если листов нет — элемента нет. Если есть — повторяем пункт 2.

Так же, Сейджвик в своем курсе на Coursera приводит пример поиска наименьшего / наибольшего элемента для заданого ключа, которые:

Наибольший = заданому ключу.

К примеру, в нашем дереве, наибольший ключ для 5 будет равен 4, а наименьший 6. Эти операции Сейджвик называет floor и ceil.

Итак, давайте приступим к написанию кода! Для начала, создадим сам объект узла:

Теперь забивка на самое дерево и корневой узел:

Добавим метод, который будем использовать для добавление узла в дерево:

Как видим в функции добавления, мы смотрим в куда нам добавить новый узел, в зависимости от величины нашей ноды. Метод count нужен для того чтобы определить ранг узла ( рангом называют высоту дерева или поддерева☺ ). Метод достаточно прост:

Теперь стоит реализовать метод поиска необходимого узла:

Метод реализован полностью по шагам, которые были описаны выше.

Методы получения минимального и максимального значения совершенно тривиальны:

Реализации floor и ceil методов:

Как видим в обоих этих методах — одинаковый подход. Как только мы находим элемент который больше/меньше нашего элемента — начинаем бегать по наследникам в противоположную сторону. Если элемент найден — возвращаем, если нет — то возвращаем данный узел.

Удаление же узла — не такая простая операция как кажется. Если подумать, у нас может быть целых три случая:

  1. Если мы удаляем узел у которого нет потомков, мы просто ссылку на него возвращаем как null.
  2. Если мы удаляем узел у которого всего лишь один наследник — то мы просто возвращаем ссылку на наследника, вместо того чтоб возвращать ссылку на себя
  3. Если у узла двое детей — то все становиться интереснее — какой наследник вернуть, чтоб наше бинарное дерево не перестало быть бинарным. В даном случае нам на помощь приходить Hibbard Delition ( не знаю как перевести ☺ ). Оно указывает, что если мы удаляем узел у которого больше одного ребенка, то его стоит просто заменить на минимальный узел справа, и удалить этот минимальный узел с предыдущего места. К примеру если мы в нашем дереве удалим допустим элемент 8, то по правилам удаления у нас должно получиться:

Что совсем не нарушает наше дерево☺Итак, для начала реализуем метод удаления минимального элемента:

По коду видно, что мы рекурсивно бегаем по всем левым листам, и как только находим самый левый лист у которого нет левого потомка, возвращаем правого потомка ( если нет — вернется null, что нам тоже подходит )

А теперь само удаление:

В следующих постах мы поговорим про трансформацию дерева в массив, балансировку и методы обхода.

Поиск элемента в худшем случае O(n)

Удаление элемента O(n)

Как обычно: исходники примеров вы можете найти тут.

Бинарное дерево — двоичное дерево поиска. Основные операции с бинарными деревьями (C#, Java)

Что такое бинарное дерево

Бинарное дерево представляет собой иерархическую структуру данных, в которой каждый узел имеет не более двух дочерних узлов. Как правило, первый называется родительским узлом или корнем дерева (root), а дочерние узлы называются левым и правым наследниками.

Бинарное дерево либо является пустым, либо состоит из данных и двух поддеревьев, каждое из которых может быть пустым. Каждое поддерево в свою очередь тоже является деревом. Узлы без наследников принято называть листьями.

Для такого дерева должны выполняться следующие условия:

  1. Левое и правое поддерево так же являются бинарными деревьями;
  2. У всех узлов левого поддерева произвольного узла x значения ключей данных меньше значения ключа данных самого узла x ;
  3. У всех узлов правого поддерева произвольного узла x значения ключей данных больше либо равны значению ключа данных самого узла x .

Основные операции с бинарным деревом

Основными операциями с бинарными деревьями являются добавление элемента в дерево, удаление элемента и поиск элемента в дереве. Сложность каждой из этих операций O(log\,n) в лучшем случае, и O(n) в худшем. Зависит от сбалансированности дерева.

Пример сбалансированного бинарного дерева (лучший случай):

Пример несбалансированного бинарного дерева (худший случай): Добавление элемента в дерево

При добавлении элемента x в дерево проверяем значение текущего узла.

  • Если значение добавляемого элемента x меньше значения текущего узла, спускаемся к левому поддереву. Если его не существует, то создаем его и присваиваем значение x . Если существует, то обозначим левое поддерево как текущий узел и повторим сначала.
  • Если значение добавляемого элемента x больше или равно значению текущего узла, спускаемся к правому поддереву. Если его не существует, то создаем его и присваиваем значение x . Если существует, то обозначим правое поддерево как текущий узел и повторим сначала.

Пример добавления элемента в двоичное дерево

Создадим бинарное дерево с корневым элементом 33 и добавим в него элементы в следующей последовательности: 5, 35, 1, 20, 99, 17, 18, 19, 31, 4. Получим бинарное дерево такого вида:

Поиск элемента в бинарном дереве

Поиск начинаем с родительского элемента. Допустим, мы ищем значение 18 (обозначим его за x ). Алгоритм поиска будет иметь следующий вид:

  1. x — спускаемся в левое поддерево;
  2. x>5 — спускаемся в правое поддерево;
  3. x — спускаемся в левое поддерево;
  4. x>17 — спускаемся в правое поддерево;
  5. x=18 — мы нашли элемент.

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

Удаление элемента из бинарного дерева

Удаление листьев

Если удаляемый элемент является листом, то просто удаляем у его родителя ссылку на этот элемент (например на значение 31). Удалим его.

Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева

После удаления 31 элементом, имеющим левое поддерево, но не имеющим правого поддерева является элемент 20. Удалим его из дерева:

  1. Указываем, что родителем элемента 17 теперь будет элемент 5.
  2. Указываем, что правым потомком элемента 5 теперь является элемент 17.

После удаления значений 31 и 20 дерево приобретает такой вид:

Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева

  1. Удалим элемент 17. Присвоим его правому поддереву в качестве родителя элемент 5.
  2. Элементу 5 укажем, что его правым поддеревом теперь является элемент 18.

Получим следующую картину:

Удаляем узел, имеющий поддеревья с обеих сторон

Первый случай

Правое поддерево не имеет потомка.

Чтобы иметь возможность рассмотреть этот случай, добавим элемент 34 в дерево: Удалим элемент 35. Для этого:

  1. Правому поддереву (99) присвоим в качестве родителя элемент 33;
  2. Ему же в качестве левого поддерева присваиваем элемент 34;
  3. Элементу 34 указываем нового родителя — 99;
  4. Родителю удаляемого элемента (33) указываем, что его правым поддерево теперь является элемент 99.

Получим такое дерево:

Второй случай

Правое поддерево имеет своих потомков.

Удаляем элемент 5. Первым потомком (одновременно самым левым — минимальным в его поддереве) элемента 5 является элемент 18:

  1. Элементу 18 в качестве левого узла присвоим элемент 1;
  2. Элементу 1 присвоим 18 как родителя;
  3. Элементу 33 (родителю удаляемого элемента) укажем в качестве левого дочернего узла элемент 18;
  4. Элементу 18 указываем в качестве родителя элемент 33 (родитель удаляемого элемента).

Дерево приобретает такой вид:

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

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

Существуют и другие механизмы удаления. Визуализировать свое дерево вы можете на ресурсе usfca.edu. Вы заметите, что алгоритм удаления там отличается от описанного выше.

Код класса дерева на Java в моем исполнении имеет следующий вид:

Поработать с классом можно следующим образом:

Получим такой вывод:

К слову, на Java такой код особого смысла писать нет, т.к. там существуют классы TreeSet и TreeMap, представляющие собой деревья.

На C# код класса бинарного дерева может иметь такой вид:

Код примерно такой же, только для C# он будет гораздо полезнее.

Часть 7. Бинарные поисковые деревья (BST)

Серия контента:

Этот контент является частью # из серии # статей: Работа со структурами данных в языках Си и Python

Этот контент является частью серии: Работа со структурами данных в языках Си и Python

Следите за выходом новых статей этой серии.

Эта статья посвящена одной из разновидностей двоичных деревьев: бинарным поисковым деревьям. Как обычно будут рассмотрены теоретические алгоритмы для выполнения различных операций: вставка и удаление узла, поиск максимума/минимума и практические реализации данных алгоритмов на языках Си и Python.

Бинарные поисковые деревья

Бинарные поисковые деревья (англ. binary search tree или сокращенно BST) — это разновидность двоичного дерева, обладающая следующими отличительными свойствами:

  1. для каждого узла X (если X не равен NULL) все узлы в его левом поддереве содержат значения, которые ВСЕГДА меньше значения узла X.
  2. все узлы в правом поддереве узла Х содержат значения, которые соответственно ВСЕГДА больше значения узла X.
  3. каждый узел в таком дереве является родителем для своих поддеревьев.

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

Результат вставки узлов в бинарное поисковое дерево может оказаться непредсказуемым. Если вставлять в такое дерево узлы, которые уже были предварительно отсортированы, то это приведет к вырождению дерева. На рисунке 1 показаны две одинаковые по содержанию реализации поискового дерева, но с различными корневыми узлами.

Рисунок 1. Два варианта представления бинарного поискового дерева

В листинге 1 приведено объявление структур для узла бинарного дерева и самого дерева на языке Си.

Листинг 1. Определение структур для представления дерева и его узлов

Структура, использующаяся для описания узла дерева, полностью совпадает со структурой, использующейся для описания связного списка. Используя эти две структуры можно подготовить функцию на языке Си для создания дерева (см. листинг 2).

Листинг 2. Функция для создания дерева

Вставка узла в бинарное поисковое дерево

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

Листинг 3. Функция для поиска узла в дереве

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

Листинг 4. Функция для вставки узла в бинарное поисковое дерево

Элемент, добавленный первым, автоматически становится корнем дерева. Функция может вернуть одно из 3-х значений: (при вставке произошла ошибка), 1 (узел успешно вставлен), 2 (такой элемент уже есть в дереве).

Удаление узла из бинарного поискового дерева

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

Рисунок 2. Три варианта удаления элемента из бинарного поискового дерева

В первом случае (вариант a) узел z имеет только левый дочерний узел, и при удалении он и будет заменен им. Во втором варианте (рисунок b) узел z заменяется узлом y.

В третьем варианте (рисунок с) корневой узел z заменяется узлом x, что приводит к дополнительным перестроениям в правом поддереве. Узел x становится преемником узла z, так как в левом поддереве узла z все узлы меньше 5, и преемника нужно искать в правом поддереве узла z.

Листинг 5. Функция для удаления узла из бинарного поискового дерева

Проход по дереву

Для прохода по дереву можно использовать рекурсию, так как любое двоичное дерево — это рекурсивная структура. Функции, приведенные в листинге 6, могут распечатать дерево, начиная с любого узла: сначала печатается левое поддерево, потом правое.

Листинг 6. Функции для вывода содержимого дерева

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

Листинг 8. Нерекурсивная реализация обхода дерева

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

Удаление дерева

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

Листинг 9. Функции для удаления дерева

Нахождение минимума и максимума в бинарном поисковом дереве

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

Листинг 10. Функции для поиска минимального и максимальных значений

Определение типа двоичного дерева

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

Листинг 11. Определение типа двоичного дерева

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

В файле sources.zip, прикрепленном к данной статье, находятся две программы, в которых используются описанные выше алгоритмы для обработки бинарного поискового дерева. В файле bst_operations.с находится реализация на языке Си, а файл bst_operations.py содержит реализацию на языке Python.

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

Заключение

В данной статье были рассмотрены основные алгоритмы, использующиеся для работы с одной из самых популярных структур данных – бинарным поисковым деревом. Кроме теоретических описаний в статье были представлены и практические реализации данных алгоритмов на языке программирования Си. Для лучшего усвоения материала читателю предлагается самостоятельно разработать реализацию этих алгоритмов на языке Python и решить следующие задачи:

  1. если вставить в бинарное поисковое дерево числа в диапазоне от 1 до 64 в порядке возрастания таким образом, что сначала вставляются нечетные числа, потом четные, то какова будет высота этого дерева?
  2. если сначала вставить 3 числа: 32, 16, 48, а потом все остальные в прежнем порядке, то какова будет высота этого дерева?

Бинарное дерево поиска — Binary search tree

Бинарное дерево поиска
Тип дерево
Изобрел 1960
Изобретенный PF Windley, AD Бут , AJT Колин , и TN Hibbard
Временная сложность в большой нотации O
Алгоритм Средний Худший случай
Космос О ( п ) О ( п )
Поиск O (журнал N ) О ( п )
Вставить O (журнал N ) О ( п )
удалять O (журнал N ) О ( п )

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

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

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

содержание

Определение

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

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

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

  • При вставке или поиске элемента в бинарном дереве поиска, ключ каждого посетил узел должен сравниваться с ключом элемента должен быть вставлен или найден.
  • Форма двоичного дерева поиска целиком и полностью зависит от порядка вставок и удалений, и может вырождаться.
  • После долгой перемешаны последовательностей случайных вставки и удаления, ожидаемая высота дерева приближается к квадратному корню из числа ключей, √ п , которая растет гораздо быстрее , чем лог — н .
  • Там было много исследований , чтобы предотвратить дегенерацию дерева , в результате худшего случая временной сложности O ( п ) (подробнее смотрите раздел Тип ).

соотношение Порядок

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

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

операции

Бинарные деревья поиска поддерживают три основные операции: введение элементов, удаление элементов и поиск (проверка, присутствует ли ключ).

поиск

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

Мы начнем с изучения корневого узла . Если дерево нулевое , ключ мы ищем не существует в дереве. В противном случае, если ключ равен у корня, поиск будет успешным , и мы возвращаем узел. Если ключ меньше , чем у корня, мы ищем левое поддерево. Точно так же, если ключ больше , чем у корня, мы ищем правое поддерево. Этот процесс повторяется до тех пор не будет найден ключ или оставшееся поддерево нуля . Если искомый ключ не найден после того, как нулевое поддерево будет достигнуто, то ключ не присутствует в дереве. Это легко выражается в виде рекурсивного алгоритма (реализован в Python ):

Тот же алгоритм может быть реализован итеративно:

Эти два примера опирается на отношении порядка, являющееся общий порядок.

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

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

вставка

Вставка начинается как начнется поиск; если ключ не равен корень, мы ищем левый или правые поддерева, как и раньше. В конце концов, мы достигнем внешнего узел и добавить новый ключ-значение пару (здесь закодированную как запись «newNode») в качестве правого или левого ребенка, в зависимости от ключа узла. Другими словами, мы рассматриваем корень и рекурсивно вставить новый узел в левой поддерева, если его ключ меньше, чем у корня, или правом поддереве, если его ключ больше или равен корню.

Вот как типичные двоичные вставки дерева поиска может быть выполнены в виде двоичного дерева в C ++ :

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

Часть , которая перестраивается использует O (журнал п ) пространство в среднем случае и O ( п ) в худшем случае.

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

Другой способ объяснить вставку, что для того, чтобы вставить новый узел в дереве, его ключ первый по сравнению с корнем. Если его ключ меньше, чем корень, он сравнивается с ключом левого ребенка в суперпользователе. Если его ключ больше, он сравнивается с правом ребенка на суперпользователя. Этот процесс продолжается, пока новый узел не сравнивается с листовым узлом, а затем добавляется в качестве права этого узла или оставить ребенка в зависимости от его ключа: если ключ меньше ключа от листа, то он вставляется как коки оставил ребенок, в противном случае, как право ребенок коки.

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

делеция

При удалении узла из двоичного поиска дерева является обязательным для поддержания последовательности в порядка узлов. Есть много возможностей сделать это. Однако следующий метод , который был предложен Т. Hibbard в 1962 году гарантий того, что высота субъекта поддерев изменяется более чем на единицу. Есть три возможных случая:

  • Удаление узла без детей: просто удалить узел из дерева.
  • Удаление узла с одним ребенком: удалить узел и заменить его своим ребенком.
  • Удаление узла с двумя детьми: вызвать узел будет удален D . Не удалять D . Вместо этого, выбрать либо его в заказ предшественника узла или его упорядоченную узел преемника в качестве замены узла Е (с. Рисунок). Скопируйте значения пользовательских Е к D . Если Е не есть ребенок просто удалить E из предыдущего родителя G . Если Е есть ребенок, скажем , F , это право ребенка. Заменить Е с F на E родителя «s.

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

Грубо говоря, узлы с детьми труднее удалить. Как и во всех бинарных деревах, в заказе преемник узла является самым левым ребенком своего правого поддерева, и в-порядка предшественник Узла является самым правым ребенком левого поддерева в. В любом случае, этот узел будет иметь только один или нет ребенка вообще. Удалите его по одному из двух простых случаев выше.

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

Анализ выполнения: Несмотря на то, что эта операция не всегда обхода дерева вниз к листу, это всегда возможность; Таким образом, в самом худшем случае это требует времени, пропорциональной высоту дерева. Она не требует даже больше, когда узел имеет двух детей, так как он все еще следует один путь и не посетить любой узел дважды.

пересечение

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

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

Прослеживание требует O ( п ) времени, так как он должен посетить каждый узел. Этот алгоритм также О ( п ) , так что асимптотически оптимальным .

Traversal также может быть реализован итеративно . Для некоторых приложений, например , более равного поиска, приближенный поиск, операции для один шаг (итеративный) обход может быть очень полезным. Это, конечно, реализовано без конструкции обратного вызова и принимает O (1) в среднем и O (журнал N ) в худшем случае.

верификация

Иногда у нас уже есть бинарное дерево, и мы должны определить, является ли это BST. Эта проблема имеет простое рекурсивное решение.

BST Свойство каждый узел на правом поддереве должен быть больше , чем текущий узел и каждый узел на левом поддереве должен быть меньше , чем текущий узел-это ключ к выяснению дерева , является ли BST или нет. Жадный алгоритм -Просто траверс дерева, на каждом узле проверки содержит ли узел значение больше , чем значение в левом ребенка и меньше , чем значение на правом ребенка-не работает для всех случаев. Рассмотрим следующее дерево:

В приведенном выше дереве, каждый узел удовлетворяет условие, что узел содержит значение больше, чем его левого ребенок и меньше, чем его право удержания ребенка, и все же это не БСТ: значение 5 находится на праве поддерева узла, содержащий 20 , нарушение собственности BST.

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

Таким образом, условие, которое мы должны проверить на каждом узле:

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

Рекурсивное решение в C ++ можно объяснить далее:

node->key+1 и node->key-1 сделаны , чтобы разрешить только отдельные элементы в BST.

Если мы хотим , чтобы одни и те же элементы также присутствуют, то мы можем использовать только node->key в обоих местах.

Первоначальный вызов этой функции может быть что-то вроде этого:

По существу, мы продолжаем создавать допустимый диапазон (начиная с [MIN_VALUE, max_value]) и продолжать сокращение его вниз для каждого узла, как мы идем вниз рекурсивно.

Как указано в разделе #Traversal , в-порядке обхода двоичного поиска дерева возвращает узлы отсортирован. Таким образом , нам нужно только сохранить последний посещаемый узел при обходе дерева и проверьте, меньше ли его ключ (или меньше / равно, если дубликаты будут разрешены в дереве) по сравнению с текущим ключом.

Примеры применения

Сортировать

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

Время наихудший случай build_binary_tree является O ( N 2 ) -если вы кормите его упорядоченный список значений, это цепочки их в связанный список с левой не поддеревьев. Так , например, build_binary_tree([1, 2, 3, 4, 5]) дает дерево (1 (2 (3 (4 (5))))) .

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

операции очередей приоритета

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

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

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

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

сравнение производительности

DA Heger (2004) представил сравнение производительности бинарных деревьев поиска. Декартово дерево было установлено, что лучший средний уровень производительности, в то время как красно-черное дерево было установлено, что наименьшее количество изменений производительности.

Оптимальные бинарные деревья поиска

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

Даже если у нас есть только оценки затрат на поиск, такая система может значительно ускорить просмотр на среднем. Например, если у вас есть BST английских слов , используемых в орфографический , вы можете сбалансировать дерево , основанное на частоте слов в текстовых корпусов , помещая слова , как возле корня и слова , как agerasia вблизи листьев. Такое дерево можно сравнить с деревьев Хаффмана , которые аналогичным образом стремятся поместить часто используемые элементы вблизи корня для получения плотной кодирования информации; Однако Хаффман дерева хранить элементы данных только в листах, и эти элементы не должны быть упорядочены.

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

Декоративные деревья являются Хаффмана деревья с дополнительным ограничением на порядок, или, что то же самое, деревья поиска с изменением , что все элементы хранятся в листьях. Существуют более быстрые алгоритмы для оптимальных алфавитных бинарных деревьев (OABTs).

Разбираемся с бинарным деревом на C#

Приветствую всех, сегодня рассмотрим алгоритм построения, поиска, удаления, и обхода двоичного дерева.

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

Двоичное дерево поиска (binary search tree, BST) — это двоичное дерево, для которого выполняются следующие условия:

  • Оба поддерева — левое и правое, являются двоичными деревьями поиска.
  • У всех узлов левого поддерева произвольного узла «A» значения ключей меньше, нежели значение ключа самого узла «A».
  • В то время, как у всех узлов правого поддерева того же узла «A» значения ключей не меньше, нежели значение ключа узла «A».
  • Очевидно, данные в каждом узле должны обладать ключами, для которых определена операция сравнения.

Двоичное дерево поиска можно определить так:

  • Каждое новое поддерево (левое и правое) являются двоичными деревьями поиска.
  • У всех узлов левого поддерева значения ключей меньше, чем значение ключа элемента родителя.
  • У всех узлов правого поддерева значения ключей не меньше, чем значения ключа родительского узла.

Основным преимуществом двоичного дерева поиска перед другими структурами данных является высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки.

Поиск по бинарному дереву. Эффективность поиска по бинарному дереву.

Вначале рассмотрим просто поиск по бинарному дереву.

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

В этом случае время поиска будет такое же, как и в однонаправленном списке, т.е. придется перебирать n/2 элементов.

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

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

Поиск элемента в сбалансированном дереве называется бинарным поиском по дереву. Такое дерево называют деревом бинарного поиска.

При бинарном поиске по дереву перебирается не больше log2N элементов. Другими словами, эффективность бинарного поиска по дереву имеет порядок O(log2N).

Суть поиска заключается в следующем. Анализируем вершину очередного поддерева. Если ключ меньше информационного поля вершины, то анализируем левое поддерево, больше — правое.

Алгоритм поиска по бинарному дереву

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

Бинарное дерево (binary tree) – это структура данных, которая состоит из узлов, при этом каждый узел может иметь не более двух дочерних. Первый узел называется корневым или родительским, а дочерние – правым и левым наследником(потомком).

Бинарное дерево поиска

Двоичное дерево поиска (binary search tree) – это бинарное дерево, которое соответствует следующим условиям:

  • Дочерние узлы являются двоичными деревьями поиска;
  • Для произвольного узла:
    • Все значения левого поддерева, меньше значения родительского узла;
    • Все значения правого поддерева, больше значения родительского узла.

Класс для описания узла

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

Класс бинарное дерево

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

Добавление данных

Первый метод, который мы реализуем, будет добавлять новый узел в дерево:

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

  • Значения совпадают, то значение узла остается прежним;
  • Новое значение меньше текущего – вставляем в левую ветку дерева;
  • Новое значение больше текущего – вставляем в правую ветку дерева.

Для упрощения непосредственного добавления данных, создадим перегрузку метода:

Поиск узла дерева по значению

Напишем рекурсивный метод для поиска узла по его значению:

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

Удаление узла бинарного дерева

Поскольку в метод для удаления, необходимо передавать экземпляр класса, то для удобства сделаем перегрузку для поиска и удаления:

Вывод бинарного дерева на экран

Напишем рекурсивный метод для вывода дерева в экран консоли:

Программа для работы с бинарным деревом поиска

Напишем программу для работы с двоичным деревом, для простоты будем использовать целочисленный тип данных:

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL