Дерево поиска, наивная реализация — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Задачи о деревьях поиска и произвольных двоичных деревьях)
м (rollbackEdits.php mass rollback)
 
(не показано 170 промежуточных версий 10 участников)
Строка 39: Строка 39:
 
=== Поиск элемента ===
 
=== Поиск элемента ===
 
[[Файл:Bst search.png|frame|right|318px|Поиск элемента 4]]
 
[[Файл:Bst search.png|frame|right|318px|Поиск элемента 4]]
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
+
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
 
<div style="width: 65%">
 
<div style="width: 65%">
 
  '''Node''' search(x : '''Node''', k : '''T'''):
 
  '''Node''' search(x : '''Node''', k : '''T'''):
Строка 49: Строка 49:
 
       '''return''' search(x.right, k)
 
       '''return''' search(x.right, k)
 
</div>
 
</div>
 
  
 
=== Поиск минимума и максимума ===
 
=== Поиск минимума и максимума ===
Строка 66: Строка 65:
 
=== Поиск следующего и предыдущего элемента ===
 
=== Поиск следующего и предыдущего элемента ===
 
====Реализация с использованием информации о родителе====
 
====Реализация с использованием информации о родителе====
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.  
+
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то предыдущий ему элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.  
 
  '''Node''' next(x : '''Node'''):
 
  '''Node''' next(x : '''Node'''):
 
     '''if''' x.right != ''null''
 
     '''if''' x.right != ''null''
Строка 85: Строка 84:
 
     '''return''' y
 
     '''return''' y
 
Обе операции выполняются за время <tex>O(h)</tex>.
 
Обе операции выполняются за время <tex>O(h)</tex>.
 +
 
====Реализация без использования информации о родителе====
 
====Реализация без использования информации о родителе====
 
Рассмотрим поиск следующего элемента для некоторого ключа <tex>x</tex>. Поиск будем начинать с корня дерева, храня текущий узел <tex>current</tex> и узел <tex>successor</tex>, последний посещенный узел, ключ которого больше <tex>x</tex>. <br>
 
Рассмотрим поиск следующего элемента для некоторого ключа <tex>x</tex>. Поиск будем начинать с корня дерева, храня текущий узел <tex>current</tex> и узел <tex>successor</tex>, последний посещенный узел, ключ которого больше <tex>x</tex>. <br>
Строка 178: Строка 178:
  
 
====Рекурсивная реализация====
 
====Рекурсивная реализация====
При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.
+
При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить '''этот''' минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.
 
Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>:
 
Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>:
 
  '''Node''' delete(root : '''Node''', z : '''T'''):              <font color="green">// корень поддерева, удаляемый ключ</font>
 
  '''Node''' delete(root : '''Node''', z : '''T'''):              <font color="green">// корень поддерева, удаляемый ключ</font>
Строка 189: Строка 189:
 
   '''else if''' root.left != ''null'' '''and''' root.right != ''null''
 
   '''else if''' root.left != ''null'' '''and''' root.right != ''null''
 
     root.key = minimum(root.right).key
 
     root.key = minimum(root.right).key
     root.right = delete(root.right, root.right.key)
+
     root.right = delete(root.right, root.key)
 
   '''else'''
 
   '''else'''
 
     '''if''' root.left != ''null''
 
     '''if''' root.left != ''null''
 
       root = root.left
 
       root = root.left
 +
    '''else if''' root.right != ''null''
 +
      root = root.right
 
     '''else'''
 
     '''else'''
       root = root.right
+
       root = ''null''
 
   '''return''' root
 
   '''return''' root
  
==Задачи о деревьях поиска и произвольных двоичных деревьях==
+
==Задачи о бинарном дереве поиска==
  
===Проверка того, что заданное дерево является деревом поиска===
+
===Проверка того, что заданное дерево является деревом поиска===
  
 
{{Задача
 
{{Задача
 
|definition = Определить, является ли заданное двоичное дерево деревом поиска.
 
|definition = Определить, является ли заданное двоичное дерево деревом поиска.
 
}}
 
}}
 +
[[Файл:Not_Enough.png|right|thumb|291px|Пример дерева, для которого недостаточно проверки лишь его соседних вершин]]
 +
Для того чтобы решить эту задачу, применим [[Обход в глубину, цвета вершин|обход в глубину]]. Запустим от корня рекурсивную логическую функцию, которая выведет <tex>\mathtt{true}</tex>, если дерево является BST и <tex>\mathtt{false}</tex> в противном случае. Чтобы дерево не являлось BST, в нём должна быть хотя бы одна вершина, которая не попадает под определение дерева поиска. То есть достаточно найти всего одну такую вершину, чтобы выйти из рекурсии и вернуть значение <tex>\mathtt{false}</tex>. Если же, дойдя до листьев, функция не встретит на своём пути такие вершины, она вернёт значение <tex>\mathtt{true}</tex>.
  
===Поиск максимального поддерева, являющегося BST, в заданном двоичном дереве===
+
Функция принимает на вход исследуемую вершину, а также два значения: <tex>\mathtt{min}</tex> и <tex>\mathtt{max}</tex>, которые до вызова функции равнялись <tex> \infty </tex> и <tex> -\infty </tex> соответственно, где <tex> \infty </tex> — очень большое число, т.е. ни один ключ дерева не превосходит его по модулю. Казалось бы, два последних параметра не нужны. Но без них программа может выдать неверный ответ, так как сравнения только вершины и её детей недостаточно. Необходимо также помнить, в каком поддереве для более старших предков мы находимся. Например, в этом дереве вершина с номером <tex>8</tex> находится левее вершины, в которой лежит <tex>5</tex>, чего не должно быть в дереве поиска, однако после проверки функция бы вернула <tex>\mathtt{true}</tex>.
  
{{Задача
+
'''bool''' isBinarySearchTree(root: '''Node'''):                    <font color="green">// Здесь root — корень заданного двоичного дерева.</font>
|definition = Найти в данном дереве максимальное из поддеревьев поиска.
+
}}
+
  '''bool''' check(v : '''Node''', min: '''T''', max: '''T'''):                <font color="green">// min и max — минимально и максимально допустимые значения в вершинах поддерева.</font>
 +
    '''if''' v == ''null''                    '''return''' ''true''
 +
    '''if''' v.key <= min '''or''' max <= v.key '''return''' ''false''
 +
    '''return''' check(v.left, min, v.key) '''and''' check(v.right, v.key, max)
 +
 +
  '''return''' check(root, <tex> -\infty </tex>, <tex> \infty </tex>)
  
В переменную <tex>maxdp</tex>, изначально равную <tex>-1</tex>, запишем число вершин максимального поддерева поиска. Будем также вместе с <tex>maxdp</tex> обновлять <tex>maxroot</tex>, где будет храниться корень такого поддерева. Чтобы найти <tex>maxdp</tex>, обойдём вершины и для каждой из них с помощью процедуры <tex>dfs</tex>, на вход которой подаются сама вершина, максимально и минимально возможные элементы поддерева и количество вершин, посчитаем число элементов, принадлежащих максимальному дереву поиска, для которого данная вершина является корнем. Если результат после обхода вершины оказался больше значения в переменной <tex>maxdp</tex>, обновляем <tex>maxdp</tex> и <tex>maxroot</tex>. Затем переходим к следующей вершине. После того как мы прошлись по всему дереву, посчитали <tex>maxdp</tex> и нашли <tex>maxroot</tex>, запускаем процедуру <tex>dfsPrint(maxroot, -INF, INF)</tex> для вывода вершин поддерева поиска. До запуска процедуры <tex>dfs</tex> от каждой вершины переменная <tex>dp</tex> равна единице.
+
Время работы алгоритма {{---}} <tex>O(n)</tex>, где <tex>n</tex> {{---}} количество вершин в дереве.
  
maxdp = -1
+
===Задачи на поиск максимального BST в заданном двоичном дереве===
maxroot = ''null''
 
'''for''' u '''in''' Tree          <font color="green">// Здесь Tree – заданное двоичное дерево.</font>
 
  dp = 1
 
  dfs(u, -INF, INF, dp)
 
  '''if''' dp > maxdp
 
    maxdp = dp
 
    maxroot = u
 
dfsPrint(maxroot, -INF, INF)
 
  
Процедура <tex>dfs(v,max,min,res)</tex> позволяет подсчитать максимальное количество вершин двоичного поддерева поиска с вершиной <tex>v</tex>. В начале работы этой процедуры <tex>max</tex> и <tex>min</tex> принимают нейтральные значения (<tex>-INF</tex> и <tex>INF</tex> соответственно, где <tex>INF</tex> - очень большое число), а <tex>res</tex> равен <tex>1</tex> (одна вершина в дереве уже имеется). Обход осуществляется следующим образом:
+
{{Задача
 +
|definition = Найти в данном дереве такую вершину, что она будет корнем поддерева поиска с наибольшим количеством вершин.
 +
}}
 +
Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за <tex>O(n^2)</tex>. Но её можно решить за <tex>O(n)</tex>, идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах:
 +
* Значение в вершине больше максимума в её левом поддереве;
 +
* Значение в вершине меньше минимума в её правом поддереве;
 +
* Левое и правое поддерево являются деревьями поиска.
  
'''1 шаг.''' Проверяем, есть ли у вершины левый сын. Если его нет, переходим к пункту 2, иначе сравниваем значения в этой вершине и в её левом потомке, а также значение в левом сыне с максимумом в поддереве. Если значение в левом сыне меньше, чем значение в вершине и больше переменной <tex>max</tex>, то запускаем <tex>dfs</tex> из левого сына. Здесь роль v будет разыгрывать <tex>v.left</tex>, <tex>max</tex> приобретёт значение <tex>v.key</tex>, <tex>min</tex> по-прежнему останется <tex>min</tex>, а <tex>res</tex> увеличится на 1. ''Пояснение:'' ключи  вершин левого поддерева не должны превосходить значения в рассматриваемой вершине, поэтому мы изменяем <tex>max</tex>. На <tex>min</tex> эта вершина не влияет в случае левого поддерева, поэтому он не изменяется. <tex>res</tex> увеличивается на 1, так как в наше поддерево добавилась ещё одна вершина.
+
Введём <tex>\mathtt{v.min}</tex> и <tex>\mathtt{v.max}</tex>, которые будут хранить минимум в левом поддереве вершины и максимум в правом. Тогда мы должны будем проверить, являются ли эти поддеревья деревьями поиска и, если да, лежит ли ключ вершины <tex>\mathtt{v}</tex> между этими значениями <tex>\mathtt{v.min}</tex> и <tex>\mathtt{v.max}</tex>.  Если вершина является листом, она автоматически становится деревом поиска, а её ключ {{---}} минимумом или максимумом для её родителя (в зависимости от расположения вершины). Функция <tex>\mathtt{cnt}</tex> записывает в <tex>\mathtt{v.kol}</tex> количество вершин в дереве, если оно является деревом поиска или <tex>\mathtt{-1}</tex> в противном случае. После выполнения функции ищем за линейное время вершину с наибольшим значением <tex>\mathtt{v.kol}</tex>.
  
'''2 шаг.''' Аналогично действуем с правым потомком. Проверяем его наличие. Если он существует, то сравниваем значение в нём с минимумом и с ключом вершины. Если значение правого сына больше минимума в поддереве и меньше значения в вершине, то запускаем от потомка <tex>dfs</tex>. Теперь на место <tex>v</tex> встаёт <tex>v.right</tex>, <tex>max</tex> остаётся прежним, <tex>min</tex> становится ключом в рассматриваемой вершине, а <tex>res</tex> снова увеличивается на 1. Для случая с правым поддеревом рассуждения аналогичны.
+
'''int''' count(root: '''Node'''):                <font color="green">// root — корень заданного двоичного дерева.</font>
 +
 +
  '''int''' cnt(v: '''Node'''):
 +
    '''if''' v == ''null''
 +
      v.kol = 0
 +
      '''return''' = 0
 +
    '''if''' cnt(v.left) != -1 '''and''' cnt(v.right) != -1
 +
      '''if''' v.left == ''null'' '''and''' v.right == ''null''
 +
        v.min = v.key
 +
        v.max = v.key
 +
        v.kol = 1
 +
        '''return''' 1
 +
      '''if''' v.left == ''null''
 +
        '''if''' v.right.max > v.key
 +
          v.min = v.key
 +
          v.kol = cnt(v.right) + 1
 +
          '''return''' v.kol
 +
      '''if''' v.right == ''null''
 +
        '''if''' v.left.min < v.key
 +
          v.max = v.key
 +
          v.kol = cnt(v.left) + 1
 +
          '''return''' v.kol
 +
      '''if''' v.left.min < v.key '''and''' v.right.max > v.key
 +
        v.min = v.left.min
 +
        v.max = v.right.max
 +
        v.kol = v.left.kol + v.right.kol + 1
 +
        v.kol = cnt(v.left) + cnt(v.right) + 1
 +
        '''return''' v.kol
 +
    '''return''' -1
 +
 +
  '''return''' cnt(root)
  
'''3 шаг.''' Возвращаем результат в переменной <tex>res</tex>, где записано количество вершин поддерева.
+
Алгоритм работает за <tex>O(n)</tex>, так как мы прошлись по дереву два раза за время, равное количеству вершин.
  
[[Файл:BST_in_Tree.gif|centre|thumb|800px|Пример выполнения процедуры dfs для вершины с номером 7]]
+
===Восстановление дерева по результату обхода preorderTraversal===
  
Процедура обхода дерева представлена ниже:
+
{{Задача
 
+
|definition = Восстановить дерево по последовательности, выведенной после выполнения процедуры <tex>\mathrm{preorderTraversal}</tex>.
'''procedure''' dfs(v: '''Node''', max: '''T''', min: '''T''', res: '''integer''')
+
}}
  '''if''' v.left != ''null''
+
[[Файл:BST_from_seq.gif|right|thumb|257px|Восстановление дерева поиска по последовательности ключей]]
    '''if''' v.left.key < v.key '''and''' v.left.key > max
 
      dfs(v.left, v.left.key, min, res+1)
 
  '''if''' v.right != ''null''
 
    '''if''' v.right.key > v.key '''and''' v.right.key < min
 
      dfs(v.left, max, v.left.key, res+1)
 
  
Наконец, рассмотрим процедуру <tex>dfsPrint</tex>, выводящую максимальное дерево поиска. Так как <tex>maxdp</tex> уже посчитано, достаточно задать три параметра: корень поддерева и максимальное и минимальное допустимые значения. <tex>max</tex> и <tex>min</tex> нам понадобятся, чтобы взять только те вершины, которые принадлежат дереву.
+
Как мы помним, процедура <tex>\mathrm{preorderTraversal}</tex> выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына. Когда мы, желая найти такую вершину, встречаем какую-нибудь другую, уже имеющую правого сына, проходим по ветке вправо. Мы имеем на это право, так как если такая вершина стоит, то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону смысла не имеет. Вершину с максимальным ключом, с которой будем начинать поиск, будем запоминать. Она будет обновляться каждый раз, когда появится новый максимум.
  
'''procedure''' dfsPrint(v: '''Node''', max: '''T''', min: '''T''')
+
Процедура восстановления дерева работает за <tex>O(n)</tex>.
  '''print''' v.key
 
  '''if''' v.left != ''null''
 
    '''if''' v.left.key < v.key '''and''' v.left.key > max
 
      dfsPrint(v.left, v.left.key, min)
 
  '''if''' v.right != ''null''
 
    '''if''' v.right.key > v.key '''and''' v.right.key < min
 
      dfsPrint(v.left, max, v.left.key)
 
  
[[Файл:BST_from_sequence.gif|right|thumb|300px|Восстановление дерева поиска по последовательности ключей]]
 
  
Заметим, что <tex>dfsPrint</tex> выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем делает шаг вправо, потом снова влево и так до тех пор, пока не будет выведено <tex>maxdp</tex> вершин. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Происходит это так:
+
Разберём алгоритм на примере последовательности <tex>\mathtt{8}</tex> <tex>\mathtt{2}</tex> <tex>\mathtt{1}</tex> <tex>\mathtt{4}</tex> <tex>\mathtt{3}</tex> <tex>\mathtt{5}</tex>.
  
- последовательно подвешиваем левых сыновей, пока не находим номер, нарушающий убывающую последовательность;
+
Будем выделять красным цветом вершины, рассматриваемые на каждом шаге, чёрным жирным {{---}} их родителей, курсивом {{---}} убывающие подпоследовательности (в случаях, когда мы их рассматриваем) или претендентов на добавление к ним правого ребёнка (когда рассматривается вершина, нарушающая убывающую последовательность).
 
+
{| style="background-color:#CCC;margin:0.5px"
- для каждого номера, нарушающего убывающую последовательность, ищем вершину с наибольшим значением, не превосходящим его, среди вершин без правого потомка и к этому элементу подвешиваем вершину с таким номером в качестве правого сына.
+
!style="background-color:#EEE"| Состояние
 
+
последовательности
Первое число последовательности всегда находится в корне, так как вывод ключей вершин начинался с него.
+
!style="background-color:#EEE"| Действие
 
+
!style="background-color:#EEE"| Пояснение
Разберём алгоритм на примере последовательности для приведённого выше дерева. Она выглядит так: ''8 2 1 4 3 5''. Сначала в корень записывается ''8''. Затем его левым сыном становится вершина с номером ''2'', а её левым сыном - ''1''. Следующее значение - ''4'' - уже нарушает убывающую подпоследовательность. Подберём для него вершину, где лежит значение, меньшее его, причём такая вершина максимальна (в противном случае он будет превосходить и прародителя, находясь в его левом поддереве, а это противоречит определению дерева поиска). Это узел с числом ''2''. Сделаем его правым сыном рассматриваемую вершину. Затем снова дадим левых потомков последней добавленной вершине, опять же, пока не найдём ключ, нарушающий порядок убывания. В нашем случае в дерево дописывается ''3''. Для следующего значения снова ищем родителя, для которого он станет правым сыном. Это значение равно ''4''. Добавляем ''5'' как правого сына для вершины ''4''. Итак, мы построили дерево.
+
|-
 +
|style="background-color:#FFF;padding:2px 10px"|  <span style="color:red">'''8'''</span> 2 1 4 3 5
 +
|style="background-color:#FFF;padding:2px 10px"| Делаем вершину корнем.
 +
|style="background-color:#FFF;padding:2px 10px"| ''Первая вершина всегда будет корнем, так как вывод начинался с него.''
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| '''''8''''' <span style="color:red">'''''2'''''</span> ''1'' 4 3 5
 +
|rowspan=2 style="background-color:#FFF;padding:2px 10px"|Находим убывающую подпоследовательность. Каждую вершину подвешиваем к последней из взятых ранее в качестве левого сына.
 +
|rowspan=2 style="background-color:#FFF;padding:2px 10px"| ''Каждая последующая вершина становится левым сыном предыдущей, так как выводя ключи, мы двигались по дереву поиска влево, пока есть вершины.''
 +
|-
 +
| style="background-color:#FFF;padding:2px 10px"| ''8 '''2''''' <span style="color:red">'''''1'''''</span> 4 3 5
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| ''8 '''2''''' 1 <span style="color:red">'''4'''</span> 3 5
 +
|style="background-color:#FFF;padding:2px 10px"| Для вершины, нарушившей убывающую последовательность, ищем максимальное значение, меньшее его. В данном случае оно равно <tex>\mathtt{2}</tex>. Затем добавляем вершину.
 +
|style="background-color:#FFF;padding:2px 10px"| ''На моменте вывода следующего номера процедура обратилась уже к какому-то из правых поддеревьев, так как влево идти уже некуда. Значит, нам необходимо найти узел, для которого данная вершина являлась бы правым сыном. Очевидно, что в её родителе не может лежать значение, которое больше её ключа. Но эту вершину нельзя подвесить и к меньшим, иначе нашёлся бы более старший предок, также хранящий какое-то значение, которое меньше, чем в исследуемой. Для этого предка вершина бы попала в левое поддерево. И тогда возникает противоречие с определением дерева поиска. Отсюда следует, что родитель определяется единственным образом {{---}} он хранит максимум среди ключей, не превосходящих значения в подвешиваемой вершине, что и требовалось доказать.''  
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| 8 2 1 '''''4''''' <span style="color:red">'''''3'''''</span> 5
 +
|style="background-color:#FFF;padding:2px 10px"| Находим убывающую подпоследовательность. Каждую вершину подвешиваем к последней из взятых ранее в качестве левого сына.
 +
|style="background-color:#FFF;padding:2px 10px"| ''Зайдя в правое поддерево, процедура обхода снова до упора начала двигаться влево, поэтому действуем аналогичным образом.''
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| ''8'' 2 1 '''''4''''' 3 <span style="color:red">'''5'''</span>
 +
|style="background-color:#FFF;padding:2px 10px"| Для этой вершины ищем максимальное значение, меньшее его. Затем добавляем вершину.
 +
|style="background-color:#FFF;padding:2px 10px"| ''Здесь процедура снова обратилась к правому поддереву. Рассуждения аналогичны. Ключ родителя этой вершины равен <tex>\mathtt{4}</tex>.''  
 +
|}
  
 
==См. также==
 
==См. также==
Строка 270: Строка 316:
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Красно-черное дерево]]
 
* [[Красно-черное дерево]]
     
+
* [[АВЛ-дерево]]
 +
 
 
==Источники информации==
 
==Источники информации==
 
* [https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0 Википедия {{---}} Двоичное дерево поиска]
 
* [https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0 Википедия {{---}} Двоичное дерево поиска]

Текущая версия на 19:21, 4 сентября 2022

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

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

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

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

struct Node:
  T key                    // ключ узла
  Node left                // указатель на левого потомка
  Node right               // указатель на правого потомка
  Node parent              // указатель на предка

Обход дерева поиска

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

  • [math]\mathrm{inorderTraversal}[/math] — обход узлов в отсортированном порядке,
  • [math]\mathrm{preorderTraversal}[/math] — обход узлов в порядке: вершина, левое поддерево, правое поддерево,
  • [math]\mathrm{postorderTraversal}[/math] — обход узлов в порядке: левое поддерево, правое поддерево, вершина.
func inorderTraversal(x : Node):
   if x != null
      inorderTraversal(x.left)
      print x.key
      inorderTraversal(x.right)

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

func preorderTraversal(x : Node)
   if x != null
      print x.key
      preorderTraversal(x.left)
      preorderTraversal(x.right)

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

func postorderTraversal(x : Node)
   if x != null
      postorderTraversal(x.left)
      postorderTraversal(x.right)
      print x.key

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

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

Поиск элемента

Поиск элемента 4

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

Node search(x : Node, k : T):
   if x == null or k == x.key
      return x
   if k < x.key
      return search(x.left, k)
   else
      return search(x.right, k)

Поиск минимума и максимума

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

Node minimum(x : Node):
  if x.left == null
     return x
  return minimum(x.left)
Node maximum(x : Node):
  if x.right == null
     return x
  return maximum(x.right)

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

Поиск следующего и предыдущего элемента

Реализация с использованием информации о родителе

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

Node next(x : Node):
   if x.right != null
      return minimum(x.right)
   y = x.parent
   while y != null and x == y.right
      x = y
      y = y.parent
   return y
Node prev(x : Node):
   if x.left != null
      return maximum(x.left)
   y = x.parent
   while y != null and x == y.left
      x = y
      y = y.parent
   return y

Обе операции выполняются за время [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]. Перейдем к нужному поддереву и повторим те же самые действия.
Аналогично реализуется операция поиска предыдущего элемента.

Node next(x : T):
   Node current = root, successor = null                // root — корень дерева
   while current != null
      if current.key > x
         successor = current
         current = current.left
      else
         current = current.right
   return successor

Вставка

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

Реализация с использованием информации о родителе

func insert(x : Node, z : Node):            // x — корень поддерева, z — вставляемый элемент
   while x != null
     if z.key > x.key
        if x.right != null
           x = x.right
        else
           z.parent = x
           x.right = z
           break
     else if z.key < x.key
        if x.left != null
           x = x.left
        else
           z.parent = x
           x.left = z
           break

Реализация без использования информации о родителе

Node insert(x : Node, z : T):               // x — корень поддерева, z — вставляемый ключ
   if x == null 
      return Node(z)                        // подвесим Node с key = z
   else if z < x.key
      x.left = insert(x.left, z)
   else if z > x.key
      x.right = insert(x.right, z)
   return x

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

Удаление

Нерекурсивная реализация

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

Случай Иллюстрация
Удаление листа Bst del1.png
Удаление узла с одним дочерним узлом Bst del2.png
Удаление узла с двумя дочерними узлами Bst del3.png
func delete(t : Node, v : Node):                 // [math]t[/math] — дерево, [math]v[/math] — удаляемый элемент
   p = v.parent                                  // предок удаляемого элемента
   if v.left == null and v.right == null         // первый случай: удаляемый элемент - лист
     if p.left == v
       p.left = null
     if p.right == v
       p.right = null
   else if v.left == null or v.right == null     // второй случай: удаляемый элемент имеет одного потомка
       if v.left == null                 
           if p.left == v
             p.left = v.right
           else
             p.right = v.right
           v.right.parent = p 
       else
           if p.left == v
               p.left = v.left
           else
               p.right = v.left
           v.left.parent = p
   else                                          // третий случай: удаляемый элемент имеет двух потомков
     successor = next(v, t)                   
     v.key = successor.key
     if successor.parent.left == successor
       successor.parent.left = successor.right
       if successor.right != null
         successor.right.parent = successor.parent
     else
       successor.parent.right = successor.right
       if successor.right != null
         successor.right.parent = successor.parent

Рекурсивная реализация

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

Node delete(root : Node, z : T):               // корень поддерева, удаляемый ключ
  if root == null
    return root
  if z < root.key
    root.left = delete(root.left, z)
  else if z > root.key
    root.right = delete(root.right, z)
  else if root.left != null and root.right != null
    root.key = minimum(root.right).key
    root.right = delete(root.right, root.key)
  else
    if root.left != null
      root = root.left
    else if root.right != null
      root = root.right
    else
      root = null
  return root

Задачи о бинарном дереве поиска

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

Задача:
Определить, является ли заданное двоичное дерево деревом поиска.
Пример дерева, для которого недостаточно проверки лишь его соседних вершин

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

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

bool isBinarySearchTree(root: Node):                    // Здесь root — корень заданного двоичного дерева.

  bool check(v : Node, min: T, max: T):                 // min и max — минимально и максимально допустимые значения в вершинах поддерева.
    if v == null                    return true
    if v.key <= min or max <= v.key return false
    return check(v.left, min, v.key) and check(v.right, v.key, max)

  return check(root, [math] -\infty [/math], [math] \infty [/math])

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

Задачи на поиск максимального BST в заданном двоичном дереве

Задача:
Найти в данном дереве такую вершину, что она будет корнем поддерева поиска с наибольшим количеством вершин.

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

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

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

int count(root: Node):                 // root — корень заданного двоичного дерева.

  int cnt(v: Node):
    if v == null
      v.kol = 0
      return = 0
    if cnt(v.left) != -1 and cnt(v.right) != -1
      if v.left == null and v.right == null
        v.min = v.key
        v.max = v.key
        v.kol = 1
        return 1
      if v.left == null
        if v.right.max > v.key
          v.min = v.key
          v.kol = cnt(v.right) + 1
          return v.kol
      if v.right == null
        if v.left.min < v.key
          v.max = v.key
          v.kol = cnt(v.left) + 1
          return v.kol
      if v.left.min < v.key and v.right.max > v.key 
        v.min = v.left.min
        v.max = v.right.max
        v.kol = v.left.kol + v.right.kol + 1
        v.kol = cnt(v.left) + cnt(v.right) + 1
        return v.kol
    return -1

  return cnt(root)

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

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

Задача:
Восстановить дерево по последовательности, выведенной после выполнения процедуры [math]\mathrm{preorderTraversal}[/math].
Восстановление дерева поиска по последовательности ключей

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

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


Разберём алгоритм на примере последовательности [math]\mathtt{8}[/math] [math]\mathtt{2}[/math] [math]\mathtt{1}[/math] [math]\mathtt{4}[/math] [math]\mathtt{3}[/math] [math]\mathtt{5}[/math].

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

Состояние

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

Действие Пояснение
8 2 1 4 3 5 Делаем вершину корнем. Первая вершина всегда будет корнем, так как вывод начинался с него.
8 2 1 4 3 5 Находим убывающую подпоследовательность. Каждую вершину подвешиваем к последней из взятых ранее в качестве левого сына. Каждая последующая вершина становится левым сыном предыдущей, так как выводя ключи, мы двигались по дереву поиска влево, пока есть вершины.
8 2 1 4 3 5
8 2 1 4 3 5 Для вершины, нарушившей убывающую последовательность, ищем максимальное значение, меньшее его. В данном случае оно равно [math]\mathtt{2}[/math]. Затем добавляем вершину. На моменте вывода следующего номера процедура обратилась уже к какому-то из правых поддеревьев, так как влево идти уже некуда. Значит, нам необходимо найти узел, для которого данная вершина являлась бы правым сыном. Очевидно, что в её родителе не может лежать значение, которое больше её ключа. Но эту вершину нельзя подвесить и к меньшим, иначе нашёлся бы более старший предок, также хранящий какое-то значение, которое меньше, чем в исследуемой. Для этого предка вершина бы попала в левое поддерево. И тогда возникает противоречие с определением дерева поиска. Отсюда следует, что родитель определяется единственным образом — он хранит максимум среди ключей, не превосходящих значения в подвешиваемой вершине, что и требовалось доказать.
8 2 1 4 3 5 Находим убывающую подпоследовательность. Каждую вершину подвешиваем к последней из взятых ранее в качестве левого сына. Зайдя в правое поддерево, процедура обхода снова до упора начала двигаться влево, поэтому действуем аналогичным образом.
8 2 1 4 3 5 Для этой вершины ищем максимальное значение, меньшее его. Затем добавляем вершину. Здесь процедура снова обратилась к правому поддереву. Рассуждения аналогичны. Ключ родителя этой вершины равен [math]\mathtt{4}[/math].

См. также

Источники информации