Древовидные структуры данных

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

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

  • Множество
  • Стеки
  • Очереди
  • Связанные списки
  • Хэш-таблицы

Нелинейные: структуры данных, которые хранятся в иерархическом отношении.

  • Деревья
  • Графики

Мы собираемся более подробно рассмотреть деревья. Какие примеры деревьев можно привести в реальной жизни?

Файловые системы

Объектная модель документа (DOM)

Азбука Морзе

Мы можем использовать деревья для:

  • Управление иерархическими данными
  • Управление отсортированными списками
  • Облегчение поиска информации (пересечение дерева)
  • Алгоритмы маршрутизации
  • И многое другое!

Терминология

  • Корень – это первый узел дерева.
  • Edge — это связь между двумя узлами.
  • Родительский – это узел, который имеет ребро к дочернему элементу.
  • Дочерний элемент – это узел, у которого есть родитель.
  • Листок – это узел, у которого нет дочерних элементов.
  • Высота – это длина самого длинного пути к листу.
  • Глубина – это длина пути к корню.
  • Поддерево являются потомками узла
  • Трансверсирование — это прохождение через узлы в определенном порядке.
  • Уровни – это поколения узла.
  • Ключи – это значение узла на основе операции поиска.

Другое о деревьях:

  • Дерево настраивается иерархически, а данные располагаются от более общего к частному.
  • Деревья состоят из узлов, которые содержат данные или значения и соединены ребрами.
  • Узлы могут иметь дочерние узлы, но если у них нет дочерних узлов, они называются листьями.
  • Каждый листовой узел будет уникальным.
  • Дочерние узлы не зависят друг от друга.
  • Первый узел дерева является корнем.
  • Если корень соединен с другим узлом, то корень также называется родительским узлом, а соединение — дочерним узлом.
  • В дереве может быть несколько родительских узлов, но только один корень.
  • Если дерево имеет n узлов, то оно всегда будет иметь (n-1) ребер.

Бинарные деревья

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

В зависимости от того, как узлы расположены в бинарном дереве, оно может быть полным, полным и идеальным:

  • Полное двоичное дерево: каждый узел имеет ровно 0 или 2 дочерних элемента (но никогда не 1), и все конечные узлы находятся на одном уровне.
  • Полное бинарное дерево: когда все уровни, кроме последнего, заполнены узлами.
  • Идеальное бинарное дерево: когда все уровни (включая последний) заполнены узлами.

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

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

поперечный

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

Обход по порядку

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

Обход после заказа

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

Обход предварительного заказа и DFS (поиск в глубину)

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

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