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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (англоязычные термины, тире)
м
Строка 4: Строка 4:
 
=== Обход дерева поиска ===
 
=== Обход дерева поиска ===
 
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
 
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
−
* inorderTraversal {{---}} обход узлов в отсортированном порядке
+
* <tex>\mathrm{inorderTraversal}</tex> {{---}} обход узлов в отсортированном порядке
−
* prefixTraversal {{---}} обход узлов в порядке: вершина, левое поддерево, правое поддерево
+
* <tex>\mathrm{preorderTraversal}</tex> {{---}} обход узлов в порядке: вершина, левое поддерево, правое поддерево
−
* postfixTraversal {{---}} обход узлов в порядке: левое поддерево, правое поддерево, вершина
+
* <tex>\mathrm{postorderTraversal}</tex> {{---}} обход узлов в порядке: левое поддерево, правое поддерево, вершина
−
  '''inorderTraversal'''(Node x)
+
  inorderTraversal('''Node''' x)
 
     '''if''' x != null
 
     '''if''' x != null
−
       '''inorderTraversal'''(x.left)
+
       inorderTraversal(x.left)
−
       '''print'''(x.key)
+
       '''print''' x.key
−
       '''inorderTraversal'''(x.right)
+
       inorderTraversal(x.right)
 
Корректность данного алгоритма следует из свойств бинарного дерева поиска.  
 
Корректность данного алгоритма следует из свойств бинарного дерева поиска.  
−
  '''prefixTraversal'''(Node x)
+
  preorderTraversal('''Node''' x)
 
     '''if''' x != null
 
     '''if''' x != null
−
       '''print'''(x.key)
+
       '''print''' x.key
−
       '''prefixTraversal'''(x.left)
+
       preorderTraversal(x.left)
−
       '''prefixTraversal'''(x.right)
+
       preorderTraversal(x.right)
  
−
  '''postfixTraversal'''(Node x)
+
  postfixTraversal('''Node''' x)
 
     '''if''' x != null
 
     '''if''' x != null
−
       '''postfixTraversal'''(x.left)
+
       postorderTraversal(x.left)
−
       '''postfixTraversal'''(x.right)
+
       postorderTraversal(x.right)
−
       '''print'''(x.key)
+
       '''print''' x.key
 
Данные алгоритмы выполняют обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева.  
 
Данные алгоритмы выполняют обход за время <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> {{---}} высота дерева.
−
  Node '''search'''(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 search'''(x.left, k)
+
       '''return''' search(x.left, k)
 
     '''else'''
 
     '''else'''
−
       '''return search'''(x.right, k)
+
       '''return''' search(x.right, k)
  
 
=== Поиск минимума и максимума ===
 
=== Поиск минимума и максимума ===
−
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям left от корня дерева, пока не встретится значение null. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.
+
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям <tex>left</tex> от корня дерева, пока не встретится значение <tex>null</tex>. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.
−
  Node '''minimum'''(Node x)
+
  '''Node''' minimum('''Node''' x)
 
   '''if''' x.left == null
 
   '''if''' x.left == null
 
       '''return''' x
 
       '''return''' x
−
   '''return minimum'''(x.left)
+
   '''return''' minimum(x.left)
  
−
  Node '''maximum'''(Node x)
+
  '''Node''' maximum('''Node''' x)
 
   '''if''' x.right == null
 
   '''if''' x.right == null
 
       '''return''' x
 
       '''return''' x
−
   '''return maximum'''(x.right)
+
   '''return''' maximum(x.right)
 
Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время <tex>O(h)</tex>.
 
Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время <tex>O(h)</tex>.
  
 
=== Поиск следующего и предыдущего элемента ===
 
=== Поиск следующего и предыдущего элемента ===
 
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.  
 
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.  
−
  Node '''next'''(Node x)
+
  '''Node''' next('''Node''' x)
 
     '''if''' x.right != null
 
     '''if''' x.right != null
−
       '''return minimum'''(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
Строка 60: Строка 60:
 
     '''return''' y
 
     '''return''' y
  
−
  Node '''prev'''(Node x)
+
  '''Node''' prev('''Node''' x)
 
     '''if''' x.left != null
 
     '''if''' x.left != null
−
       '''return maximum'''(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
Строка 71: Строка 71:
 
=== Вставка ===
 
=== Вставка ===
 
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
 
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
−
  '''insert'''(Node x, Node z) // корень поддерева, вставляемый элемент
+
  insert('''Node''' x, '''Node''' z)           <font color="green">// корень поддерева, вставляемый элемент</font>
 
     '''if''' z.key > x.key
 
     '''if''' z.key > x.key
 
       '''if''' x.right != null
 
       '''if''' x.right != null
−
           '''insert'''(x.right, z)
+
           insert(x.right, z)
 
       '''else'''
 
       '''else'''
 
           z.parent = x;
 
           z.parent = x;
Строка 80: Строка 80:
 
     '''else'''
 
     '''else'''
 
       '''if''' x.left != null
 
       '''if''' x.left != null
−
           '''insert'''(x.left, z)
+
           insert(x.left, z)
 
       '''else'''
 
       '''else'''
 
           z.parent = x;
 
           z.parent = x;
Строка 101: Строка 101:
 
  | [[Файл:Bst_del3.png‎|900px]]
 
  | [[Файл:Bst_del3.png‎|900px]]
 
  |}
 
  |}
−
  '''delete'''(Node root, Node z) //корень поддерева, удаляемый элемент
+
  delete('''Node''' root, '''Node''' z)                         <font color="green">// корень поддерева, удаляемый элемент</font>
−
   Node x, y //x - элемент, который нужно поместить вместо y
+
   '''Node''' x, y                                       <font color="green">// x - элемент, который нужно поместить вместо y</font>
−
   '''if''' z.left != null '''and''' z.right != null //если z имеет двух детей
+
   '''if''' z.left != null '''and''' z.right != null           <font color="green">// если z имеет двух детей</font>
−
       y = '''next'''(z) //y - элемент, следующий за удаляемым, x - null
+
       y = '''next'''(z)                                 <font color="green">// y - элемент, следующий за удаляемым, x - null</font>
 
       x = null
 
       x = null
 
       '''if''' y == y.parent.left
 
       '''if''' y == y.parent.left
Строка 110: Строка 110:
 
       '''else'''
 
       '''else'''
 
         y.parent.right = null
 
         y.parent.right = null
−
       z.key = y.key //подвешиваем y вместо z
+
       z.key = y.key                               <font color="green">// подвешиваем y вместо z</font>
 
       z.data = y.data
 
       z.data = y.data
−
   '''else if''' z.left != null '''or''' z.right != null //eсли z имеет одного ребенка
+
   '''else if''' z.left != null '''or''' z.right != null       <font color="green">// eсли z имеет одного ребенка</font>
−
       y = z //y - удаляемый элемент
+
       y = z                                       <font color="green">// y - удаляемый элемент</font>
−
       '''if''' y.left != null //x - ребенок y
+
       '''if''' y.left != null                           <font color="green">// x - ребенок y</font>
−
         x = y.left
+
         x = y.left            
 
       '''else'''
 
       '''else'''
 
         x = y.right
 
         x = y.right
−
   '''else''' //если z не имеет детей
+
   '''else'''                                           <font color="green">// если z не имеет детей</font>
−
       y = z //y - удаляемый элемент, x - null
+
       y = z                                       <font color="green">// y - удаляемый элемент, x - null</font>
 
       x = null
 
       x = null
−
   '''if''' x != null //подвешиваем x вместо y
+
   '''if''' x != null                                   <font color="green">// подвешиваем x вместо y</font>
−
       x.parent = y.parent
+
       x.parent = y.parent          
 
   '''if''' y.parent == null
 
   '''if''' y.parent == null
 
       root = x
 
       root = x

Версия 13:07, 24 мая 2015

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

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

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

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

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

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

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

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

postfixTraversal(Node x)
   if x != null
      postorderTraversal(x.left)
      postorderTraversal(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)

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

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

Node minimum(Node x)
  if x.left == null
     return x
  return minimum(x.left)

Node maximum(Node x)
  if x.right == null
     return x
  return maximum(x.right)

Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время [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)            // корень поддерева, вставляемый элемент
   if z.key > x.key
      if x.right != null
         insert(x.right, z)
      else
         z.parent = x;
         x.right = z;
   else
      if x.left != null
         insert(x.left, z)
      else
         z.parent = x;
         x.left = z;

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

Удаление

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

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

Ссылки

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

Литература

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

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