В компании, занимающейся решением проблем, вы всегда можете использовать грубую силу для решения любой проблемы. Но мы - больше, чем просто 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, поскольку у него нет узлов поверх него или можно сказать, что у него нет родителя.
Надеюсь, вы смогли немного узнать о том, как древовидная структура данных помогает в решении проблем.