Как в целом пишут представление (структуры данных) деревьев в коде? и в чём суть Деревьев?

Question

[habrdima]

Простите что длинный вопрос, но для полного понимания сути я с начало описал свои знания, потом задал основные вопросы, они пронумерованы

В общем начал просматривать тему структуры данных и узнал вот что

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

важно, связанный список очевидно отличается от встроенного списка, и реализуется как экземпляр класса, где узел содержит ссылку на следующий узел

в)так же узнал что дек разумно написать как связанный список, и по сути это двусвязный список,
эта логика мне тоже понятна, надо вставлять узел в начало эффективно))

г)Графы, терминология и задачи графа вполне понятны, реализация очень интересна, это

• список смежностей
  
• список ребер
  
• матрица смежностей
  
• матрица ребер, возможно термин не верен
  

д)Деревья

а вот тут уже есть вопросы которые не получается осмыслить в интернете, к примеру

1) пишут что дерево это граф без цикла, это понятно, но значит ли что дерево можно представить как

• список смежностей
  
• список ребер
  
• матрица смежностей
  
• матрица ребер, возможно термин не верен
  

и если можно, то имеет ли это смысл? делает так кто нибуть?

2)так же в википедии есть такая картинка

здесь показано что дерево можно представить в виде встроенного списка, но примеры реализации такого подхода я не нашёл, так вообще делают?

3)Находил пример где Дерево реализуют на подобии связанного списка, значит ли что дерево это тоже просто список? потому что Дерево хоть и похоже на граф, но вершины графа имеют пространственную логику, а у дерева вершины это причинно следственная последовательность и иерархия, из за чего дерево больше похож на связанный список, это так?

4)так же прочитал что

Зачем нужны деревья
Другие структуры данных, например, массивы, списки, стеки и очереди, линейные. Это значит, что данные в них хранятся последовательно. Когда мы выполняем любую операцию в линейной структуре данных, временная сложность растет с увеличением размера данных. В современном мире это не очень круто.

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

значит дерево это просто список для более быстрого поиска?

5)с учётом всего выше сказанного, я пока сделал вывод что дерево это одна из реализаций связанного списка, хотя об этом ни кто не говорит, я понимаю что можно и в виде встроенного списка представить дерево или например в виде словаря, но как это делают в реальных задачах?

Comments

[Wataru]

"встроенный список" - встроенный куда? Вы о каком-то конкретном языке программирования?

[habrdima]

Wataru, python

Answer 1

[Wataru]

1) Можно представлять дерево всеми способами, как и граф. Но в этом случае о деревьях обычно и не говорят. Ну граф, ну без цикла может даже быть. Ну и что? Пользы никакой не несет. Вот если же дерево представлять подвешанным - с одним корнем, с детьми и родителем у каждой вершины, то уже есть куча полезных применений. В основном при реализации всяких хитрых структур данных.

2) Дерево представляется в виде массива. Но не любое. А только полу-полное двоичное дерево (у каждой вершины до 2 детей. Если ребенок один, то левый. Все уровни, кроме последнего заполненны целиком, последний заполнен слева-направо).

3) Дерево нельзя представить в виде списка в общем случае. Потому что список - линеен, а дерево нет. Можно детей в каждой вершине хранить списком. Ну или вырожденное дерево, где у каждой вершины есть только один ребенек.

4) Нет.

5) Нет.

Comments

[habrdima]

1)кто нибуть представляет дерево ввиде матрицы смежности? есть рабочие задачи?
2)картинка про дерево куча, можете дать пример как работать с массивом для дерева кучи?
3)имелось ввиду реализация через класс, как это делается с связанным списком, пример на пайтон https://codechick.io/tutorials/dsa/dsa-binary-sear...
4)зачем в структуре дерево что либо хранить тогда? дерево хоть и не линейное но последовательность узлов, последовательность данных это список
5)как чаще реализуют деревья?

[Wataru]

habrdima,

1) Нет. Только если не знают, что это дерево. Это очень неэффективно хранить n-1 ребер в матрице n x n.

2) Просто в таком полу-полном дереве, как расписал Alexandroppolus можно занумеровать вершины и не хранить ребра вообще, а по номеру вершины вычислять двух ее детей и отца.

3) Не понял

4) Не понял

5) Зависит от задачи. Иногда релизуют класс вершины, в котором есть ссылки на фиксированное количество детей. Иногда хранят списком смежности. Иногда используют массив и вычисляют номера детей.

Answer 2

[Alexandroppolus]

Для дерева чаще всего удобен список смежностей. Или, если явно задано паренты и чилды, у каждого узла есть массив (или список) чилдов, иногда можно хранить ссылку на родительский узел, в зависимости от задачи. Матрица смежностей бесполезна и даже вредна, поскольку она требует O(N^2) памяти и времени работы при N узлах, а у дерева всего N-1 ребер. Для чего может понадобиться список/матрица ребер в случае деревьев, тоже не совсем понятно.

Отдельный часто используемый вид деревьев - двоичное дерево, когда есть не просто равноправные "чилды", а "правый" и "левый" чилд, т.е. вместо списка будут две явно заданные ссылки.

Двоичное дерево из пункта Д2 можно разместить в массиве, потому что оно удачно заполнено (см. описание в ответе Wataru). Зачем нужно? Супер-экономное использование памяти - хранятся только значения узлов, но не нужно хранить ссылки и вообще создавать узлы. Если узел лежит в ячейке arr[i], то его левый чилд - в ячейке arr[2i + 1], правый - в arr[2i + 2], а парент - в arr[floor((i - 1) / 2)]. То есть мгновенный доступ к чилдам и паренту. Подробнее здесь и здесь

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

зависит от ситуации, от алгоритма. Где-то хорош список, где-то массив, где-то дерево - надо выбирать инструмент под задачу. Идеальной для всех случаев структуры данных нет.

Answer 3

[Александр Скуснов]

1) Можно дерево и не привязывать к графу. Есть такое понятие, как иерархия (например проводник в Windows - дерево папок).
2) array это вообще-то массив, а не список. А где искали (и не нашли)?
3) список линейный, дерево разветвлённое
4) дерево не список.
5) дерево не список. Структуру часто представляют в виде хэш-таблицы.

Comments

[habrdima]

1)что такое привязывать к графу?
2)простите, в python array называют список, надо было указать что маслю на этом языке
3)имелось ввиду реализация похожа на связанный список
4)что еще из себя представляют узлы дерева как не список? причем к примеру для кучи и бинарного дерева поиска узлы числовые не просто так
5)хеш-таблица это тот же словарь (я про python, извините если это не удобно), но суть их та же и я про это написал, но вопрос по сути что за идея с этими деревьями и как их больше всего реализуют? можете дать ссылку где показывается задача с реализацией дерева через массив и словарь?

[Александр Скуснов]

1) Вы же сами так и описали:
граф - множество вершин и множество дуг между ними
дерево - граф без циклов
Можно дерево определить как множество иерархических объектов (есть один родитель) с одним корнем (нет родителя).

[Александр Скуснов]

5) я структурами не занимаюсь, просто гуглите и читайте (и книжки в том числе)