В компании, занимающейся решением проблем, вы всегда можете использовать грубую силу для решения любой проблемы. Но мы - больше, чем просто BF (грубая сила) проблемы для решения. Здесь на помощь приходит структура данных. Просто чтобы облегчить жизнь нашим (так называемым программистам). Структура данных дает вам возможность хранить, организовывать и манипулировать данными.

Структура данных: структура данных может быть определена как интерпретация логических отношений, существующих между отдельными элементами данных.

Любого программиста научили бы обрабатывать данные с помощью массивов, связанных списков, стеков и очередей, которые известны как «линейная структура данных» (LDS) и являются основополагающими в процессе обучения. Это простой, но не очень эффективный способ обработки данных. Выбор DS (структуры данных) играет жизненно важную роль во временной и пространственной сложности.

Линейная структура данных:

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

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

Структура данных описывает, как данные организованы, доступны, связаны и обрабатываются.

Как выбрать свой DS?

Нет единого определения, какие DS следует использовать всем. Когда мы выбираем язык программирования, это должно быть нашим собственным выводом.

При выборе DS следует учитывать следующие факторы:

1. Данные, над которыми вы работаете

2. Стоимость операций

3. Пространственно-временная сложность

4. Простота реализации.

Нелинейные структуры данных:

Хотя я уже упоминал выше, что выбор DS - это индивидуальный выбор, этот пост здесь, чтобы сказать, что нелинейная структура данных (NLDS) намного лучше, чем линейная структура данных, в 90% случаев.

Дерево и График обычно используются в NLDS. При использовании NLDS использование памяти будет эффективным, тогда как LDS будет неэффективным.

В отличие от LDS, NLDS не требует предварительного выделения памяти.

Здесь данные хранятся в иерархическом порядке, и элемент (узел) может быть присоединен к более чем одному элементу и может иметь между собой отношения родитель-потомок.

В этом посте все будет о «ДЕРЕВЕ». Он был назван так из-за того, что он перевернут, он выглядит в точности как дерево.

Дерево :

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

Вкратце, Tree - это совокупность узлов, связанных иерархическим образом.

Объект дерева

Object tree{
data_type data;
data_type left_reference;
data_type right_reference;
}

Данные: могут иметь любой тип данных.

Узел может иметь или не иметь ссылки на дочерние элементы, которые называются листовыми узлами.

Жаргоны…

Корневой узел, Родитель, Дети, Братья (и) и двоюродный брат (и) (не часто), Предок и Потомки, Общий предок - все это жаргоны, используемые в древовидной структуре данных.

И узел "Leaf", который, как я упоминал выше, является узлом без ссылки.

Корневой узел: узел, не имеющий родителя и расположенный на вершине дерева.

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

родительские отношения

Дочерние: узел, на который ссылается верхний узел, будет иметь дочерние отношения с верхним узлом.

В дереве обход выполняется только в одном направлении.

Двоичное дерево:

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

Бинарное дерево создается динамически, поэтому нет необходимости объявлять размер, в отличие от LDS.

В BT узлы связаны с помощью указателей / ссылок на дочерние узлы.

Узел BT: каждый узел BT имеет три поля для данных и справки. Поскольку узел может указывать до двух узлов, для ссылок выделяются два поля.

Данные узла могут иметь любой тип данных.

Приложения дерева:

1. Хранить данные иерархически.

2. Чтобы организовать данные для поиска, вставки и удаления. Бывший. Дерево двоичного поиска

3. Специальные деревья, такие как дерево Trie, такие как словарь, который используется при динамической проверке орфографии, которая является быстрой и эффективной.

4. Может быть построен алгоритм сетевой маршрутизации.

Балансы и неуравновешенность:

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

В несбалансированном дереве поиск или вставка занимает O (n), тогда как в сбалансированном - всего O (logn).

Методы обхода:

Простое двоичное дерево предоставляет три способа обхода по нему. Они есть,

1. Предзаказ

2. В порядке

3. Пост-заказ

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

Корень - ›Левый -› Правый

Обход по порядку. Обход по порядку выполняется из формата ниже,

Слева - ›Корень -› справа

Этот метод считается эффективным, поскольку он дает реальное представление двоичного дерева по мере его формирования.

Обход постзаказов. При постзаказе обход выполняется в следующем формате

Слева - ›Справа -› Корень

Характеристики:

Граница дерева: каждая связь между парой узлов в дереве описывается как граница.

Если самый длинный путь Дерева имеет N узлов, количество ребер будет N-1.

Глубина узла: количество ребер на пути от «корневого» узла до этого «узла» считается глубиной.

Высота узла: количество ребер на пути от «узла» до «листа» считается высотой узла.

Высота дерева: количество ребер на пути от «корня» до «листа» считается высотой дерева.

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

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