В этом руководстве вы узнаете о древовидной структуре данных. Кроме того, вы узнаете о различных типах деревьев и терминологии, используемой в дереве.
Дерево - это нелинейная иерархическая структура данных, состоящая из узлов, соединенных ребрами.
Дерево
Почему древовидная структура данных?
Другие структуры данных, такие как массивы, связанный список, стек и очередь, представляют собой линейные структуры данных, в которых данные хранятся последовательно. Чтобы выполнить любую операцию в линейной структуре данных, временная сложность увеличивается с увеличением размера данных. Но это неприемлемо в современном вычислительном мире.
Различные древовидные структуры данных обеспечивают более быстрый и легкий доступ к данным, поскольку это нелинейная структура данных.
Терминология дерева
Узел
Узел - это объект, который содержит ключ или значение и указатели на его дочерние узлы.
Последние узлы каждого пути называются листовыми узлами или внешними узлами, которые не содержат ссылки / указателя на дочерние узлы.
Узел, имеющий по крайней мере дочерний узел, называется внутренним узлом .
Край
Это связь между любыми двумя узлами.
Узлы и края дерева
Корень
Это самый верхний узел дерева.
Высота узла
Высота узла - это количество ребер от узла до самого глубокого листа (т. Е. Самый длинный путь от узла до листового узла).
Глубина узла
Глубина узла - это количество ребер от корня до узла.
Высота дерева
Высота дерева - это высота корневого узла или глубина самого глубокого узла.
Высота и глубина каждого узла в дереве
Степень узла
Степень узла - это общее количество ветвей этого узла.
лес
Набор непересекающихся деревьев называется лесом.
Создание леса из дерева
Вы можете создать лес, срезав корень дерева.
Виды дерева
- Двоичное дерево
- Дерево двоичного поиска
- AVL Tree
- B-дерево
Обход дерева
Чтобы выполнить какую-либо операцию с деревом, вам необходимо достичь определенного узла. Алгоритм обхода дерева помогает посетить требуемый узел в дереве.
Чтобы узнать больше, посетите обход дерева.
Дерево приложений
- Деревья двоичного поиска (BST) используются для быстрой проверки того, присутствует ли элемент в наборе или нет.
- Куча - это своего рода дерево, которое используется для сортировки кучи.
- Модифицированная версия дерева под названием Tries используется в современных маршрутизаторах для хранения информации о маршрутизации.
- Большинство популярных баз данных используют B-деревья и T-деревья, которые являются вариантами древовидной структуры, которую мы узнали выше, для хранения своих данных.
- Компиляторы используют дерево синтаксиса для проверки синтаксиса каждой программы, которую вы пишете.
