Как найти по узелкам

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

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

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

Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:

struct Node:
  T key                    // ключ узла
  Node left                // указатель на левого потомка
  Node right               // указатель на правого потомка
  Node parent              // указатель на предка

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

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

• — обход узлов в отсортированном порядке,
• — обход узлов в порядке: вершина, левое поддерево, правое поддерево,
• — обход узлов в порядке: левое поддерево, правое поддерево, вершина.

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.

Данные алгоритмы выполняют обход за время , поскольку процедура вызывается ровно два раза для каждого узла дерева.

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

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

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)

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

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

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)

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

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

Реализация с использованием информации о родителе

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

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

Обе операции выполняются за время .

Реализация без использования информации о родителе

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

Node next(x : T):
   Node current = root, successor = null                // root — корень дерева
   while current != null
      if current.key > x
         successor = current
         current = current.left
      else
         current = current.right
   return successor

Вставка

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

Реализация с использованием информации о родителе

func insert(x : Node, z : Node):            // x — корень поддерева, z — вставляемый элемент
   while x != null
     if z.key > x.key
        if x.right != null
           x = x.right
        else
           z.parent = x
           x.right = z
           break
     else if z.key < x.key
        if x.left != null
           x = x.left
        else
           z.parent = x
           x.left = z
           break

Реализация без использования информации о родителе

Node insert(x : Node, z : T):               // x — корень поддерева, z — вставляемый ключ
   if x == null 
      return Node(z)                        // подвесим Node с key = z
   else if z < x.key
      x.left = insert(x.left, z)
   else if z > x.key
      x.right = insert(x.right, z)
   return x

Время работы алгоритма для обеих реализаций — .

Удаление

Нерекурсивная реализация

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

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

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

Рекурсивная реализация

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

Node delete(root : Node, z : T):               // корень поддерева, удаляемый ключ
  if root == null
    return root
  if z < root.key
    root.left = delete(root.left, z)
  else if z > root.key
    root.right = delete(root.right, z)
  else if root.left != null and root.right != null
    root.key = minimum(root.right).key
    root.right = delete(root.right, root.key)
  else
    if root.left != null
      root = root.left
    else if root.right != null
      root = root.right
    else
      root = null
  return root

Задачи о бинарном дереве поиска

Проверка того, что заданное дерево является деревом поиска

Для того чтобы решить эту задачу, применим обход в глубину. Запустим от корня рекурсивную логическую функцию, которая выведет , если дерево является BST и в противном случае. Чтобы дерево не являлось BST, в нём должна быть хотя бы одна вершина, которая не попадает под определение дерева поиска. То есть достаточно найти всего одну такую вершину, чтобы выйти из рекурсии и вернуть значение . Если же, дойдя до листьев, функция не встретит на своём пути такие вершины, она вернёт значение .

Функция принимает на вход исследуемую вершину, а также два значения: и , которые до вызова функции равнялись и соответственно, где — очень большое число, т.е. ни один ключ дерева не превосходит его по модулю. Казалось бы, два последних параметра не нужны. Но без них программа может выдать неверный ответ, так как сравнения только вершины и её детей недостаточно. Необходимо также помнить, в каком поддереве для более старших предков мы находимся. Например, в этом дереве вершина с номером находится левее вершины, в которой лежит , чего не должно быть в дереве поиска, однако после проверки функция бы вернула .

bool isBinarySearchTree(root: Node):                    // Здесь root — корень заданного двоичного дерева.

  bool check(v : Node, min: T, max: T):                 // min и max — минимально и максимально допустимые значения в вершинах поддерева.
    if v == null                    return true
    if v.key <= min or max <= v.key return false
    return check(v.left, min, v.key) and check(v.right, v.key, max)

  return check(root, , )

Время работы алгоритма — , где — количество вершин в дереве.

Задачи на поиск максимального BST в заданном двоичном дереве

Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за . Но её можно решить за , идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах:

• Значение в вершине больше максимума в её левом поддереве;
• Значение в вершине меньше минимума в её правом поддереве;
• Левое и правое поддерево являются деревьями поиска.

Введём и , которые будут хранить минимум в левом поддереве вершины и максимум в правом. Тогда мы должны будем проверить, являются ли эти поддеревья деревьями поиска и, если да, лежит ли ключ вершины между этими значениями и . Если вершина является листом, она автоматически становится деревом поиска, а её ключ — минимумом или максимумом для её родителя (в зависимости от расположения вершины). Функция записывает в количество вершин в дереве, если оно является деревом поиска или в противном случае. После выполнения функции ищем за линейное время вершину с наибольшим значением .

int count(root: Node):                 // root — корень заданного двоичного дерева.

  int cnt(v: Node):
    if v == null
      v.kol = 0
      return = 0
    if cnt(v.left) != -1 and cnt(v.right) != -1
      if v.left == null and v.right == null
        v.min = v.key
        v.max = v.key
        v.kol = 1
        return 1
      if v.left == null
        if v.right.max > v.key
          v.min = v.key
          v.kol = cnt(v.right) + 1
          return v.kol
      if v.right == null
        if v.left.min < v.key
          v.max = v.key
          v.kol = cnt(v.left) + 1
          return v.kol
      if v.left.min < v.key and v.right.max > v.key 
        v.min = v.left.min
        v.max = v.right.max
        v.kol = v.left.kol + v.right.kol + 1
        v.kol = cnt(v.left) + cnt(v.right) + 1
        return v.kol
    return -1

  return cnt(root)

Алгоритм работает за , так как мы прошлись по дереву два раза за время, равное количеству вершин.

Восстановление дерева по результату обхода preorderTraversal

Как мы помним, процедура выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына. Когда мы, желая найти такую вершину, встречаем какую-нибудь другую, уже имеющую правого сына, проходим по ветке вправо. Мы имеем на это право, так как если такая вершина стоит, то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону смысла не имеет. Вершину с максимальным ключом, с которой будем начинать поиск, будем запоминать. Она будет обновляться каждый раз, когда появится новый максимум.

Процедура восстановления дерева работает за .

Разберём алгоритм на примере последовательности .

Будем выделять красным цветом вершины, рассматриваемые на каждом шаге, чёрным жирным — их родителей, курсивом — убывающие подпоследовательности (в случаях, когда мы их рассматриваем) или претендентов на добавление к ним правого ребёнка (когда рассматривается вершина, нарушающая убывающую последовательность).

См. также

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

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

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

АВЛ-деревья

Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.

Понятие АВЛ-дерева

АВЛ-дерево — это прежде всего двоичное дерево поиска, ключи которого удовлетворяют стандартному свойству: ключ любого узла дерева не меньше любого ключа в левом поддереве данного узла и не больше любого ключа в правом поддереве этого узла. Это значит, что для поиска нужного ключа в АВЛ-дереве можно использовать стандартный алгоритм. Для простоты дальнейшего изложения будем считать, что все ключи в дереве целочисленны и не повторяются.

Особенностью АВЛ-дерева является то, что оно является сбалансированным в следующем смысле: для любого узла дерева высота его правого поддерева отличается от высоты левого поддерева не более чем на единицу. Доказано, что этого свойства достаточно для того, чтобы высота дерева логарифмически зависела от числа его узлов: высота h АВЛ-дерева с n ключами лежит в диапазоне от log₂(n + 1) до 1.44 log₂(n + 2) − 0.328. А так как основные операции над двоичными деревьями поиска (поиск, вставка и удаление узлов) линейно зависят от его высоты, то получаем гарантированную логарифмическую зависимость времени работы этих алгоритмов от числа ключей, хранимых в дереве. Напомним, что рандомизированные деревья поиска обеспечивают сбалансированность только в вероятностном смысле: вероятность получения сильно несбалансированного дерева при больших n хотя и является пренебрежимо малой, но остается не равной нулю.

Структура узлов

Будем представлять узлы АВЛ-дерева следующей структурой:

struct node // структура для представления узлов дерева
{
	int key;
	unsigned char height;
	node* left;
	node* right;
	node(int k) { key = k; left = right = 0; height = 1; }
};

Поле key хранит ключ узла, поле height — высоту поддерева с корнем в данном узле, поля left и right — указатели на левое и правое поддеревья. Простой конструктор создает новый узел (высоты 1) с заданным ключом k.

Традиционно, узлы АВЛ-дерева хранят не высоту, а разницу высот правого и левого поддеревьев (так называемый balance factor), которая может принимать только три значения -1, 0 и 1. Однако, заметим, что эта разница все равно хранится в переменной, размер которой равен минимум одному байту (если не придумывать каких-то хитрых схем «эффективной» упаковки таких величин). Вспомним, что высота h < 1.44 log₂(n + 2), это значит, например, что при n=10⁹ (один миллиард ключей, больше 10 гигабайт памяти под хранение узлов) высота дерева не превысит величины h=44, которая с успехом помещается в тот же один байт памяти, что и balance factor. Таким образом, хранение высот с одной стороны не увеличивает объем памяти, отводимой под узлы дерева, а с другой стороны существенно упрощает реализацию некоторых операций.

Определим три вспомогательные функции, связанные с высотой. Первая является оберткой для поля height, она может работать и с нулевыми указателями (с пустыми деревьями):

unsigned char height(node* p)
{
	return p?p->height:0;
}

Вторая вычисляет balance factor заданного узла (и работает только с ненулевыми указателями):

int bfactor(node* p)
{
	return height(p->right)-height(p->left);
}

Третья функция восстанавливает корректное значение поля height заданного узла (при условии, что значения этого поля в правом и левом дочерних узлах являются корректными):

void fixheight(node* p)
{
	unsigned char hl = height(p->left);
	unsigned char hr = height(p->right);
	p->height = (hl>hr?hl:hr)+1;
}

Заметим, что все три функции являются нерекурсивными, т.е. время их работы есть величина О(1).

Балансировка узлов

В процессе добавления или удаления узлов в АВЛ-дереве возможно возникновение ситуации, когда balance factor некоторых узлов оказывается равными 2 или -2, т.е. возникает расбалансировка поддерева. Для выправления ситуации применяются хорошо нам известные повороты вокруг тех или иных узлов дерева. Напомню, что простой поворот вправо (влево) производит следующую трансформацию дерева:

Код, реализующий правый поворот, выглядит следующим образом (как обычно, каждая функция, изменяющая дерево, возвращает новый корень полученного дерева):

node* rotateright(node* p) // правый поворот вокруг p
{
	node* q = p->left;
	p->left = q->right;
	q->right = p;
	fixheight(p);
	fixheight(q);
	return q;
}

Левый поворот является симметричной копией правого:

node* rotateleft(node* q) // левый поворот вокруг q
{
	node* p = q->right;
	q->right = p->left;
	p->left = q;
	fixheight(q);
	fixheight(p);
	return p;
}

Рассмотрим теперь ситуацию дисбаланса, когда высота правого поддерева узла p на 2 больше высоты левого поддерева (обратный случай является симметричным и реализуется аналогично). Пусть q — правый дочерний узел узла p, а s — левый дочерний узел узла q.

Анализ возможных случаев в рамках данной ситуации показывает, что для исправления расбалансировки в узле p достаточно выполнить либо простой поворот влево вокруг p, либо так называемый большой поворот влево вокруг того же p. Простой поворот выполняется при условии, что высота левого поддерева узла q больше высоты его правого поддерева: h(s)≤h(D).

Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.

Код, выполняющий балансировку, сводится к проверке условий и выполнению поворотов:

node* balance(node* p) // балансировка узла p
{
	fixheight(p);
	if( bfactor(p)==2 )
	{
		if( bfactor(p->right) < 0 )
			p->right = rotateright(p->right);
		return rotateleft(p);
	}
	if( bfactor(p)==-2 )
	{
		if( bfactor(p->left) > 0  )
			p->left = rotateleft(p->left);
		return rotateright(p);
	}
	return p; // балансировка не нужна
}

Описанные функции поворотов и балансировки также не содержат ни циклов, ни рекурсии, а значит выполняются за постоянное время, не зависящее от размера АВЛ-дерева.

Вставка ключей

Вставка нового ключа в АВЛ-дерево выполняется, по большому счету, так же, как это делается в простых деревьях поиска: спускаемся вниз по дереву, выбирая правое или левое направление движения в зависимости от результата сравнения ключа в текущем узле и вставляемого ключа. Единственное отличие заключается в том, что при возвращении из рекурсии (т.е. после того, как ключ вставлен либо в правое, либо в левое поддерево, и это дерево сбалансировано) выполняется балансировка текущего узла. Строго доказывается, что возникающий при такой вставке дисбаланс в любом узле по пути движения не превышает двух, а значит применение вышеописанной функции балансировки является корректным.

node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
	if( !p ) return new node(k);
	if( k<p->key )
		p->left = insert(p->left,k);
	else
		p->right = insert(p->right,k);
	return balance(p);
}

Чтобы проверить соответствие реализованного алгоритма вставки теоретическим оценкам для высоты АВЛ-деревьев, был проведен несложный вычислительный эксперимент. Генерировался массив из случайно расположенных чисел от 1 до 10000, далее эти числа последовательно вставлялись в изначально пустое АВЛ-дерево и измерялась высота дерева после каждой вставки. Полученные результаты были усреднены по 1000 расчетам. На следующем графике показана зависимость от n средней высоты (красная линия); минимальной высоты (зеленая линия); максимальной высоты (синяя линия). Кроме того, показаны верхняя и нижняя теоретические оценки.

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

Удаление ключей

С удалением узлов из АВЛ-дерева, к сожалению, все не так шоколадно, как с рандомизированными деревьями поиска. Способа, основанного на слиянии (join) двух деревьев, ни найти, ни придумать не удалось. Поэтому за основу был взят вариант, описываемый практически везде (и который обычно применяется и при удалении узлов из стандартного двоичного дерева поиска). Идея следующая: находим узел p с заданным ключом k (если не находим, то делать ничего не надо), в правом поддереве находим узел min с наименьшим ключом и заменяем удаляемый узел p на найденный узел min.

При реализации возникает несколько нюансов. Прежде всего, если у найденный узел p не имеет правого поддерева, то по свойству АВЛ-дерева слева у этого узла может быть только один единственный дочерний узел (дерево высоты 1), либо узел p вообще лист. В обоих этих случаях надо просто удалить узел p и вернуть в качестве результата указатель на левый дочерний узел узла p.

Пусть теперь правое поддерево у p есть. Находим минимальный ключ в этом поддереве. По свойству двоичного дерева поиска этот ключ находится в конце левой ветки, начиная от корня дерева. Применяем рекурсивную функцию:

node* findmin(node* p) // поиск узла с минимальным ключом в дереве p 
{
	return p->left?findmin(p->left):p;
}

Еще одна служебная функция у нас будет заниматься удалением минимального элемента из заданного дерева. Опять же, по свойству АВЛ-дерева у минимального элемента справа либо подвешен единственный узел, либо там пусто. В обоих случаях надо просто вернуть указатель на правый узел и по пути назад (при возвращении из рекурсии) выполнить балансировку. Сам минимальный узел не удаляется, т.к. он нам еще пригодится.

node* removemin(node* p) // удаление узла с минимальным ключом из дерева p
{
	if( p->left==0 )
		return p->right;
	p->left = removemin(p->left);
	return balance(p);
}

Теперь все готово для реализации удаления ключа из АВЛ-дерева. Сначала находим нужный узел, выполняя те же действия, что и при вставке ключа:

node* remove(node* p, int k) // удаление ключа k из дерева p
{
	if( !p ) return 0;
	if( k < p->key )
		p->left = remove(p->left,k);
	else if( k > p->key )
		p->right = remove(p->right,k);	

Как только ключ k найден, переходим к плану Б: запоминаем корни q и r левого и правого поддеревьев узла p; удаляем узел p; если правое поддерево пустое, то возвращаем указатель на левое поддерево; если правое поддерево не пустое, то находим там минимальный элемент min, потом его извлекаем оттуда, слева к min подвешиваем q, справа — то, что получилось из r, возвращаем min после его балансировки.

	else //  k == p->key 
	{
		node* q = p->left;
		node* r = p->right;
		delete p;
		if( !r ) return q;
		node* min = findmin(r);
		min->right = removemin(r);
		min->left = q;
		return balance(min);
	}

При выходе из рекурсии не забываем выполнить балансировку:

	return balance(p);
}

Вот собственно и все! Поиск минимального узла и его извлечение, в принципе, можно реализовать в одной функции, при этом придется решать (не очень сложную) проблему с возвращением из функции пары указателей. Зато можно сэкономить на одном проходе по правому поддереву.

Очевидно, что операции вставки и удаления (а также более простая операция поиска) выполняются за время пропорциональное высоте дерева, т.к. в процессе выполнения этих операций производится спуск из корня к заданному узлу, и на каждом уровне выполняется некоторое фиксированное число действий. А в силу того, что АВЛ-дерево является сбалансированным, его высота зависит логарифмически от числа узлов. Таким образом, время выполнения всех трех базовых операций гарантированно логарифмически зависит от числа узлов дерева.

Всем спасибо за внимание!

struct node // структура для представления узлов дерева
{
	int key;
	unsigned char height;
	node* left;
	node* right;
	node(int k) { key = k; left = right = 0; height = 1; }
};

unsigned char height(node* p)
{
	return p?p->height:0;
}

int bfactor(node* p)
{
	return height(p->right)-height(p->left);
}

void fixheight(node* p)
{
	unsigned char hl = height(p->left);
	unsigned char hr = height(p->right);
	p->height = (hl>hr?hl:hr)+1;
}

node* rotateright(node* p) // правый поворот вокруг p
{
	node* q = p->left;
	p->left = q->right;
	q->right = p;
	fixheight(p);
	fixheight(q);
	return q;
}

node* rotateleft(node* q) // левый поворот вокруг q
{
	node* p = q->right;
	q->right = p->left;
	p->left = q;
	fixheight(q);
	fixheight(p);
	return p;
}

node* balance(node* p) // балансировка узла p
{
	fixheight(p);
	if( bfactor(p)==2 )
	{
		if( bfactor(p->right) < 0 )
			p->right = rotateright(p->right);
		return rotateleft(p);
	}
	if( bfactor(p)==-2 )
	{
		if( bfactor(p->left) > 0  )
			p->left = rotateleft(p->left);
		return rotateright(p);
	}
	return p; // балансировка не нужна
}

node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
	if( !p ) return new node(k);
	if( k<p->key )
		p->left = insert(p->left,k);
	else
		p->right = insert(p->right,k);
	return balance(p);
}

node* findmin(node* p) // поиск узла с минимальным ключом в дереве p 
{
	return p->left?findmin(p->left):p;
}

node* removemin(node* p) // удаление узла с минимальным ключом из дерева p
{
	if( p->left==0 )
		return p->right;
	p->left = removemin(p->left);
	return balance(p);
}

node* remove(node* p, int k) // удаление ключа k из дерева p
{
	if( !p ) return 0;
	if( k < p->key )
		p->left = remove(p->left,k);
	else if( k > p->key )
		p->right = remove(p->right,k);	
	else //  k == p->key 
	{
		node* q = p->left;
		node* r = p->right;
		delete p;
		if( !r ) return q;
		node* min = findmin(r);
		min->right = removemin(r);
		min->left = q;
		return balance(min);
	}
	return balance(p);
}

Источники

• B. Pfaff, An Introduction to Binary Search Trees and Balanced Trees — описание библиотеки libavl
• Н. Вирт, Алгоритмы и структуры данных — сбалансированные деревья по Вирту — это как раз АВЛ-деревья
• Т. Кормен и др., Алгоритмы: построение и анализ — про АВЛ-деревья говорится в упражнениях к главе про красно-черные деревья
• Д. Кнут, Искусство программирования — раздел 6.2.3 посвящен теоретическому анализу АВЛ-деревьев

Узлы в БДО — это точки на карте, которые открываются, когда персонаж впервые прибывает в неизведанную локацию. Узлы можно связывать между собой, вкладывая в них очки влияния. Связанные узлы образуют маршруты, которые используются в торговле и сборе ресурсов при помощи рабочих. Сеть узлов обычно именуется «империей рабочих». Помимо очков влияния, в узлы можно вкладывать энергию, тем самым повышая количество добычи за убийство монстров и вероятность успешных диалогов с NPC в этих самых узлах.

Содержание:

• 1. Типы узлов в БДО
• 2. Как связать узлы в БДО
• 3. Как прокачивать узлы

1. Типы узлов в БДО

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

Узлы приключений

Ресурсные узлы

Иконка	Узел	Информация
	Сбор и возделывание земли	Эти узлы имеют одинаковые иконки. На узлах для сбора добываются следующие материалы: грибы, мед, финики, теф, травы и так далее. На узлах для возделывания земли добываются следующие материалы: оливки, алоэ, виноград, тыква, пшеница, ячмень, картофель, кукуруза, клубника и так далее.
	Производство	Производственных узлов в игре не так много. Это ферма Алехандро, специализирующаяся на производстве меда, и фермы Пинто и Бартелли, специализирующиеся на производстве яиц и куриного мяса.
	Лесопилка	На лесопилках добывается древесина и сок из разных видов деревьев. Например, на лесопилке у пещеры гоблинов добывается древесина ясеня, а также обработанная версия древесины, доски из ясеня. На лесопилке можно получить и другие побочные материалы: Волшебный листок, Ветвь монаха, Сучок кровавого дерева, Красная почка, Кактус и так далее.
	Шахта	В шахтах добываются всевозможные камни и минералы. Побочные материалы: Необработанный опал, Грубый черный хрусталь, Пыль огня, Пыль земли, Мельхиор, Уголь, Пыль разрушения, Порошок тьмы и так далее.
	Раскопки	Раскопки обычно требуют вложения большого количества очков влияния. На раскопках можно добыть разные порошки (Порошок битвы, Порошок памяти, Порошок земли и так далее). Порошки — это дорогие материалы, поэтому мы рекомендуем вам прокачивать узлы с раскопками во что бы то ни стало. Узел у Звездной гробницы особенно выгоден, так как там можно добыть Сгустки чистых чар, необходимые для усиления оружия Черной звезды. На раскопки лучше посылать рабочих-людей, так как они обладают высокими показателями удачи и с большей вероятностью находят порошки. Чтобы открыть доступ к раскопкам, нужно поговорить с распорядителем связанного с ними узла приключений и потратить при этом энергию.
	Сушка рыбы	Мастерские для сушки рыбы находятся в море. В них можно сушить разную рыбу, которая в дальнейшем  используется в кулинарии.
	Продукты	Продуктовые узлы — это особые узлы приключений с домами первого ранга. Большинству игроков они недоступны. На продуктовых узлах можно изготавливать дорогостоящие материалы для продажи торговцам.
	Биржа	Биржи обычно располагаются в городах и деревнях. Чтобы получить доступ к бирже, не нужно тратить очки влияния, но нужно иметь дом первого ранга. Большинству игроков биржи недоступны. Чтобы получить доступ к бирже, нужно отдать распорядителю золотые слитки. Через 24 часа вы получите серебро в количестве, эквивалентном стоимости слитков (или большем). В игре есть биржи, для доступа к которым не нужно иметь дом первого ранга, но они с меньшей вероятностью приносят прибыль, и мы не рекомендуем с ними связываться.

2. Как связать узлы в БДО

Маршрут или последовательность узлов всегда начинается в городе или деревне. Города и деревни открываются автоматически, и в них не нужно вкладывать очки влияния. Узлы приключений, которые можно связать между собой, соединены белыми линиями на карте. Узлы, которые уже были связаны, соединяются желтыми линиями.

Чтобы соединить узлы, отправляйтесь к управляющему. Для этого необходимо кликнуть по иконке узла правой кнопкой мыши, и персонаж сам отыщет путь. Прибыв на место, поговорите с управляющим и выберите пункт «Логистика».

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

В левом верхнем углу окна информации об узле указывается название региона и имя управляющего узлом, а также количество очков влияния, которое нужно вложить, чтобы вписать узел в маршрут.

Чтобы связать узлы, нажмите кнопку «Внести».

Если на вас действует эффект «Набор характеристик игрока», идти к управляющему узлом необязательно. Откройте карту, щелкните по нужному узлу левой кнопкой мыши и вложите очки (это стоит 10 ед. энергии за каждый узел).

Если вам необходимо разорвать связь, откройте карту, кликните по иконке узла и нажмите кнопку «Забрать очки».  В этом случае уровень узла сбросится до 0, и при повторном вложении очков вам придется качать его заново.

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

3. Как прокачивать узлы

Вложив очки в узел, вы можете щелкнуть по его иконке и вложить в него энергию. За каждые 10 ед. энергии узел получает опыт. Чтобы прокачать узел до 10 уровня, нужно потратить 3200 ед. энергии.

Если узел является городом или деревней, после прокачки вы сможете дружить в NPC, которые в нем живут.

Для всех остальных узлов прокачка влияет на количество ценной добычи с монстров, которые живут поблизости. Узел 10 уровня увеличивает количество добычи на 50%, но эффект срабатывает в 10% случаев, то есть для каждого десятого монстра.

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

До сих пор мы рассматривали структуры данных, данные в которых располагаются линейно. В связном списке — от первого узла к единственному последнему. В динамическом массиве — в виде непрерывного блока.

В этой части мы рассмотрим совершенно новую структуру данных — дерево. А точнее, двоичное (бинарное) дерево поиска (binary search tree). Бинарное дерево поиска имеет структуру дерева, но элементы в нем расположены по определенным правилам.

Также смотрите другие материалы этой серии: стеки и очереди, динамический массив, связный список, оценка сложности алгоритма, сортировка и множества.

Для начала мы рассмотрим обычное дерево.

Деревья

Дерево — это структура, в которой у каждого узла может быть ноль или более подузлов — «детей». Например, дерево может выглядеть так:

Это дерево показывает структуру компании. Узлы представляют людей или подразделения, линии — связи и отношения. Дерево — это самый эффективный способ представления и хранения такой информации.

Дерево на картинке выше очень простое. Оно отражает только отношение родства категорий, но не накладывает никаких ограничений на свою структуру. У генерального директора может быть как один непосредственный подчиненный, так и несколько или ни одного. На рисунке отдел продаж находится левее отдела маркетинга, но порядок на самом деле не имеет значения. Единственное ограничение дерева — каждый узел может иметь не более одного родителя. Самый верхний узел (совет директоров, в нашем случае) родителя не имеет. Этот узел называется «корневым», или «корнем».

Вопросы о деревьях задают даже на собеседовании в Apple.

Двоичное дерево поиска

Двоичное дерево поиска похоже на дерево из примера выше, но строится по определенным правилам:

• У каждого узла не более двух детей.
• Любое значение меньше значения узла становится левым ребенком или ребенком левого ребенка.
• Любое значение больше или равное значению узла становится правым ребенком или ребенком правого ребенка.

Давайте посмотрим на дерево, построенное по этим правилам:

Обратите внимание, как указанные ограничения влияют на структуру дерева. Каждое значение слева от корня (8) меньше восьми, каждое значение справа — больше либо равно корню. Это правило применимо к любому узлу дерева.

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

Мы не знаем точно, в каком порядке добавлялись остальные значения, но можем представить один из возможных путей. Узлы добавляются методом Add, который принимает добавляемое значение.

BinaryTree tree = new BinaryTree();
tree.Add(8);
tree.Add(4);
tree.Add(2);
tree.Add(3);
tree.Add(10);
tree.Add(6);
tree.Add(7);

Рассмотрим подробнее первые шаги.

В первую очередь добавляется 8. Это значение становится корнем дерева. Затем мы добавляем 4. Поскольку 4 меньше 8, мы кладем ее в левого ребенка, согласно правилу 2. Поскольку у узла с восьмеркой нет детей слева, 4 становится единственным левым ребенком.

После этого мы добавляем 2. 2 меньше 8, поэтому идем налево. Так как слева уже есть значение, сравниваем его со вставляемым. 2 меньше 4, а у четверки нет детей слева, поэтому 2 становится левым ребенком 4.

Затем мы добавляем тройку. Она идет левее 8 и 4. Но так как 3 больше, чем 2, она становится правым ребенком 2, согласно третьему правилу.

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

Класс BinaryTreeNode

Класс BinaryTreeNode представляет один узел двоичного дерева. Он содержит ссылки на левое и правое поддеревья (если поддерева нет, ссылка имеет значение null), данные узла и метод IComparable.CompareTo для сравнения узлов. Он пригодится для определения, в какое поддерево должен идти данный узел. Как видите, класс BinaryTreeNode очень простой:

class BinaryTreeNode : IComparable
    where TNode : IComparable
{
    public BinaryTreeNode(TNode value)
    {
        Value = value;
    }
 
    public BinaryTreeNode Left { get; set; }
    public BinaryTreeNode Right { get; set; }
    public TNode Value { get; private set; }
 
    /// 
    /// Сравнивает текущий узел с данным.
    /// 
    /// Сравнение производится по полю Value.
    /// Метод возвращает 1, если значение текущего узла больше,
    /// чем переданного методу, -1, если меньше и 0, если они равны
    public int CompareTo(TNode other)
    {
        return Value.CompareTo(other);
    }
}

Класс BinaryTree

Класс BinaryTree предоставляет основные методы для манипуляций с данными: вставка элемента (Add), удаление (Remove), метод Contains для проверки, есть ли такое значение в дереве, несколько методов для обхода дерева различными способами, метод Count и Clear.

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

public class BinaryTree : IEnumerable
    where T : IComparable
{
    private  BinaryTreeNode _head;
    private int _count;
 
    public void Add(T value)
    {
        throw new NotImplementedException();
    }
 
    public bool Contains(T value)
    {
        throw new NotImplementedException();
    }
 
    public bool Remove(T value)
    {
        throw new NotImplementedException();
    }
 
    public void PreOrderTraversal(Action action)
    {
        throw new NotImplementedException();
    }
 
    public void PostOrderTraversal(Action action)
    {
        throw new NotImplementedException();
    }
 
    public void InOrderTraversal(Action action)
    {
        throw new NotImplementedException();
    }
 
    public IEnumerator GetEnumerator()
    {
        throw new NotImplementedException();
    }
 
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        throw new NotImplementedException();
    }
 
    public void Clear()
    {
        throw new NotImplementedException();
    }
 
    public int Count
    {
        get;
    }
}

Метод Add

• Поведение: Добавляет элемент в дерево на корректную позицию.
• Сложность: O(log n) в среднем; O(n) в худшем случае.

Добавление узла не представляет особой сложности. Оно становится еще проще, если решать эту задачу рекурсивно. Есть всего два случая, которые надо учесть:

1. Дерево пустое.
2. Дерево не пустое.

Если дерево пустое, мы просто создаем новый узел и добавляем его в дерево. Во втором случае мы сравниваем переданное значение со значением в узле, начиная от корня. Если добавляемое значение меньше значения рассматриваемого узла, повторяем ту же процедуру для левого поддерева. В противном случае — для правого.

public void Add(T value)
{
//Случай 1: Если дерево пустое, просто создаем корневой узел.
    if (_head == null)
    {
        _head = new BinaryTreeNode(value);
    }
//Случай 2: Дерево не пустое => 
//ищем правильное место для вставки.
    else
    {
        AddTo(_head, value);
    }
 
    _count++;
}
 
//Рекурсивная ставка.
private void AddTo(BinaryTreeNode node, T value)
{
//Случай 1: Вставляемое значение меньше значения узла
    if (value.CompareTo(node.Value) < 0)
    {
//Если нет левого поддерева, добавляем значение в левого ребенка,
        if (node.Left == null)
        {
            node.Left = new BinaryTreeNode(value);
        }
        else
        {
//в противном случае повторяем для левого поддерева.
            AddTo(node.Left, value);
        }
    }
//Случай 2: Вставляемое значение больше или равно значению узла.
    else
    {
//Если нет правого поддерева, добавляем значение в правого ребенка,
        if (node.Right == null)
        {
            node.Right = new BinaryTreeNode(value);
        }
        else
        {
//в противном случае повторяем для правого поддерева.
            AddTo(node.Right, value);
        }
    }
}

Метод Remove

• Поведение: Удаляет первый узел с заданным значением.
• Сложность: O(log n) в среднем; O(n) в худшем случае.

Удаление узла из дерева — одна из тех операций, которые кажутся простыми, но на самом деле таят в себе немало подводных камней.

В целом, алгоритм удаления элемента выглядит так:

• Найти узел, который надо удалить.
• Удалить его.

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

Случай 1: У удаляемого узла нет правого ребенка.

В этом случае мы просто перемещаем левого ребенка (при его наличии) на место удаляемого узла. В результате дерево будет выглядеть так:

Случай 2: У удаляемого узла есть только правый ребенок, у которого, в свою очередь нет левого ребенка.

В этом случае нам надо переместить правого ребенка удаляемого узла (6) на его место. После удаления дерево будет выглядеть так:

Случай 3: У удаляемого узла есть первый ребенок, у которого есть левый ребенок.

В этом случае место удаляемого узла занимает крайний левый ребенок правого ребенка удаляемого узла.

Давайте посмотрим, почему это так. Мы знаем о поддереве, начинающемся с удаляемого узла следующее:

• Все значения справа от него больше или равны значению самого узла.
• Наименьшее значение правого поддерева — крайнее левое.

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

После удаления узла дерево будет выглядеть так:

Теперь, когда мы знаем, как удалять узлы, посмотрим на код, который реализует этот алгоритм.

Отметим, что метод FindWithParent (см. метод Contains) возвращает найденный узел и его родителя, поскольку мы должны заменить левого или правого ребенка родителя удаляемого узла.

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

public bool Remove(T value)
{
    BinaryTreeNode current, parent;
 
    // Находим удаляемый узел.
    current = FindWithParent(value, out parent);
 
    if (current == null)
    {
        return false;
    }
 
    _count--;
 
//Случай 1: Если нет детей справа,
//левый ребенок встает на место удаляемого.
    if (current.Right == null)
    {
        if (parent == null)
        {
            _head = current.Left;
        }
        else
        {
            int result = parent.CompareTo(current.Value);
            if (result > 0)
            {
//Если значение родителя больше текущего,
//левый ребенок текущего узла становится левым ребенком родителя.
                parent.Left = current.Left;
            }
            else if (result < 0) {
//Если значение родителя меньше текущего,
// левый ребенок текущего узла становится правым ребенком родителя.
               parent.Right = current.Left;
             }
         }
    }
//Случай 2: Если у правого ребенка нет детей слева
//то он занимает место удаляемого узла.
            else if (current.Right.Left == null) {
               current.Right.Left = current.Left;
               if (parent == null) {
                 _head = current.Right;
               } else {
                 int result = parent.CompareTo(current.Value);
                 if (result > 0)
            {
//Если значение родителя больше текущего,
//правый ребенок текущего узла становится левым ребенком родителя.
                parent.Left = current.Right;
            }
            else if (result < 0) {
//Если значение родителя меньше текущего,
// правый ребенок текущего узла становится правым ребенком родителя.
               parent.Right = current.Right;
            }
       }
   }
//Случай 3: Если у правого ребенка есть дети слева,
//крайний левый ребенок 
//из правого поддерева заменяет удаляемый узел.
            else {
//Найдем крайний левый узел.
               BinaryTreeNode leftmost = current.Right.Left;
               BinaryTreeNode leftmostParent = current.Right;
               while (leftmost.Left != null) {
                  leftmostParent = leftmost; leftmost = leftmost.Left;
               }
//Левое поддерево родителя становится правым поддеревом
//крайнего левого узла.
               leftmostParent.Left = leftmost.Right;
//Левый и правый ребенок текущего узла становится левым
//и правым ребенком крайнего левого. leftmost.
               Left = current.Left;
               leftmost.Right = current.Right;
               if (parent == null) {
                  _head = leftmost;
               } else {
                  int result = parent.CompareTo(current.Value);
                  if (result > 0)
            {
//Если значение родителя больше текущего,
//крайний левый узел становится левым ребенком родителя.
                parent.Left = leftmost;
            }
            else if (result < 0)
            {
//Если значение родителя меньше текущего,
//крайний левый узел становится правым ребенком родителя.
                parent.Right = leftmost;
            }
        }
    }
 
    return true;
}

Метод Contains

• Поведение: Возвращает true если значение содержится в дереве. В противном случает возвращает false.
• Сложность: O(log n) в среднем; O(n) в худшем случае.

Метод Contains выполняется с помощью метода FindWithParent, который проходит по дереву, выполняя в каждом узле следующие шаги:

1. Если текущий узел null, вернуть null.
2. Если значение текущего узла равно искомому, вернуть текущий узел.
3. Если искомое значение меньше значения текущего узла, установить левого ребенка текущим узлом и перейти к шагу 1.
4. В противном случае, установить правого ребенка текущим узлом и перейти к шагу 1.

Поскольку Contains возвращает булево значение, оно определяется сравнением результата выполнения FindWithParent с null. Если FindWithParent вернул непустой узел, Contains возвращает true.

Метод FindWithParent также используется в методе Remove.

public bool Contains(T value)
{
//Поиск узла осуществляется другим методом.
    BinaryTreeNode parent;
    return FindWithParent(value, out parent) != null;
}
  
//Находит и возвращает первый узел с заданным значением.
//Если значение не найдено, возвращает null.
//Также возвращает родителя найденного узла (или null)
//для использования в методе Remove. 
private BinaryTreeNode FindWithParent(T value,
                            out BinaryTreeNode parent)
{
//Попробуем найти значение в дереве.
    BinaryTreeNode current = _head;
    parent = null;
 
//До тех пор, пока не нашли...
    while (current != null)
    {
        int result = current.CompareTo(value);
 
        if (result > 0)
        {
//Если искомое значение меньше, идем налево.
            parent = current;
            current = current.Left;
        }
        else if (result < 0)
        {
//Если искомое значение больше, идем направо.
            parent = current;
            current = current.Right;
        }
        else
        {
//Если равны, то останавливаемся
            break;
        }
    }
 
    return current;
}

Метод Count

• Поведение: Возвращает количество узлов дерева или 0, если дерево пустое.
• Сложность: O(1)

Это поле инкрементируется методом Add и декрементируется методом Remove.

>public int Count
{
    get
    {
        return _count;
    }
}

Метод Clear

• Поведение: Удаляет все узлы дерева.
• Сложность: O(1)

public void Clear()
{
    _head = null;
    _count = 0;
}

Обход деревьев

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

Методы обхода в примерах будут принимать параметр Action<T>, который определяет действие, поизводимое над каждым узлом.

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

Метод Preorder (или префиксный обход)

• Поведение: Обходит дерево в префиксном порядке, выполняя указанное действие над каждым узлом.
• Сложность: O(n)
• Порядок обхода: 4, 2, 1, 3, 5, 7, 6, 8

При префиксном обходе алгоритм получает значение текущего узла перед тем, как перейти сначала в левое поддерево, а затем в правое. Начиная от корня, сначала мы получим значение 4. Затем таким же образом обходятся левый ребенок и его дети, затем правый ребенок и все его дети.

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

public void PreOrderTraversal(Action action)
{
    PreOrderTraversal(action, _head);
}
 
private void PreOrderTraversal(Action action, BinaryTreeNode node)
{
    if (node != null)
    {
        action(node.Value);
        PreOrderTraversal(action, node.Left);
        PreOrderTraversal(action, node.Right);
    }
}

Метод Postorder (или постфиксный обход)

• Поведение: Обходит дерево в постфиксном порядке, выполняя указанное действие над каждым узлом.
• Сложность: O(n)
• Порядок обхода: 1, 3, 2, 6, 8, 7, 5, 4

При постфиксном обходе мы посещаем левое поддерево, правое поддерево, а потом, после обхода всех детей, переходим к самому узлу.

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

public void PostOrderTraversal(Action action)
{
    PostOrderTraversal(action, _head);
}
 
private void PostOrderTraversal(Action action, BinaryTreeNode node)
{
    if (node != null)
    {
        PostOrderTraversal(action, node.Left);
        PostOrderTraversal(action, node.Right);
        action(node.Value);
    }
}

Метод Inorder (или инфиксный обход)

• Поведение: Обходит дерево в инфиксном порядке, выполняя указанное действие над каждым узлом.
• Сложность: O(n)
• Порядок обхода: 1, 2, 3, 4, 5, 6, 7, 8

Инфиксный обход используется тогда, когда нам надо обойти дерево в порядке, соответствующем значениям узлов. В примере выше в дереве находятся числовые значения, поэтому мы обходим их от самого маленького до самого большого. То есть от левых поддеревьев к правым через корень.

В примере ниже показаны два способа инфиксного обхода. Первый — рекурсивный. Он выполняет указанное действие с каждым узлом. Второй использует стек и возвращает итератор для непосредственного перебора.

Public void InOrderTraversal(Action action)
{
    InOrderTraversal(action, _head);
}
 
private void InOrderTraversal(Action action, BinaryTreeNode node)
{
    if (node != null)
    {
        InOrderTraversal(action, node.Left);
 
        action(node.Value);
 
        InOrderTraversal(action, node.Right);
    }
}
 
public IEnumerator InOrderTraversal()
{
// Это нерекурсивный алгоритм.
// Он использует стек для того, чтобы избежать рекурсии.
    if (_head != null)
    {
// Стек для сохранения пропущенных узлов.
        Stack stack = new Stack();
 
        BinaryTreeNode current = _head;

// Когда мы избавляемся от рекурсии, нам необходимо
// запоминать, в какую стороны мы должны двигаться.
        bool goLeftNext = true;
 
// Кладем в стек корень.
        stack.Push(current);
 
        while (stack.Count > 0)
        {
// Если мы идем налево...
            if (goLeftNext)
            {
// Кладем все, кроме самого левого узла на стек.
// Крайний левый узел мы вернем с помощю yield.
                while (current.Left != null)
                {
                    stack.Push(current);
                    current = current.Left;
                }
            }
 
// Префиксный порядок: left->yield->right.
            yield return current.Value;
 
// Если мы можем пойти направо, идем.
            if (current.Right != null)
            {
                current = current.Right;
 
// После того, как мы пошли направо один раз,
// мы должным снова пойти налево.
                goLeftNext = true;
            }
            else
            {
// Если мы не можем пойти направо, мы должны достать родительский узел
// со стека, обработать его и идти в его правого ребенка.
                current = stack.Pop();
                goLeftNext = false;
            }
        }
    }
}

Метод GetEnumerator

• Поведение: Возвращает итератор для обхода дерева инфиксным способом.
• Сложность: Получение итератора — O(1). Обход дерева — O(n).

public IEnumerator GetEnumerator()
{
    return InOrderTraversal();
}
 
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}

Продолжение следует

На этом мы заканчивает пятую часть руководства по алгоритмам и структурам данных. В следующей статье мы рассмотрим множества (Set).

_{Перевод статьи «The Binary Search Tree»}