[TEORIA] Somma di alberi binari

[kevinpirola]

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).




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

[__ZERO_UNO__]

Ciao kevinpirola,

mi piacerebbe poterti aiutare anche per testare le mia conoscenza.
Però non ho ben capito cosa intendi con albero 2-4 con chiavi ordinate.Forse albero binario di ricerca completo? Cioè un albero binario con figlio sinistro minore della radice e figlio destro maggiore della radice e ogni nodo ha due figli oppure è una foglia?
La somma di che tipo? Per livello, ramo, casuale??

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.

Le chiavi di B dovranno essere tutte minori di 15.Anche se non credo che cambi nulla al fine dell'esercizio.

[kevinpirola]

Grazie per la risposta.

Allora, come spiegare cos'è un albero 2-4... mm intanto, è un albero multiway, quindi non solo binario, ovviamente può non essere completo.
E' un caso particolare degli alberi AVL.

Albero 2-4 detto anche 2-3-4 ha una proprietà di misura ovvero ogni nodo interno possiede al più quattro figli; una proprietà di profondità: tutti i nodi esterni hanno la stessa profondità.

detto questo dire che è ordinato è come dire appunto che
le chiavi memorizzate nei nodi del sottoalbero sinistro di v sono minori o uguali a k (chiave di v).
le chiavi memorizzate nei nodi del sottoalbero destro di v sono maggiori o uguali a k.

Clausula dell'esercizio era che A aveva TUTTE le chiavi minori di B.

quindi paradossalmente se io avessi avuto due alberi uguali con in tutto 30 chiavi dall'1 al 30 nell'albero A avrei avuto le chiavi dall'1 al 15 e nell'albero B quelle dal 16 al 30.


Sono riuscito a spiegarmi meglio?