Бинарное дерево что такое


B-tree / Хабр

Введение

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

Основные операции в деревьях выполняются за время пропорциональное его высоте. Сбалансированные деревья минимизируют свою высоту (к примеру, высота бинарного сбалансированного дерева с n узлами равна log n). Большинство знакомо с такими сбалансированными деревьями, как «красно-черное дерево», «AVL-дерево», «Декартово дерево», поэтому не будем углубляться.

В чем же проблема этих стандартных деревьев поиска? Рассмотрим огромную базу данных, представленную в виде одного из упомянутых деревьев. Очевидно, что мы не можем хранить всё это дерево в оперативной памяти => в ней храним лишь часть информации, остальное же хранится на стороннем носителе (допустим, на жестком диске, скорость доступа к которому гораздо медленнее). Такие деревья как красно-черное или Декартово будут требовать от нас log n обращений к стороннему носителю. При больших n это очень много. Как раз эту проблему и призваны решить B-деревья!

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

Структура

При построении B-дерева применяется фактор t, который называется минимальной степенью. Каждый узел, кроме корневого, должен иметь, как минимум t – 1, и не более 2t – 1 ключей. Обозначается n[x] – количество ключей в узле x.

Ключи в узле хранятся в неубывающем порядке. Если x не является листом, то он имеет n[x] + 1 детей. Если занумеровать ключи в узле x, как k[i], а детей c[i], то для любого ключа в поддереве с корнем c[i] (пусть k1), выполняется следующее неравенство – k[i-1] ≤k1≤k[i] (для c[0]: k[i-1] = -∞, а для c[n[x]]: k[i] = +∞). Таким образом, ключи узла задают диапазон для ключей их детей.

Все листья B-дерева должны быть расположены на одной высоте, которая и является высотой дерева. Высота B-дерева с n ≥ 1 узлами и минимальной степенью t ≥ 2 не превышает logt(n+1). Это очень важное утверждение (почему – мы поймем чуть позже)!

h ≤ logt((n+1)/2) — логарифм по основанию t.

Операции, выполнимые с B-деревом

Как упоминалось выше, в B-дереве выполняются все стандартные операции по поиску, вставке, удалению и т.д.
Поиск

Поиск в B-дереве очень схож с поиском в бинарном дереве, только здесь мы должны сделать выбор пути к потомку не из 2 вариантов, а из нескольких. В остальном — никаких отличий. На рисунке ниже показан поиск ключа 27. Поясним иллюстрацию (и соответственно стандартный алгоритм поиска):

Операция поиска выполняется за время O(t logt n), где t – минимальная степень. Важно здесь, что дисковых операций мы совершаем всего лишь O(logt n)!

Добавление

В отличие от поиска, операция добавления существенно сложнее, чем в бинарном дереве, так как просто создать новый лист и вставить туда ключ нельзя, поскольку будут нарушаться свойства B-дерева. Также вставить ключ в уже заполненный лист невозможно => необходима операция разбиения узла на 2. Если лист был заполнен, то в нем находилось 2t-1 ключей => разбиваем на 2 по t-1, а средний элемент (для которого t-1 первых ключей меньше его, а t-1 последних больше) перемещается в родительский узел. Соответственно, если родительский узел также был заполнен – то нам опять приходится разбивать. И так далее до корня (если разбивается корень – то появляется новый корень и глубина дерева увеличивается). Как и в случае обычных бинарных деревьев, вставка осуществляется за один проход от корня к листу. На каждой итерации (в поисках позиции для нового ключа – от корня к листу) мы разбиваем все заполненные узлы, через которые проходим (в том числе лист). Таким образом, если в результате для вставки потребуется разбить какой-то узел – мы уверены в том, что его родитель не заполнен!

На рисунке ниже проиллюстрировано то же дерево, что и в поиске (t=3). Только теперь добавляем ключ «15». В поисках позиции для нового ключа мы натыкаемся на заполненный узел (7, 9, 11, 13, 16). Следуя алгоритму, разбиваем его – при этом «11» переходит в родительский узел, а исходный разбивается на 2. Далее ключ «15» вставляется во второй «отколовшийся» узел. Все свойства B-дерева сохраняются!

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

Удаление

Удаление ключа из B-дерева еще более громоздкий и сложный процесс, чем вставка. Это связано с тем, что удаление из внутреннего узла требует перестройки дерева в целом. Аналогично вставке необходимо проверять, что мы сохраняем свойства B-дерева, только в данном случае нужно отслеживать, когда ключей t-1 (то есть, если из этого узла удалить ключ – то узел не сможет существовать). Рассмотрим алгоритм удаления:
1)Если удаление происходит из листа, то необходимо проверить, сколько ключей находится в нем. Если больше t-1, то просто удаляем и больше ничего делать не нужно. Иначе, если существует соседний лист (находящийся рядом с ним и имеющий такого же родителя), который содержит больше t-1 ключа, то выберем ключ из этого соседа, который является разделителем между оставшимися ключами узла-соседа и исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Пусть это ключ k1. Выберем ключ k2 из узла-родителя, который является разделителем исходного узла и его соседа, который мы выбрали ранее. Удалим из исходного узла нужный ключ (который необходимо было удалить), спустим k2 в этот узел, а вместо k2 в узле-родителе поставим k1. Чтобы было понятнее ниже представлен рисунок (рис.1), где удаляется ключ «9». Если же все соседи нашего узла имеют по t-1 ключу. То мы объединяем его с каким-либо соседом, удаляем нужный ключ. И тот ключ из узла-родителя, который был разделителем для этих двух «бывших» соседей, переместим в наш новообразовавшийся узел (очевидно, он будет в нем медианой).
Рис. 1.

2)Теперь рассмотрим удаление из внутреннего узла x ключа k. Если дочерний узел, предшествующий ключу k содержит больше t-1 ключа, то находим k1 – предшественника k в поддереве этого узла. Удаляем его (рекурсивно запускаем наш алгоритм). Заменяем k в исходном узле на k1. Проделываем аналогичную работу, если дочерний узел, следующий за ключом k, имеет больше t-1 ключа. Если оба (следующий и предшествующий дочерние узлы) имеют по t-1 ключу, то объединяем этих детей, переносим в них k, а далее удаляем k из нового узла (рекурсивно запускаем наш алгоритм). Если сливаются 2 последних потомка корня – то они становятся корнем, а предыдущий корень освобождается. Ниже представлен рисунок (рис.2), где из корня удаляется «11» (случай, когда у следующего узла больше t-1 ребенка).
Рис.2.

Операция удаления происходит за такое же время, что и вставка O(t logt n). Да и дисковых операций требуется всего лишь O(h), где h – высота дерева.

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

Базы Данных

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

Очевидно, увеличивая t (минимальную степень), мы увеличиваем ветвление нашего дерева, а следовательно уменьшаем высоту! Какое же t выбрать? — Выбираем согласно размеру оперативной памяти, доступной нам (т.е. сколько ключей мы можем единовременно просматривать). Обычно это число находится в пределах от 50 до 2000. Разберёмся, что же дает нам ветвистость дерева на стандартном примере, который используется во всех статьях про B-tree. Пусть у нас есть миллиард ключей, и t=1001. Тогда нам потребуется всего лишь 3 дисковые операции для поиска любого ключа! При этом учитываем, что корень мы можем хранить постоянно. Теперь видно, на сколько это мало!

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

Соответственно, мы имеем минимальную нагрузку на сервер, и при этом малое время ожидания. Эти и другие описанные преимущества позволили B-деревьям стать основой для индексов, базирующихся на деревьях в СУБД.

Upd: визуализатор

Литература

«Алгоритмы. Построение и анализ» Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн (второе издание)
«Искусство программирование. Сортировка и поиск» Дональд Кнут.

обзор сбалансированных деревьев / Хабр

Первая статья цикла

Интро


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

Красно-черное дерево


Другие названия: Red-black tree, RB tree.
В этой структуре баланс достигается за счет поддержания раскраски вершин в два цвета (красный и черный, как видно из названия :), подчиняющейся следующим правилам:
  1. Красная вершина не может быть сыном красной вершины
  2. Черная глубина любого листа одинакова (черной глубиной называют количество черных вершин на пути из корня)
  3. Корень дерева черный

Здесь мы несколько меняем определение листа, и называем так специальные null-вершины, которые замещают отсутствующих сыновей. Будем считать такие вершины черными.

Пример:

Давайте посмотрим, какой может быть максимальная глубина корректного красно-черного дерева с n вершинами.
Возьмем самый глубокий лист. Пусть он находится на глубине h. Из-за правила 1, как минимум половина вершин на пути из корня будет черными, то есть черная высота дерева будет не меньше h/2. Можно показать, что в таком дереве будет не менее 2^(h/2)-1 черных вершин (так как у каждой черной вершины с черной глубиной k, если она не лист, должно быть как минимум два потомка с черной глубиной k+1). Тогда 2^(h/2)-1 <= n или h <= 2*log2(n+1).

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

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

Красно-черные деревья широко используются — реализация set/map в стандартных библиотеках, различные применения в ядре Linux (для организации очередей запросов, в ext3 etc.), вероятно во многих других системах для аналогичных нужд.

Красно-черные деревья тесно связаны с B-деревьями. Можно сказать, что они идентичны B-деревьям порядка 4 (или 2-3-4 деревьям). Более подробно об этом можно прочитать в статье на википедии или в книге «Алгоритмы: построение и анализ», упомянутой в прошлой статье.

Статья в википедии
Статья в английской википедии (с описанием операций)
визуализатор красно-черных деревьев

AA-дерево


Модификация красно-черного дерева, в которой накладывается дополнительное ограничение: красная вершина может быть только правым сыном. Если красно-черное дерово изоморфно 2-3-4 дереву, то AA-дерево изоморфно 2-3 дереву.

Из-за дополнительного ограничения операции реализуются проще чем у красно-черного дерева (за счет уменьшения количества разбираемых случаев). Оценка на высоту деревьев остается прежней, 2*log2(n). Эффективность по времени у них примерно одинаковая, но так как в реализации вместо цвета обычно хранят другую характеристику («уровень» вершины), overhead по памяти достигает байта.

Статья в английской википедии

АВЛ-дерево


Названо так по фамилиям придумавших его советских математиков: Г.М. Адельсон-Вельского и Е.М. Ландиса.

Накладывает на дерево следующее ограничение: у любой вершины высоты левого и правого поддеревьев должны отличаться не более чем на 1. Легко доказать по индукции, что дерево с высотой h должно содержать как минимум F_h вершин, где F_i — i-ое число Фибоначчи. Так как F_i ~ phi^n (phi=(sqrt(5)+1)/2 — золотое сечение), высота дерева с n вершинами не может превысить log2(n)/log2(phi) ~ 1.44*log2(n)

Реализация, как и у красно-черного дерева, основана на разборе случаев и достаточно сложна для понимания (хотя имхо проще красно-черного) и имеет сложность O(log(n)) на все основные операции. Для работы необходимо хранить в каждой вершине разницу между высотами левого и правого поддеревьев. Так как она не превосходит 1, достаточно использовать 2 бита на вершину.

Подробное описание можно найти в книге Н. Вирта «Алгоритмы + структуры данных = программы» или в книге А. Шеня «Программирование: теоремы и задачи»

Статья в википедии

Декартово дерево


Другие названия: Cartesian tree, treap (tree+heap), дуча (дерево+куча).

Если рисовать дерево на плоскости, ключ будет соответствовать x-координате вершины (за счет упорядоченности). Тогда можно ввести и y-координату (назавем ее высотой), которая будет обладать следующим свойством: высота вершины больше высоты детей (такое же свойство имеют значения в другой структуре данных на основе двоичных деревьев — куче (heap). Отсюда второй вариант названия той структуры)

Оказывается, если высоты выбирать случайным образом, высота дерева, удовлетворяющего свойству кучи наиболее вероятно будет O(log(n)). Численные эксперименты показывают, что высота получается примерно 3*log(n).

Реализация операций проста и логична, за счет этого структура очень любима в спортивном программировании). По результатам тестирования, признана наиболее эффективной по времени (среди красно-черных, AA и АВЛ — деревьев, а так же skip-list'ов (структура, не являющаяся двоичным деревом, но с аналогичной областью применения) и radix-деревьев). К сожалению, обладает достаточно большим overheadом по памяти (2-4 байта на вершину, на хранение высоты) и неприминима там, где требуется гарантированная производительность (например в ядре ОС).

Splay-дерево


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

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

Зная магию операции splay, эти деревья реализуются не легко, а очень легко, поэтому они тоже очень популярны в ACM ICPC, Topcoder etc.

Ясно, что в таком дереве нельзя гарантировать сложность операций O(log(n)) (вдруг нас попросят найти глубоко залегшую вершину в несбалансированном на данный момент дереве?). Вместо этого, гарантирается амортизированная сложность операции O(log(n)), то есть любая последовательность из m операций с деревом размера n работает за O((n+m)*log(n)). Более того, splay-дерево обладает некоторыми магическими свойствами, за счет которого оно на практике может оказаться намного эффективнее остальных вариантов. Например, вершины, к которым обращались недавно, оказываются ближе к корню и доступ к ним ускоряется. Более того, доказано что если вероятности обращения к элементам фиксированы, то splay-дерево будет работать асимптотически не медленней любой другой реализации бинарных деревьев. Еще одно преимущество в том, что отсутствует overhead по памяти, так как не нужно хранить никакой дополнительной информации.

В отличие от других вариантов, операция поиска в дереве модифицирует само дерево, поэтому в случае равномерного обращения к элементам splay-дерево будет работать медленней. Однако на практике оно часто дает ощутимый прирост производительности. Тесты это подтверждают — в тестах, полученных на основе Firefox'а, VMWare и Squid'а, splay-дерево показывает прирост производительности в 1.5-2 раза по сравнению с красно-черными и АВЛ- деревьями. В тоже время, на синтетических тестах splay-деревья работают в 1.5 раза медленней. К сожалению, из-за отсутствия гарантий на производительность отдельных операций, splay-деревья неприминимы в realtime-системах (например в ядре ОС, garbage-collector'ах), а так же в библиотеках общего назначения.

Статья в английской википедии
Оригинальная статья Р. Тарьяна и Д. Слейтора

Scapegoat-дерево


Это дерево похоже на предыдущее тем, что у него отсутствует overhead по памяти. Однако это дерево является в полной мере сбалансированным. Более того, коэффициент 0

Коэффициент жесткости сильно влияет на баланс производительности: чем «жестче» дерево, тем меньше у него будет высота и тем быстрее будет работать поиск, но тем сложнее будет поддерживать порядок в операциях модификации. Например, так как АВЛ-дерево «жестче» красно-черного, поиск в нем работает быстрее, а модификация медленней. Если же пользоваться scapegoat-деревом, баланс между этими операциями можно выбирать в зависимости от специфики применения дерева.

Статья в английской википедии

Еще пара слов


Два последних дерева сильно отличаются от своих конкурентов. Например, только они могут использоваться в эффективной реализации структуры данных link/cut tree, использующейся в основе наиболее быстрого известного алгоритма поиска потока в графе. С другой стороны из-за их амортизационной сути они не могут использоваться во многих алгоритмах, в частности для построения ropes. Свойства этих деревьев, особенно splay-дерева, в настоящее время активно изучаются теоретиками.

Кроме сбалансированных деревьев, можно использовать следующий трюк: реализовать обычное бинарное дерево и в процессе работы периодически делать ребалансировку. Для этого существует несколько алгоритмов, например DSW algorithm, работающий за O(n)

В следующей серии


Я расскажу более подробно про декартовы деревья и их реализацию

Общие ссылки


визуализатор деревьев (умеет визуализировать все деревья из обзора)

НОУ ИНТУИТ | Лекция | Бинарные деревья

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

Представление бинарных деревьев

Бинарное дерево определяется рекурсивно как имеющее левое поддерево, корень и правое поддерево. Левое и правое поддеревья сами являются бинарными деревьями. На рис. 8.1 показан пример бинарного дерева.


Рис. 8.1. Бинарное дерево.

Такие деревья можно представить термами вида

бд(Лд, К, Пд),

где Лд — левое поддерево, К — корень, а Пд — правое поддерево. Для обозначения пустого бинарного дерева будем использовать атом nil. Бинарное дерево на рис.8.1 имеет левое поддерево бд(бд(nil, d, nil), b, бд(nil, е, nil)) правое поддерево бд(nil,с, nil) и записывается целиком как бд(бд(бд(nil,d, nil), b, бд(nil,е, nil)), а, бд(nil, с, nil)).

Представление множеств с помощью бинарных деревьев

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

Однако для множеств, состоящих из большого числа элементов, списковые целевые утверждения становятся неэффективными. Рассмотрим, например, как целевое утверждение "принадлежит" (см. "Язык программирования Пролог" ) позволяет моделировать принадлежность множеству. Пусть L — список, описывающий множество из первых 1024 натуральных чисел. Тогда при ответе на запрос

?- принадлежит(3000, b).

Прологу придется проверить все 1024 числа, прежде чем заключить, что такого числа нет:

нет

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


Рис. 8.2. Упорядоченное бинарное дерево

Обратите внимание, что упорядочение приводит не к единственному варианту представления множества с помощью дерева. Например, на рис. 8.3 изображено то же множество, что и на рис. 8.2

Будем называть линейным представление такого вида, как на рис. 8.3, и сбалансированным — такое, как на рис. 8.2


Рис. 8.3. Линейное представление

Моделирование принадлежности множеству. Имея множество, описанное бинарным деревом, мы можем моделировать принадлежность множеству с помощью целевого утверждения принадлежит_дереву. При этом используется оператор @<, выражающий отношение "меньше, чем", и оператор @>, выражающий отношение "больше, чем".

/* Граничное условие: Х принадлежит /* дереву, если Х является корнем. принадлежит_дереву(Х, бд(Лд, Х, Пд)), /* Рекурсивные условия /* Х принадлежит дереву, если Х больше /* значении корня и находится в правом /* поддереве: принадлежит_дереву(Х, бд(Лд, У, Пд)) :- [email protected], припадлежит_дереву(Х, Пд). /* Х принадлежит дереву, если Х меньше /* значения корня и находится в левом /* поддереве: принадлежит_дереву(Х, бд(Лд ,У ,Пд)) :[email protected], принадлежит_дереву(Х, Лд).

Если множество из первых 1024 чисел описать с помощью сбалансированного бинарного дерева Т, то при ответе на запрос

?- принадлежит_дереву(3000, Т).

Пролог сравнит число 3000 не более чем с 11 элементами множества. прежде чем ответит:

нет

Конечно, если Т имеет линейное представление, то потребуется сравнение 3000 с 1024 элементами множества.

Построение бинарного дерева. Задача создания упорядоченного бинарного дерева при добавлении элемента Х к другому упорядоченному бинарному дереву формулируется следующим образом.

Граничное условие:

Добавление Х к nil дает бд(nil, Х, nil).

Рекурсивные условия:

При добавлении Х к бд(Лд, К, Пд) нужно рассмотреть два случая, чтобы быть уверенным, что результирующее дерево будет упорядоченным.

  1. Х меньше, чем К. В этом случае нужно добавить Х к Лд, чтобы получить левое поддерево. Правое поддерево равно Пд, а значение корня результирующего дерева равно К.
  2. Х больше, чем К. В таком случае нужно добавить Х к Пд, чтобы получить правое поддерево. Левое поддерево равно Лд, а значение корня — К.

Такой формулировке задачи соответствует программа:

/* Граничное условие: включ_бд(nil, Х, бд(nil, Х, nil)). /* Рекурсивные условия: /*(1) включ_бд(бд(Лд, К, Пд), Х, бд(Лднов, К, Пд)) :- Х@К, включ_бд(Лд,Х,Лднов). /*(2) включ_бд(бд(Лд, К, Пд), Х, бд(Лд, К, Пднов)) :- Х@К, включ_бд(Пд, Х, Пднов). На запрос ?- включ_бд(nil, d, Т1), включ_бд(Т1, а, Т2). будут получены значения Т1=бд(nil, d, nil) Т2=бд(бд(nil, а, nil), d, nil)

Процедуру включ_бд() можно использовать для построения упорядоченного дерева из списка:

/* Граничное условие: список_в_дерево([], nil). /* Рекурсивное условие: список_в_дерево([Н | Т], Бд) :- список_в_дерево(Т, Бд2), включ_бд(Н, Бд2, Бд).

Заметим, что включ_бд не обеспечивает построения сбалансированного дерева. Однако существуют алгоритмы, гарантирующие такое построение.

Бинарное (двоичное) дерево поиска, обходы и применение

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

Ещё деревья можно определить рекурсивно: дерево может быть или пустым, или состоять из узла (корня), являющимся родительским узлом для некоторого количества деревьев. Количество дочерних узлов обозначает арность дерева; другими словами, n-арное дерево не может содержать более n дочерних элементов (далее дочерний узел, дочерний элемент и потомок будут иметь один и тот же смысл) для каждого узла. Арность дерева — это тоже самое, что и степень дерева. Если же для каждого узла дерева определяется индивидуальная степень, то говорят только про степень конкретных узлов.

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

Одной из форм записи деревьев «на бумаге» называется скобочной записью:

(8 (3 (1) (6 (4) (7))) (10 (14 (13)))) 

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


 (8 
 (3 
 (1) 
 (6 
 (4) 
 (7) 
 ) 
 ) 
 (10 
 (14
 (13) 
 )
 )
 ) 
 

А так оно выглядит на самом деле:

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

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

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


 ::= ( ) | nil
 

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

А вот другое — бинарное дерево поиска. Используется для организации хранения данных таким образом, чтобы гарантировать поиск элемента за логарифмическое время:

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

Чтобы работать с деревьями, нужно уметь обходить его элементы. Существуют такие 3 варианта обхода:

  1. Прямой обход (КЛП): корень → левое поддерево → правое поддерево.
  2. Центрированный обход (ЛКП): левое поддерево → корень → правое поддерево.
  3. Обратный обход (ЛПК): левое поддерево → правое поддерево → корень

Прямой обход

Центрированный обход

Обратный обход

Такие обходы называются поиском в глубину, поскольку на каждом шаге итератор пытается продвинуться вертикально вниз по дереву перед тем, как перейти к родственному узлу (узлу на том же уровне). Ещё существует поиск в ширину. Его суть в обходе узлов дерева по уровням, начиная с корня (нужно пройти всего лишь 1 узел) и далее (на втором 2 узла, на третьем 4 узла, ну и т.д.; сколько узлов надо пройти на k-м уровне?).

Обход в ширину

Реализация поиска в глубину может осуществляться или с использованием рекурсии или с использованием стека, а поиск в ширину реализуется за счёт использования очереди:

Рекурсивный:


 preorder(node)
 if (node = null)
 return
 visit(node)
 preorder(node.left)
 preorder(node.right)
 

Через стек:


 iterativePreorder(node)
 s ← empty stack
 s.push(node)
 while (not s.isEmpty())
 node ← s.pop()
 visit(node)
 if (node.right ≠ null)
 s.push(node.right)
 if (node.left ≠ null)
 s.push(node.left)
 

Правый потомок заносится первым, так что левый потомок обрабатывается первым

Через очередь:


 levelorder(root)
 q ← empty queue
 q.enqueue(root)
 while (not q.isEmpty())
 node ← q.dequeue()
 visit(node)
 if (node.left ≠ null)
 q.enqueue(node.left)
 if (node.right ≠ null)
 q.enqueue(node.right)
 

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

Прошитое бинарное дерево поиска

Типичная структура данных одного узла такого дерева выглядит так:


 struct node { 
 data_type_t dat; 
 node *left, *right; //теперь left и right могут указывать как на дочерние элементы, так и содержать нитки, ведущие на другие уровни 
 bool left_is_thread, right_is_thread;
 }
 

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

Использование обхода бинарных деревьев облегчает работу с алгебраическими выражениями. Так, обратная польская нотация для алгебраического выражения получается путём обратного обхода заранее построенного бинарного дерева. Такое дерево называется деревом синтаксического разбора выражения, в котором узлы хранят операнды (+, –, *, /), а листья — числовые значения.

AA-Tree или простое бинарное дерево / Хабр

Тема бинарных деревьев уже обсуждалась на хабре (здесь и здесь).

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

Мне, однако, кажется, что AA-дерево заслуживает отдельной статьи.

Почему?

Потому, что фактически это самое быстрое (или одно из самых быстрых) бинарное дерево с простой реализацией.

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

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

AA-дерево было придумано Arne Andersson, который решил, что для упрощения балансировки дерева нужно ввести понятие уровень (level) вершины. Если представить себе дерево растущим сверху вниз от корня (то есть «стоящим на листьях»), то уровень любой листовой вершины будет равен 1. В своей работе Arne Andersson приводит простое правило, которому должно удовлетворять AA-дерево:

К одной вершине можно присоединить другую вершину того же уровня но только одну и только справа.

(В своей статье автор AA-дерева использует немного другую терминологию, связанную с 2-3 деревьями, но суть не меняется).

Таким образом, введенное понятие уровня вершины не всегда совпадает с реальной высотой вершины (расстояния от земли), но дерево сохраняет балансировку при следовании правилу «одна правая связь на одном уровне».

Для балансировки АА-дерева нужно всего 2 (две) операции.

Нетрудно их понять из правила «одна правая одноуровневая связь»: это устранение левой связи на одном уровне и устранение двух правых связей на одном уровне.

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

skew, устранение левой связи на одном уровне

split, устранение двух правых связей на одном уровне

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

В рамках недель Delphi на Хабре, исходный код будет в виде псевдокода, похожего на Delphi (для влюбленных в кофе C++: операция P^.x в Delphi эквивалентна P->x, var означает что переменная передается по ссылке, а не по значению, т.е. при изменении меняется внешняя переменная).

Определим вершину AA-дерева.

  PNode = ^TNode;
  TNode = packed record
    left, right: PNode;
    level: integer; // уровень; 1 у листьев
    key: pointer; // ключ, данные связанные с вершиной
  end;
 

Вставка элемента newkey проще всего выглядит в рекурсивной реализации.

procedure NodeInsert(var P: PNode; newkey: pointer);
begin
  if P = bottom then begin // достигли "дна" - создаем новую вершину
    new(P);
    P^.left := bottom;
    P^.right := bottom;
    P^.level := 1;
    P^.key := newkey;
  end else begin
    if newkey < P^.key then
      NodeInsert(P^.left, newkey)
    else if  newkey > P^.key then 
      NodeInsert(P^.right, newkey)
    else begin
      P^.key := newkey;
      exit;
    end;
    Skew(P);
    Split(P);
  end;
end;
 

Для вставки в дерево ключа newkey вызываем NodeInsert(root, newkey). Спускаемся от корня вниз по дереву, сравнивая ключи; вставляем; идем вверх и выполняем балансировку: skew и split для каждой вершины.

Удаление немного хитрее.

procedure NodeDelete(var P:PNode; newkey: pointer);
begin
 
  if P <> bottom then begin
 
  // 1. спускаемся вниз и запоминаем last и deleted
    last := P;
    if Compare(newkey, P) < 0 then  // newkey < key
      NodeDelete(P^.left, newkey)
    else begin
      deleted := P;
      NodeDelete(P^.right, newkey);
    end;
 
  // 2. удаляем элемент, если найден
    if (P = last) and (deleted <> bottom) and (newkey == deleted^.key) then begin
      deleted^.key := P^.key;
      deleted := bottom;
      P := P^.right;
      delete last;
    end else if (P^.left.level < P^.level - 1) or (P^.right.level < P^.level - 1) then begin
   // 3. выполняем балансировку при движении вверх
      Dec(P^.level);
      if P^.right.level > P^.level then P^.right.level := P^.level;
      Skew(P);
      Skew(P^.right);
      Skew(P^.right^.right);
      Split(P);
      Split(P^.right);
    end;
  end;
 
end;
 

Используются две вспомогательные переменные — deleted и last. При спуске вниз по дереву (как и при вставке) сравниваются ключи вершин с удаляемым ключом. Если ключ вершины меньше удаляемого, то переходим к левой ссылке, иначе — к правой (т.е. к правой переходим даже при совпадении ключей). В last заносится каждая проходимая вершина, а в deleted — только та, где «свернули направо».

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

Далее выполняется балансировка — нужно выполнить 3 skew и 2 split.

Реализация skew и split банальна.

// поменять местами _содержимое_ записей с вершинами (не указатели)
procedure Swap(P1, P2: PNode);
var
  tmp: TNode;
begin
  tmp := P1^;
  P1^ := P2^;
  P2^ := tmp;
end;
 
procedure Skew(T: PNode);
var
  L: PNode;
begin
  L := T^.left;
  if T^.level = L^.level then begin
    Swap(T, L); // теперь T ==> L, L ==> T
    L^.left := T^.right; // т.е. T.left = L.right
    T^.right := L; // т.е. L.right = T
  end;
end;
 
procedure Split(T: PNode);
var
  R: PNode;
begin
  R := T^.right;
  if T^.level = R^.right^.level then begin
    Swap(T, R); // теперь T ==> R, R ==> T
    R^.right := T^.left;
    T^.left := R;
    Inc(T^.level);
  end;
end;
 

Фактически, приведенный псевдокод достаточен для создания реализации АА-дерева (добавить лишь «мелочи» вроде модификации корня дерева (root) и пр.).

Некоторые полезные ссылки.

Реализация AA-дерева на C.

Замечательный апплет, в котором можно поиграться с различными видами деревьев (в том числе и с АА-деревьями).

Delphi проект с визуализацией АА-дерева и исходным кодом.

Статья в википедии.

Двоичное дерево | Набор 3 (Типы двоичного дерева)

Мы обсудили введение в двоичное дерево в наборе 1 и свойства двоичного дерева в наборе 2. В этом посте обсуждаются общие типы двоичных деревьев.

Ниже приведены распространенные типы двоичных деревьев.

Полное двоичное дерево Двоичное дерево - это полное двоичное дерево, если каждый узел имеет 0 или 2 дочерних элемента. Ниже приведены примеры полного двоичного дерева. Мы также можем сказать, что полное двоичное дерево - это двоичное дерево, в котором все узлы, кроме конечных, имеют двух дочерних элементов.

 18 / \ 15 30 / \ / \ 40 50 100 40 18 / \ 15 20 / \ 40 50 / \ 30 50 18 / \ 40 30 / \ 100 40 

В полном двоичном дереве количество конечных узлов равно количеству внутренних узлов плюс 1
L = I + 1
Где L = количество конечных узлов, I = количество внутренних узлов
См. Лемму и дерево о подтверждении связи для доказательства.


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

Ниже приведены примеры полных двоичных деревьев

 18 / \ 15 30 / \ / \ 40 50 100 40 18 / \ 15 30 / \ / \ 40 50 100 40 / \ / 8 7 9 

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

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

 18 / \ 15 30 / \ / \ 40 50 100 40 18 / \ 15 30 

Совершенное двоичное дерево высоты h (где высота двоичного дерева - это самый длинный путь от корневого узла до любого листового узла в дереве) имеет 2 h + 1 - 1 узел.

Пример Совершенного двоичного дерева - это предки в семье. Держите человека в корне, родителей как детей, родителей родителей как своих детей.

Сбалансированное двоичное дерево
Двоичное дерево сбалансировано, если высота дерева равна O (Log n), где n - количество узлов. Например, дерево AVL поддерживает высоту O (Log n), следя за тем, чтобы разница между высотами левого и правого поддеревьев была почти 1. Красно-черные деревья поддерживают высоту O (Log n), следя за тем, чтобы количество Черные узлы на каждом пути от корня до листа одинаковы, и нет смежных красных узлов.Деревья сбалансированного двоичного поиска хороши с точки зрения производительности, поскольку они предоставляют время O (log n) для поиска, вставки и удаления.

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

 10 / 20 \ 30 \ 40 

Источник:
https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не переставай учиться сейчас.Освойте все важные концепции DSA с помощью курса DSA Self Paced Course по доступной для студентов цене и будьте готовы к работе в отрасли.

.

Двоичное дерево | Набор 2 (Свойства)

Мы обсудили Введение в двоичное дерево в наборе 1. В этом посте обсуждаются свойства двоичного дерева.

1) Максимальное количество узлов на уровне «l» двоичного дерева составляет 2 l .
Здесь уровень - это количество узлов на пути от корня до узла (включая корень и узел). Уровень корня равен 0.
Это можно доказать по индукции.
Для корня, l = 0, количество узлов = 2 0 = 1
Предположим, что максимальное количество узлов на уровне 'l' равно 2 l
Поскольку в двоичном дереве каждый узел имеет не более 2 дочерних элементов, следующий уровень будет иметь два узла, т.е.е. 2 * 2 л

2) Максимальное количество узлов в двоичном дереве высотой «h» составляет 2 h - 1 .
Здесь высота дерева - это максимальное количество узлов на пути от корня к листу. Высота дерева с одним узлом считается равной 1.
Этот результат может быть получен из пункта 2 выше. Дерево имеет максимальное количество узлов, если все уровни имеют максимальное количество узлов. Таким образом, максимальное количество узлов в двоичном дереве высотой h равно 1 + 2 + 4 +.. + 2 ч-1 . Это простой геометрический ряд с h членами, а сумма этого ряда равна 2 h - 1.
В некоторых книгах высота корня считается равной 0. В этом соглашении приведенная выше формула принимает вид 2 h + 1. - 1

3) В двоичном дереве с N узлами минимально возможная высота или минимальное количество уровней равно? Лог 2 (N + 1)?
Это можно непосредственно вывести из пункта 2 выше.Если мы рассмотрим соглашение, согласно которому высота листового узла считается равной 0, то приведенная выше формула для минимально возможной высоты принимает вид? Лог 2 (N + 1)? - 1

4) Бинарное дерево с L листьями имеет не менее? Лог 2 L? + 1 уровни
Двоичное дерево имеет максимальное количество листьев (и минимальное количество уровней), когда все уровни полностью заполнены. Пусть все листья находятся на уровне l, тогда ниже верно для количества листьев L.


 L <= 2  l-1  [Из пункта 1] l =? Лог  2  L? +1 где l - минимальное количество уровней.

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

 L = Т + 1 Где L = количество листовых узлов T = количество внутренних узлов с двумя дочерними элементами 

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

Вниманию читателя! Не переставай учиться сейчас. Освойте все важные концепции DSA с помощью курса DSA Self Paced Course по приемлемой для студентов цене и будьте готовы к работе в отрасли.

.

Разница между двоичным деревом и двоичным деревом поиска

Разница между двоичным деревом и двоичным деревом поиска

Структура данных двоичного дерева

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

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

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



Разница между двоичным деревом и двоичным деревом поиска:

ДВОИЧНОЕ ДЕРЕВО ДВОИЧНОЕ ПОИСКОВОЕ ДЕРЕВО
ДВОИЧНОЕ ДЕРЕВО - это нелинейная структура данных, в которой каждый узел может иметь почти два дочерних узла ДВОИЧНОЕ ДЕРЕВО ПОИСКА - это двоичное дерево на основе узлов, которое также имеет правое и левое поддерево, которые также являются двоичным деревом поиска.
ДВОИЧНОЕ ДЕРЕВО неупорядочено, следовательно, медленнее в процессе вставки, удаления и поиска. Вставка, удаление и поиск элемента быстрее в ДВОИЧНОМ ДЕРЕВЕ ПОИСКА, чем в БИНАРНОМ ДЕРЕВЕ из-за упорядоченных характеристик
В БИНАРНОМ ДЕРЕВЕ нет порядка расположения узлов В ДВОИЧНОМ ДЕРЕВЕ ПОИСКА левое поддерево имеет элементы меньше, чем элемент узлов, а правое поддерево имеет элементы больше, чем элемент узлов.

Вниманию читателя! Не переставай учиться сейчас. Освойте все важные концепции DSA с помощью курса DSA Self Paced Course по приемлемой для студентов цене и будьте готовы к работе в отрасли.

.

Сложность различных операций в двоичном дереве, двоичном дереве поиска и дереве AVL

Сложность различных операций в двоичном дереве, двоичном дереве поиска и дереве AVL

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

Основные операции в двоичном дереве: поиск, вставка и удаление.Мы увидим наихудший случай временной сложности этих операций в двоичных деревьях.

Двоичное дерево -
В двоичном дереве узел может иметь максимум двух дочерних элементов. Рассмотрим скошенное влево двоичное дерево, показанное на рисунке 1.

Дерево двоичного поиска (BST) -
BST - это особый тип двоичного дерева, в котором левый дочерний элемент узла имеет значение меньше, чем родительский, а правый дочерний элемент имеет значение больше, чем родительский.Рассмотрим левый наклонный BST, показанный на рисунке 2.


AVL / Дерево со сбалансированной высотой -
Дерево AVL - это двоичное дерево поиска с дополнительным свойством, согласно которому разница между высотой левого поддерева и правого поддерева любого узла не может быть больше 1. Например, показан BST. на рисунке 2 не является AVL, поскольку разница между левым поддеревом и правым поддеревом узла 3 равна 2.Однако BST, показанный на рисунке 3, представляет собой дерево AVL.

Мы обсудим вопросы, основанные на сложности операций над двоичным деревом.

Que-1. Какова наихудшая временная сложность операций поиска, вставки и удаления в общем дереве двоичного поиска?
(A) O (n) для всех
(B) O (Logn) для всех
(C) O (Logn) для поиска и вставки и O (n) для удаления
(D) O (Logn) для поиска , и O (n) для вставки и удаления

Решение: Как обсуждалось, все операции в BST имеют временную сложность наихудшего случая O (n).Итак, правильный вариант - (А).

Que-2. Каковы наихудшие временные сложности поиска в двоичном дереве, дереве BST и дереве AVL соответственно?
(A) O (n) для всех
(B) O (Logn) для всех
(C) O (n) для двоичного дерева и O (Logn) для других
(D) O (n) для двоичного дерева и BST, и O (Logn) для AVL

Решение: Как обсуждалось, операция поиска в двоичном дереве и BST имеет временную сложность наихудшего случая O (n). Однако для дерева AVL временная сложность наихудшего случая равна O (logn).Итак, правильный вариант - (D).

Вниманию читателя! Не переставай учиться сейчас. Освойте все важные концепции DSA с помощью курса DSA Self Paced Course по приемлемой для студентов цене и будьте готовы к работе в отрасли.

.

двоичных древовидных структур данных - qaru Переполнение стека
  1. Около
  2. Продукты
  3. Для команд
  1. Переполнение стека Общественные вопросы и ответы
  2. Переполнение стека для команд Где разработчики и технологи делятся частными знаниями с коллегами
  3. Вакансии Программирование и связанные с ним технические возможности карьерного роста
  4. Талант Нанимайте технических специалистов и создавайте свой бренд работодателя
.

Смотрите также

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

Содержание, карта сайта.