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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Обход дерева поиска)
Строка 2: Строка 2:
 
Бинарное дерево поиска обладает следующим свойством: если <tex>x</tex> {{---}} узел бинарного дерева с ключом <tex>k</tex>, то все узлы в левом поддереве должны иметь ключи, меньшие <tex>k</tex>, а в правом поддереве большие <tex>k</tex>.
 
Бинарное дерево поиска обладает следующим свойством: если <tex>x</tex> {{---}} узел бинарного дерева с ключом <tex>k</tex>, то все узлы в левом поддереве должны иметь ключи, меньшие <tex>k</tex>, а в правом поддереве большие <tex>k</tex>.
 
== Операции в бинарном дереве поиска ==
 
== Операции в бинарном дереве поиска ==
 +
Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:
 +
'''Node''':
 +
  '''T''' key                    <font color="green">// ключ узла</font>
 +
  '''Node''' left                <font color="green">// указатель на левого потомка</font>
 +
  '''Node''' right              <font color="green">// указатель на правого потомка</font>
 +
  '''Node''' parent              <font color="green">// указатель на предка</font>
 +
 
=== Обход дерева поиска ===
 
=== Обход дерева поиска ===
 
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
 
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
Строка 7: Строка 14:
 
* <tex>\mathrm{preorderTraversal}</tex> {{---}} обход узлов в порядке: вершина, левое поддерево, правое поддерево,
 
* <tex>\mathrm{preorderTraversal}</tex> {{---}} обход узлов в порядке: вершина, левое поддерево, правое поддерево,
 
* <tex>\mathrm{postorderTraversal}</tex> {{---}} обход узлов в порядке: левое поддерево, правое поддерево, вершина.
 
* <tex>\mathrm{postorderTraversal}</tex> {{---}} обход узлов в порядке: левое поддерево, правое поддерево, вершина.
  inorderTraversal('''Node''' x)
+
  '''func''' inorderTraversal(x : '''Node'''):
 
     '''if''' x != ''null''
 
     '''if''' x != ''null''
 
       inorderTraversal(x.left)
 
       inorderTraversal(x.left)
Строка 14: Строка 21:
 
При выполнении данного обхода вершины будут выведены в следующем порядке: ''1 3 4 6 7 8 10 13 14''.
 
При выполнении данного обхода вершины будут выведены в следующем порядке: ''1 3 4 6 7 8 10 13 14''.
  
  preorderTraversal('''Node''' x)
+
  '''func''' preorderTraversal(x : '''Node''')
 
     '''if''' x != ''null''
 
     '''if''' x != ''null''
 
       '''print''' x.key
 
       '''print''' x.key
Строка 21: Строка 28:
 
При выполнении данного обхода вершины будут выведены в следующем порядке: ''8 3 1 6 4 7 10 14 13''.
 
При выполнении данного обхода вершины будут выведены в следующем порядке: ''8 3 1 6 4 7 10 14 13''.
  
  postorderTraversal('''Node''' x)
+
  '''func''' postorderTraversal(x : '''Node''')
 
     '''if''' x != ''null''
 
     '''if''' x != ''null''
 
       postorderTraversal(x.left)
 
       postorderTraversal(x.left)
 
       postorderTraversal(x.right)
 
       postorderTraversal(x.right)
 
       '''print''' x.key
 
       '''print''' x.key
При выполнении данного обхода вершины будут выведены в следующем порядке: ''1 4 7 6 3 13 14 10 8 ''
+
При выполнении данного обхода вершины будут выведены в следующем порядке: ''1 4 7 6 3 13 14 10 8''.
  
 
Данные алгоритмы выполняют обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева.
 
Данные алгоритмы выполняют обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева.
  
 
=== Поиск элемента ===
 
=== Поиск элемента ===
[[Файл:Bst search.png|thumb|right|318px|Поиск элемента 4]]
+
[[Файл:Bst search.png|frame|right|318px|Поиск элемента 4]]
 
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
 
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
  '''Node''' search('''Node''' x, '''key''' k)
+
<div style="width: 65%">
 +
  '''Node''' search(x : '''Node''', k : '''T'''):
 
     '''if''' x == ''null'' '''or''' k == x.key
 
     '''if''' x == ''null'' '''or''' k == x.key
 
       '''return''' x
 
       '''return''' x
Строка 40: Строка 48:
 
     '''else'''
 
     '''else'''
 
       '''return''' search(x.right, k)
 
       '''return''' search(x.right, k)
 +
</div>
 +
  
 
=== Поиск минимума и максимума ===
 
=== Поиск минимума и максимума ===
 
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям <tex>left</tex> от корня дерева, пока не встретится значение <tex>null</tex>. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.
 
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям <tex>left</tex> от корня дерева, пока не встретится значение <tex>null</tex>. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.
  '''Node''' minimum('''Node''' x)
+
  '''Node''' minimum(x : '''Node'''):
 
   '''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(x : '''Node'''):
 
   '''if''' x.right == ''null''
 
   '''if''' x.right == ''null''
 
       '''return''' x
 
       '''return''' x
Строка 57: Строка 67:
 
====Реализация с использованием информации о родителе====
 
====Реализация с использованием информации о родителе====
 
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.  
 
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.  
  '''Node''' next('''Node''' x)
+
  '''Node''' next(x : '''Node'''):
 
     '''if''' x.right != ''null''
 
     '''if''' x.right != ''null''
 
       '''return''' minimum(x.right)
 
       '''return''' minimum(x.right)
Строка 66: Строка 76:
 
     '''return''' y
 
     '''return''' y
  
  '''Node''' prev('''Node''' x)
+
  '''Node''' prev(x : '''Node'''):
 
     '''if''' x.left != ''null''
 
     '''if''' x.left != ''null''
 
       '''return''' maximum(x.left)
 
       '''return''' maximum(x.left)
Строка 77: Строка 87:
 
====Реализация без использования информации о родителе====
 
====Реализация без использования информации о родителе====
 
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то начнем поиск от корня. Спускаемся вниз по дереву. Если значение узла больше значения в рассматриваемом в данный момент узле, перейдем в правое поддерево, иначе перейдем в левое поддерево. Аналогично выполняется поиск предыдущего элемента. Рекурсивные реализации обеих функций:
 
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то начнем поиск от корня. Спускаемся вниз по дереву. Если значение узла больше значения в рассматриваемом в данный момент узле, перейдем в правое поддерево, иначе перейдем в левое поддерево. Аналогично выполняется поиск предыдущего элемента. Рекурсивные реализации обеих функций:
  '''Node''' next('''Node''' x, '''Node''' t)        <font color="green">// x - элемент, для которого ищем следующий, t - текущее поддерево</font>
+
  '''Node''' next(x : '''Node''', t : '''Node'''):         <font color="green">// x {{---}} элемент, для которого ищем следующий, t {{---}} текущее поддерево</font>
 
     '''if''' t != ''null''
 
     '''if''' t != ''null''
 
       '''Node''' successor = next(x, t.left)
 
       '''Node''' successor = next(x, t.left)
Строка 88: Строка 98:
 
     '''return''' ''null''
 
     '''return''' ''null''
  
  '''Node''' prev('''Node''' x, '''Node''' t)        <font color="green">// x - элемент, для которого ищем предыдущий, t - текущее поддерево</font>
+
  '''Node''' prev(x : '''Node''', t : '''Node'''):         <font color="green">// x {{---}} элемент, для которого ищем предыдущий, t {{---}} текущее поддерево</font>
 
     '''if''' t != ''null''
 
     '''if''' t != ''null''
 
       '''Node''' ancestor = prev(x, t.right)
 
       '''Node''' ancestor = prev(x, t.right)
Строка 101: Строка 111:
 
=== Вставка ===
 
=== Вставка ===
 
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
 
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
  insert('''Node''' x, '''Node''' z)            <font color="green">// x - корень поддерева, z - вставляемый элемент</font>
+
====Реализация с использованием информации о родителе====
 +
  '''func''' insert(x : '''Node''', z : '''Node'''):           <font color="green">// x {{---}} корень поддерева, z {{---}} вставляемый элемент</font>
 
     '''if''' z.key > x.key
 
     '''if''' z.key > x.key
 
       '''if''' x.right != ''null''
 
       '''if''' x.right != ''null''
Строка 114: Строка 125:
 
           z.parent = x
 
           z.parent = x
 
           x.left = z
 
           x.left = z
 +
====Реализация без использования информации о родителе====
 +
'''func''' insert(x : '''Node''', z : '''Node'''):            <font color="green">// x {{---}} корень поддерева, z {{---}} вставляемый элемент</font>
 +
    '''if''' z.key <= x.key
 +
      '''if''' x.left == ''null''
 +
          x.left = z
 +
      '''else'''
 +
          insert(x.left, z)
 +
    '''else'''
 +
      '''if''' x.right == ''null''
 +
          x.right = z
 +
      '''else'''
 +
          insert(x.right, z)
  
Время работы алгоритма {{---}} <tex>O(h)</tex>.
+
Время работы алгоритма для обеих реализаций {{---}} <tex>O(h)</tex>.
  
 
=== Удаление ===
 
=== Удаление ===
 
====Нерекурсивная реализация====
 
====Нерекурсивная реализация====
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на <tex>null</tex>. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка) и переместить его на место удаляемого узла. Время работы алгоритма {{---}} <tex>O(h)</tex>.
+
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на <tex>null</tex>. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка), его правого потомка подвесить на место найденного элемента, а удаляемый узел заменить найденным узлом. Таким образом, свойство бинарного дерева поиска не будет нарушено. Время работы алгоритма {{---}} <tex>O(h)</tex>.
 
{| border="1" cellpadding="5" cellspacing="0"  
 
{| border="1" cellpadding="5" cellspacing="0"  
 
  !Случай
 
  !Случай
Строка 133: Строка 156:
 
  | [[Файл:Bst_del3.png‎|900px]]
 
  | [[Файл:Bst_del3.png‎|900px]]
 
  |}
 
  |}
  delete('''Node''' root, '''Node''' z)                         <font color="green">// корень поддерева, удаляемый элемент</font>
+
  '''func''' delete(t : '''Node''', v : '''Node'''):                <font color="green">// дерево и удаляемый элемент</font>
  '''Node''' x, y                                      <font color="green">// x - элемент, который нужно поместить вместо y</font>
+
    p = v.parent                                  <font color="green">// предок удаляемого элемента</font>
  '''if''' z.left != ''null'' '''and''' z.right != ''null''           <font color="green">// если z имеет двух детей</font>
+
    '''if''' v.left == ''null'' '''and''' v.right == ''null''         <font color="green">// первый случай: удаляемый элемент - лист</font>
       y = '''next'''(z)                                  <font color="green">// y - элемент, следующий за удаляемым, x - null</font>
+
       '''if''' p.left == v
      x = ''null''
+
        p.left = ''null''
       '''if''' y == y.parent.left
+
       '''if''' p.right == v
        y.parent.left = ''null''
+
        p.right = ''null''
      '''else'''
+
    '''else'''
        y.parent.right = ''null''
+
        '''if''' v.left == ''null'' '''or''' v.right == ''null''     <font color="green">// второй случай: удаляемый элемент имеет одного потомка</font>
      z.key = y.key                                <font color="green">// подвешиваем y вместо z</font>
+
            '''if''' v.left == ''null''                
      z.data = y.data
+
                '''if''' p.left == v
  '''else if''' z.left != ''null'' '''or''' z.right != ''null''       <font color="green">// eсли z имеет одного ребенка</font>
+
                  p.left = v.right
      y = z                                        <font color="green">// y - удаляемый элемент</font>
+
                '''else'''
      '''if''' y.left != ''null''                            <font color="green">// x - ребенок y</font>
+
                  p.right = v.right
        x = y.left            
+
                v.right.parent = p
      '''else'''
+
            '''else'''
        x = y.right
+
                '''if''' p.left == v
  '''else'''                                           <font color="green">// если z не имеет детей</font>
+
                    p.left = v.left
      y = z                                        <font color="green">// y - удаляемый элемент, x - null</font>
+
                '''else'''
      x = ''null''
+
                    p.right = v.left
  '''if''' x != ''null''                                    <font color="green">// подвешиваем x вместо y</font>
+
                v.left.parent = p
      x.parent = y.parent         
+
        '''else'''                                     <font color="green">// третий случай: удаляемый элемент имеет двух потомков</font>
  '''if''' y.parent == ''null''
+
            successor = next(v, t)                 
      root = x
+
            v.key = successor.key
  '''else'''
+
            '''if''' successor.parent.left == successor
      '''if''' y == y.parent.left
+
                successor.parent.left = successor.right
        y.parent.left = x
+
                '''if''' successor.right != ''null''
      '''else'''
+
                    successor.right.parent = successor.parent
        y.parent.right = x
+
            '''else'''
 +
                successor.parent.right = successor.right
 +
                '''if''' successor.right != ''null''
 +
                    successor.right.parent = successor.parent
 
====Рекурсивная реализация====
 
====Рекурсивная реализация====
 
При рекурсивном удаления узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.
 
При рекурсивном удаления узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.
 
Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>:
 
Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>:
  '''Node''' delete('''Node''' root, '''Node''' z)            <font color="green">// корень поддерева, удаляемый элемент</font>
+
  '''Node''' delete(root : '''Node''', z : '''Node'''):           <font color="green">// корень поддерева, удаляемый элемент</font>
 
   '''if''' root == ''null''
 
   '''if''' root == ''null''
 
       '''return''' root
 
       '''return''' root

Версия 17:06, 28 мая 2015

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

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

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

Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:

Node:
  T key                    // ключ узла
  Node left                // указатель на левого потомка
  Node right               // указатель на правого потомка
  Node parent              // указатель на предка

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

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

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

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 3 4 6 7 8 10 13 14.

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

При выполнении данного обхода вершины будут выведены в следующем порядке: 8 3 1 6 4 7 10 14 13.

func postorderTraversal(x : Node)
   if x != null
      postorderTraversal(x.left)
      postorderTraversal(x.right)
      print x.key

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 4 7 6 3 13 14 10 8.

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

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

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

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

Node search(x : Node, k : T):
   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(x : Node):
  if x.left == null
     return x
  return minimum(x.left)
Node maximum(x : Node):
  if x.right == null
     return x
  return maximum(x.right)

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

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

Реализация с использованием информации о родителе

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

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

Реализация без использования информации о родителе

Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то начнем поиск от корня. Спускаемся вниз по дереву. Если значение узла больше значения в рассматриваемом в данный момент узле, перейдем в правое поддерево, иначе перейдем в левое поддерево. Аналогично выполняется поиск предыдущего элемента. Рекурсивные реализации обеих функций:

Node next(x : Node, t : Node):         // x — элемент, для которого ищем следующий, t — текущее поддерево
   if t != null
      Node successor = next(x, t.left)
      if successor == null
         if t.key > x.key
            return t
      else
         return successor
      return next(x, t.right)
   return null
Node prev(x : Node, t : Node):         // x — элемент, для которого ищем предыдущий, t — текущее поддерево
   if t != null
      Node ancestor = prev(x, t.right)
      if ancestor == null
         if t.key <= x.key
            return t
      else
         return ancestor
      return prev(x, t.left)
   return null

Обе операции выполняются за время [math]O(h)[/math].

Вставка

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

Реализация с использованием информации о родителе

func insert(x : Node, z : Node):            // x — корень поддерева, 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

Реализация без использования информации о родителе

func insert(x : Node, z : Node):            // x — корень поддерева, z — вставляемый элемент
   if z.key <= x.key
      if x.left == null
         x.left = z
      else
         insert(x.left, z)
   else
      if x.right == null
         x.right = z
      else
         insert(x.right, z)

Время работы алгоритма для обеих реализаций — [math]O(h)[/math].

Удаление

Нерекурсивная реализация

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

Случай Иллюстрация
Удаление листа Bst del1.png
Удаление узла с одним дочерним узлом Bst del2.png
Удаление узла с двумя дочерними узлами Bst del3.png
func delete(t : Node, v : Node):                 // дерево и удаляемый элемент
   p = v.parent                                  // предок удаляемого элемента
   if v.left == null and v.right == null         // первый случай: удаляемый элемент - лист
     if p.left == v
       p.left = null
     if p.right == v
       p.right = null
   else
       if v.left == null or v.right == null      // второй случай: удаляемый элемент имеет одного потомка
           if v.left == null                 
               if p.left == v
                 p.left = v.right
               else
                 p.right = v.right
               v.right.parent = p 
           else
               if p.left == v
                   p.left = v.left
               else
                   p.right = v.left
               v.left.parent = p
       else                                      // третий случай: удаляемый элемент имеет двух потомков
           successor = next(v, t)                   
           v.key = successor.key
           if successor.parent.left == successor
               successor.parent.left = successor.right
               if successor.right != null
                   successor.right.parent = successor.parent
           else
               successor.parent.right = successor.right
               if successor.right != null
                   successor.right.parent = successor.parent

Рекурсивная реализация

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

Node delete(root : Node, z : Node):            // корень поддерева, удаляемый элемент
  if root == null
     return root
  if z.key < root.key
    root.left = remove(root.left, z)
  else if z.key > root.key
     root.right = remove(root.right, z)
  else if root.left != null and root.right != null
     root.key = minimum(root.right).key
     root.right = remove(root, root.right)
  else
     if root.left != null
        root = t.left
     else
        root = t.right
  return root

См. также

Источники информации