Объяснение 4 типов деревьев в структуре данных: свойства и приложения

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

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

Вот несколько терминов, связанных с деревьями в структуре данных :

• Узел : узел — это объект в древовидной структуре данных, который содержит ключ или значение и указатели на его дочерние узлы.
• Дочерний узел : дочерний узел является потомком любого узла.
• Листовые узлы: узлы, которые не имеют дочерних узлов и являются самым нижним узлом в дереве. Их также называют внешними узлами.
• Корень : это самая верхняя точка дерева.
• Внутренний узел : узел, имеющий хотя бы один дочерний узел.
• Край: край относится к соединению между любыми двумя узлами в дереве.
• Высота узла: количество ребер от узла до самого глубокого листа.
• Глубина узла : количество ребер от корня до узла.
• Высота дерева : высота корневого узла.
• Степень узла : общее количество ветвей к этому узлу.
• Лес: набор непересекающихся деревьев.

Виды дерева

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

Двоичное дерево — это тип древовидной структуры данных, в которой каждый родительский узел имеет не более двух дочерних узлов. Как следует из названия, двоичный означает два, поэтому каждый узел может иметь 0, 1 или 2 узла. Структура данных двоичного дерева показана на рисунке 1. Узел 1 в дереве содержит два указателя, по одному на каждый дочерний узел. Узел 2 снова имеет по два указателя на два дочерних узла. Принимая во внимание, что узлы 3, 5 и 6 являются конечными узлами и, следовательно, имеют нулевые указатели как в левой, так и в правой частях.

Рисунок 1: Представление бинарного дерева ( https://www.javatpoint.com/binary-tree ).

Свойства бинарного дерева

• Максимальное количество узлов на каждом уровне I равно 2 i .
• Высота дерева на рисунке 1 равна 3, что означает, что максимальное количество узлов будет (1+2+4+8)=15.

• На высоте h максимально возможное количество узлов равно (20 + 21 + 22+….2h) = 2h+1 -1.

• На высоте h минимально возможное количество узлов равно h+1.

• Минимальное количество узлов будет представлять дерево максимальной высоты и наоборот.

Даже бинарные деревья можно разделить на следующие типы деревьев:

• Полное бинарное дерево: это особый тип бинарного дерева. В этой древовидной структуре данных каждый родительский узел или внутренний узел имеет либо двух дочерних узлов, либо не имеет дочерних узлов.
• Идеальное бинарное дерево: в этом типе древовидной структуры данных каждый внутренний узел имеет ровно два дочерних узла, и все конечные узлы находятся на одном уровне.
• Полное бинарное дерево: похоже на полное бинарное дерево с некоторыми отличиями.
• Каждый уровень полностью заполнен.
• Листовые узлы наклоняются влево от дерева.
• Не обязательно, чтобы последний листовой узел имел правильного родственного узла, т. е. полное бинарное дерево не обязательно должно быть полным бинарным деревом.
• Вырожденное или патологическое дерево: у этих деревьев есть один дочерний элемент слева или справа от родительского узла.
• Искаженное бинарное дерево: это патологическое или вырожденное дерево, в котором преобладают либо левые, либо правые узлы. Таким образом, существует два типа асимметричных бинарных деревьев, т.е. асимметричное влево или бинарное дерево с правосторонним асимметрией.
• Сбалансированное бинарное дерево: разница между высотой левого и правого поддеревьев для каждого узла равна 0 или 1.

2. Двоичное дерево поиска

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

• Каждый узел имеет не более двух дочерних узлов.
• Его можно использовать для поиска элемента за время 0 (log (n)) и, следовательно, известное как дерево поиска.

Рисунок: Пример двоичного дерева поиска ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

Свойства бинарного дерева поиска:

• Значение во всех узлах левого поддерева должно быть меньше значения в корневом узле.
• Значение во всех узлах правого поддерева должно быть больше значения в корневом узле.

3. Дерево АВЛ

Деревья AVL — это типы или варианты двоичного дерева. Он состоит из свойств как двоичного, так и двоичного дерева поиска. Эти деревья, изобретенные Адельсоном Вельски Линдасом, являются самобалансирующими, что означает, что высота левого поддерева и правого поддерева сбалансированы. Этот баланс измеряется с точки зрения уравновешивающего фактора.

Балансирующий фактор:

• Это разница между левым поддеревом и правым поддеревом.
• Значение коэффициента балансировки должно быть 0, -1 или 1. Следовательно, каждый узел дерева AVL должен состоять из значения коэффициента балансировки, т. е. 0, -1 или 1.
• Коэффициент баланса = (высота левого поддерева – высота правого поддерева)
• Дерево AVL называется сбалансированным, если коэффициент баланса каждого узла находится в диапазоне от -1 до 1.

Значения узлов, отличные от -1, до 1 в дереве AVL, будут представлять несбалансированное дерево, которое необходимо сбалансировать.

• Если узел имеет коэффициент баланса 1, это означает, что левое поддерево на один уровень выше правого поддерева.
• Если узел имеет коэффициент баланса 0, это означает, что высота левого поддерева и правого поддерева равны.
• Если узел имеет коэффициент баланса -1, это означает, что правое поддерево на один уровень выше левого поддерева или левое поддерево на один уровень ниже правого поддерева.

4. B-дерево

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

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

• Ключи хранятся в порядке возрастания для каждого узла x.
• В каждом узле существует логическое значение «x.leaf», которое истинно, если x является листом.
• Внутренние узлы должны иметь не более «n-1» ключей, где n — порядок дерева. Он также должен иметь указатель для каждого ребенка.
• Все узлы будут иметь не более n дочерних элементов и не менее n/2 дочерних элементов, кроме корневого узла.
• Листовые узлы дерева имеют одинаковую глубину.
• Корневой узел будет иметь не менее 1 ключа и не менее двух дочерних элементов.
• Если n ≥ 1, то для любого n-ключевого B-дерева высоты h и минимальной степени t ≥ 2 h ≥ logt (n+1)/2.

Приложения

• Двоичное дерево поиска можно применять для поиска элемента в наборе элементов.
• Деревья кучи используются для сортировки кучи.
• Современные маршрутизаторы используют тип дерева под названием Tries для хранения маршрутной информации.
• B-деревья и T-деревья в основном используются популярными базами данных для хранения своих данных.
• Синтаксическое дерево используется компиляторами для проверки синтаксиса каждой написанной программы.

Заключение

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

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

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

Программа Executive PG в разработке программного обеспечения — специализация в разработке полного стека, курируемая upGrad и IIIT-Bangalore, может помочь вам улучшить свой профиль и обеспечить лучшие возможности трудоустройства в качестве программиста.