kevinpirola
30-09-2010, 17:44
Finally...
Eccomi qui, da molto lettore, per la prima volta scrittore.
E come ogni prima volta in un forum, il primo messaggio è una richiesta (ahimè)
Il quesito è il seguente:
Come posso fare la somma di due alberi binari?
Nello specifico questi due alberi sono due alberi 2-4 con chiavi ordinate.
Altra clausula, che forse è stata messa per semplificare è che i due alberi hanno una relazione d'ordine particolare, nel senso che l'albero A con a elementi ha tutte chiavi che sono maggiori dell'albero B con b elementi.
Esempio:
se l'albero A contiene figli con indici(key) 1,4,5,7,8,15 l'albero B dovrà avere tutte le chiavi > di 15.
Il tutto deve stare in una complessità O[n(log a + log b)] se non ricordo male.
--------------------
L'esercizio (perchè è di questo che alla fine si tratta) è tratto dall'ultimo compito scritto di informatica al quale diedi una soluzione ma che però non mi fruttò molto.
L'idea mia (senza scrivere codice) era (se devo sommare B ad A e le chiavi(B) > chiavi(A) ) parto dalla root di B prendo gli elementi e li sommo alla root di A. Se necessario ristrutturo.
Passo al figlio estremo sx della root di B e lo sommo al figlio estremo dx della root di A. Se necessario ristrutturo e così via finchè uno dei due alberi non ha più figli sx (risp.dx).
(questo perchè immaginando un cammino inordere alla fine i nodi saranno sempre nello stesso ordine.)
Finiti tutti i "raggruppamenti" dei nodi esterni e fatte le ristrutturazioni l'albero "dovrebbe" essere apposto.
Non credo però che sia un metodo valido (A: non so come testarlo, B: sicuramente non rispetta la complessità), purtroppo non mi viene in mente molto altro :(
Avete qualche suggerimento?
Ho controllato sul libro ma di somma di più alberi non se ne parla.
Avevo anche pensato di creare un albero vuoto (una root in pratica) a cui attaccare a sx e a dx i due alberi. Poi però mi resterebbe vuota e non credo che vada bene con la definizione di albero 2-4.
Il mio libro è il Goodrich-Tamassia (strutture dati e algoritmi in java).
:mc:
EDIT: leggo adesso nel regolamento di sezione:
Linguaggio JAVA
Sistema operativo Linux
Compilatore JDK ultima relase
La domanda, comunque, è più di carattere teorico quindi risposte in qualsiasi linguaggio vanno bene ;)
Eccomi qui, da molto lettore, per la prima volta scrittore.
E come ogni prima volta in un forum, il primo messaggio è una richiesta (ahimè)
Il quesito è il seguente:
Come posso fare la somma di due alberi binari?
Nello specifico questi due alberi sono due alberi 2-4 con chiavi ordinate.
Altra clausula, che forse è stata messa per semplificare è che i due alberi hanno una relazione d'ordine particolare, nel senso che l'albero A con a elementi ha tutte chiavi che sono maggiori dell'albero B con b elementi.
Esempio:
se l'albero A contiene figli con indici(key) 1,4,5,7,8,15 l'albero B dovrà avere tutte le chiavi > di 15.
Il tutto deve stare in una complessità O[n(log a + log b)] se non ricordo male.
--------------------
L'esercizio (perchè è di questo che alla fine si tratta) è tratto dall'ultimo compito scritto di informatica al quale diedi una soluzione ma che però non mi fruttò molto.
L'idea mia (senza scrivere codice) era (se devo sommare B ad A e le chiavi(B) > chiavi(A) ) parto dalla root di B prendo gli elementi e li sommo alla root di A. Se necessario ristrutturo.
Passo al figlio estremo sx della root di B e lo sommo al figlio estremo dx della root di A. Se necessario ristrutturo e così via finchè uno dei due alberi non ha più figli sx (risp.dx).
(questo perchè immaginando un cammino inordere alla fine i nodi saranno sempre nello stesso ordine.)
Finiti tutti i "raggruppamenti" dei nodi esterni e fatte le ristrutturazioni l'albero "dovrebbe" essere apposto.
Non credo però che sia un metodo valido (A: non so come testarlo, B: sicuramente non rispetta la complessità), purtroppo non mi viene in mente molto altro :(
Avete qualche suggerimento?
Ho controllato sul libro ma di somma di più alberi non se ne parla.
Avevo anche pensato di creare un albero vuoto (una root in pratica) a cui attaccare a sx e a dx i due alberi. Poi però mi resterebbe vuota e non credo che vada bene con la definizione di albero 2-4.
Il mio libro è il Goodrich-Tamassia (strutture dati e algoritmi in java).
:mc:
EDIT: leggo adesso nel regolamento di sezione:
Linguaggio JAVA
Sistema operativo Linux
Compilatore JDK ultima relase
La domanda, comunque, è più di carattere teorico quindi risposte in qualsiasi linguaggio vanno bene ;)