Организованы ли деревья структурой «первый ребенок»? Если нет, то почему нет?

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

       +-----------------------------------------+
       |        root                             | 
       | child1            child2         child3 |
       +--+------------------+----------------+--+
          |                  |                |
+---------------+    +---------------+    +---------------+
|    node1      |    |     node2     |    |     node3     |
| child1 child2 |    | child1 child2 |    | child1 child2 |
+--+---------+--+    +--+---------+--+    +--+---------+--+
   |         |          |         |          |         |

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

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

       +-------------------+
       |        root       |
       | child    sibling  +--->NULL
       +--+----------------+
          |             
+----------------+    +----------------+    +----------------+
|    node1       |    |     node2      |    |     node3      |
| child  sibling +--->| child  sibling +--->| child  sibling +--->NULL
+--+-------------+    +--+-------------+    +--+-------------+
   |                     |                     |

Очевидно, что такая структура также может представлять деревья, но она также предлагает некоторые преимущества. Самое главное, что нам больше не нужно беспокоиться о количестве дочерних узлов. При использовании для дерева разбора он предлагает естественное представление для термина типа «a + b + c + d + e», не превращаясь в глубокое дерево.

Библиотеки коллекций предлагают такие древовидные структуры? Используют ли парсеры такую ​​структуру? Если нет, то каковы причины?

Деревья, как и списки, являются «абстрактными типами данных», которые могут быть реализованы различными способами. У каждого способа есть свои преимущества и недостатки.

В первом примере основным преимуществом этой структуры является то, что вы можете получить доступ к любому дочернему элементу в O (1). Недостатком является то, что добавление потомка может иногда быть немного дороже, когда массив должен быть расширен. Эта стоимость относительно мала, хотя. Это также одна из самых простых реализаций.

Во втором примере главное преимущество заключается в том, что вы всегда добавляете дочерний элемент в O (1). Основным недостатком является то, что произвольный доступ к ребенку стоит O (n). Кроме того, он может быть менее интересным для огромных деревьев по двум причинам: он имеет накладные расходы на память одного заголовка объекта и двух указателей на узел, а узлы случайным образом распределяются по памяти, что может вызвать значительную перестановку между кэшем ЦП и памяти при обходе дерева, что делает эту реализацию менее привлекательной для них. Это не проблема для обычных деревьев и приложений.

Последняя интересная возможность, о которой не упоминалось, - хранить все дерево в одном массиве. Это приводит к более сложному коду, но иногда является очень выгодной реализацией в конкретных случаях, особенно для огромных фиксированных деревьев, так как вы можете сэкономить стоимость заголовка объекта и выделить непрерывную память.

Почти у каждого проекта, который имеет какую-либо редактируемую модель или документ, будет иерархическая структура. Это может пригодиться для реализации «иерархического узла» в качестве базового класса для различных объектов. Часто связанный список (дочерний брат, 2-я модель) является естественным способом роста многих библиотек классов, однако дочерние объекты могут быть разных типов, и, вероятно, « объектная модель » - это не то, что мы рассматриваем, когда говорим о деревьях в целом.

Моя любимая реализация дерева (узла) вашей первой модели - это однострочная (в C #):

public class node : List<node> { /* props go here */ }

Наследовать от универсального списка вашего собственного типа (или наследовать от любого другого универсального набора ваших собственных типов). Ходьба возможна в одном направлении: сформируйте корень вниз (предметы не знают своих родителей).

Только родительское дерево

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

               null
                 |
       +---------+---------------------------------+
       |       parent                              |
       | root                                      |
       +-------------------------------------------+
          |                   |                |
+---------+------+    +-------+--------+    +--+-------------+
|     parent     |    |     parent     |    |     parent     |
|     node 1     |    |     node 2     |    |     node 3     |
+----------------+    +----------------+    +----------------+

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

Эти только родительские деревья обычно видны в приложениях базы данных. Найти дочерние элементы узла с помощью операторов SELECT * WHERE ParentId = x довольно просто. Однако мы редко находим их преобразованными в объекты класса дерева-узла как таковые. В приложениях Statefull (для настольных компьютеров) они могут быть включены в существующие элементы управления узлов деревьев. В приложениях без сохранения состояния (веб) даже это может быть маловероятным. Я видел, как инструменты генерации классов ORM-карт генерируют ошибки переполнения стека при генерации классов для таблиц, которые имеют отношение к себе (смех), так что, возможно, эти деревья не так уж и распространены.

двунаправленные судоходные деревья

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

                          null
                            |
       +--------------------+--------------------+
       |                  parent                 |
       |        root                             | 
       | child1            child2         child3 |
       +--+------------------+----------------+--+
          |                  |                |
+---------+-----+    +-------+-------+    +---+-----------+
|      parent   |    |     parent    |    |  parent       |
|    node1      |    |     node2     |    |     node3     |
| child1 child2 |    | child1 child2 |    | child1 child2 |
+--+---------+--+    +--+---------+--+    +--+---------+--+
   |         |          |         |          |         |

Это включает в себя еще много аспектов для рассмотрения:

• Где реализовать связывание и открепление родительского?
  • позвольте бизнес-логике позаботиться и оставить аспект вне узла (они забудут!)
  • узлы имеют методы для создания дочерних элементов (не позволяет переупорядочивать) (выбор Microsoft в их DOM-реализации System.Xml.XmlDocument, что почти свело меня с ума, когда я впервые столкнулся с этим)
  • Узлы принимают родительский элемент в своем конструкторе (не позволяет переупорядочивать)
  • во всех методах add (), insert () и remove () и их перегрузках узлов (обычно мой выбор)
• Настойчивость
  • Как пройтись по дереву при сохранении (не указывать, например, родительские ссылки)
  • Как восстановить двустороннюю связь после десериализации (снова установив всех родителей как действие после десериализации)
• Уведомления
  • Статические механизмы (флаг IsDirty), рекурсивно обрабатывать в свойствах?
  • События, всплывающие через родителей, вниз через детей, или обоими способами (например, рассмотрите насос сообщений Windows).

Теперь, чтобы ответить на вопрос , двунаправленные навигационные деревья имеют тенденцию (пока что в моей карьере и области) наиболее широко используемые. Примерами являются реализация Microsoft System.Windows.Forms.Control или System.Web.UI.Control в среде .Net, но также каждая реализация DOM (объектная модель документа) будет иметь узлы, которые знают своего родителя, а также перечисление их детей. Причина: простота использования, а не простота реализации. Кроме того, это, как правило, базовые классы для более специфических классов (XmlNode может являться базой для классов Tag, Attribute и Text), и эти базовые классы являются естественными местами для размещения общих сериализаций и архитектур обработки событий.

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

Я не знаю ни одной библиотеки контейнеров, которая напрямую поддерживает ваш второй случай, но большинство библиотек контейнеров могут легко поддерживать этот сценарий. Например, в C ++ вы могли бы иметь:

class Node;  // forward reference to satisfy the compiler
typedef std::list<Node*> NodeList;
class Node : public NodeList { /* . . . */ };  // a node is also a list

Node* n = new Node;
n->push_back(new Node);
Node* tree = new Node;
tree->push_back(new Node);
tree->push_back(n);

Парсеры, вероятно, используют структуру, подобную этой, потому что она эффективно поддерживает узлы с переменным количеством элементов и дочерних элементов. Я не знаю наверняка, потому что я обычно не читаю их исходный код.

Один из случаев, когда предпочтительнее иметь массив дочерних элементов, - это когда вам нужен произвольный доступ к дочерним элементам. И это обычно когда дети сортируются. Например, файловое дерево иерархии может использовать это для более быстрого поиска пути. Или дерево тегов DOM, когда индексный доступ очень естественен

Другой пример, когда наличие «указателей» на всех детей позволяет более удобное использование. Например, оба описанных вами типа могут использоваться при реализации древовидных отношений с реляционной базой данных. Но первое (в данном случае master-detail от родительских до дочерних) позволит запрашивать полезные данные с помощью общего SQL, а второе значительно ограничит вас.