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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
== Операции в бинарном дереве поиска ==
 
== Операции в бинарном дереве поиска ==
 
=== Обход дерева поиска ===
 
=== Обход дерева поиска ===
−
Для вывода всех ключей бинарного дерева поиска в отсортированном порядке используется простой алгоритм (англ. ''inorder tree traversal'').
+
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
−
  inorderTreeWalk(Node x)
+
* inorderTraversal - обход узлов в отсортированном порядке
−
     if x != null
+
* prefixTraversal - обход узлов в порядке: вершина, левое поддерево, правое поддерево
−
       inorderTreeWalk(x.left)
+
* postfixTraversal - обход узлов в порядке: левое поддерево, правое поддерево, вершина
−
       print(x.key)
+
'''inorderTraversal'''(Node x)
−
       inorderTreeWalk(x.right)
+
    '''if''' x != null
−
Данный алгоритм выполняет обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева. Корректность данного алгоритма следует из свойств бинарного дерева поиска.  
+
      '''inorderTraversal'''(x.left)
 +
      '''print'''(x.key)
 +
      '''inorderTraversal'''(x.right)
 +
Корректность данного алгоритма следует из свойств бинарного дерева поиска.  
 +
  '''prefixTraversal'''(Node x)
 +
     '''if''' x != null
 +
       '''print'''(x.key)
 +
      '''prefixTraversal'''(x.left)
 +
       '''prefixTraversal'''(x.right)
 +
 
 +
'''postfixTraversal'''(Node x)
 +
    '''if''' x != null
 +
      '''postfixTraversal'''(x.left)
 +
       '''postfixTraversal'''(x.right)
 +
      '''print'''(x.key)
 +
Данные алгоритмы выполняют обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева.  
 
=== Поиск элемента ===
 
=== Поиск элемента ===
 
[[Файл:Bst search.png|thumb|318px|Поиск элемента 4]]
 
[[Файл:Bst search.png|thumb|318px|Поиск элемента 4]]
 
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
 
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
−
  treeSearch(Node x, key k)
+
  Node '''search'''(Node x, key k)
−
     if x == null or k == x.key
+
     '''if''' x == null '''or''' k == x.key
−
       return x
+
       '''return''' x
−
     if k < x.key
+
     '''if''' k < x.key
−
       return treeSearch(x.left, k)
+
       '''return search'''(x.left, k)
−
     else
+
     '''else'''
−
       return treeSearch(x.right, k)
+
       '''return search'''(x.right, k)
  
 
=== Поиск минимума и максимума ===
 
=== Поиск минимума и максимума ===
 
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям left от корня дерева, пока не встретится значение null. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.
 
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям left от корня дерева, пока не встретится значение null. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.
−
  treeMinimum(Node x)
+
  Node '''minimum'''(Node x)
−
   while x.left != null
+
   '''while''' x.left != null
 
       x = x.left
 
       x = x.left
−
   return x
+
   '''return''' x
  
−
  treeMaximum(Node x)
+
  Node '''maximum'''(Node x)
−
   while x.right != null
+
   '''while''' x.right != null
 
       x = x.right
 
       x = x.right
−
   return x
+
   '''return''' x
 
Данные функции принимают корень дерева, и возвращают минимальный(максимальный) элемент в дереве. Обе процедуры выполняются за время <tex>O(h)</tex>.
 
Данные функции принимают корень дерева, и возвращают минимальный(максимальный) элемент в дереве. Обе процедуры выполняются за время <tex>O(h)</tex>.
  
 
=== Поиск следующего и предыдущего элемента ===
 
=== Поиск следующего и предыдущего элемента ===
 
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.  
 
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.  
−
  treeNext(Node x)
+
  Node '''next'''(Node x)
−
     if x.right != null
+
     '''if''' x.right != null
−
       return treeMinimum(x.right)
+
       '''return minimum'''(x.right)
 
     y = x.parent
 
     y = x.parent
−
     while y != null and x == y.right
+
     '''while''' y != null '''and''' x == y.right
 
       x = y
 
       x = y
 
       y = y.parent
 
       y = y.parent
−
     return y
+
     '''return''' y
  
−
  treePrev(Node x)
+
  Node '''prev'''(Node x)
−
     if x.left != null
+
     '''if''' x.left != null
−
       return treeMaximum(x.left)
+
       '''return maximum'''(x.left)
 
     y = x.parent
 
     y = x.parent
−
     while y != null and x == y.left
+
     '''while''' y != null '''and''' x == y.left
 
       x = y
 
       x = y
 
       y = y.parent
 
       y = y.parent
−
     return y
+
     '''return''' y
 
Обе операции выполняются за время <tex>O(h)</tex>.
 
Обе операции выполняются за время <tex>O(h)</tex>.
 
=== Вставка ===
 
=== Вставка ===
−
Операция вставки работает аналогично поиску элемента, только при обнаружении нулевого указателя нужно подвесить на него вставляемый элемент. Приведем итеративную реализацию этого алгоритма.
+
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент. Приведем итеративную реализацию этого алгоритма.
−
  treeInsert(Node x, Node z) // корень дерева, вставляемый элемент
+
  '''insert'''(Node x, Node z) // корень дерева, вставляемый элемент
 
     Node y = null
 
     Node y = null
−
     while x != null
+
     '''while''' x != null
 
       y = x
 
       y = x
−
       if z.key > x.key
+
       '''if''' z.key > x.key
 
           x = x.right
 
           x = x.right
−
       else
+
       '''else'''
 
           x = x.left
 
           x = x.left
 
     z.parent = y
 
     z.parent = y
−
     if z.key > y.key
+
     '''if''' z.key > y.key
 
       y.right = z
 
       y.right = z
−
     else
+
     '''else'''
 
       y.left = z
 
       y.left = z
 
Время работы алгоритма <tex>O(h)</tex>.
 
Время работы алгоритма <tex>O(h)</tex>.
Строка 88: Строка 103:
 
  | [[Файл:Bst_del4.png‎]]   
 
  | [[Файл:Bst_del4.png‎]]   
 
  |}
 
  |}
−
  treeDelete(Node t, Node z) // корень дерева, удаляемый элемент
+
  '''delete'''(Node root, Node z) //корень дерева, удаляемый элемент
−
    Node x, y
+
  Node x, y
−
    if z.left == null or z.right == null
+
  '''if''' z.left == null '''or''' z.right == null //y - удаляемый элемент, если тот имеет не более одного ребенка
−
      y = z
+
      y = z
−
    else
+
  '''else''' //иначе - следующий за ним
−
      y = treeNext(z)
+
      y = '''next'''(z)
−
    if y.left != null
+
  '''if''' y.left != null //x - ребенок y
−
      x = y.left
+
      x = y.left
−
    else
+
  '''else'''
−
      x = y.right
+
      x = y.right
−
    if x != null
+
  '''if''' x != null //подвешиваем x вместо y
−
      x.parent = y.parent
+
      x.parent = y.parent
−
    if y.parent == null
+
  '''if''' y.parent == null
−
      t = x
+
      root = x
−
    else
+
  '''else'''
−
      if y == y.parent.left
+
      '''if''' y == y.parent.left
−
          y.parent.left = x
+
        y.parent.left = x
−
      else
+
      '''else'''
−
          y.parent.right = x
+
        y.parent.right = x
−
    if y != z
+
  '''if''' y != z //если y - не удаляемый, а следующий за ним, то меняем z на y
−
      z.key = y.key
+
      z.key = y.key
−
      z.data = y.data
+
      z.data = y.data
−
    return y
+
 
 +
== Ссылки ==
 +
[[Упорядоченное множество]]
 +
 
 +
[http://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 Двоичное дерево поиска]
 
        
 
        
 
== Литература ==
 
== Литература ==

Версия 16:57, 10 июня 2012

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

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

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

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

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

  • inorderTraversal - обход узлов в отсортированном порядке
  • prefixTraversal - обход узлов в порядке: вершина, левое поддерево, правое поддерево
  • postfixTraversal - обход узлов в порядке: левое поддерево, правое поддерево, вершина
inorderTraversal(Node x)
   if x != null
      inorderTraversal(x.left)
      print(x.key)
      inorderTraversal(x.right)

Корректность данного алгоритма следует из свойств бинарного дерева поиска. 

prefixTraversal(Node x)
   if x != null
      print(x.key)
      prefixTraversal(x.left)
      prefixTraversal(x.right)

postfixTraversal(Node x)
   if x != null
      postfixTraversal(x.left)
      postfixTraversal(x.right)
      print(x.key)

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

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

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

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

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

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

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

Node minimum(Node x)
  while x.left != null
     x = x.left
  return x

Node maximum(Node x)
  while x.right != null
     x = x.right
  return x

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

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

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

Node next(Node x)
   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(Node x)
   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].

Вставка

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

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

Время работы алгоритма [math]O(h)[/math].

Удаление

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

Случай Иллюстрация
Удаление листа Bst del1.png
Удаление узла с одним дочерним узлом Bst del2.png
Удаление узла с двумя дочерними узлами Bst del3.png
Удаление корня Bst del4.png 
delete(Node root, Node z) 			//корень дерева, удаляемый элемент
  Node x, y					
  if z.left == null or z.right == null		//y - удаляемый элемент, если тот имеет не более одного ребенка
     y = z					
  else						//иначе - следующий за ним
     y = next(z)				
  if y.left != null				//x - ребенок y
     x = y.left				
  else
     x = y.right
  if x != null					//подвешиваем x вместо y
     x.parent = y.parent			
  if y.parent == null
     root = x
  else
     if y == y.parent.left
        y.parent.left = x
     else
        y.parent.right = x
  if y != z					//если y - не удаляемый, а следующий за ним, то меняем z на y
     z.key = y.key				
     z.data = y.data

Ссылки

Упорядоченное множество

Двоичное дерево поиска

Литература

1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дерево_поиска,_наивная_реализация&oldid=24751»