Un esempio di alberi bilanciati: gli alberi di Fibonacci
Rappresentazione di alberi binari
Supponiamo di rappresentare alberi binari etichettati con interi per mezzo di espressioni così definite:
- l'albero vuoto è indicato con 0
- assumendo che, se l ≥ 0, allora l+ = 0, mentre se l < 0, allora l+ = l, l'albero T la cui radice contiene l'etichetta l e ha come figlio sinistro l'albero T1 e come figlio destro l'albero T2, lo si rappresenta con l+ t1 t2, ovvero con la sequenza formata da l+ seguita dalla sequenza t1 che rappresenta l'albero T1 e dalla seqeunza t2 che rappresenta T2.
Si osservi che l'aggiunta di 1 alle etichette non-negative serve a garantire la possibilità di usare 0 per indicare l'albero vuoto.
Esempio La sequenza
1 2 0 -2 3 4 0 0 5 -6 0 0 0 0 -1 0 1 0 0
corrisponde all'albero
Gli alberi di Fibonacci
Gli alberi di Fibonacci sono un caso particolare di alberi binari bilanciati in altezza. Per ogni numero naturale i = 0,1,2,3,... il corrispondente albero di Fibonacci di ordine i è definito ricorsivamente da:
- l'albero vuoto è l'unico albero di Fibonacci di ordine 0
- tutti gli alberi contenenti un solo nodo sono alberi di Fibonacci di ordine 1
- un albero binario la cui radice ha come figlio sinistro un albero di Fibonacci di ordine n+1 e come figlio destro un albero di Fibonacci di ordine n è un albero di Fibonacci di ordine n+2
E' facile vedere che ogni albero di Fibonacci di ordine i > 0 ha altezza i-1. Quindi, per ogni nodo non-foglia di un albero di Fibonacci si ha che l'altezza del figlio sinistro è maggiore di 1 dell'altezza del figlio destro.
Funzioni da implementare
- Scrivere una funzione che legge una sequenza di interi che rappresenta un albero binario in base alle regole sopra descritte e costruisce il corrispondente albero.
- Scrivere una funzione che, in base alle regole sopra descritte, stampa la sequenza corrispondente a un albero binario.
- Scrivere una funzione che verifica se un albero binario è un albero di Fibonacci.
- Scrivere un programma che, dopo aver letto un albero binario T, stampa gli alberi contenuti in T che non-sono alberi di Fibonacci, ma tali che i loro sotto-alberi sinistro e destro sono alberi di Fibonacci.
--
StefanoGuerrini - 05 Jun 2007