Gli alberi sono organizzati da una struttura "firstchild, nextsibling"? Se no, perché no?

Gli alberi, come gli elenchi, sono "tipi di dati astratti" che possono essere implementati in modi diversi. Ogni modo ha i suoi vantaggi e svantaggi.

Nel primo esempio, il vantaggio principale di questa struttura è che puoi accedere a qualsiasi bambino in O (1). Lo svantaggio è che l'aggiunta di un figlio a volte può essere un po 'più costosa quando il la matrice deve essere espansa. Questo costo è relativamente piccolo però. È anche una delle più semplici implementazioni.

Nel secondo esempio, il vantaggio principale è che si aggiunge sempre un bambino in O (1). Il principale svantaggio è che l'accesso casuale a un bambino costa O (n). Inoltre, potrebbe essere meno interessante per gli alberi enormi per due motivi: ha un overhead di memoria di un'intestazione di un oggetto e due puntatori per nodo, ei nodi sono distribuiti casualmente sulla memoria che possono causare un sacco di swap tra la cache della CPU e la memoria quando l'albero viene attraversato, rendendo questo implementazione meno attraente per loro. Tuttavia, questo non è un problema per alberi e applicazioni normali.

Un'ultima possibilità interessante che non è stata menzionata è quella di memorizzare l'intero albero in un singolo array. Ciò porta a un codice più complesso, ma a volte è un'implementazione molto vantaggiosa in casi specifici, soprattutto per gli enormi alberi fissi, poiché è possibile risparmiare il costo dell'intestazione dell'oggetto e allocare memoria contigua.

Quasi tutti i progetti con modelli o documenti modificabili avranno una struttura gerarchica. Può tornare utile per implementare il 'nodo gerarchico' come classe base per diverse entità. Spesso la lista collegata (fratello minore, secondo modello) è il modo naturale in cui crescono molte librerie di classi, tuttavia i bambini possono essere di diversi tipi e probabilmente un " modello di oggetto " non è quello che consideriamo quando parlando di alberi in generale.

La mia implementazione preferita di un albero (nodo) del tuo primo modello è un one-liner (in C #):

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

Eredita da un Elenco generico del tuo tipo (o ereditato da qualsiasi altra raccolta generica del tuo stesso tipo). Camminare è possibile in una direzione: formare la radice verso il basso (gli oggetti non conoscono i loro genitori).

Albero solo genitore

Un altro modello che non hai menzionato è quello in cui ogni bambino ha un riferimento al suo genitore:

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

Camminare su questo albero è possibile solo viceversa, normalmente tutti questi nodi saranno memorizzati in una collezione (array, hashtable, dizionario ecc.) e un nodo sarà localizzato ricercando la collezione su criteri diversi da quelli gerarchici posizione nell'albero che in genere non sarebbe di primaria importanza.

Questi alberi di soli genitori sono solitamente visti nelle applicazioni di database. È abbastanza facile trovare i figli di un nodo con istruzioni "SELECT * WHERE ParentId = x". Tuttavia, raramente troviamo questi trasformati in oggetti di classe del nodo dell'albero come tali. Nelle applicazioni statefull (desktop) possono essere racchiuse in controlli di nodi dell'albero esistenti. Nelle applicazioni stateless (web) anche questo può essere improbabile. Ho visto che gli strumenti di generazione di classi di mappatura ORM generano errori di overflow dello stack quando generano classi per tabelle che hanno una relazione con se stessi (ridacchia), quindi forse questi alberi non sono poi così comuni.

alberi navigabili bidirezionali

Nella maggior parte dei casi pratici, tuttavia, è conveniente avere il meglio di entrambi i mondi. Nodi che hanno una lista di bambini e conoscono anche i loro genitori: alberi bidirezionali navigabili.

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

Questo porta molti altri aspetti da considerare:

• Dove implementare il collegamento e lo scollegamento dei genitori?
  • fai attenzione alla logica del business e lascia l'aspetto fuori dal nodo (lo dimenticheranno!)
  I nodi
  • hanno metodi per creare figli (non consentono di riordinare) (scelta di Microsofts nella loro implementazione di System.Xml.XmlDocument DOM, che mi ha fatto impazzire quando l'ho incontrata per la prima volta)
  • I nodi accettano un genitore nel costruttore (non consente di riordinare)
  • in tutti i metodi add (), insert () e remove () e il loro overload dei nodi (di solito la mia scelta)
• Persistenza
  • Come camminare sull'albero quando si persiste (ad esempio, escludere i collegamenti parentali)
  • Come ricostruire il collegamento bidirezionale dopo la de-serializzazione (impostazione di tutti i genitori come azione post-deserializzazione)
• Notifiche
  • Meccanismi statici (indicatore IsDirty), gestisci in modo ricorsivo nelle proprietà?
  • Eventi, bolla tra i genitori, in basso tra i bambini o in entrambi i modi (ad esempio, si consideri il pump dei messaggi di Windows).

Ora per rispondere alla domanda , gli alberi bidirezionali navigabili tendono ad essere (nella mia carriera e campo finora) il più usato. Esempi sono l'implementazione di Microsoft System.Windows.Forms.Control o System.Web.UI.Control nel framework .Net, ma anche ogni implementazione DOM (Document Object Model) avrà nodi che conoscono il loro genitore e un'enumerazione dei loro figli. Il motivo: facilità d'uso oltre la facilità di implementazione. Inoltre, queste sono in genere classi base per classi più specifiche (XmlNode può essere la base delle classi Tag, Attribute e Text) e queste classi base sono luoghi naturali in cui inserire architetture di serializzazione e gestione eventi generiche.

Gli alberi sono al centro di molte architetture e poter navigare liberamente significa essere in grado di implementare le soluzioni più velocemente.

Non conosco alcuna libreria di container che supporti direttamente il secondo caso, ma la maggior parte delle librerie di contenitori può facilmente supportare tale scenario. Ad esempio, in C ++ potresti avere:

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

I parser probabilmente usano una struttura simile a questa, perché supporta in modo efficiente nodi con numero variabile di elementi e bambini. Non lo so per certo perché di solito non leggo il loro codice sorgente.

Uno dei casi in cui è preferibile disporre della matrice di bambini è quando è necessario un accesso casuale ai bambini. E questo di solito è quando i bambini sono ordinati. Ad esempio, l'albero gerarchico simile a un file può utilizzare questo per una ricerca più rapida del percorso. O albero dei tag DOM quando l'accesso all'indice è molto naturale

Un altro esempio è quando avere i "puntatori" per tutti i bambini consente un utilizzo più conveniente. Ad esempio, entrambi i tipi che hai descritto possono essere usati quando si implementano le relazioni dell'albero con il database relazionale. Ma il primo (dettaglio principale da genitore a figlio in questo caso) consentirà l'interrogazione con SQL generale per dati utili, mentre il secondo vi limiterà in modo significativo.