Fórum studentů MFF UK

od **Tuetschek** » 7. 1. 2007 20:06

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.

od **Dawe** » 7. 1. 2007 18:25

Jo dle mýho jsou taky dvě poslední řešení obě správně, to Tuetschekovo je rozhodně špatně (viz skripta str.73).

od **nohis** » 7. 1. 2007 18:09

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

od **twoflower** » 7. 1. 2007 17:58

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.

od **nohis** » 7. 1. 2007 17:55

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

od **Tuetschek** » 7. 1. 2007 17:44

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 ?

od **Tuetschek** » 7. 1. 2007 17:40

LuKu píše:Já jsem došla k tomu samému jako Tuetschek. Navíc si myslím, že ta poslední úroveň jsou opravdu listy, jinak by se v tom kousku stromu přece na začátku nemohly 21 a 29 vyskytovat dvakrát, nebo ano?

Aaa pravda

... takze uz je to jednoznacne uplne ... zakerne jako obvykle

od **LuKu** » 7. 1. 2007 17:18

Já jsem došla k tomu samému jako Tuetschek. Navíc si myslím, že ta poslední úroveň jsou opravdu listy, jinak by se v tom kousku stromu přece na začátku nemohly 21 a 29 vyskytovat dvakrát, nebo ano?

od **Tuetschek** » 7. 1. 2007 17:07

Anonymous píše: Je to takhle spravne?

Pokud jsi v REDUNDANTNIM strome, zalezi na tom jestli ta nejnizsi uroven jsou listy ... pokud ano, 21 se proste ve strome nenachazi a niz ho soupnout nemuzes, tak ho proste vyhodis:

Kód: Vybrat vše

|3|7|29|
    |
|14|22|23|

Pokud nejnizsi uroven nejsou listy, je to stejne jako v normalnim B-strome, a to cos udelal je spravne.

Tak ted doufam ze tu nekazu blbosti

od **Návštěvník** » 7. 1. 2007 16:38

Muzu se zeptat, jestli byste nasledujici priklad resili stejne?

"Provedte postupne zadane operace v redundantnim B-strome (m = 5):"

Kód: Vybrat vše

         |3|7|21|29|
            /    \ 
|11|14|15|21|    |22|23|29|

Na ostatnich pointerech je take neco zaveseno, ale zname jen tento kus B-stromu.

Operace: delete(21), delete(15), delete(29), delete(11).

Po delete(21), delete(15), delete(29) - nedeje se nic zajimaveho, zadny uzel nepodtece, tedy:

Kód: Vybrat vše

         |3|7|21|29|
            /    \ 
     |11|14|      |22|23|

Pri delete(11) nam podtece levy uzel, tak se kouknu doprava, jestli bych si nemohl pujcit. Nemohl. Tak udelam (doufam ze spravne) to, ze si vezmu z rodice prvek 21 (tedy oddelovac mezi mnou a bratrickem) a soupnu ho o uroven niz:

Kód: Vybrat vše

          |3|7|29|
              |     
        |14|21|22|23|

Je to takhle spravne?

od **Dawe** » 7. 1. 2007 14:17

Anonymous píše: Jeste se chci zeptat, je nejaky principialni rozdil mezi mazanim prvku z B-stromu/B*-stromu?

Jestli si to dobře pamatuju, tak mazání v B* stromech je celkem zajímavá věc, stejně tak jako se při přidávání štěpí 2 na 3 (resp 3 na 4) , tak by se něco podobného mělo dít i u mazání, jenomže to může být celkem problém především když se maže z některého vnitřního uzlu, protože člověk neví, který 4 má nacpat do 3... Myslím, že je to o dost složitější a snad by to tam být nemuselo...
Jesli kecám, tak ať mě někdo opraví...

od **Návštěvník** » 7. 1. 2007 12:32

pcv píše:
Anonymous píše:Jak byste provedli odstraneni prvku 1 z nasledujiciho neredundantniho B-stromu (takoveho, ze kazdy uzel ma nejvyse 5 potomku a nejmene 2 klice, tedy ten klasicky m = 4 z prednasky)
Bacha na to, parametr m znamena kolik ma uzel maximalne potomku, na prednasce to Zemlicka delal podle me blbe. Takze aby mel kazdy uzel max 5 potomku, muselo by byt m=5, ale pak by v kazdem uzlu muselo byt horni_cela_cast(m/2) hodnot, coz je 3.
Takze jinymi slovy tento B strom je cely nejaky divny

Ted jsem si jeste uvedomil - v kazdem uzlu nema byt minimalne horni_cela_cast(m/2), ale horni_cela_cast(m/2) - 1 datovych polozek, takze vyse uvedeny strom je korektni 5-arni B-strom

od **nohis** » 7. 1. 2007 12:31

Anonymous píše:
pcv píše:
Anonymous píše:Jak byste provedli odstraneni prvku 1 z nasledujiciho neredundantniho B-stromu (takoveho, ze kazdy uzel ma nejvyse 5 potomku a nejmene 2 klice, tedy ten klasicky m = 4 z prednasky)
Bacha na to, parametr m znamena kolik ma uzel maximalne potomku, na prednasce to Zemlicka delal podle me blbe. Takze aby mel kazdy uzel max 5 potomku, muselo by byt m=5, ale pak by v kazdem uzlu muselo byt horni_cela_cast(m/2) hodnot, coz je 3.
Takze jinymi slovy tento B strom je cely nejaky divny
Je pravda, ze Zemlicka to na prednasce asi znacil spatne, ale proc by mel byt ten strom divny? Tech zpusobu parametrizace je vic, treba dle wiki je tenhle strom ok

na přednášce to Žemlička dělal opravdu špatně, nám se za to na cvikách omlouval, takže parametr m opravdu znamená max. počet potomků uzlu

od **Návštěvník** » 7. 1. 2007 12:11

pcv píše:
Anonymous píše:Jak byste provedli odstraneni prvku 1 z nasledujiciho neredundantniho B-stromu (takoveho, ze kazdy uzel ma nejvyse 5 potomku a nejmene 2 klice, tedy ten klasicky m = 4 z prednasky)
Bacha na to, parametr m znamena kolik ma uzel maximalne potomku, na prednasce to Zemlicka delal podle me blbe. Takze aby mel kazdy uzel max 5 potomku, muselo by byt m=5, ale pak by v kazdem uzlu muselo byt horni_cela_cast(m/2) hodnot, coz je 3.
Takze jinymi slovy tento B strom je cely nejaky divny

Je pravda, ze Zemlicka to na prednasce asi znacil spatne, ale proc by mel byt ten strom divny? Tech zpusobu parametrizace je vic, treba dle wiki je tenhle strom ok

od **Návštěvník** » 7. 1. 2007 12:01

Dawe, Anonym: diky! Uz je mi to snad jasnejsi

Jeste se chci zeptat, je nejaky principialni rozdil mezi mazanim prvku z B-stromu/B*-stromu?

Fórum studentů MFF UK

DELETE v B-stromu

Odeslat odpověď

Rozšířit náhled Přehled tématu: DELETE v B-stromu

Re: DELETE v B-stromu

Re: DELETE v B-stromu

Re: DELETE v B-stromu