aiuto B-alberi BD2

[onka]

devo dare un esame di BD2 e non sò come si fanno i b-alberi..qualcuno sa risolvere questo?

Dato il seguente insieme di chiavi:
27, 19, 6, 10, 34, 15, 2, 40, 31, 3, 20, 7, 8, 9, 11, 12, 13
(a) Mostrare il B-albero di ordine 5 ottenuto inserendo le chiavi nell’ordine
dato.
(b)Mostrare il B-albero ottenuto dalla cancellazione dell’elemento 22
dall’albero al punto (a).

[clasprea]

per B-albero si intende in albro binario qualsiasi o uno di ricerca?

[onka]

Il B-albero è un albero di ricerca bilanciato in cui i nodi hanno un numero variabile di figli ed in cui ogni nodo è memorizzato in una pagina di memoria secondaria ad esso dedicata.

Un B–albero di ordine m (m≥3) è un albero con le seguenti proprietà:
•Ogni nodo, tranne la radice, ha almeno m/2figli.
•Ogni nodo contiene al più mfigli
•Tutti i nodi terminali sono allo stesso livello
•Ogni nodo non terminale con j+1 figli contiene anche j coppie (k,r) ed ha la struttura:
[p0,(k1, r1), p1, (k2,r2), p2, …, (kj, rj), pj]
dove:
•le chiavi sono ordinate: k1< k2 < …< kj
•p0…pj sono i riferimenti ai figli, indefiniti nei nodi terminali
•Sia K(p)l’insieme delle chiavi contenute nel sottoalbero p; per ogni nodo non terminale vale che:
∀y∈K(p0).(y<k1)∀y∈K(pi).(ki<y<ki+1)∀y∈K(pj).(kj<y)

[clasprea]

uhm ok è peggio di quelli di ricerca... io quelli li sapevo fare, ma i B-alberi no...

[onka]

Originariamente inviato da clasprea

uhm ok è peggio di quelli di ricerca... io quelli li sapevo fare, ma i B-alberi no...

grazie lo stesso