Treelogy
Treelogy
Dimostrare che per ogni n questi due insiemi hanno la stessa cardinalità: gli alberi binari cardinali con n nodi, le stringhe di parentesi bilanciate di lunghezza 2n.
P.S. In un albero binario cardinale i nodi possono avere un solo figlio sinistro, un solo figlio destro, entrambi o nessuno dei due.
P.S. In un albero binario cardinale i nodi possono avere un solo figlio sinistro, un solo figlio destro, entrambi o nessuno dei due.
La maggior parte della gente si lamenta se qualcuno gli brucia il problema nelle prime 10 ore, tu vai controcorrente!
P.S. Propongo un'alleanza con il mio topic
P.S. Propongo un'alleanza con il mio topic
Se prendi un espressione, e togli tutto tranne le parentesi ottieni una stringa di parentesi bilanciate. Comunque, detto più semanticamente, le stringhe di parentesi bilanciate sono stringhe di ( e ) tali che la differenza tra il numero di ( e di ) fino ad un qualsiasi punto della stringa è non negativa ed è 0 alla fine della stringa. Tipo (), ((())), ()(())...
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Molto carino questo fatterello, e confesso di non averlo mai notato!
Prima che scrivessi l'hint avevo trovato un algoritmo per passare da alberi a stringhe di parentesi in modo bigettivo, ma una volta letto l'hint ne è venuta una soluzione molto più pulita. Buon lavoro a tutti e grazie a rand per il bel problema!
Btw, come ne sei venuto a conoscenza? Ha qualche applicazione non fine a sé stessa?
Prima che scrivessi l'hint avevo trovato un algoritmo per passare da alberi a stringhe di parentesi in modo bigettivo, ma una volta letto l'hint ne è venuta una soluzione molto più pulita. Buon lavoro a tutti e grazie a rand per il bel problema!
Btw, come ne sei venuto a conoscenza? Ha qualche applicazione non fine a sé stessa?
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
lol
Un algoritmo per trasformare alberi in stringhe è:
Siccome la seguente è una grammatica non ambigua per le stringhe di parentesi bilanciate:
$ S \rightarrow \epsilon $
$ S \rightarrow (S)S $
allora la seguente funzione è ben definita (puntatori a parte ) e trasforma stringhe in alberi:
E' piuttosto facile convincersi che le due funzioni sono una l'inversa dell'altra, e definiscono quindi la bigezione voluta.
Inoltre, gli alberi binari così generati sono precisamente gli alberi di derivazione delle stringhe di parentesi definiti dalla grammatica (ovviamente, togliendo tutta la roba di troppo, tipo foglie con i simboli terminali attaccati, etc... insomma, ci siamo capiti).
Un algoritmo per trasformare alberi in stringhe è:
Codice: Seleziona tutto
void albero2stringa(albero)
scrivi("(");
if (albero.sinistro != NULL)
albero2stringa(albero.sinistro);
scrivi(")");
if (albero.destro != NULL)
albero2stringa(albero.destro);
$ S \rightarrow \epsilon $
$ S \rightarrow (S)S $
allora la seguente funzione è ben definita (puntatori a parte ) e trasforma stringhe in alberi:
Codice: Seleziona tutto
albero stringa2albero(stringa)
if (stringa = "") return NULL;
r := crea_nodo;
match stringa with "("s1")"s2, con s1 e s2 bilanciate;
r.sinistro := stringa2albero(s1);
r.destro := stringa2albero(s2);
return r;
Inoltre, gli alberi binari così generati sono precisamente gli alberi di derivazione delle stringhe di parentesi definiti dalla grammatica (ovviamente, togliendo tutta la roba di troppo, tipo foglie con i simboli terminali attaccati, etc... insomma, ci siamo capiti).
E' noto fin da tempi antichi (sicuramente più antichi di Google) che alberi binari cardinali e alberi sono in corrispondenza biunivoca, come pure alberi e parentesi bilanciate, da cui segue l'asserto. Io mi sono semplicemente accorto che si può arrivare direttamente alla stessa conclusione sfruttando la non-ambiguità di quella grammatica. Credo che ci siano tante applicazioni, ad esempio immagina di voler rappresentare un albero usando solo due bit per nodo, invece di log n richiesti da una rappresentazione a puntatori.
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12