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

Бинарное дерево поиска из 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].

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

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

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

Вставка

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

insert(Node x, Node z)            // 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;

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

Удаление

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

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

Случай	Иллюстрация
Удаление листа
Удаление узла с одним дочерним узлом
Удаление узла с двумя дочерними узлами

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

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

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

Node delete(Node root, Node z)            // корень поддерева, удаляемый элемент
  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

См. также

• Поисковые структуры данных
• Рандомизированное бинарное дерево поиска

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

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