DELETE v B-stromu

Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

Timhle si ale moc jisty nejsem (priklad 5 pisemky C):
Vlozte do neredundantniho B* stromu (m=5) prvek "3":

Kód: Vybrat vše

                |15|35|
               /   |   \
     /--------/    |    \-----\
    /              |           \
 |2|5|7|11|   |19|20|23|30|  |40|42|50|55|
Ja myslim, ze musim vzit vsechny 3 vetve (2 proste nestaci - v kazdem uzlu musi byt aspon 3 prvky)
a vyjde:

Kód: Vybrat vše

       |7|20|40|
      /  |   \  \----------------\
    --    \   \------\            |
   /       \          \           \
 |2|3|5|  |11|15|19|  |23|30|35|  |42|50|55|
je to dobre ?
Plug 'n' Pray.
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:

Příspěvek od nohis »

Tuetschek píše:Timhle si ale moc jisty nejsem.....
takto to myslím nebude, berou se vždy jen sousední větvě, a ty co mají jenom jednoho souseda mají holt smolík :D
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
Příspěvky: 445
Registrován: 22. 9. 2004 21:07
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Příspěvek od twoflower »

Tuetschek píše:Timhle si ale moc jisty nejsem (priklad 5 pisemky C):
Vlozte do neredundantniho B* stromu (m=5) prvek "3":

Kód: Vybrat vše

                |15|35|
               /   |   \
     /--------/    |    \-----\
    /              |           \
 |2|5|7|11|   |19|20|23|30|  |40|42|50|55|
Ja myslim, ze musim vzit vsechny 3 vetve (2 proste nestaci - v kazdem uzlu musi byt aspon 3 prvky)
a vyjde:

Kód: Vybrat vše

       |7|20|40|
      /  |   \  \----------------\
    --    \   \------\            |
   /       \          \           \
 |2|3|5|  |11|15|19|  |23|30|35|  |42|50|55|
je to dobre ?
Mne to vyslo jinak:

Kód: Vybrat vše

               |7|20|35|
              /   |  \
            /     |    \
     |2|3|5|  |11|15|19| |23|30|  
a na poslednim pointeru bude |40|42|50|55|

Vychazim z toho, ze v B*-stromu se vzdy distribuuji dva uzly do tri, ne tri do ctyr a z toho, ze zalezi na nas, jak to rozdelime.
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:

Příspěvek od nohis »

twoflower píše: ......
Vychazim z toho, ze v B*-stromu se vzdy distribuuji dva uzly do tri, ne tri do ctyr a z toho, ze zalezi na nas, jak to rozdelime.
v případě že má uzel dva sousedy a jsou plné pak se tři uzly rozdělí do 4 uzlů , pokud ale sousedi nejsou plní, je možné to zpřeházet tak (resp. mělo by se to tak myslím udělat) že vůbec není třeba dělit uzly

jinak mě to vyšlo

Kód: Vybrat vše

               |5|19|35|
              /   |  \     ---------------------|
            /     |    \                             |
     |2|3|  |7|11|15| |20|23|30|        |40|42|50|55|
ale myslím že i twoflower to má dobře, tady opět zaleží na implementaci dle mého nazoru :)
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 dle mýho jsou taky dvě poslední řešení obě správně, to Tuetschekovo je rozhodně špatně (viz skripta str.73).
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

Dawe píše:Jo dle mýho jsou taky dvě poslední řešení obě správně, to Tuetschekovo je rozhodně špatně (viz skripta str.73).
Hm ze skript jsem toho prave moc nepochopil :( ... ale asi mate pravdu, me zase zmatly ty udavane minimalni pocty potomku versus prvku -- nejak jsem se za kazdou cenu snazil dosahnout stavu kdy vsechny uzly budou mit aspon 3 prvky a 2 mi nestacily ... a ted vidim ze staci. Diky.
Plug 'n' Pray.
Odpovědět

Zpět na „2006“