Дерево поиска, наивная реализация

Бинарное дерево поиска обладает следующим свойством: если [math]x[/math] — узел бинарного дерева с ключом [math]k[/math] , то все узлы в левом поддереве должны иметь ключи, меньшие [math]k[/math] , а в правом поддереве большие [math]k[/math] .

Содержание

Операции в бинарном дереве поиска [ править ]

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

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:

• [math]\mathrm[/math] — обход узлов в отсортированном порядке,
• [math]\mathrm[/math] — обход узлов в порядке: вершина, левое поддерево, правое поддерево,
• [math]\mathrm[/math] — обход узлов в порядке: левое поддерево, правое поддерево, вершина.

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 3 4 6 7 8 10 13 14.

При выполнении данного обхода вершины будут выведены в следующем порядке: 8 3 1 6 4 7 10 14 13.

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 4 7 6 3 13 14 10 8.

Данные алгоритмы выполняют обход за время [math]O(n)[/math] , поскольку процедура вызывается ровно два раза для каждого узла дерева.

Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы [math]O(h)[/math] , где [math]h[/math] — высота дерева.

Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям [math]left[/math] от корня дерева, пока не встретится значение [math]null[/math] . Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.

Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время [math]O(h)[/math] .

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

Обе операции выполняются за время [math]O(h)[/math] .

Рассмотрим поиск следующего элемента для некоторого ключа [math]x[/math] . Поиск будем начинать с корня дерева, храня текущий узел [math]current[/math] и узел [math]successor[/math] , последний посещенный узел, ключ которого больше [math]x[/math] . Спускаемся вниз по дереву, как в алгоритме поиска узла. Рассмотрим ключ текущего узла [math]current[/math] . Если [math]current.key \leqslant x[/math] , значит следующий за [math]x[/math] узел находится в правом поддереве (в левом поддереве все ключи меньше [math]current.key[/math] ). Если же [math]x \lt current.key[/math] , то [math]x \lt next(x) \leqslant current.key[/math] , поэтому [math]current[/math] может быть следующим для ключа [math]x[/math] , либо следующий узел содержится в левом поддереве [math]current[/math] . Перейдем к нужному поддереву и повторим те же самые действия. Аналогично реализуется операция поиска предыдущего элемента.

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

Время работы алгоритма для обеих реализаций — [math]O(h)[/math] .

Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на [math]null[/math] . Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка), его правого потомка подвесить на место найденного элемента, а удаляемый узел заменить найденным узлом. Таким образом, свойство бинарного дерева поиска не будет нарушено. Данная реализация удаления не увеличивает высоту дерева. Время работы алгоритма — [math]O(h)[/math] .

Случай Иллюстрация Удаление листа Удаление узла с одним дочерним узлом Удаление узла с двумя дочерними узлами

При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить этот минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма — [math]O(h)[/math] . Рекурсивная функция, возвращающая дерево с удаленным элементом [math]z[/math] :

Задачи о бинарном дереве поиска [ править ]

Для того чтобы решить эту задачу, применим обход в глубину. Запустим от корня рекурсивную логическую функцию, которая выведет [math]\mathtt[/math] , если дерево является BST и [math]\mathtt[/math] в противном случае. Чтобы дерево не являлось BST, в нём должна быть хотя бы одна вершина, которая не попадает под определение дерева поиска. То есть достаточно найти всего одну такую вершину, чтобы выйти из рекурсии и вернуть значение [math]\mathtt[/math] . Если же, дойдя до листьев, функция не встретит на своём пути такие вершины, она вернёт значение [math]\mathtt[/math] .

Функция принимает на вход исследуемую вершину, а также два значения: [math]\mathtt[/math] и [math]\mathtt[/math] , которые до вызова функции равнялись [math] \infty [/math] и [math] -\infty [/math] соответственно, где [math] \infty [/math] — очень большое число, т.е. ни один ключ дерева не превосходит его по модулю. Казалось бы, два последних параметра не нужны. Но без них программа может выдать неверный ответ, так как сравнения только вершины и её детей недостаточно. Необходимо также помнить, в каком поддереве для более старших предков мы находимся. Например, в этом дереве вершина с номером [math]8[/math] находится левее вершины, в которой лежит [math]5[/math] , чего не должно быть в дереве поиска, однако после проверки функция бы вернула [math]\mathtt[/math] .

Время работы алгоритма — [math]O(n)[/math] , где [math]n[/math] — количество вершин в дереве.

Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за [math]O(n^2)[/math] . Но её можно решить за [math]O(n)[/math] , идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах:

• Значение в вершине больше максимума в её левом поддереве;
• Значение в вершине меньше минимума в её правом поддереве;
• Левое и правое поддерево являются деревьями поиска.

Введём [math]\mathtt[/math] и [math]\mathtt[/math] , которые будут хранить минимум в левом поддереве вершины и максимум в правом. Тогда мы должны будем проверить, являются ли эти поддеревья деревьями поиска и, если да, лежит ли ключ вершины [math]\mathtt[/math] между этими значениями [math]\mathtt[/math] и [math]\mathtt[/math] . Если вершина является листом, она автоматически становится деревом поиска, а её ключ — минимумом или максимумом для её родителя (в зависимости от расположения вершины). Функция [math]\mathtt[/math] записывает в [math]\mathtt[/math] количество вершин в дереве, если оно является деревом поиска или [math]\mathtt[/math] в противном случае. После выполнения функции ищем за линейное время вершину с наибольшим значением [math]\mathtt[/math] .

Алгоритм работает за [math]O(n)[/math] , так как мы прошлись по дереву два раза за время, равное количеству вершин.

Как мы помним, процедура [math]\mathrm[/math] выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына. Когда мы, желая найти такую вершину, встречаем какую-нибудь другую, уже имеющую правого сына, проходим по ветке вправо. Мы имеем на это право, так как если такая вершина стоит, то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону смысла не имеет. Вершину с максимальным ключом, с которой будем начинать поиск, будем запоминать. Она будет обновляться каждый раз, когда появится новый максимум.

Процедура восстановления дерева работает за [math]O(n)[/math] .

Разберём алгоритм на примере последовательности [math]\mathtt[/math] [math]\mathtt[/math] [math]\mathtt[/math] [math]\mathtt[/math] [math]\mathtt[/math] [math]\mathtt[/math] .

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