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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 65: Строка 65:
 
=== Поиск следующего и предыдущего элемента ===
 
=== Поиск следующего и предыдущего элемента ===
 
====Реализация с использованием информации о родителе====
 
====Реализация с использованием информации о родителе====
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то предыдущий ему элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.  
+
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.  
 
  '''Node''' next(x : '''Node'''):
 
  '''Node''' next(x : '''Node'''):
 
     '''if''' x.right != ''null''
 
     '''if''' x.right != ''null''
Строка 84: Строка 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>
Строка 173: Строка 172:
 
           successor.right.parent = successor.parent
 
           successor.right.parent = successor.parent
 
       '''else'''
 
       '''else'''
         successor.parent.right = successor.left
+
         successor.parent.right = successor.right
         '''if''' successor.left != ''null''
+
         '''if''' successor.right != ''null''
 
           successor.right.parent = successor.parent
 
           successor.right.parent = successor.parent
  
 
====Рекурсивная реализация====
 
====Рекурсивная реализация====
При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить '''этот''' минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <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: Строка 188:
 
   '''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.key)
+
     root.right = delete(root.right, root.right.key)
 
   '''else'''
 
   '''else'''
 
     '''if''' root.left != ''null''
 
     '''if''' root.left != ''null''
 
       root = root.left
 
       root = root.left
     '''else if''' root.right != ''null''
+
     '''else'''
 
       root = root.right
 
       root = root.right
    '''else'''
 
      root = ''null''
 
 
   '''return''' root
 
   '''return''' root
  
Строка 211: Строка 208:
 
Функция принимает на вход исследуемую вершину, а также два значения: <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>.
 
Функция принимает на вход исследуемую вершину, а также два значения: <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>
+
  '''bool''' isBinarySearchTree(root: '''Node'''):                    <font color="green">// Здесь Tree заданное двоичное дерево.</font>
 
   
 
   
   '''bool''' check(v : '''Node''', min: '''T''', max: '''T'''):                 <font color="green">// min и max — минимально и максимально допустимые значения в вершинах поддерева.</font>
+
   '''bool''' check(v : '''Node''', min: '''T''', max: '''T'''):                   <font color="green">// min и max — минимально и максимально допустимые значения в вершинах поддерева.</font>
 
     '''if''' v == ''null''                    '''return''' ''true''
 
     '''if''' v == ''null''                    '''return''' ''true''
 
     '''if''' v.key <= min '''or''' max <= v.key '''return''' ''false''
 
     '''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(v.left, min, v.key) '''and''' check(v.right, v.key, max)
 
   
 
   
   '''return''' check(root, <tex> -\infty </tex>, <tex> \infty </tex>)
+
   '''return''' check(root, <tex> -\infty </tex>, <tex> \infty </tex>)                                       <font color="green">// root {{---}} корень дерева.</font>
  
 
Время работы алгоритма {{---}} <tex>O(n)</tex>, где <tex>n</tex> {{---}} количество вершин в дереве.
 
Время работы алгоритма {{---}} <tex>O(n)</tex>, где <tex>n</tex> {{---}} количество вершин в дереве.
Строка 225: Строка 222:
  
 
{{Задача
 
{{Задача
|definition = Найти в данном дереве такую вершину, что она будет корнем поддерева поиска с наибольшим количеством вершин.
+
|definition = Найти в данном дереве такую вершину, что поддерево, для которого она является корнем, будет максимальным деревом поиска.
 
}}
 
}}
 
Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за <tex>O(n^2)</tex>. Но её можно решить за <tex>O(n)</tex>, идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах:
 
Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за <tex>O(n^2)</tex>. Но её можно решить за <tex>O(n)</tex>, идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах:
Строка 234: Строка 231:
 
Введём <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>.
 
Введём <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>.
  
  '''int''' count(root: '''Node'''):                <font color="green">// root корень заданного двоичного дерева.</font>
+
  '''int''' count(root: '''Node'''):                <font color="green">// Tree заданное двоичное дерево.</font>
 
   
 
   
 
   '''int''' cnt(v: '''Node'''):
 
   '''int''' cnt(v: '''Node'''):
Строка 267: Строка 264:
  
 
Алгоритм работает за <tex>O(n)</tex>, так как мы прошлись по дереву два раза за время, равное количеству вершин.
 
Алгоритм работает за <tex>O(n)</tex>, так как мы прошлись по дереву два раза за время, равное количеству вершин.
 +
{{Задача
 +
|definition = Выделить в данном дереве наибольшее возможное количество соседних вершин, образующих дерево поиска.
 +
}}
 +
Рассмотрим каждую вершину дерева, предполагая, что она может быть корнем максимального поддерева поиска. Найдём для каждой из них количество всех вершин, которые могут находиться в таком поддереве. Максимальный из результатов, получаемых на каждом шаге, будем запоминать. Вместе с максимумом будем запоминать и соответствующую ему вершину. После того, как мы обошли всё дерево и нашли корень дерева поиска с наибольшим количеством вершин, при помощи обхода <tex>\mathrm{preorderTraversal}</tex> выводим все вершины на экран.
 +
 +
'''Node''' root(Tree[n]: '''Node''')          <font color="green">// Tree — заданное двоичное дерево.</font>
 +
  maxdp = -1
 +
  maxroot = ''null''
 +
  '''for''' u '''in''' Tree         
 +
    dp = dfs(u, <tex> -\infty </tex>, <tex> \infty </tex>)
 +
    '''if''' dp > maxdp
 +
      maxdp = dp
 +
      maxroot = u
 +
  '''return''' maxroot
 +
 +
Функция <tex>\mathtt{dfs}</tex> позволяет найти для каждой вершин максимально возможное количество узлов поддерева. На вход функции подаются сама анализируемая вершина и левая и правая границы интервала, в которой могут находиться значения в её поддереве. Начальные значения двух последних аргументов равны <tex> -\infty </tex> и <tex> \infty </tex> соответственно.
 +
 +
В основе функции также лежит [[Обход в глубину, цвета вершин|обход в глубину]]. Рекурсивная функция обходит всех существующих детей вершины, поданной на вход, и, если ребёнок не нарушает условия дерева поиска, она добавляет его в поддерево и анализирует его потомков. В этом случае роль <tex>v</tex> будет разыгрывать ребёнок, удовлетворяющий условию дерева поиска. Если он был левым сыном, то максимально возможному значению присваивается число, стоящее в его родителе, а минимальное возможное значение не изменяется. Наоборот, если он был правым сыном, увеличиваем минимум, а максимум оставляем тем же. В случае, когда левый или правый сын не удовлетворяет условию дерева поиска, этот узел не включается в искомое поддерево и дальше не рассматривается.
 +
 +
Функция возвращает значение переменной <tex>\mathtt{res}</tex>, где записано количество вершин поддерева.
 +
 +
'''int''' dfs(v: '''Node''', max: '''T''', min: '''T''')
 +
  res = 1
 +
  '''if''' v.left != ''null''
 +
    '''if''' v.left.key < v.key '''and''' v.left.key > max
 +
      res += dfs(v.left, v.left.key, min)
 +
  '''if''' v.right != ''null''
 +
    '''if''' v.right.key > v.key '''and''' v.right.key < min
 +
      res += dfs(v.left, max, v.left.key)
 +
  '''return''' res
 +
 +
Время работы алгоритма {{---}} <tex>O(n^2)</tex>. Существуют также алгоритмы, позволяющие найти поддерево за линейное время.
  
 
===Восстановление дерева по результату обхода preorderTraversal===
 
===Восстановление дерева по результату обхода preorderTraversal===
Строка 316: Строка 345:
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Красно-черное дерево]]
 
* [[Красно-черное дерево]]
* [[АВЛ-дерево]]
+
     
 
 
 
==Источники информации==
 
==Источники информации==
 
* [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 Википедия {{---}} Двоичное дерево поиска]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: