Albero radicato - Rappresentazione e prestazioni

Question

Albero radicato - Rappresentazione e prestazioni

#1 da (3 voti)
#2 da (0 voti)

1

Rappresentazione 1 - Albero a più percorsi

typedef struct multiWalkTreeNode{
  struct multiWalkTreeNode * parent;
  void *item;
  struct multiWalkTreeNode **childPointer;
}Node;

typedef struct multiWalkTree{
  Node *root;
  int size; /*Number of nodes in the tree*/
}Tree;

Vista grafica:

Rappresentazione2-AlberoLCRS

typedefstructSiblingTreeNode{structSiblingTreeNode*parent;void*item;structSiblingTreeNode*firstChild;structSiblingTreeNode*nextSibling;}Node;typedefstructLCRSTree{Node*root;intsize;}Tree;

Vistagrafica:

Rappresentazione3-Strutturaadalbero(Comedenominarequestoalbero?)

typedefstructDListNode{intitem;structDListNode*next;structDListNode*prev;}DListNode;typedefstructDList{//CircularDListNode*head;intsize;}List;typedefstructtreeNode{structtreeNode*parent;void*item;List*childList;/*Sentinelnodeiscreatedoninitialconstructionofa"List" */
}Node;

typedef struct treeUsingList{
  Node *root;
  int size;
}Tree;

Vista grafica:

Viene introdotto il puntatore padre per eseguire DFS senza ricorsione o stack esplicito.

Conferma la correttezza della rappresentazione.

Domanda:

1) Abbiamo un nome per albero in Representation 3 ?

2) Per le operazioni di inserimento / cancellazione / ricerca, quale rappresentazione si comporta meglio?

3) Ci sono altre rappresentazioni per l'albero radicato, che possono migliorare le prestazioni?

c data-structures trees

posta overexchange 12.12.2016 - 23:45

fonte

2 risposte

0

Puoi considerare la rappresentazione 3 come un albero binario che è appena organizzato in modo diverso. Quindi, invece di scendere, ordini l'elemento sullo stesso livello. Puoi anche chiamarlo grafico, dato che hai i backpointers.

Generalmente un hash può migliorare enormemente le cose. Dal momento che non hai specificato a quale scopo desideri prestazioni migliori è difficile dare una dichiarazione.

risposta data 13.12.2016 - 12:35

fonte

Leggi altre domande sui tag c data-structures trees

ORM Ereditarietà mappatura o no, come mappare proprietà condivise e specifiche per un insieme di oggetti del mondo reale correlati Ricerca della transazione minima

score 3 · Accepted Answer

Ecco alcune considerazioni:

Nel n. 1, non stai acquisendo una dimensione della matrice childPointer , quindi non puoi sapere quanti bambini ci sono.
Il tuo codice per # 3 utilizza void *item nel testo, ma Node *item nel diagramma. Inoltre, gli elementi contrassegnati come sentinella hanno item (struckthru), next e prev, ma dovrebbero (per abbinare il testo) avere head e size.
Nessuna di queste strutture dati è ottimizzata per le operazioni di ricerca, quindi tra queste, meno strutture di dati sono, meglio è, con un piccolo margine (dato che nessuna è ottima per la ricerca). Se la ricerca è la preoccupazione principale, passerei a una struttura dati completamente diversa (ad esempio Albero B o albero binario bilanciato o qualsiasi altra cosa)!
La scelta n. 3, la vedo fondamentalmente rotta. Utilizza una lista doppiamente collegata, che a prima vista potrebbe implicare qualche miglioramento per un numero elevato di bambini riguardo l'inserimento / eliminazione. Tuttavia, osserva che i puntatori principali dei nodi fanno riferimento solo ad altri nodi dell'albero, e non anche alla posizione nella lista doppiamente collegata (che a loro volta non offrono un puntatore genitore). Quindi è ancora necessario un attraversamento completo dei bambini immediati, proprio come nell'opzione n. 2, e l'elenco doppiamente collegato non offre alcun miglioramento, richiede solo più manutenzione e spazio occupato (tutto negativo).
Il carico di lavoro sarà la preoccupazione principale qui per quanto riguarda quale sia il migliore per le prestazioni. Alberi regolari (non una delle tue opzioni) sarebbe il migliore per l'inserimento se ci sono, diciamo, due o meno figli. Per un numero enorme di bambini, una lista doppiamente collegata potrebbe essere migliore, ma non se implementata come # 3.