Benvenuto!
Accedi
o
registrati
.
08-12-2019, 20:45:56
Home
CDL Informatica
UniCT
CEA
Prof
Help
Search
Calendar
Login
Register
Forum Informatica Unict
»
Vecchi ordinamenti ad esaurimento
»
Laurea Triennale (D.M. 509/00)
»
Algoritmi 2
(Moderator:
Domenico Cantone
) »
eliminazione b-tree
Pages: [
1
]
Go Down
« precedente
successivo »
Print
Author
Topic: eliminazione b-tree (Read 3493 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
rabbit
Apprendista Forumista
Offline
Gender:
Posts: 136
eliminazione b-tree
«
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
Gender:
Posts: 224
Re:eliminazione b-tree
«
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
http://xkcd.com/435/
rabbit
Apprendista Forumista
Offline
Gender:
Posts: 136
Re:eliminazione b-tree
«
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
Gender:
Posts: 136
Re:eliminazione b-tree
«
Reply #3 on:
26-11-2009, 16:07:37 »
ho trovato la soluzione: scaricare l'emulatore di b-tree dhooooooooo
Logged
havoc
Apprendista Forumista
Offline
Gender:
Posts: 224
Re:eliminazione b-tree
«
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
http://xkcd.com/435/
rabbit
Apprendista Forumista
Offline
Gender:
Posts: 136
Re:eliminazione b-tree
«
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
Gender:
Posts: 224
Re:eliminazione b-tree
«
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?
Logged
http://xkcd.com/435/
rabbit
Apprendista Forumista
Offline
Gender:
Posts: 136
Re:eliminazione b-tree
«
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
Gender:
Posts: 224
Re:eliminazione b-tree
«
Reply #8 on:
26-11-2009, 17:41:41 »
Sì, scusami... si applica il 3b, non il 2a (il nodo x è DGK).
Logged
http://xkcd.com/435/
Atlantide
Apprendista Forumista
Offline
Posts: 179
Re:eliminazione b-tree
«
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
Gender:
Posts: 224
Re:eliminazione b-tree
«
Reply #10 on:
26-11-2009, 18:39:19 »
Quote from: Atlantide on 26-11-2009, 18:03:26
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
http://xkcd.com/435/
Domenico Cantone
Moderator
Apprendista Forumista
Offline
Gender:
Posts: 345
Re:eliminazione b-tree
«
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
« precedente
successivo »
Jump to:
Please select a destination:
-----------------------------
Area Ufficiale
-----------------------------
=> Annunci Ufficiali
=> Segreteria Didattica
=> Aiuto, proposte e commenti
=> Stages e progetti finali
=> C.O.F. Centro Orientamento e Formazione
=> Messaggi (d)agli amministratori del forum
-----------------------------
LAUREA TRIENNALE (D.M. 270/04)
-----------------------------
=> I anno
===> Architettura degli Elaboratori, 9 CFU
===> Elementi di Analisi Matematica, 12 CFU
===> Fondamenti di Informatica, 9 CFU
===> Matematica Discreta, 12 CFU
===> Programmazione 1, 9 CFU
===> Programmazione 2, 9 CFU
=> II anno
===> Algoritmi, 9 CFU
===> Basi di Dati, 9 CFU
===> Fisica, 9 CFU
===> Ingegneria del Software, 9 CFU
===> Inglese, 3 e 6 CFU
===> Interazione e Multimedia, 9 CFU
===> Sistemi Operativi, 9 CFU
=> III anno
===> Calcolo Numerico, 6 CFU
===> Formazione Numerica, 6 CFU
===> Introduzione all'Analisi dei Dati, 9 CFU
===> Metodi Matematici e Statistici, 6 CFU
===> Reti di Calcolatori, 9 CFU
===> Tecniche di Programmazione Concorrente e Distribuita, 9 CFU
===> Teoria dell'Informazione e Crittografia, 9 CFU
=> III anno - Materie a scelta (crediti liberi)
===> Computer Forensics, 6 CFU
===> Computer Graphics, 9 CFU
===> Digital Game Development, 6 CFU
===> GPGPU/CUDA, 6 CFU
===> Informatica Musicale, 6 CFU
===> LAP 1: programmazione C/C++ 6 CFU
===> LAP 2: Programmazione Android, 6 CFU
===> Sistemi Centrali, 6 CFU
===> Startup d'impresa e Modelli di Business, 6 CFU
===> Internet Security 9 CFU
===> Social Media Management, 6 CFU
=> Corsi disattivati - Vecchio curriculum
===> E-Commerce, 6 CFU
===> Legislazione Informatica, 6 CFU
===> Teoria della Computabilità, 9 CFU
-----------------------------
LAUREA MAGISTRALE
-----------------------------
=> I ANNO
===> Intelligenza Artificiale e Lab, 9 CFU
===> Algoritmi e Complessità, 9 CFU
===> Computer Vision, 9 CFU
===> Crittografia, 9 CFU
===> Fondamenti e Linguaggi per la Programmazione Distribuita
===> Inglese Scientifico, 3 CFU
===> Metodi analitici per l'informatica, 6 CFU
===> Metodi Matematici per l'Ottimizzazione (Corso Integrato), 12 CFU
===> Multimedia, 9 CFU
===> Sicurezza dei Sistemi Informatici 9 CFU
===> Computer Security, 9 CFU
=> II ANNO
===> Machine Learning 6 CFU
===> Teoria della Computabilità, 9 CFU
===> Analisi e Gestione dei Dati, 9 CFU
===> Compilatori, 9 CFU
===> Computazione Naturale e BioIspirata, 6 CFU
===> Introduzione alla Bioinformatica, 9 CFU
===> Linguaggi Formali e Applicazioni, 9 CFU
===> Logica Computazionale, 9 CFU
===> P2P & Wireless Networks, 9 CFU
===> Pattern Recognition, 9 CFU
===> Sistemi Distribuiti, 9 CFU
===> Sistemi dedicati e laboratorio, 9 CFU
===> Web Reasoning
=> Corsi disattivati - Vecchio curriculum
===> Fisica moderna per l'informatica, 6 CFU
===> Linguaggi di Programmazione, 9 CFU
===> Protocolli di Rete
===> Teoria dei Codici, 6 CFU
-----------------------------
Vecchi ordinamenti ad esaurimento
-----------------------------
=> Laurea Triennale (D.M. 509/00)
===> Algoritmi 1
===> Algoritmi 2
===> Basi Teoriche dell'Informatica
===> Economia Aziendale
===> Fisica 1, 6 CFU
===> Fisica 2, 6 CFU
===> Fisica 3
===> Formazione Analitica 1
===> Formazione Analitica 2
===> Formazione Discreta 1
===> Formazione Discreta 2
===> J2ME
===> Lab. Amministrazione di Sistemi
===> Laboratorio di Interazione
===> Modelli Matematici
===> Multimedia per Dispositivi Mobile
===> Progetto Software
===> Reti 1, 6 CFU
===> Sicurezza dei Sistemi Informatici 1
===> Sistemi Distribuiti 1
===> Teoria dei Grafi
===> Usabilità ed Estetica del Web
===> Web Programming
=> Laurea Specialistica (D.M. 509/00)
===> Algoritmi 3
===> Analisi Numerica
===> Complessità
===> Computabilità
===> Data analysis e management
===> Ingegneria del software 2
===> Linguaggi Formali
===> Metodi algoritmici per l'ottimizzazione combinatoria
===> Programmazione Funzionale
===> Reti di Calcolatori 2
===> Ricerca Operativa
===> Sistemi Distribuiti 2
-----------------------------
Dottorandi
-----------------------------
=> Wall
=> Events
-----------------------------
Area Studenti
-----------------------------
=> Agorà
=> L'angolo del tecnico
=> Il Mercatino degli studenti
=> Software
===> -vecchia catalogazione [sarà rimossa a breve]-
=====> Proprietario
=====> Free Software
=====> Open Source
===> Approfondimenti
===> News
===> Studio
===> Videogiochi
===> Networking e telecomunicazioni
===> Sviluppo
===> Ufficio e produttività
===> Sistemi Operativi
=====> Microsoft Windows
=====> GNU/Linux, Unix e BSD
=====> Mac OS X
=====> Windows Phone
=====> Android
=====> iOS
=====> Altri
===> Eventi, conferenze, concorsi
=> Microsoft Student Partner - Avvisi e informazioni
=> ERASMUS/borse di studio internazionali
Caricamento in corso...