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

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

Внимание! Вы не авторизовались на сайте. Ваш 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
  
Строка 225: Строка 222:
  
 
{{Задача
 
{{Задача
|definition = Найти в данном дереве такую вершину, что она будет корнем поддерева поиска с наибольшим количеством вершин.
+
|definition = Найти в данном дереве такую вершину, что поддерево, для которого она является корнем, будет максимальным деревом поиска.
 
}}
 
}}
 
Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за <tex>O(n^2)</tex>. Но её можно решить за <tex>O(n)</tex>, идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах:
 
Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за <tex>O(n^2)</tex>. Но её можно решить за <tex>O(n)</tex>, идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах:
Строка 316: Строка 313:
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Красно-черное дерево]]
 
* [[Красно-черное дерево]]
* [[АВЛ-дерево]]
+
     
 
 
 
==Источники информации==
 
==Источники информации==
 
* [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 Википедия {{---}} Двоичное дерево поиска]

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

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

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

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