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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 36: Строка 36:
 
     if (x.right != null)
 
     if (x.right != null)
 
       return Tree_min(x.right)
 
       return Tree_min(x.right)
     else
+
     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;
 +
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.
 
=== Вставка ===
 
=== Вставка ===
 
Операция вставки работает аналогично поиску элемента, только при обнаружении нулевого указателя нужно подвесить на него вставляемый элемент. Приведем итеративную реализацию этого алгоритма.
 
Операция вставки работает аналогично поиску элемента, только при обнаружении нулевого указателя нужно подвесить на него вставляемый элемент. Приведем итеративную реализацию этого алгоритма.
Строка 57: Строка 69:
 
=== Удаление ===
 
=== Удаление ===
 
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на null. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент(у этого элемента не будет левого потомка) и переместить его на место удаляемого узла.
 
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на 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
 
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4

Версия 20:04, 22 марта 2011

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