Gli alberi binari hanno uno scopo specifico nella memorizzazione di dati gerarchici? Qual è il loro uso canonico?

No, gli alberi binari non servono per memorizzare i dati gerarchici nel senso in cui stai pensando. Il caso d'uso principale per gli alberi n-ary, dove n è un numero fisso, è capacità di ricerca rapida , non una gerarchia semantica.

Ricorda il vecchio gioco in cui una persona pensa ad un numero compreso tra 1 e 100, e l'altra deve indovinarla nel minor numero possibile di ipotesi, e se indovina la persona che pensa al numero deve dirti se Sei troppo alto o troppo basso? Dopo un po 'diventa noioso perché capisci subito che dovresti sempre iniziare a 50, quindi andare a 25 o 75, e continuare a dividere l'intervallo da cercare a metà con ogni nuova ipotesi dopo quella, e alla fine puoi indovinare qualsiasi numero al massimo 7 ipotesi, garantito.

Potrebbe non essere un gioco divertente, ma quella proprietà è ciò che rende utili gli alberi binari (e altri n-ari): puoi usarli per cercare un insieme di dati molto grande in un tempo molto breve.

Qualsiasi struttura ad albero, in cui un nodo può avere un numero illimitato di bambini, può essere implementata usando un albero binario.

Per ogni nodo nella struttura, sostituirlo con un nodo con un puntatore destro e sinistro. Il puntatore a sinistra va al primo dei figli del nodo. Il nodo giusto passa al fratello successivo del nodo. Tutti i figli di un determinato nodo si trovano in una lista collegata unita dai loro puntatori a destra, con la testa della lista puntata dal puntatore sinistro del loro genitore.

Il tuo complicato albero n-ary è diventato un semplice albero binario.

Sono sicuro che questo è in Knuth, vol. 1 da qualche parte.

Alberi binari perché usarli?

Nella programmazione lavori molto con raccolte di dati dello stesso tipo.

I due modi fondamentali per archiviare questi dati sono: liste e matrici collegate.

Entrambe sono dotate di aspetti negativi: In un elenco collegato è facile aggiungere elementi in qualsiasi posizione o rimuovere elementi. Ma l'accesso a un elemento specifico è più difficile, perché devi passare attraverso l'elenco finché non sei nell'elemento che desideri.

• Non esegue ricerche in modo efficiente, ma l'inserimento e l'eliminazione sono facili.

Con un array l'accesso a un elemento specifico è facile, ma è più difficile inserire o eliminare un elemento perché inserire significa: estendere l'array di uno, spostare tutti gli elementi prima della posizione di inserimento 1 a destra e inserire l'elemento.

• Cerca in modo efficiente (se ordinato) ma l'inserimento e l'eliminazione sono difficili.

Quindi sia la lista collegata che l'array hanno aspetti negativi.

Gli alberi binari sono fatti per affrontare entrambi i problemi dell'array e dell'elenco collegato:

1. Inserimento ed eliminazione semplificati
2. Ricerca facile

Quindi sono fatti gli alberi binari quando hai molti dati che cambiano regolarmente.