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

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

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

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

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

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

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

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

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

Бинарное дерево поиска

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

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

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

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

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

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

Чтобы работать с деревьями, нужно уметь обходить его элементы. Существуют такие 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;
}

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

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

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: