Типы бинарного дерева

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

Мы обсудили введение в бинарное дерево в наборе 1 и свойства бинарного дерева в наборе 2. В этом посте обсуждаются распространенные типы бинарных деревьев.

Типы бинарного дерева в зависимости от количества детей:

Ниже приведены типы двоичного дерева в зависимости от количества дочерних элементов:

  1. Полное бинарное дерево
  2. Вырожденное бинарное дерево
  3. Искаженные бинарные деревья

1. Полное бинарное дерево

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

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

2. Вырожденное (или патологическое) дерево

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

3. Искаженное бинарное дерево

Искаженное бинарное дерево — это патологическое/вырожденное дерево, в котором доминируют либо левые, либо правые узлы. Таким образом, существует два типа искаженного бинарного дерева: левостороннее двоичное дерево и правостороннее двоичное дерево.

Обратитесь к этой статье, чтобы узнать больше об искаженном двоичном дереве.

Виды бинарного дерева по принципу прохождения уровней :

  1. Полное бинарное дерево
  2. Идеальное бинарное дерево
  3. Сбалансированное бинарное дерево

1. Полное бинарное дерево

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

Полное бинарное дерево похоже на полное бинарное дерево, но с двумя основными отличиями:

  • Каждый уровень должен быть полностью заполнен
  • Все элементы листа должны наклоняться влево.
  • У последнего листового элемента может не быть правильного родственного элемента, т. е. полное бинарное дерево не обязательно должно быть полным бинарным деревом.

Обратитесь к этой статье, чтобы узнать больше о Complete Tree

2. Идеальное бинарное дерево

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

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

В идеальном бинарном дереве количество листовых узлов равно количеству внутренних узлов плюс 1.

L = I + 1, где L = количество листовых узлов, I = количество внутренних узлов.

Идеальное бинарное дерево высоты h (где высота бинарного дерева — это количество ребер на самом длинном пути от корневого узла до любого конечного узла в дереве, высота корневого узла равна 0) имеет 2 h + 1 — 1 узел.

Примером идеального бинарного дерева являются предки в семье. Держите человека в корне, родителей как детей, родителей родителей как своих детей.

Обратитесь к этой статье, чтобы узнать больше о Perfect Tree

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

Бинарное дерево является сбалансированным, если высота дерева равна O(Log n), где n — количество узлов. Например, дерево AVL поддерживает высоту O(Log n), следя за тем, чтобы разница между высотами левого и правого поддеревьев не превышала 1. Красно-черные деревья поддерживают высоту O(Log n), следя за тем, чтобы число Количество черных узлов на каждом пути от корня к листу одинаково и нет соседних красных узлов. Сбалансированные деревья двоичного поиска хороши с точки зрения производительности, поскольку они обеспечивают время O (log n) для поиска, вставки и удаления.

Это тип бинарного дерева, в котором разница между высотой левого и правого поддерева для каждого узла равна 0 или 1. На рисунке выше корневой узел со значением 0 несбалансирован с глубиной 2 единицы. .

Некоторые специальные типы деревьев:

На основе значений узлов бинарное дерево можно разделить на следующие специальные типы:

  1. Бинарное дерево поиска
  2. АВЛ-дерево
  3. Красное черное дерево
  4. Б Дерево
  5. B+ Дерево
  6. Дерево сегментов

На изображении ниже показаны важные особые случаи бинарных деревьев:

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

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

  • Левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла.
  • Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла.
  • Каждое из левого и правого поддеревьев также должно быть бинарным деревом поиска.

2. Дерево АВЛ

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

Пример дерева AVL показан ниже:
Приведенное ниже дерево является AVL, потому что разница между высотами левого и правого поддеревьев для каждого узла меньше или равна 1.

3. Красное черное дерево

Красно-черное дерево — это своего рода самобалансирующееся бинарное дерево поиска, в котором каждый узел имеет дополнительный бит, и этот бит часто интерпретируется как цвет (красный или черный). Эти цвета используются для обеспечения сбалансированности дерева при вставках и удалениях. Хотя баланс дерева не идеален, он достаточно хорош, чтобы сократить время поиска и поддерживать его около времени O(log n), где n — общее количество элементов в дереве. Это дерево было изобретено в 1972 году Рудольфом Байером.

4. Б – Дерево

B-Tree — это самобалансирующееся дерево поиска. В большинстве других самобалансирующихся деревьев поиска (таких как AVL и Red-Black Trees) предполагается, что все находится в основной памяти.
Чтобы понять использование B-деревьев, мы должны подумать об огромном количестве данных, которые не могут поместиться в основную память. При большом количестве ключей данные считываются с диска в виде блоков. Время доступа к диску очень велико по сравнению со временем доступа к основной памяти. Основная идея использования B-Trees — уменьшить количество обращений к диску. Большинство операций с деревом (поиск, вставка, удаление, max, min, ..etc ) требуют O(h) обращений к диску, где h — высота дерева. B-дерево — толстое дерево. Высота B-деревьев поддерживается низкой за счет размещения максимально возможных ключей в узле B-дерева. Как правило, размер узла B-дерева сохраняется равным размеру блока диска. Поскольку высота B-дерева невелика, общий доступ к диску для большинства операций значительно сокращается по сравнению со сбалансированными двоичными деревьями поиска, такими как дерево AVL, красно-черное дерево и т. д.

Обратитесь к этой статье, чтобы узнать больше о B-Tree.

5. Дерево В+

B-Tree — это самобалансирующееся дерево поиска. В большинстве других самобалансирующихся деревьев поиска (таких как AVL и Red-Black Trees) предполагается, что все находится в основной памяти.

Чтобы понять использование B-деревьев, мы должны подумать об огромном количестве данных, которые не могут поместиться в основную память. При большом количестве ключей данные считываются с диска в виде блоков. Время доступа к диску очень велико по сравнению со временем доступа к основной памяти. Основная идея использования B-деревьев — уменьшить количество обращений к диску. Для большинства операций с деревом (поиск, вставка, удаление, max, min, ..etc) требуется O(h) обращений к диску, где h — высота дерева. B-дерево — толстое дерево. Высота B-деревьев поддерживается низкой за счет размещения максимально возможных ключей в узле B-дерева. Как правило, размер узла B-дерева сохраняется равным размеру блока диска. Поскольку высота B-дерева невелика, общий доступ к диску для большинства операций значительно сокращается по сравнению со сбалансированными двоичными деревьями поиска, такими как дерево AVL, красно-черное дерево и т. д.

Обратитесь к этой статье, чтобы узнать больше о B+ Tree

6. Дерево сегментов

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

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

Обратитесь к этой статье, чтобы узнать больше о дереве сегментов.

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