Что такое двоичное дерево
Бинарные деревья поиска и рекурсия – это просто
Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.
Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями.
Рис. 1 Бинарное дерево
Бинарное дерево поиска — это бинарное дерево, обладающее дополнительными свойствами: значение левого потомка меньше значения родителя, а значение правого потомка больше значения родителя для каждого узла дерева. То есть, данные в бинарном дереве поиска хранятся в отсортированном виде. При каждой операции вставки нового или удаления существующего узла отсортированный порядок дерева сохраняется. При поиске элемента сравнивается искомое значение с корнем. Если искомое больше корня, то поиск продолжается в правом потомке корня, если меньше, то в левом, если равно, то значение найдено и поиск прекращается.
Рис. 2 Бинарное дерево поиска
Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. Данное определение скорее идейное, чем строгое. Строгое определение оперирует разницей глубины самого глубокого и самого неглубокого листа (в AVL-деревьях) или отношением глубины самого глубокого и самого неглубокого листа (в красно-черных деревьях). В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). В вырожденном случае несбалансированного бинарного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности.
Рис. 3 Сбалансированное бинарное дерево поиска
Сбалансированное бинарное дерево поиска применяется, когда необходимо осуществлять быстрый поиск элементов, чередующийся со вставками новых элементов и удалениями существующих. В случае, если набор элементов, хранящийся в структуре данных фиксирован и нет новых вставок и удалений, то массив предпочтительнее. Потому что поиск можно осуществлять алгоритмом бинарного поиска за то же логарифмическое время, но отсутствуют дополнительные издержки по хранению и использованию указателей. Например, в С++ ассоциативные контейнеры set и map представляют собой сбалансированное бинарное дерево поиска.
Рис. 4 Экстремально несбалансированное бинарное дерево поиска
Теперь кратко обсудим рекурсию. Рекурсия в программировании – это вызов функцией самой себя с другими аргументами. В принципе, рекурсивная функция может вызывать сама себя и с теми же самыми аргументами, но в этом случае будет бесконечный цикл рекурсии, который закончится переполнением стека. Внутри любой рекурсивной функции должен быть базовый случай, при котором происходит выход из функции, а также вызов или вызовы самой себя с другими аргументами. Аргументы не просто должны быть другими, а должны приближать вызов функции к базовому случаю. Например, вызов внутри рекурсивной функции расчета факториала должен идти с меньшим по значению аргументом, а вызовы внутри рекурсивной функции обхода дерева должны идти с узлами, находящимися дальше от корня, ближе к листьям. Рекурсия может быть не только прямой (вызов непосредственно себя), но и косвенной. Например А вызывает Б, а Б вызывает А. С помощью рекурсии можно эмулировать итеративный цикл, а также работу структуры данных стек (LIFO).
Кратко обсудим деревья с точки зрения теории графов. Граф – это множество вершин и ребер. Ребро – это связь между двумя вершинами. Количество возможных ребер в графе квадратично зависит от количества вершин (для понимания можно представить турнирную таблицу сыгранных матчей). Дерево – это связный граф без циклов. Связность означает, что из любой вершины в любую другую существует путь по ребрам. Отсутствие циклов означает, что данный путь – единственный. Обход графа – это систематическое посещение всех его вершин по одному разу каждой. Существует два вида обхода графа: 1) поиск в глубину; 2) поиск в ширину.
Поиск в ширину (BFS) идет из начальной вершины, посещает сначала все вершины находящиеся на расстоянии одного ребра от начальной, потом посещает все вершины на расстоянии два ребра от начальной и так далее. Алгоритм поиска в ширину является по своей природе нерекурсивным (итеративным). Для его реализации применяется структура данных очередь (FIFO).
Поиск в глубину (DFS) идет из начальной вершины, посещая еще не посещенные вершины без оглядки на удаленность от начальной вершины. Алгоритм поиска в глубину по своей природе является рекурсивным. Для эмуляции рекурсии в итеративном варианте алгоритма применяется структура данных стек.
С формальной точки зрения можно сделать как рекурсивную, так и итеративную версию как поиска в ширину, так и поиска в глубину. Для обхода в ширину в обоих случаях необходима очередь. Рекурсия в рекурсивной реализации обхода в ширину всего лишь эмулирует цикл. Для обхода в глубину существует рекурсивная реализация без стека, рекурсивная реализация со стеком и итеративная реализация со стеком. Итеративная реализация обхода в глубину без стека невозможна.
Асимптотическая сложность обхода и в ширину и в глубину O(V + E), где V – количество вершин, E – количество ребер. То есть является линейной по количеству вершин и ребер. Записи O(V + E) с содержательной точки зрения эквивалентна запись O(max(V,E)), но последняя не принята. То есть, сложность будет определятся максимальным из двух значений. Несмотря на то, что количество ребер квадратично зависит от количества вершин, мы не можем записать сложность как O(E), так как если граф сильно разреженный, то это будет ошибкой.
DFS применяется в алгоритме нахождения компонентов сильной связности в ориентированном графе. BFS применяется для нахождения кратчайшего пути в графе, в алгоритмах рассылки сообщений по сети, в сборщиках мусора, в программе индексирования – пауке поискового движка. И DFS и BFS применяются в алгоритме поиска минимального покрывающего дерева, при проверке циклов в графе, для проверки двудольности.
Обходу в ширину в графе соответствует обход по уровням бинарного дерева. При данном обходе идет посещение узлов по принципу сверху вниз и слева направо. Обходу в глубину в графе соответствуют три вида обходов бинарного дерева: прямой (pre-order), симметричный (in-order) и обратный (post-order).
Прямой обход идет в следующем порядке: корень, левый потомок, правый потомок. Симметричный — левый потомок, корень, правый потомок. Обратный – левый потомок, правый потомок, корень. В коде рекурсивной функции соответствующего обхода сохраняется соответствующий порядок вызовов (порядок строк кода), где вместо корня идет вызов данной рекурсивной функции.
Если нам дано изображение дерева, и нужно найти его обходы, то может помочь следующая техника (см. рис. 5). Обводим дерево огибающей замкнутой кривой (начинаем идти слева вниз и замыкаем справа вверх). Прямому обходу будет соответствовать порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами слева. Для симметричного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами снизу. Для обратного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами справа. В коде рекурсивного вызова прямого обхода идет: вызов, левый, правый. Симметричного – левый, вызов, правый. Обратного – левый правый, вызов.
Рис. 5 Вспомогательный рисунок для обходов
Для бинарных деревьев поиска симметричный обход проходит все узлы в отсортированном порядке. Если мы хотим посетить узлы в обратно отсортированном порядке, то в коде рекурсивной функции симметричного обхода следует поменять местами правого и левого потомка.
Надеюсь Вы не уснули, и статья была полезна. Скоро надеюсь последует продолжение банкета статьи.
Дерево
Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.
Способ представления бинарного дерева: 
Корень дерева расположен на уровне с минимальным значением.
Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.
Остальные элементы – внутренние узлы (узлы ветвления).
Бинарное дерево применяется в тех случаях, когда в каждой точке вычислительного процесса должно быть принято одно из двух возможных решений.
Имеется много задач, которые можно выполнять на дереве.
Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.
Если рассматривать задачу как единый последовательный процесс, то отдельные узлы посещаются в определенном порядке и могут считаться расположенными линейно.
Способы обхода дерева
Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.
Существует три способа обхода дерева:
Реализация дерева
Узел дерева можно описать как структуру:
При этом обход дерева в префиксной форме будет иметь вид
Обход дерева в инфиксной форме будет иметь вид
Обход дерева в постфиксной форме будет иметь вид
Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.
Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.
Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.
Добавление узлов в дерево
Удаление поддерева
Пример Написать программу, подсчитывающую частоту встречаемости слов входного потока.
Поскольку список слов заранее не известен, мы не можем предварительно упорядочить его. Неразумно пользоваться линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет, т.к. в этом случае программа работает слишком медленно.
Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Воспользуемся бинарным деревом.
В дереве каждый узел содержит:
Рассмотрим выполнение программы на примере фразы
now is the time for all good men to come to the aid of their party
При этом дерево будет иметь следующий вид 
Результат выполнения 
Двоичное дерево поиска (Binary Search Tree (BST))
Свойства, которые отличают двоичное дерево поиска от обычного двоичного дерева:
Двоичное дерево справа не является двоичным деревом поиска, потому что правое поддерево узла «3» содержит значение, которое меньше его.
Есть две основные операции, которые вы можете выполнять в двоичном дереве поиска:
1. Проверка, присутствует ли число в двоичном дереве поиска.
Алгоритм зависит от свойства BST так, что, если каждое левое поддерево имеет значения ниже корневого, то каждое правое поддерево имеет значения выше корневого.
Если значение ниже корневого, мы можем с уверенностью сказать, что значение находится не в правом поддереве, а значит нам стоит искать его в левом поддереве.
И наоборот, если значение выше корневого, наверняка, что значение находится не в левом поддереве, а значит нужно искать в правом.
Алгоритм:
Давайте попробуем визуализировать алгоритм с помощью диаграммы.
Если значение найдено, мы возвращаем значение, чтобы оно распространялось на каждом шаге рекурсии, как показано на рисунке ниже.
Вы могли заметить, что мы вызывали функцию return search (struct node) четыре раза. Когда мы возвращаем либо новый узел, либо NULL, значение возвращается снова и снова, до тех пор, пока search (root) не вернет окончательный результат.
Если значение не найдено, мы в конечном итоге достигаем левого или правого потомка конечного узла, который равен NULL, и он распространяется и возвращается.
2. Вставка значения в двоичное дерево поиска (BST)
Вставка значения в правильную позицию аналогична поиску, потому что мы пытаемся соответствовать правилу, согласно которому левое поддерево меньше корневого, а правое поддерево больше корневого.
Мы продолжаем идти либо к правому поддереву, либо к левому в зависимости от значения, а когда мы достигаем точки, где левое или правое поддерево равно нулю, мы помещаем туда новый узел.
Алгоритм:
Алгоритм не так прост, как кажется. Давайте попробуем визуализировать, как мы добавляем число к существующему BST.
Мы подсоединили узел, но нам все еще нужно выйти из функции, не нанося вреда остальной части дерева. Вот где return node (возвратный узел) в конце пригодится. В этом случае NULL, вновь созданный узел возвращается и присоединяется к родительскому узлу, в противном случае тот же самый узел возвращается без каких-либо изменений, пока мы не вернемся к корневому узлу.
Это гарантирует, что когда мы вернемся вверх по дереву, соединения с другими узлами не изменятся.
Полный код для вставки и поиска в BST на языке программирования C приведен ниже:
Рекомендуем хостинг TIMEWEB
Рекомендуемые статьи по этой тематике
Двоичное дерево, двоичное дерево поиска, двоичная куча, B-дерево
В большинстве реляционных СУБД в качестве структуры данных для индексов (та или иная их реализация) используются именно деревья. И не просто деревья, а сбалансированные деревья поиска. В этой статье как раз о них.
Сами по себе деревья бесполезны, если мы не можем выполнять с ними определенные операции. К таким операциям обычно относят: поиск элемента, поиск минимального (максимального) элемента, вставка, удаление. В разрезе этих операций мы и рассмотрим каждое из 4 деревьев отдельно. Каждое дерево имеет свои особенности, связанные как правило с организацией хранения данных, но при этом они все связаны между собой:
Теперь рассмотрим каждое дерево отдельно.
Двоичное дерево
Пример двоичного дерева:
Особый интерес из себя не представляет, нужно только для понимания что такое вообще двоичное дерево. Нас интересуют следующие два дерева, которые являются его разновидностью.
Двоичное дерево поиска (binary search tree)
Структура дерева зависима от порядка заполнения ключей. Если мы будем заполнять предварительно отсортированными массивом ключей (например: 10; 20; 30; 40), то мы получим экстремально сбалансированное дерево. Т.е. дерево, у которого высота равна количеству элементов.
Поиск элемента
Поиск начинается с корня. При этом значение каждого узла сравнивается с искомым значением:
Для поиска ключа 23 мы нужно 4 итерации (начинаем с корня, ключ расположен на 4 уровне):
Добавление элемента
Добавление аналогично поиску элемента, только если отсутствует дочерний узел нужно создать его, вставляя добавляемый элемент. Добавим ключ 7 в дерево:
Удаление элемента
А вот операция удаления уже сложнее. Нужно сначала найти нужный нам ключ, а потом уже обработать его. Всего возможны 3 варианта:
Если узел не имеет дочерних узлов, то просто удаляем его. Удалим ключ 23:
Если узел имеет только один дочерний узел, то заменяем связь с родителем узла на дочерний узел. Удалим узел 11:
Если же узел имеет два дочерних узла, тогда надо найти следующий элемент в правом дочернем узле (т.е. минимальный узел, который не имеет дочерних узлов). Удалим узел 21:
Двоичная куча (binary heap)
Существуют также кучи, где значение в любой вершине, наоборот, не больше, чем значения её потомков. Структура данных как двоичная куча используется в основном в алгоритмах сортировки.
Пример двоичной кучи:
Над кучей можно выполнять следующие операции:
Добавление элемента
Добавление элемента всегда происходит последовательно в первый незаполненный узел, начиная сверху вниз и перемещаясь слева направо по уровню. Добавим в кучу ключ 16:
Для удобства на картинке все узлы пронумерованы, начиная с единицы (корневой узел). В нашем случае самым крайним и свободным узлом оказался узел под номером 12. Туда-то мы и записали свое значение.
Если бы на 4-ом уровне дерева все узлы были заполнены (т.е. узлы с номерами от 8 до 15), тогда мы бы добавили левый дочерний узел к элементу 8, как самому левому узлу 4-го уровня, при этом бы образовался новый 5-ый уровень.
При этом необходимо выполнить условие, что элемент родительского узла должен быть всегда больше элемента дочернего. Поэтому, если наше значение меньше значения родителя, то необходимо родителя и потомка поменять местами:
Двигаемся вверх по дереву, пока значение нашего узла не станет меньше значения родителя.
Исключение максимального элемента
Т.к. самым максимальным узлом кучи является корневой элемент, то необходимо удалить именно его. На его место записывается самый последний элемент дерева (нумерация элементов сверху вниз, слева направо):
Если при этом нарушилось свойство кучи и значение узла стало меньше значения одного из дочерних узлов (или обоих), то меняем местами значение текущего узла и дочернего. Сравнение нужно делать сперва с левым дочерним узлом, затем с правым. Рекурсивно продолжать сравнение, спускаясь вниз по измененным узлам.
Изменение значения элемента
При изменении элемента кучи возможны два варианта:
B-дерево (B-tree)
B-деревья (или их разновидности) используются в индексах большинства реляционных СУБД. Оптимизированы специально для работы с дисковой подсистемой.
При построении дерева применяется параметр t, который называется минимальной степенью. Количество ключей в узле (за исключением корневого) должно быть от t – 1 до 2t – 1.
Стоит обратить внимание, что дочерние узлы ссылаются не на сам родитель, а разделитель между ключами этого родителя.
Поиск элемента
Алгоритм поиска элемента схож с алгоритмом двоичного дерева поиска. Обход начинается с корня. Так как все ключи хранятся в неубывающем порядке, то поиск ведем слева на право. Если ключ содержится в текущем узле, возвращаем его. Иначе определяем интервал и переходим к соответствующему потомку. Повторяем пока ключ не найден или не дошли до листа.
Добавление элемента
Добавление элемента уже интереснее. Возможны два случая:
Удаление элемента
Удаление происходит сложнее, потому что при удалении происходит перестроение дерева. Удалять можно как из листового узла, так и из внутреннего.
Рассмотрим удаление из листового узла:
Специальные предложения
В ms sql насколько я знаю, получить данные индекса нельзя.
В Oracle посмотреть на внутреннюю структуру индекса можно, для этого выгрузить индекс в дамп следующей командой:
alter session set events ‘immediate trace name treedump level nnnn ; где nnnn это object_id индекса.
В этом дампе мы увидели общую структуру индекса и сколько ключей хранятся в каждом узле индекса, но в ней нет самих значений ключей.
Все это информация о дереве.
Динамические структуры данных: бинарные деревья
Цель лекции: изучить понятие, формирование, особенности доступа к данным и работы с памятью в бинарных деревьях, научиться решать задачи с использованием рекурсивных функций и алгоритмов обхода бинарных деревьев в языке C++.
Деревья являются одними из наиболее широко распространенных структур данных в информатике и программировании, которые представляют собой иерархические структуры в виде набора связанных узлов.
Каждое дерево обладает следующими свойствами:
Деревья особенно часто используют на практике при изображении различных иерархий. Например, популярны генеалогические деревья.
Все вершины, в которые входят ветви, исходящие из одной общей вершины, называются потомками, а сама вершина – предком. Для каждого предка может быть выделено несколько. Уровень потомка на единицу превосходит уровень его предка. Корень дерева не имеет предка, а листья дерева не имеют потомков.
Поддерево – часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева.
Деревья являются рекурсивными структурами, так как каждое поддерево также является деревом. Таким образом, дерево можно определить как рекурсивную структуру, в которой каждый элемент является:
Действия с рекурсивными структурами удобнее всего описываются с помощью рекурсивных алгоритмов.
Для того, чтобы выполнить определенную операцию над всеми вершинами дерева необходимо все его вершины просмотреть. Такая задача называется обходом дерева.
Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только один раз.
При обходе все вершины дерева должны посещаться в определенном порядке. Существует несколько способов обхода всех вершин дерева. Выделим три наиболее часто используемых способа обхода дерева ( рис. 31.2):
Бинарные деревья
Бинарные деревья являются деревьями со степенью не более двух.
Каждая вершина бинарного дерева является структурой, состоящей из четырех видов полей. Содержимым этих полей будут соответственно:
По степени вершин бинарные деревья делятся на ( рис. 31.4):
Дерево называется сбалансированным, если длины всех путей от корня к внешним вершинам равны между собой. Дерево называется почти сбалансированным, если длины всевозможных путей от корня к внешним вершинам отличаются не более, чем на единицу.
