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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 267: Строка 267:
  
 
Алгоритм работает за <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===

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

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

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

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