Problem s B stromom

sabol.v
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 12. 10. 2004 20:08
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Problem s B stromom

Příspěvek od sabol.v »

http://mff.fear.cz/forum/viewtopic.php? ... c&start=21

nemyslite ze v druhej hladine by tam nemalo byt 28? (je to z prikladu 5a v prilohe)
Přílohy
priklad 5.a
priklad 5.a
page2.jpg (141.72 KiB) Zobrazeno 6194 x
Uživatelský avatar
Dawe
Supermatfyz(ák|ačka)
Příspěvky: 360
Registrován: 12. 10. 2004 12:32
Typ studia: Informatika Mgr.
Bydliště: Doma a nebo na koleji

Příspěvek od Dawe »

A máš nějakej rozumnej důvo, proč by to tam být nemělo? Já myslím, že je to OK. Ale třeba sem něco přehlíd.
sabol.v
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 12. 10. 2004 20:08
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od sabol.v »

myslim samozrejme tu 28 v tom vysledku (z fearu), ked to urobim ako Zemlicka na prednaske tak to tam nedostanem,(pri inserte 23 do redundantneho stromu na prednaske dostal zemlicka cislo 30 do korena, ale v druhej hladine to tam uz nenechal)
Uživatelský avatar
Dawe
Supermatfyz(ák|ačka)
Příspěvky: 360
Registrován: 12. 10. 2004 12:32
Typ studia: Informatika Mgr.
Bydliště: Doma a nebo na koleji

Příspěvek od Dawe »

Jo tak, atk to potom jo, jasně že to tam být nemá. Pokud je strom redundantní, tak jen listy ke zbytku. Zbytek stromu krom listů se chová skoro jako B-Strom.
Jinak výsledek by měl být asi takový:

Kód: Vybrat vše

                       30|41|62|88		
                       /  \
                     /     \
          13|21|28      32|40		
	  /  \				
 3|6|12    13|15|20		
Nějak se mi to nechce kloudně naformátovat, ale snad se to dá pochopit...
Naposledy upravil(a) Dawe dne 7. 1. 2007 18:33, celkem upraveno 2 x.
Keleen
Matfyz(ák|ačka) level II
Příspěvky: 90
Registrován: 19. 1. 2005 22:20

Příspěvek od Keleen »

Jj, podle me mas pravdu, nema to tam byt.
Redundantni je pouze nejnizsi hladina Bstromu a vyssi uz se chovaji neredundantne, takze ta 28 do te druhe vrstvy skutecne nepatri a mela by byt jen v koreni.
Uživatelský avatar
nohis
Matfyz(ák|ačka) level III
Příspěvky: 128
Registrován: 7. 11. 2004 13:39
Typ studia: Informatika Mgr.
Bydliště: Praha - Prosek / Krakovany
Kontaktovat uživatele:

Re: Problem s B stromom

Příspěvek od nohis »

sabol.v píše:http://mff.fear.cz/forum/viewtopic.php? ... c&start=21

nemyslite ze v druhej hladine by tam nemalo byt 28? (je to z prikladu 5a v prilohe)
souhlasím s tebou myslím že by tam ta 28 neměla být :
- měla by být buď v listu a v jednom uzlu

- nebo pokud se 28 někdy dřív odstranila ze stromu, tak pak mohla být v některém uzlu ponechána jako klíč, ale zde je ve dvou uzlech což myslím taky nejde...
src
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 28. 1. 2007 17:02

Příspěvek od src »

Dawe píše:Jo tak, atk to potom jo, jasně že to tam být nemá. Pokud je strom redundantní, tak jen listy ke zbytku. Zbytek stromu krom listů se chová skoro jako B-Strom.
Jinak výsledek by měl být asi takový:

Kód: Vybrat vše

                       30|41|62|88		
                       /  \
                     /     \
          13|21|28      32|40		
	  /  \				
 3|6|12    13|15|20		
Nějak se mi to nechce kloudně naformátovat, ale snad se to dá pochopit...
Ten strom je spatne, misto 13|21|28 tam ma byt 12|21|28, jelikoz redundatni B-strom ma vlastnost, ze vsechny klice z podstromu jsou mensi ci rovny nadrazenemu klici (viz skripta s. 66). Taktez novy hranicni klic je maximum z (zmenene) puvodni stranky, tj. 12.

Taky neni pravda, ze redundantni B-strom je redundantni ve vztahu listu ke zbytku. Existuji totiz dva typy: a) s duplikaci klice v listu a b) s duplikaci klice kdekoliv (opet viz skripta s. 66) - obrazky ve skriptech vypadaji jako a), ale popis algoritmu vkladani i ten desivy Pascal u toho je skoro urcite b) (nerozlisuje mezi listy a uzly, rekl bych). Takze vyse uvedeny strom je typu a) a na fearu je pokus o typ b) (ktery je ale spatne, protoze 28 a 30 puvodne mely spolecny podstrom a ted maji mit kazdy svuj - jak to ma byt dobre, to ze skript neplyne). At zije chaos!

Vsechno IMHO, samozrejme.
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re:

Příspěvek od peterblack »

src píše:
Dawe píše:Jo tak, atk to potom jo, jasně že to tam být nemá. Pokud je strom redundantní, tak jen listy ke zbytku. Zbytek stromu krom listů se chová skoro jako B-Strom.
Jinak výsledek by měl být asi takový:

Kód: Vybrat vše

                       30|41|62|88		
                       /  \
                     /     \
          13|21|28      32|40		
	  /  \				
 3|6|12    13|15|20		
Nějak se mi to nechce kloudně naformátovat, ale snad se to dá pochopit...
Ten strom je spatne, misto 13|21|28 tam ma byt 12|21|28, jelikoz redundatni B-strom ma vlastnost, ze vsechny klice z podstromu jsou mensi ci rovny nadrazenemu klici (viz skripta s. 66). Taktez novy hranicni klic je maximum z (zmenene) puvodni stranky, tj. 12.

Taky neni pravda, ze redundantni B-strom je redundantni ve vztahu listu ke zbytku. Existuji totiz dva typy: a) s duplikaci klice v listu a b) s duplikaci klice kdekoliv (opet viz skripta s. 66) - obrazky ve skriptech vypadaji jako a), ale popis algoritmu vkladani i ten desivy Pascal u toho je skoro urcite b) (nerozlisuje mezi listy a uzly, rekl bych). Takze vyse uvedeny strom je typu a) a na fearu je pokus o typ b) (ktery je ale spatne, protoze 28 a 30 puvodne mely spolecny podstrom a ted maji mit kazdy svuj - jak to ma byt dobre, to ze skript neplyne). At zije chaos!

Vsechno IMHO, samozrejme.
pane kolego uz jste zesilel gratuluji :-D
Dawe to ma podle zpusobu probiranem Zemlickou na cvikach, takze predpokladam ze to bude na zkouce vyzadovat
vse ostatni od Dawa take odpovida cvikam, prikladam zapisky ze cvik od Anicky, je to nich dobre videt
=> Dave tam zadnou chybu nema (ve smyslu reseni jake Zemlicka vyzaduje)
Přílohy
012.jpg
013.jpg
Odpovědět

Zpět na „2006“