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

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

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

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

См. также

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

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

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