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

Материал из Викиконспекты
Перейти к: навигация, поиск
Бинарное дерево поиска из 9 элементов
Бинарное дерево поиска (англ. binary search tree, BST) - структура данных для работы с упорядоченными множествами.

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

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

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

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:

  • inorderTraversal - обход узлов в отсортированном порядке
  • prefixTraversal - обход узлов в порядке: вершина, левое поддерево, правое поддерево
  • postfixTraversal - обход узлов в порядке: левое поддерево, правое поддерево, вершина
inorderTraversal(Node x)
   if x != null
      inorderTraversal(x.left)
      print(x.key)
      inorderTraversal(x.right)

Корректность данного алгоритма следует из свойств бинарного дерева поиска.

prefixTraversal(Node x)
   if x != null
      print(x.key)
      prefixTraversal(x.left)
      prefixTraversal(x.right)
postfixTraversal(Node x)
   if x != null
      postfixTraversal(x.left)
      postfixTraversal(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)

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

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

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].

Вставка

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

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

Случай Иллюстрация
Удаление листа Bst del1.png
Удаление узла с одним дочерним узлом Bst del2.png
Удаление узла с двумя дочерними узлами Bst del3.png
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

Ссылки

Литература

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