Типы бинарного дерева
Мы обсудили введение в бинарное дерево в наборе 1 и свойства бинарного дерева в наборе 2. В этом посте обсуждаются распространенные типы бинарных деревьев.
Типы бинарного дерева в зависимости от количества детей:
Ниже приведены типы двоичного дерева в зависимости от количества дочерних элементов:
- Полное бинарное дерево
- Вырожденное бинарное дерево
- Искаженные бинарные деревья
1. Полное бинарное дерево
Двоичное дерево является полным двоичным деревом, если каждый узел имеет 0 или 2 дочерних элемента. Ниже приведены примеры полного бинарного дерева. Мы также можем сказать, что полное бинарное дерево — это бинарное дерево, в котором все узлы, кроме листовых, имеют двух дочерних элементов.
Полное бинарное дерево — это особый тип бинарного дерева, в котором каждый родительский узел/внутренний узел имеет либо двух дочерних элементов, либо ни одного. Он также известен как правильное бинарное дерево.
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 единицы. .
Некоторые специальные типы деревьев:
На основе значений узлов бинарное дерево можно разделить на следующие специальные типы:
- Бинарное дерево поиска
- АВЛ-дерево
- Красное черное дерево
- Б Дерево
- B+ Дерево
- Дерево сегментов
На изображении ниже показаны важные особые случаи бинарных деревьев:
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 — количество извлеченных интервалов или сегментов.
Обратитесь к этой статье, чтобы узнать больше о дереве сегментов.