Бинарное (двоичное) дерево поиска, обходы и применение
Дерево — это один из абстрактных типов данных, а также любая структура данных, которая этот тип реализует. Деревья моделируют иерархичную древовидную структуру (ну например, семейное древо), в котором существует только один корень (корневой элемент) и узлы (другие элементы), связанные отношениями потомок — родитель, где любой отдельно взятый элемент имеет только одного родителя (кроме корня, у него-то родителей нет).
Ещё деревья можно определить рекурсивно: дерево может быть или пустым, или состоять из узла (корня), являющимся родительским узлом для некоторого количества деревьев. Количество дочерних узлов обозначает арность дерева; другими словами, n-арное дерево не может содержать более n дочерних элементов (далее дочерний узел, дочерний элемент и потомок будут иметь один и тот же смысл) для каждого узла. Арность дерева — это тоже самое, что и степень дерева. Если же для каждого узла дерева определяется индивидуальная степень, то говорят только про степень конкретных узлов.
Помимо этого необходимо знать ещё 2 понятия в разговоре о деревьях: путь до вершины (всегда начинаем от корня) и высота дерева (реже — глубина). Путь — это множество переходов в дереве, от корня к необходимому узлу. Число узлов в любом пути называется длиной пути, а максимальная длина пути из всех — высотой дерева. Поскольку дерево — частный случай графа, то такие переходы называют рёбрами, а узлы — вершинами.
Одной из форм записи деревьев «на бумаге» называется скобочной записью:
А для наглядности расставим пробелы и переносы:
А так оно выглядит на самом деле:
Деревья полезны, они используются во многих задачах, например:
- парсеры и трансляторы используют синтаксическое дерево;
- при работе со строками используются суффиксные деревья;
- бинарные деревья используются в большом количестве задач: от сортировки и поиска, до создания на их базе других, более сложных структур данных.
Важно место в информатике занимают бинарные (или двоичные) деревья, у которых для каждого узла не более 2-х дочерних элементов, это левый и правый наследники. БНФ форма его определения выглядит так:
Существуют множество разных бинарных деревьев, например, двоичная куча (или сортирующее дерево). Оно используется в пирамидальной сортировке и при реализации приоритетных очередей. Для этого на обычное бинарное дерево нужно всего лишь наложить такие ограничения:
- Значение в любой вершине не меньше, чем значения её потомков.
- Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой.
- Последний слой заполняется слева направо без «дырок».
А вот другое — бинарное дерево поиска. Используется для организации хранения данных таким образом, чтобы гарантировать поиск элемента за логарифмическое время:
- Оба поддерева — левое и правое — являются двоичными деревьями поиска.
- У всех узлов левого поддерева для произвольного узла значения ключей меньше значения ключа этого узла.
- У всех узлов правого поддерева для произвольного узла значения ключей больше либо равны значения ключа этого узла.
Поиск элемента с заданным значением в таком дереве происходит очевидным образом: начиная с корня сравниваем текущее значение узла с заданным; если они равны, то значение найдено, иначе сравниваем значения и выбираем следующий узел для проверки: левый или правый.
Чтобы работать с деревьями, нужно уметь обходить его элементы. Существуют такие 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)
Чтобы реализовать центрированный обход, не обязательно использовать рекурсии или стек. Для этого добавляют новые связи (полученное дерево будет называться прошитым бинарным деревом), где каждому левому потомку, у которого нет своего левого потомка, назначают указатель на предыдущий элемент в порядке центрированного обхода, а для правых по тем же причинам — следующий.
Прошитое бинарное дерево поиска
Типичная структура данных одного узла такого дерева выглядит так:
Другой способ обхода дерева заключается в способе хранения информации о связях в массиве. Такой способ позволяет быстро находить дочерние и родительские элементы, производя обычные арифметические операции (а именно — для левого потомка и для правого, где — индекс родительского узла, если считать с 1). Но эффективность заполнения такого массива напрямую зависит от полноты бинарного дерева. Самый худший вариант развития событий произойдёт тогда, когда у дерева есть только один дочерний элемент в каждом узле (не важно, левого или правого). Тогда для хранения узлов потребуется ячеек в массиве.
Использование обхода бинарных деревьев облегчает работу с алгебраическими выражениями. Так, обратная польская нотация для алгебраического выражения получается путём обратного обхода заранее построенного бинарного дерева. Такое дерево называется деревом синтаксического разбора выражения, в котором узлы хранят операнды ( +, –, *, / ), а листья — числовые значения.
Источник
Обход дерева – центрированный (inorder), прямой (preorder) и обратный (postorder) (три основных способа обхода)
Обход дерева означает посещение каждого узла дерева. Например, вы можете добавить все значения в дерево или найти самое большое. Для всех этих операций вам необходимо будет посетить каждый узел дерева. Линейные структуры данных, такие как массивы, стеки, очереди и связанный список, имеют только один способ чтения данных. Но иерархическая структура данных, такая как дерево, может проходить разными способами. Давайте подумаем о том, как мы можем прочитать элементы дерева на изображении, показанном выше. Начиная сверху, слева направо
Начиная снизу, слева направо
Хотя этот процесс в некотором роде прост, он не учитывает иерархию дерева, а только глубину узлов. Вместо этого мы используем методы обхода, которые учитывают базовую структуру дерева, то есть
Помните, что нашей задачей является посещение каждого узла, поэтому нам нужно посетить все узлы в поддереве, посетить корневой узел и также посетить все узлы в правом поддереве.
В зависимости от порядка, в котором мы это делаем, может быть три типа обхода .
Центрированный тип обхода (Inorder traversal)
- Сначала посетите все узлы в левом поддереве
- Затем корневой узел
- Посетите все узлы в правом поддереве
inorder(root->left) display(root->data) inorder(root->right)Прямой тип обхода (Preorder traversal)
- Посетите корневой узел
- Посетите все узлы в левом поддереве
- Посетите все узлы в правом поддереве
display(root->data) preorder(root->left) preorder(root->right)Обратный тип обхода (Postorder traversal)
- посетить все узлы в левом поддереве
- посетить корневой узел
- посетить все узлы в правом поддереве
postorder(root->left) postorder(root->right) display(root->data)Давайте визуализируем центрированный тип обхода (inorder traversal). Начнем с корневого узла.
Сначала мы проходим левое поддерево. Мы также должны помнить, что нужно посетить корневой узел и правое поддерево, когда дерево будет готово.
Давайте поместим все это в стек, чтобы мы помнили.
Теперь перейдем к поддереву, указанному на вершине стека.
Опять же, мы следуем тому же правилу центрированного типа (inorder)
Left subtree -> root -> right subtreeПройдя левое поддерево, мы остаемся с
Поскольку у узла "5" нет поддеревьев, мы печатаем его напрямую. После этого мы печатаем его родительский узел «12», а затем правый дочерний «6».
Поместить все в стек было полезно, потому как теперь, когда левое поддерево корневого узла было пройдено, мы можем распечатать его и перейти к правому поддереву.
После прохождения всех элементов, центрированный тип обхода (inorder traversal) выглядит так:
Нам не нужно создавать стек самостоятельно, потому что рекурсия поддерживает для нас правильный порядок.
Полный код для центрированного (inorder), прямого (preorder) и обратного (postorder) типа обхода на языке программирования C размещен ниже:
#include #include struct node < int data; struct node* left; struct node* right; >; void inorder(struct node* root)< if(root == NULL) return; inorder(root->left); printf("%d ->", root->data); inorder(root->right); > void preorder(struct node* root)< if(root == NULL) return; printf("%d ->", root->data); preorder(root->left); preorder(root->right); > void postorder(struct node* root) < if(root == NULL) return; postorder(root->left); postorder(root->right); printf("%d ->", root->data); > struct node* createNode(value)< struct node* newNode = malloc(sizeof(struct node)); newNode->data = value; newNode->left = NULL; newNode->right = NULL; return newNode; > struct node* insertLeft(struct node *root, int value) < root->left = createNode(value); return root->left; > struct node* insertRight(struct node *root, int value)< root->right = createNode(value); return root->right; > int main()< struct node* root = createNode(1); insertLeft(root, 12); insertRight(root, 9); insertLeft(root->left, 5); insertRight(root->left, 6); printf("Inorder traversal \n"); inorder(root); printf("\nPreorder traversal \n"); preorder(root); printf("\nPostorder traversal \n"); postorder(root); >Вывод кода будет выглядеть так:
Inorder traversal 5 ->12 ->6 ->1 ->9 -> Preorder traversal 1 ->12 ->5 ->6 ->9 -> Postorder traversal 5 ->6 ->12 ->9 ->1 ->
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
Рекомендуемые статьи по этой тематике
По статье задано0 вопрос(ов)
Вам это нравится? Поделитесь в социальных сетях!
Источник
