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

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

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

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

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

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

Имеется простой алгоритм вывода всех ключей бинарного дерева поиска в отсортированном порядке.

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

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

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

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

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 от корня дерева, пока не встретится значение hull. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.

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;

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

Вставка

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

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;

Удаление

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

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