Pages: [1]   Go Down
Print
Author Topic: eliminazione b-tree  (Read 3454 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
rabbit
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 136



« on: 26-11-2009, 09:24:20 »

ragazzi qualcuno sa come si elimina il nodo H da questo b-tree?
                             K
        DG                                  NRV

ABC  EF  HI                       LM  OPQ  ST  WX

il nodo DG ha due chiavi ma non posso fonderlo con K e NRV visto che si sfora oltre il grado massimo. Qualcuno sa aiutarmi? 
Logged
havoc
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 224


« Reply #1 on: 26-11-2009, 15:18:29 »

Io ho fatto questo passo:
                             N
        DGK                                  RV

ABC  EF  HI  LM                  OPQ  ST  WX

cioè ho applicato il caso 3a (anche se ho qualche dubbio).
Successivamente si procede con il caso 2a:
                             N
        DG                                    RV

ABC  EF  HIKLM                  OPQ  ST  WX

                             N
        DG                                    RV

ABC   EF  IKLM                   OPQ  ST  WX

Spero di aver fatto bene... i risultati lo diranno!
Logged

rabbit
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 136



« Reply #2 on: 26-11-2009, 16:06:41 »

guarda come ho fatto io..
l'albero di partenza era questo:
                   DGKNV
     AC  EF  HI  LM  OPRST WX

inseriamo B solo che il passo iniziale dell'alg. dice che se la root è piena bisogna splittarla( t=3 2t-1=5)
                        K
          DG                      NV
    AC  EF  HI           LM  OPRST  WX

inserisco B
                        K
          DG                      NV
    ABC  EF  HI           LM  OPRST  WX

per inserire Q altro split (nella foglia)
                         K
          DG                      NRV
    AC  EF  HI           LM  OP  ST  WX

inserisco Q
                       K
          DG                      NRV
    AC  EF  HI           LM  OPQ  ST  WX

abbiamo alberi differenti. Contestami il mio così capisco l'inghippo se c'è e se ti viene in mente o scrivimi come sei arrivato a quel passo. Al di la di questo risultato che ho ottenuto, mi chiedo come si ci muove in un b-tree con questa configurazione se volessi eliminare H. Per scendere a livello H devo garantire t chiavi a livello precedente(quello di DG).

l'errore sarà così ovvio che ci sarà da ridere




« Last Edit: 26-11-2009, 16:41:17 by rabbit » Logged
rabbit
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 136



« Reply #3 on: 26-11-2009, 16:07:37 »

ho trovato la soluzione: scaricare l'emulatore di b-tree dhooooooooo testate
Logged
havoc
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 224


« Reply #4 on: 26-11-2009, 16:34:16 »

Non capisco perché dici "abbiamo due alberi differenti".
Io sono partito dall'albero che mi hai dato tu... non ho guardato l'esercizio dal testo originale. Semplicemente non ho ricopiato:
                             K
        DG                                  NRV

ABC  EF  HI                       LM  OPQ  ST  WX

Partendo da questa configurazione per cancellare H ti ritrovi il nodo con DG che è magro, con fratello non magro (caso 3a come scritto prima). La chiave N sale, K scende e LM viene messo a destra di K.
Appena ho un po' più di tempo ti scrivo tutti i passi che ho fatto.

Poi mi fai sapere con l'emulatore cosa viene.
Logged

rabbit
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 136



« Reply #5 on: 26-11-2009, 16:44:31 »

avevo capito male. Ora tt chiaro. L'emulatore non serve in questo contesto.Ora vedo di capire cosa non sapevo. grazie mille
Logged
havoc
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 224


« Reply #6 on: 26-11-2009, 17:04:28 »

Suppongo che l'emulatore non ti faccia partire da una data configurazione di B-tree e riuscire ad avere tale configurazione tramite inserimenti e cancellazioni sia un po' complicato...
Ho indovinato come funziona l'emulatore?

Ci sono altri colleghi di buona volontà che vogliono contribuire? Smiley
Logged

rabbit
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 136



« Reply #7 on: 26-11-2009, 17:14:24 »

si esatto. Senti ma sei sicuro che dopo il 3a applichi il 2a? H si trova in una foglia..
è giusto il passaggio..cioè tu hai fatto la fusione e poi hai applicato il caso 1, correggimi quando ti capita.
Mi spiace farti perdere del tempo utile..ti ringrazio nuovamente
« Last Edit: 26-11-2009, 17:28:16 by rabbit » Logged
havoc
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 224


« Reply #8 on: 26-11-2009, 17:41:41 »

Sì, scusami... si applica il 3b, non il 2a (il nodo x è DGK).
Logged

Atlantide
Apprendista Forumista
**
Offline Offline

Posts: 179


« Reply #9 on: 26-11-2009, 18:03:26 »

io l'ho svolto come havoc...
l'unica differenza e che ho fuso il nodo HI con il fratello sinistro EF (abbassando G )
« Last Edit: 28-11-2009, 10:12:54 by Atlantide » Logged
havoc
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 224


« Reply #10 on: 26-11-2009, 18:39:19 »

io lo svolto come havoc...
l'unica differenza e che ho fuso il nodo HI con il fratello sinistro EF (abbassando G )
A dirti la verità io non ricordo come l'ho svolto nel compito, però di consuetudine si dovrebbe usare il fratello sinistro (quindi come dici tu).
Logged

Domenico Cantone
Moderator
Apprendista Forumista
*****
Offline Offline

Gender: Male
Posts: 345



« Reply #11 on: 07-12-2009, 09:00:55 »

Poiché l'esercizio 2 della prova in itinere ha suscitato tanto interesse, ecco la soluzione (notate che, secondo le convenzioni stabilite a lezione, in quei passi in cui si potevano utilizzare indifferentemente sia il fratello sinistro che quello destro è stata data priorità al fratello sinistro) :

**B-tree iniziale (di grado minimo t=3, ma occorreva dimostrarlo!)

             DGKNV
AC  EF  HI  LM  OPRST WX


**dopo Insert(B)

                            K
        DG                              NV
ABC  EF  HI                LM  OPRST  WX


**dopo Insert(Q)

                           K
        DG                             NRV
ABC  EF  HI                LM  OPQ  ST  WX


**dopo Delete(H)

                           N
        DK                           RV
ABC  EFGI  LM           OPQ  ST  WX


**dopo Delete(L)
                             
               DINRV
ABC  EFG  KM  OPQ  ST  WX
Logged
Pages: [1]   Go Up
Print
Jump to: