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

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

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

Двоичное дерево состоит из узлов, где каждый узел содержит «левую» ссылку, «правую» ссылку и элемент данных. Самый верхний узел в дереве называется корнем.

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

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

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

  • Предварительный обход — сначала посетите родительский элемент, а затем левый и правый дочерние элементы.
  • Обход InOrder — посещение левого дочернего элемента, затем родителя и правого дочернего элемента
  • Обход PostOrder - посещение левого дочернего элемента, затем правого дочернего элемента, а затем родительского

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

На следующем рисунке мы демонстрируем порядок посещения узлов. Число 1 обозначает первый узел в конкретном обходе, а число 7 обозначает последний узел.

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

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

  • каждый узел содержит один ключ (также известный как данные)
  • ключи в левом поддереве меньше, чем ключ в его родительском узле, короче L ‹ P;
  • ключи в правом поддереве больше ключа в его родительском узле, короче говоря, P ‹ R;
  • дубликаты ключей не допускаются.