Qual è la rappresentazione di un albero di sinistra, fratello destro? Perché dovresti usarlo?

Molte strutture dati memorizzano alberi multi-way come alberi binari usando una rappresentazione chiamata rappresentazione “left-child, right-sibling” . Cosa significa questo? Perché dovresti usarlo?

La rappresentazione left-child, right-sibling (LCRS) è un modo di codificare un albero a più vie (una struttura ad albero in cui ogni nodo può avere un numero qualsiasi di bambini) usando un albero binario (una struttura ad albero in cui ogni nodo può avere al massimo due bambini).

Motivazione

Per motivare come funziona questa rappresentazione, iniziamo considerando un semplice albero a più vie, come questo qui:

A //|\ \ / / | \ \ BCDEF | /|\ / \ GHIJKL 

(Ci scusiamo per l’artwork ASCII di bassa qualità!)

In questa struttura ad albero, possiamo navigare verso il basso da qualsiasi nodo dell’albero ad uno qualsiasi dei suoi figli. Ad esempio, possiamo migrare da A a B, da A a C, da A a D, ecc.

Se volessimo rappresentare un nodo in un albero come questo, normalmente useremmo una sorta di struttura nodo / class nodo come questa qui (scritta in C ++):

 struct Node { DataType value; std::vector children; }; 

Nella rappresentazione LCRS, rappresentiamo l’albero a più vie in un modo in cui ogni nodo richiede al massimo due puntatori. Per fare ciò, modificheremo leggermente l’albero. Piuttosto che avere ogni nodo nel puntatore del diagramma ad albero di tutti i suoi figli, struttureremo l’albero in un modo leggermente diverso facendo in modo che ogni nodo memorizzi un puntatore su uno dei suoi figli (in LCRS, il figlio più a sinistra). Avremo quindi ogni nodo memorizzare un puntatore al suo fratello destro, il prossimo nodo dell’albero che è figlio dello stesso nodo genitore. Nel caso dell’albero sopra, potremmo rappresentare l’albero nel seguente modo:

  A / / / B -> C -> D -> E -> F / / / G H->I->J K->L 

Si noti che in questa nuova struttura è ancora ansible navigare da un nodo genitore al suo kesimo figlio (indicizzato a zero). La procedura per farlo è la seguente:

  • Discendi nel figlio sinistro del nodo corrente. (Questo è il primo nodo nell’elenco dei suoi figli).
  • Segui il puntatore di pari livello di suo figlio k volte. (Questo ti porta al kesimo figlio del nodo).
  • Restituisci quel nodo.

Ad esempio, per trovare il terzo (figlio indicizzato a zero) del nodo radice A, scendiamo al figlio più a sinistra (B), quindi seguiamo tre collegamenti a destra (visitando B, C, D e infine E). Arriviamo quindi al nodo per E, che contiene il terzo figlio del nodo A.

La ragione principale per rappresentare l’albero in questo modo è che anche se qualsiasi nodo può avere un numero qualsiasi di bambini, la rappresentazione richiede al massimo due puntatori per ogni nodo: un nodo per memorizzare il figlio più a sinistra e un puntatore per memorizzare il fratello giusto. Di conseguenza, possiamo archiviare l’albero a più vie usando una struttura di nodo molto più semplice:

 struct Node { DataType data; Node* leftChild; Node* rightSibling; }; 

Questa struttura di nodes ha esattamente la stessa forma di un nodo in un albero binario (dati più due puntatori). Di conseguenza, la rappresentazione LCRS rende ansible rappresentare un albero a più vie arbitrario utilizzando solo due puntatori per nodo.

Analisi

Vediamo ora la complessità temporale e spaziale delle due diverse rappresentazioni dell’albero a più vie e alcune operazioni di base su di esso.

Iniziamo osservando l’utilizzo totale dello spazio richiesto per la rappresentazione iniziale della “schiera dynamic dei bambini”. Quanto spazio di memoria totale ci sarà per un albero n-nodo? Bene, sappiamo quanto segue:

  1. Ogni nodo, indipendentemente dal numero di figli, contribuisce allo spazio per i dati non elaborati memorizzati (sizeof (dati)) e allo spazio sull’overhead dell’array dinamico. L’array dinamico (in genere) ha un puntatore memorizzato (che punta all’array assegnato), una parola macchina per il numero totale di elementi nell’array dinamico e (facoltativamente) una parola macchina per la capacità allocata dell’array. Ciò significa che ogni nodo occupa spazio sizeof (Data) + sizeof (Nodo *) + 2 * sizeof (parola macchina).

  2. Attraverso tutti gli array dinamici dell’albero, ci saranno n – 1 puntatori ai bambini, poiché i n nodes nell’albero n – 1 di loro hanno genitori. Ciò aggiunge un fattore extra (n – 1) * sizeof (Nodo *).

Pertanto, l’utilizzo totale dello spazio è

n · (sizeof (Data) + sizeof (Nodo *) + 2 * sizeof (parola macchina)) + (n – 1) * sizeof (Nodo *)

= n * sizeof (Dati) + (2n – 1) * sizeof (Nodo *) + 2n * sizeof (parola macchina)

Ora, parliamone con un albero LCRS. Ogni nodo in un albero LCRS memorizza due puntatori (2 * sizeof (Nodo *)) e un elemento dati (sizeof (Dati)), quindi il suo spazio totale è

n * sizeof (Data) + 2n * sizeof (Nodo *)

E qui vediamo la vittoria: notiamo che non stiamo memorizzando memoria extra 2n * sizeof (parola macchina) per tenere traccia delle dimensioni degli array allocati. Ciò significa che la rappresentazione LCRS utilizza una quantità di memoria notevolmente inferiore rispetto a un normale albero a più vie.

Tuttavia, le operazioni di base sulla struttura ad albero LCRS tendono a richiedere più tempo delle corrispondenti operazioni sul normale albero a più vie. In particolare, in un albero a più vie rappresentato nel modulo standard (ogni nodo memorizza una matrice di puntatori figlio), il tempo richiesto per navigare da un nodo al suo kesimo figlio è dato dal tempo richiesto per seguire un singolo puntatore. D’altra parte, nella rappresentazione LCRS, il tempo richiesto per farlo è dato dal tempo necessario per seguire i puntatori k + 1 (un puntatore secondario sinistro, quindi k puntatori figlio destro). Di conseguenza, se l’albero ha un grande fattore di ramificazione, può essere molto più lento eseguire ricerche in una struttura ad albero LCRS rispetto alla struttura ad albero a più vie corrispondente.

Possiamo quindi pensare alla rappresentazione LCRS come ad offrire un compromesso spazio-tempo tra lo spazio di archiviazione della struttura dati e i tempi di accesso. La rappresentazione LCRS ha un sovraccarico di memoria inferiore rispetto all’albero a più vie originale, mentre l’albero a più vie dà ricerche costanti di ciascuno dei suoi figli.

Casi d’uso

A causa del compromesso spazio-temporale implicato nella rappresentazione LCRS, la rappresentazione LCRS non viene in genere utilizzata a meno che uno dei due criteri non contenga:

  1. La memoria è estremamente scarsa, o
  2. Non è richiesto l’accesso casuale dei figli di un nodo.

Il caso (1) potrebbe sorgere se fosse necessario archiviare un enorme albero multiway nella memoria principale. Ad esempio, se è necessario memorizzare un albero filogenetico contenente molte specie diverse soggette a frequenti aggiornamenti, la rappresentazione LCRS potrebbe essere appropriata.

Il caso (2) si presenta in strutture di dati specializzate in cui la struttura ad albero viene utilizzata in modi molto specifici. Ad esempio, molti tipi di strutture di dati heap che utilizzano alberi a più vie possono essere ottimizzati nello spazio utilizzando la rappresentazione LCRS. La ragione principale di ciò è che nelle strutture di dati heap, le operazioni più comuni tendono ad essere

  1. Rimuovere la radice di un albero ed elaborare ognuno dei suoi figli, o
  2. Unisci due alberi insieme creando un albero un figlio dell’altro.

L’operazione (1) può essere eseguita in modo molto efficiente nella rappresentazione LCRS. In una rappresentazione LCRS, la radice dell’albero non ha mai un figlio destro (poiché non ha fratelli), e quindi rimuovere la radice significa semplicemente staccare il nodo radice e discendere nel suo sottoalbero sinistro. Da lì, l’elaborazione di ogni bambino può essere effettuata semplicemente camminando lungo la colonna vertebrale destra dell’albero rimanente e elaborando ogni nodo a turno.

L’operazione (2) può essere eseguita in modo molto efficiente. Ricordiamo dall’alto che in una rappresentazione LCRS, la radice di un albero non ha mai un figlio giusto. Pertanto, è molto facile unire insieme due alberi nella rappresentazione LCRS come segue. Iniziando con due alberi come questo:

  R1 R2 / / (children 1) (children 2) 

Possiamo fondere gli alberi in questo modo:

  R1 / R2 / \ (children 2) (children 1) 

Questo può essere fatto in tempo O (1), ed è abbastanza semplice. Il fatto che la rappresentazione LCRS abbia questa proprietà significa che molti tipi di code di priorità heap, come l’ heap binomiale o l’ heap di accoppiamento di rango, sono in genere rappresentati come alberi LCRS.

Spero che questo ti aiuti!