Введение в дерево — учебные пособия по структуре данных и алгоритмам

Опубликовано: 26 Февраля, 2023

Что такое древовидная структура данных?

A Tree is a non-linear data structure and a hierarchy consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the “children”).

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

Рекурсивное определение:

A tree consists of a root, and zero or more subtrees T1, T2, … , Tk such that there is an edge from the root of the tree to the root of each subtree.

Почему дерево считается нелинейной структурой данных?

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

Основные термины в древовидной структуре данных:

  • Родительский узел: узел, который является предшественником узла, называется родительским узлом этого узла. {B} является родительским узлом {D, E} .
  • Дочерний узел: узел, который является непосредственным преемником узла, называется дочерним узлом этого узла. Примеры: {D, E} являются дочерними узлами {B}.
  • Корневой узел: самый верхний узел дерева или узел, не имеющий родительского узла, называется корневым узлом. {A } — корневой узел дерева. Непустое дерево должно содержать ровно один корневой узел и ровно один путь от корня ко всем остальным узлам дерева.
  • Листовой узел или внешний узел: узлы, не имеющие дочерних узлов, называются листовыми узлами. {K, L, M, N, O, P} — листовые узлы дерева.
  • Предок узла: любые предшествующие узлы на пути от корня к этому узлу называются предками этого узла. {A,B} являются узлами-предками узла {E}.
  • Потомок: любой последующий узел на пути от конечного узла к этому узлу. {E,I} являются потомками узла {B}.
  • Родной брат: дочерние элементы одного и того же родительского узла называются братьями и сестрами. {D,E} называются братьями и сестрами.
  • Уровень узла: количество ребер на пути от корневого узла к этому узлу. Корневой узел имеет уровень 0 .
  • Внутренний узел: узел с хотя бы одним дочерним элементом называется внутренним узлом.
  • Сосед узла: родительские или дочерние узлы этого узла называются соседями этого узла.
  • Поддерево : любой узел дерева вместе с его потомком.

Свойства дерева:

  • Количество ребер: ребро можно определить как соединение между двумя узлами. Если дерево имеет N узлов, то оно будет иметь (N-1) ребер. Существует только один путь от каждого узла к любому другому узлу дерева.
  • Глубина узла: Глубина узла определяется как длина пути от корня до этого узла. Каждое ребро добавляет к пути 1 единицу длины. Таким образом, его также можно определить как количество ребер на пути от корня дерева к узлу.
  • Высота узла: высота узла может быть определена как длина самого длинного пути от узла до конечного узла дерева.
  • Высота дерева: Высота дерева — это длина самого длинного пути от корня дерева до конечного узла дерева.
  • Степень узла: общее количество поддеревьев, прикрепленных к этому узлу, называется степенью узла. Степень листового узла должна быть 0 . Степень дерева — это максимальная степень узла среди всех узлов дерева.

Еще некоторые свойства:

  • Обход дерева осуществляется алгоритмами поиска в глубину и поиска в ширину.
  • У него нет ни петли, ни цепи
  • у него нет самозамыкания
  • Его иерархическая модель.

Синтаксис:

struct Node
{
   int data;
   struct Node *left_child;
   struct Node *right_child;
};

Основная операция дерева:

Create – create a tree in data structure.
Insert − Inserts data in a tree.
Search − Searches specific data  in a tree to check it is present or not.
Preorder Traversal – perform Traveling a tree in a pre-order manner in data structure .
In order Traversal – perform Traveling a tree in an in-order manner.
Post order Traversal –perform Traveling a tree in a post-order manner.

Пример структуры данных дерева

Здесь,

Узел 1 является корневым узлом

1 является родителем 2 и 3

2 и 3 это братья и сестры

4, 5, 6 и 7 — листовые узлы.

1 и 2 являются предками 5

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

Различают следующие типы древовидных структур данных:

1. Общее дерево

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

2. Бинарное дерево

У узла бинарного дерева может быть максимум два дочерних узла. На данной древовидной диаграмме узлы B, D и F являются левыми дочерними элементами, а E, C и G — правыми дочерними элементами.

3. Сбалансированное дерево

Если высота левого поддерева и правого поддерева равна или отличается не более чем на 1, дерево называется сбалансированным.

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

Как следует из названия, бинарные деревья поиска используются для различных алгоритмов поиска и сортировки. Примеры включают дерево AVL и красно-черное дерево. Это нелинейная структура данных. Он показывает, что значение левого узла меньше, чем у его родителя, а значение правого узла больше, чем у его родителя.

Приложения структуры данных дерева:

Приложения древовидных структур данных следующие:

1. Связующие деревья. Это дерево кратчайших путей, используемое маршрутизаторами для направления пакетов к месту назначения.

2. Двоичное дерево поиска: это тип древовидной структуры данных, который помогает поддерживать отсортированный поток данных.

  1. Полное бинарное дерево
  2. Полное бинарное дерево
  3. Искривленное бинарное дерево
  4. Строго бинарное дерево
  5. Расширенное бинарное дерево

3. Хранение иерархических данных: древовидные структуры данных используются для хранения иерархических данных, что означает, что данные расположены в упорядоченном виде.

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

5. Попробуйте: это быстрый и эффективный способ динамической проверки орфографии. Он также используется для поиска определенных ключей внутри набора.

6. Куча: это также древовидная структура данных, которую можно представить в виде массива. Он используется для реализации приоритетных очередей.

РЕКОМЕНДУЕМЫЕ СТАТЬИ