As árvores são organizadas por uma estrutura de "primeiro filho, próximo"? Se não, por que não?

Geralmente, as estruturas de dados em árvore são organizadas de maneira que cada nó contenha ponteiros para todos os seus filhos.

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

Isso parece natural, mas vem com alguns problemas. Por exemplo, quando o número de nós filhos varia, você precisa de algo como uma matriz ou lista para gerenciar os filhos.

Ao usar apenas ponteiros filho (primeiro) e (próximo) irmão, obtemos algo parecido com isso:

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

Obviamente, esse tipo de estrutura também pode representar árvores, mas também oferece algumas vantagens. O mais importante é que não precisamos mais nos preocupar com o número de nós filhos. Quando usado para uma árvore de análise, oferece uma representação natural para um termo como "a + b + c + d + e" sem se tornar uma árvore profunda.

As bibliotecas de coleções oferecem estruturas de árvores como essa? Os analisadores usam essa estrutura? Caso contrário, quais são os motivos?

Árvores, como listas, são "tipos de dados abstratos" que podem ser implementados de maneiras diferentes. Cada caminho tem suas vantagens e desvantagens.

No primeiro exemplo, a principal vantagem dessa estrutura é que você pode acessar qualquer filho em O (1). A desvantagem é que acrescentar um filho às vezes pode ser um pouco mais caro quando a matriz precisa ser expandida. Esse custo é relativamente pequeno. É também uma das implementações mais simples.

No segundo exemplo, a principal vantagem é que você sempre acrescenta um filho em O (1). A principal desvantagem é que o acesso aleatório a uma criança custa O (n). Além disso, pode ser menos interessante para árvores enormes por dois motivos: possui uma sobrecarga de memória de um cabeçalho de objeto e dois ponteiros por nó, e os nós são aleatoriamente distribuídos pela memória, o que pode causar muitas trocas entre o cache da CPU e o memória quando a árvore é atravessada, tornando essa implementação menos atraente para eles. Isso não é um problema para árvores e aplicativos normais.

Uma última possibilidade interessante que não foi mencionada é armazenar a árvore inteira em uma única matriz. Isso leva a um código mais complexo, mas às vezes é uma implementação muito vantajosa em casos específicos, especialmente para grandes árvores fixas, já que você pode economizar o custo do cabeçalho do objeto e alocar memória contígua.

Quase todo projeto que possui algum modelo ou documento editável terá uma estrutura hierárquica. Pode ser útil implementar o 'nó hierárquico' como uma classe base para diferentes entidades. Frequentemente, a lista vinculada (irmão filho, segundo modelo) é a maneira natural de muitas bibliotecas de classes crescerem, no entanto, os filhos podem ser de diversos tipos e, provavelmente, um " modelo de objeto " não é o que consideramos quando se fala em árvores em geral.

Minha implementação favorita de uma árvore (nó) do seu primeiro modelo é uma linha (em C #):

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

Herdar de uma lista genérica do seu próprio tipo (ou herdar de qualquer outra coleção genérica do seu próprio tipo). É possível caminhar em uma direção: formar a raiz para baixo (os itens não conhecem seus pais).

Árvore apenas dos pais

Outro modelo que você não mencionou é aquele em que toda criança faz referência ao pai:

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

Andar nessa árvore só é possível ao contrário, normalmente todos esses nós serão armazenados em uma coleção (matriz, hashtable, dicionário etc.) e um nó será localizado pesquisando a coleção em critérios diferentes da posição hierárquica no árvore que normalmente não seria de importância primária.

Essas árvores somente para pais são geralmente vistas em aplicativos de banco de dados. É muito fácil encontrar os filhos de um nó com instruções "SELECT * WHERE ParentId = x". No entanto, raramente os encontramos transformados em objetos de classe de nó de árvore, como tal. Em aplicativos statefull (desktop), eles podem ser agrupados em controles de nó de árvore existentes. Em aplicativos sem estado (web), mesmo isso pode ser improvável. Vi ferramentas de gerador de classe de mapeamento ORM gerarem erros de estouro de pilha ao gerar classes para tabelas que têm uma relação consigo mesma (risos), então talvez essas árvores não sejam tão comuns assim.

árvores navegáveis ​​bidirecionais

Na maioria dos casos práticos, no entanto, é conveniente ter o melhor dos dois mundos. Os nós que possuem uma lista de filhos e também conhecem seus pais: árvores navegáveis ​​bidirecionais.

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

Isso traz muitos outros aspectos a serem considerados:

• Onde implementar a vinculação e desvinculação dos pais?
  • deixe a lógica do negócio tomar cuidado e deixe o aspecto fora do nó (eles esquecerão!)
  • os nós têm métodos para criar filhos (não permitem reordenar) (escolha Microsofts na implementação do DOM System.Xml.XmlDocument, que quase me deixou maluco quando o encontrei pela primeira vez)
  • Nós assumem um pai em seu construtor (não permite reordenar)
  • em todos os métodos add (), insert () e remove () e suas sobrecargas nos nós (geralmente minha escolha)
• Persistência
  • Como percorrer a árvore ao persistir (deixe de fora os links dos pais, por exemplo)
  • Como reconstruir o vínculo bidirecional após a desserialização (configurando todos os pais novamente como uma ação pós-desserialização)
• Notificações
  • Mecanismos estáticos (sinalizador IsDirty), manipulam recursivamente nas propriedades?
  • Eventos, borbulham nos pais, nos filhos ou nos dois sentidos (considere a bomba de mensagens do Windows, por exemplo).

Agora, para responder à pergunta , as árvores navegáveis ​​bidirecionais tendem a ser (na minha carreira e campo até agora) as mais utilizadas. Os exemplos são a implementação de System.Windows.Forms.Control ou System.Web.UI.Control na estrutura .Net da Microsoft, mas também toda implementação de DOM (Document Object Model) terá nós que conhecem seus pais e uma enumeração dos filhos deles. O motivo: facilidade de uso sobre facilidade de implementação. Além disso, essas geralmente são classes base para classes mais específicas (XmlNode pode ser a base das classes Tag, Attribute e Text) e essas classes base são locais naturais para colocar arquiteturas genéricas de serialização e manipulação de eventos.

O Tree está no centro de muitas arquiteturas, e poder navegar livremente significa poder implementar soluções mais rapidamente.

Não conheço nenhuma biblioteca de contêineres que suporte diretamente seu segundo caso, mas a maioria das bibliotecas de contêineres pode suportar facilmente esse cenário. Por exemplo, em C ++, você poderia ter:

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);

Os analisadores provavelmente usam uma estrutura semelhante a essa, porque suporta eficientemente nós com números variáveis ​​de itens e filhos. Não sei ao certo porque geralmente não leio o código fonte.

Um dos casos em que é preferível ter filhos é quando você precisa de acesso aleatório aos filhos. E isso geralmente ocorre quando as crianças são classificadas. Por exemplo, a árvore de hierarquia semelhante a arquivo pode usar isso para uma pesquisa de caminho mais rápida. Ou árvore de tags DOM quando o acesso ao índice é muito natural

Outro exemplo é quando o uso de "ponteiros" para todos os filhos permite um uso mais conveniente. Por exemplo, os dois tipos que você descreveu podem ser usados ​​ao implementar relações em árvore com o banco de dados relacional. Mas o primeiro (detalhes principais de pai para filho, neste caso) permitirá consultar o SQL geral para obter dados úteis, enquanto o último o limitará significativamente.