Бинарное (двоичное) дерево поиска, обходы и применение

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

Ещё деревья можно определить рекурсивно: дерево может быть или пустым, или состоять из узла (корня), являющимся родительским узлом для некоторого количества деревьев. Количество дочерних узлов обозначает арность дерева; другими словами, n-арное дерево не может содержать более n дочерних элементов (далее дочерний узел, дочерний элемент и потомок будут иметь один и тот же смысл) для каждого узла. Арность дерева — это тоже самое, что и степень дерева. Если же для каждого узла дерева определяется индивидуальная степень, то говорят только про степень конкретных узлов.

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

Одной из форм записи деревьев «на бумаге» называется скобочной записью:

(8 (3 (1) (6 (4) (7))) (10 (14 (13)))) 

А для наглядности расставим пробелы и переносы:

(8  
    (3  
        (1) 
        (6 
            (4) 
            (7) 
        )  
    )  
    (10 
        (14
            (13) 
        )
    )
) 

А так оно выглядит на самом деле:

Деревья полезны, они используются во многих задачах, например:

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

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

<дерево> ::= ( <данные> <дерево> <дерево> ) | nil

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

• Значение в любой вершине не меньше, чем значения её потомков.
• Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой.
• Последний слой заполняется слева направо без «дырок».

А вот другое — бинарное дерево поиска. Используется для организации хранения данных таким образом, чтобы гарантировать поиск элемента за логарифмическое время:

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

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

Чтобы работать с деревьями, нужно уметь обходить его элементы. Существуют такие 3 варианта обхода:

1. Прямой обход (КЛП): корень → левое поддерево → правое поддерево.
2. Центрированный обход (ЛКП): левое поддерево → корень → правое поддерево.
3. Обратный обход (ЛПК): левое поддерево → правое поддерево → корень

Такие обходы называются поиском в глубину, поскольку на каждом шаге итератор пытается продвинуться вертикально вниз по дереву перед тем, как перейти к родственному узлу (узлу на том же уровне). Ещё существует поиск в ширину. Его суть в обходе узлов дерева по уровням, начиная с корня (нужно пройти всего лишь 1 узел) и далее (на втором 2 узла, на третьем 4 узла, ну и т.д.; сколько узлов надо пройти на k-м уровне?).

Реализация поиска в глубину может осуществляться или с использованием рекурсии или с использованием стека, а поиск в ширину реализуется за счёт использования очереди:

preorder(node)
  if (node = null)
    return
  visit(node)
  preorder(node.left)
  preorder(node.right)

iterativePreorder(node)
  s ← empty stack
  s.push(node)
  while (not s.isEmpty())
    node ← s.pop()
    visit(node)
    if (node.right ≠ null)
      s.push(node.right)
    if (node.left ≠ null)
      s.push(node.left)

levelorder(root)
  q ← empty queue
  q.enqueue(root)
  while (not q.isEmpty())
    node ← q.dequeue()
    visit(node)
    if (node.left ≠ null)
      q.enqueue(node.left)
    if (node.right ≠ null)
      q.enqueue(node.right)

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

Типичная структура данных одного узла такого дерева выглядит так:

struct node {    
	data_type_t dat;    
	node *left, *right; //теперь left и right могут указывать как на дочерние элементы, так и содержать нитки, ведущие на другие уровни    
	bool left_is_thread, right_is_thread;
}

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

Использование обхода бинарных деревьев облегчает работу с алгебраическими выражениями. Так, обратная польская нотация для алгебраического выражения получается путём обратного обхода заранее построенного бинарного дерева. Такое дерево называется деревом синтаксического разбора выражения, в котором узлы хранят операнды (+, –, *, /), а листья — числовые значения.