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

AlberoBinario.jpg

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

  1. 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.
  2. Scrivere una funzione che, in base alle regole sopra descritte, stampa la sequenza corrispondente a un albero binario.
  3. Scrivere una funzione che verifica se un albero binario è un albero di Fibonacci.
  4. 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


This topic: Programmazione2pz > WebHome > AnnoAcc0607 > HomeWork0607 > HomeWork060703
Topic revision: r1 - 2007-06-05 - StefanoGuerrini
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback