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

Бинарное дерево поиска из 9 элементов

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

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

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

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

Для вывода всех ключей бинарного дерева поиска в отсортированном порядке используется простой алгоритм (англ. inorder tree traversal).

Tree_inorder(node x)
   if(x != null)
      Tree_inorder(x.left);
      print(x.key);
      Tree_inorder(x.right);

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

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

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

Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой.

Tree_search(node x, key k)
   if (x == null or k == x.key)
      return x;
   if (k < x.key)
      return Tree_search(x.left, k);
   else
      return Tree_search(x.right, k);

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

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

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

Tree_min(root x)
  while (x.left != null)
     x = x.left;
  return x;

Tree_max(root x)
  while (x.right != null)
     x = x.right;
  return x;

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

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

Tree_next(root x)
   if (x.right != null)
      return Tree_min(x.right);
   y = x.parent;
   while(y != null and x == y.right)
      x = y;
      y = y.parent;
   return y;

Tree_prev(root x)
   if (x.left != null)
      return Tree_max(x.left);
   y = x.parent;
   while(y != null and x == y.left)
      x = y;
      y = y.parent;
   return y;

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

Вставка

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

Tree_insert(root x, root z) // корень дерева, вставляемый элемент
   root 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].

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

Tree_delete(root t, root z) // корень дерева, вставляемый элемент
   root x, y;
   if(z.left == null or z.right == null) 
      y = z;
   else
      y = Tree_next(z);
   if(y.left != null)
      x = y.left;
   else
      x = y.right;
   if(x != null)
      x.parent = y.parent;
   if(y.parent == null)
      t = x;
   else
      if(y == y.parent.left)
         y.parent.left = x;
      else
         y.parent.right = x;
  if(y != z)
     z.key = y.key;
     z.data = y.data;
  return y;
      

Литература

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