DELETE v B-stromu

[Návštěvník]

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)

Kód: Vybrat vše

                   |12|
                  /    \
                /        \
              /            \
            /                \
       |4|7|                  |15|20|
      /  |  \                 /   |  \
    /    |    \             /     |    \
  1|2   5|6   8|9        13|14  16|17 21|22 

Je mi jasne, ze existuje vice strategii pro smazani prvku, ale zajimalo by me, jak byste to delali v tomto pripade, aby to nebyl jen nejaky zpusob, ktery proste zachova vlastnosti B-stromu, ale aby se ten algoritmus dal aplikovat i v jinych pripadech.

Diky za odpovedi.

[Návštěvník]

|12|
/ \
/ \
/ \
/ \
|7| |15|20|
| \ / | \
| \ / | \
2|4|5|6 8|9 13|14 16|17 21|22



|7| 12 |15|20|
| \ / | \
| \ / | \
2|4|5|6 8|9 13|14 16|17 21|22

[Dawe]

Zaprvé bych chtěl podotknout, že Žemlička říkal, že autoři B-Stromu definovali jen přidávání. Z čehož plyne, že mazání nemusí být jednoznačné, každopádně podle toho co jsme dělali na cviku je tohle skoro inverze k přidání.
Vlevo ti zbyde (2) v otci (4) a vpravo (5|6) to už můžeš sloučit do jednoho syna, pak máš ale v otci jen (7) , tedy aplikuješ to o úroveň víš. Mohl by si udělat to, že 12 připojíš k 7 -> (7|12) (včetně nejlevějších synů vpravo (13|14)) a 15 hodit na místo 12, jenže to by ti pak vparvo zbylo jen (20) tudíž musíš sloučit ty hořejší prvky do jedný buňky.
Jednoduše by si to člověk taky možná moh představit tak, že když je toho v synech málo, otec se prostě propadne o úroveň níž mezi levý a pravý syny.

Kód: Vybrat vše

    12
  /     \         ->    7|12|15|20
7    15|20

Asi sem nepřines nic moc novýho než co tady bylo, ale snad sem to vysvětlil pro obecný případ...

[Dawe]

Ještě se tak zeptám - když mám rerundantní B-strom, a v listech něco většího uloženýho. Dejme tomu, že je ten strom 3-patrovej. Do kolika bloků můžu nacpat 2 vrchní patra? Předpokládám, že jsou tam jen malý indexy a vešlo by se to klidně celý do jednoho bloku. Mám to dát do jednoho bloku a nebo každej zvlášť?

[Tuetschek]

Ještě se tak zeptám - když mám rerundantní B-strom, a v listech něco většího uloženýho. Dejme tomu, že je ten strom 3-patrovej. Do kolika bloků můžu nacpat 2 vrchní patra? Předpokládám, že jsou tam jen malý indexy a vešlo by se to klidně celý do jednoho bloku. Mám to dát do jednoho bloku a nebo každej zvlášť?

No zdravy rozum veli nacpat to do jednoho bloku, jestlize se to vejde ... jde o to kolik to ma spolecnyho s vypracovanim pisemky ... ja bych to asi tak fakt nacpal a nejak se to snazil argumentaci podporit

[pcv]

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

[Návštěvník]

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?

[Návštěvník]

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

[nohis]

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

[Návštěvník]

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

[Dawe]

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í...

[Návštěvník]

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?

[Tuetschek]

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

[LuKu]

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?

[Tuetschek]

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