Однажды, в погожий день. Команда Панды узнает о Канге: Кенгуру делает машину, которая сжимает все Деревья в деревне Панды. Поскольку Домино — панда, он должен спасти всех своих людей. Он выбирает Rubics, чтобы составить полный отчет о деревьях. Он использует этот отчет, чтобы победить Канга и спасти свою деревню.
Вот полный отчет Rubics on Trees:
Что такое дерево?
Дерево — это нелинейная структура данных, представляющая иерархические данные. Древовидная структура данных определяется как набор объектов или сущностей, известных как узлы, которые связаны друг с другом для представления или имитации иерархии.
Почему дерево в структуре данных?
Для выполнения любой операции в линейной структуре данных (массив, связанный список) сложность времени увеличивается с увеличением размера данных. но это не принято в современном вычислительном мире.
Другая древовидная структура данных обеспечивает более быстрый и легкий доступк данным, поскольку это нелинейная структура данных.
Дерево (с некоторым порядком, например, BST) обеспечивает умеренный доступ/поиск быстрее, чем связанный список, и медленнее, чем массив. Дерево обеспечивает умеренную вставку/удаление (быстрее, чем неупорядоченные связанные списки). Подобно связанным спискам и в отличие от деревьев массивов, нет верхнего предела количества узлов, поскольку узлы связаны с помощью указателя.
Терминология, связанная с древовидной структурой данных:
1) Корень. Первый узел, из которого берет начало дерево, называется корневым узлом. В любом дереве должен быть только один корневой узел.
2) Край. Соединительное звено между любыми двумя узлами называется краем. В дереве с n узлами ровно (n-1) ребер.
3) Родитель:- Узел, который имеет ответвление от него к любому другому узлу, называется родительским узлом. В дереве родитель может иметь любое количество дочерних узлов.
4) Степень. Степень узла — это общее количество дочерних элементов этого узла. Степень дерева — это наивысшая степень узла среди всех узлов дерева.
5) Конечный узел. Узел, не имеющий дочерних элементов, называется конечным узлом. Листовые узлы также называются внешними узлами или конечными узлами.
6) Уровень:- В дереве каждый шаг сверху вниз называется уровнем дерева.
7) Глубина. Общее количество ребер от корневого узла до определенного узла называется глубиной этого узла.
8) Высота:- Общее количество ребер, лежащих на самом длинном пути от любого конечного узла к определенному узлу, называется высотой этого узла.
Различные типы двоичного дерева: -
Существуют различные типы деревьев в структуре данных. Каждое дерево уникально и имеет свое предназначение. Но сначала давайте посмотрим список всех типов деревьев:
- Двоичное дерево с резьбой
- Дерево Хаффмана
- Б Дерево
- Общее дерево
- Лес
- Бинарные деревья
- Бинарные деревья поиска
- Деревья выражений
- Красно-черное дерево
- N-арное дерево
- АВЛ-дерево
Хорошо… отлично!! так что я должен узнать все это?
НЕТ, каждое дерево важно, но вам не нужно учить все. Даже, давайте небольшое объяснение только одного важного.
Резьбовое двоичное дерево: -
Идея многопоточного бинарного дерева состоит в том, чтобы ускорить обход порядка и сделать это без стека и рекурсии. Двоичное дерево делается многопоточным путем создания правого дочернего указателя, который обычно был бы нулевой точкой на неупорядоченный преемник узла (если он существует).
Преимущество:
- Нет необходимости в стеках или рекурсии
Недостатки:
- Операция вставки и удаления становится более сложной
Дерево Хаффмана: -
Идея дерева Хаффмана состоит в том, чтобы построить дерево с минимальным весом внешнего пути.
Дерево Хаффмана или дерево кодирования Хаффмана определяется как полное двоичное дерево, в котором каждый лист дерева соответствует букве в данном алфавите.
Преимущество:
- легко кодировать и декодировать
Недостатки:
- сложнее кодировать и декодировать
Дерево B:-
B-дерево — это самобалансирующаяся древовидная структура данных, которая поддерживает отсортированную структуру данных и позволяет осуществлять поиск, последовательный доступ, вставки и удаления в логарифмическом масштабе. B-дерево обобщает бинарное дерево поиска, допуская узлы с более чем двумя дочерними элементами.
Преимущество:
- сохраняет ключи в отсортированном порядке для последовательного обхода
Недостатки:
- Листовые и нелистовые узлы имеют разный размер
Бинарные деревья: -
Двоичное дерево — это структура данных, которая определяется как набор элементов, называемых узлами. В двоичном дереве самый верхний элемент называется корневым узлом, и каждый узел имеет 0, 1 или максимум 2 дочерних элемента. Узел, который не имеет дочерних элементов, называется конечным узлом или конечным узлом.
Каждый узел содержит элемент данных, левый указатель, указывающий на левого дочернего элемента, и правый указатель, указывающий на правый дочерний элемент.
a) Полные бинарные деревья. Полное бинарное дерево — это бинарное дерево, удовлетворяющее двум свойствам. Во-первых, в полном бинарном дереве каждый уровень, кроме, возможно, последнего, полностью заполнен. Во-вторых, все узлы отображаются максимально слева.
b) Расширенные бинарные деревья. Бинарное дерево T называется расширенным бинарным деревом (или 2-деревом), если каждый узел в дереве не имеет потомка или ровно двое детей
Преимущество:
- Главное преимущество использования бинарных деревьев — простота.
- используется для отражения отношений между данными
Недостатки:
- Удаление узлов — сложная процедура
- Операции вставки, удаления и поиска зависят от высоты дерева.
Двоичные деревья поиска: -
Бинарное дерево поиска, также известное как упорядоченное бинарное дерево, представляет собой вариант бинарного дерева, в котором узлы расположены в определенном порядке.
Преимущество:
- Идеальный способ использовать иерархический способ хранения данных.
- Отразить структурные отношения, существующие в данном наборе данных.
- Сделайте вставку и удаление быстрее, чем связанные списки и массивы.
- Гибкий способ хранения и перемещения данных.
- Используются для хранения как можно большего количества узлов.
Недостатки:
- Он использует рекурсивный подход, который требует больше места в стеке.
- Программирование алгоритма бинарного поиска подвержено ошибкам и сложно.
- Взаимодействие бинарного поиска с иерархией памяти, т.е. кэширование, плохое.
Красно-черное дерево:-
Еще один вид автобалансирующегося дерева — красно-черный. Согласно свойствам красно-черного дерева, красно-черное имя дается потому, что красно-черное дерево окрашено либо в красный, либо в черный цвет на каждом узле.
Оно поддерживает баланс лес. Несмотря на то, что это дерево не полностью сбалансировано, операция поиска занимает всего O (log n) времени.
Когда новые узлы добавляются в красно-черное дерево, узлы будут чередоваться поддерживать свойства красно-черных деревьев.
Преимущество:
- Красно-черные деревья уравновешивают высоту бинарного дерева.
- Красно-черное дерево требует меньше времени для структурирования дерева за счет восстановления высоты бинарного дерева.
- Временная сложность операции поиска составляет O(log n).
- Он имеет сравнительно низкие константы в широком диапазоне сценариев.
Недостатки:
- Даже если вам нужны упорядоченные данные, красно-черные деревья могут быть не идеальными.
- В дисковом вводе-выводе поиск дороже по сравнению с последовательным чтением блоков.
Дерево АВЛ: -
Дерево AVL — это бинарное дерево поиска, самобалансирующееся. От имени изобретателей Адельсон-Велши и Лэндис дано название AVL. Это было первое дерево, которое динамически балансировалось. Коэффициент балансировки назначается для каждого узла в дереве AVL в зависимости от того, сбалансировано дерево или нет.
Высота дочерних узлов не превышает 1. AVL vine. В дереве AVL правильный коэффициент баланса равен 1, 0 и -1. Если в дереве есть новый узел, он будет повернут, чтобы убедиться, что он сбалансирован. Затем он будет вращаться. Общие операции, такие как просмотр, вставка и удаление, занимают O(log n) время в дереве AVL. В основном он применяется при работе с операциями поиска.
Преимущество:
- Высота дерева AVL всегда сбалансирована. Высота никогда не превышает log N, где N — общее количество узлов в дереве.
- Это дает лучшую сложность времени поиска по сравнению с простыми деревьями двоичного поиска.
- Деревья AVL обладают способностью к самобалансировке.
Недостатки:
- Как видите, деревья AVL сложно реализовать.
- Кроме того, деревья AVL имеют высокие постоянные коэффициенты для некоторых операций. …
- Большинство реализаций STL упорядоченных ассоциативных контейнеров (множества, мультимножества, карты и мультикарты) используют красно-черные деревья вместо деревьев AVL.
Заключение:
Итак, вот полный отчет, предоставленный Rubics about Trees.
О, Рубикс, что это? Я просил тебя написать про настоящие Деревья? Что Вы написали? — Домино
О, извините, я думал, вы сказали мне писать о деревьях в структуре данных. Не беда, это тоже может быть полезно. ХЕ-ХЕ! — Рубикс
О нас:
Подпишитесь на нас на medium, чтобы получить полное путешествие по теме, или подпишитесь на Facebook, Quora, LinkedIn или свяжитесь с сообществом >» на Facebook. Прочтите наши другие блоги.
Читать: Хотите начать работу со структурой данных
Читать: Поиск и сортировка
Прочтите: Давайте нарисуем дорожную карту конкурентного кодирования
Если вы новичок, вы можете проверить свои навыки программирования в нашей лаборатории кода.
Спасибо за чтение, Пожалуйста, поддержите в комментариях вопросы, предложения или оценки.
До скорой встречи!!
