B-stromy

B-stromy sú jedným z typov dátových štruktúr, konkrétne z vyhľadávacích stromov. Od väčšiny ostatných sa však líšia v tom, že v jeho uzloch možno uložiť viac ako jeden prvok. Čo to so sebou prináša? Poďme sa na to pozrieť!

Najskôr si definujeme B-stromy, konkrétne ich vlastnosti. Pomôže nám to k jednoduchšiemu pochopeniu algoritmu

Vlastnosti

• 1. Maximálny počet prvkov v uzle je u všetkých uzlov rovnaký a volíme ho na začiatku (od tejto chvíle budem túto vlastnosť nazývať kapacita a značiť ju budem písmenom r (r> = 2)). Poďme si tu rovno povedať, že dôležitá je väčšinou polovica z kapacity. Polovicu (budeme značiť p) zr vypočítame ľahko: p = r / 2 (v prípade párneho r), p = (r-1) / 2 (v prípade nepárneho r)
• 2. Jednotlivé uzly (koreňa) musí byť aspoň z polovice zaplnené, nesmie však prekročiť r.
• 3. Prvky uložené v uzle sú zoradené vzostupne.
• 4. Uzol je buďto list alebo má o jedného následníka viac, než je počet prvkov v ňom uložený. Následník potom v sebe obsahuje prvky väčší ako jeho ľavá hodnota v predkovi a menšie ako pravá hodnota predkovi.
• 5. Listy sú v B-stromu len v jeho poslednej (najspodnejšej) úrovni. Inými slovami vzdialenosť všetkých listov od koreňa je rovná (a je rovná aj s výškou stromu).

Na obrázku vidíme B-strom s výškou 1 as kapacitou 3. Keďže je v jeho koreni (uzol hore) jeden prvok, podľa vlastnosti vyššie musia mať presne 2 následníkov, ak to teda nie je listový uzol. Na druhú stranu, jeho potomkovia sú listovej uzly, takže musí byť na rovnakej úrovni. Môžete tiež skontrolovať, že prvky sú zoradené, takže všetky vlastnosti platí.

Pozn .: Niekedy môžete v súvislosti s B-stromy započuť pojem "poriadok". B-strom s kapacitou uzla r má poriadok r + 1, keďže nelistový uzol môže mať až r + 1 následníkov.

Vyhľadávanie

Teraz k samotnému algoritmu. Kvôli odlišnosti implementácie, veľkosti a zložitosti, tu nebudem uvádzať pseudokód alebo kód v nejakom konkrétnom jazyku. Ale napíšem detailný popis slovami pre vyhľadávanie, vkladanie a odstraňovanie.

Značenie

• Aktuálny uzol budeme označovať u (na začiatku ním bude koreň uzla - najvyšší uzol, ktorý nemá žiadneho predka)
• Hľadanú hodnotu potom budeme označovať x.

Algoritmus

1. Vyhľadanie xv uzla u (môžeme použiť napríklad sekvenčné alebo binárne vyhľadávanie), tento krok môže skončiť 3 spôsobmi:

1. x bol vu nájdený - vyhľadávanie úspešne končí
2. x nebol nájdený vuau je list - vyhľadávanie neúspešne končí
3. x nebol vu nájdený au je nelistový. V tom prípade skončilo v mieste, kde je odkaz na jeho následníka, ktorý by mal prvok obsahovať. Pokračujeme v teda v ňom, zmeníme aktuálny uzol u na onoho následníka a vrátime sa na krok 1.

A to je všetko Veľmi jednoduché že?

Vkladanie prvku

Značenie

• Aktuálny uzol - u
• Pridávaný prvok - x

Algoritmus

1. Vykonáme vyhľadanie v strome, môže to skončiť 2 spôsobmi:

1. prvok x bol nájdený. Pridávanie končí (nepredpokladá sa viac rovnakých prvkov vo stromu)
2. vyhľadávanie skončilo v lístkovom uzle u, kde by mal prvok nachádzať (vzhľadom k veľkosti), x na toto miesto vložíme. Ak uzol u nie je zaplnený (počet prvkov vu nie je väčšia ako r), pridávanie končí. Ak však r presiahne, dôjde k rozdeleniu uzlov.

2. Rozdeľujeme uzly. Ak má u po pridaní r + 1 prvkov, rozdelíme uzol na tri časti. Využijeme známeho pa rozdelíme ho teda:

P prvkov na začiatku uzle + prvok uprostred + p prvkov na konci uzla.

Prvá a druhá časť budú nové uzly (môžete si všimnúť, podmienka minimálneho počtu p bude platiť) a prvok uprostred presunieme do predchodca, na miesto, kde bol odkaz na uzol u. Akonáhle presunieme prvok, vytvoríme naľavo a napravo od neho odkazy na novovzniknuté listy.

Možno vás napadlo, že sme tým problém nemuseli vyriešiť. Áno, skutočne, v prípade umiestnenia prvku vyššie môže dôjsť k preplneniu uzla, do ktorého sme prvok vložili. To vyriešime rovnakým spôsobom. Krok 2 opakujeme kým sa nedostaneme ku koreňu alebo kým nedospejeme k uzlu, ktorý nebude preplnený. Keď aj v koreni dôjde k preplneniu, rozdelí sa znovu na tri časti a prostredný bude umiestnená do samostatného uzla a tento uzol sa stane novým koreňom. Časti sp prvky budú znovu jeho odkazy. V tejto chvíli dochádza k zväčšeniu stromu.

Skúsme si to na príklade. Zoberme si napríklad tento strom kapacity 4.

Pridáme prvok 15. To by nemal byť problém. Problémom však je, že sme prekročili kapacitu uzla.

Našťastie vieme ako to vyriešiť - rozdelíme si preplnený uzol a prvok presunieme hore.

Odoberanie prvku

Značenie

• Aktuálny uzol - u
• Odoberaný prvok - x

Algoritmus

1. Vykonáme vyhľadanie v strome prvku x, môže to skončiť 3 spôsobmi:

1. x nebolo v strome nenašlo - operácia končí, nie je čo odobrať.
2. x bolo nájdené v lístkovom uzla (uzol v najspodnejšej úrovni). X z uzla odstránime. Keď je uzol aspoň z polovice (p) zaplnený, operácia končí. Inak prejdeme ku 2. kroku.
3. x bolo nájdené v nelistovém uzla. X z uzla odstránime a na voľné miesto umiestnime buď najväčšie (teda najpravejšie) prvok z ľavého podstromu (najpravejšie list). Alebo najmenších (teda najľavejšiu) prvok v pravom podstrome (najľavejšiu list). Ak je vo všetkých listových uzloch aspon polovica prvkov, operácia odobratie končí. Inak prejdeme ku 2. kroku.

2. Môže sa stať, že narušíme podmienku - každý uzol musí byť aspoň z polovice (p) zaplnený, má teda p-1 prvkov. Tento stav sa dá, samozrejme, riešiť. V podstate máme riešenie 2:

Prakticky to budem predvádzať na tomto strome (r = 4)

1. List u má aspoň jedného súrodenca, ktorý obsahuje viac ako p prvkov. Presunieme do uzla u prvok z predchodcu a na novo vzniknuté miesto v predchodcovia presunieme najväčšej (v prípade, že sused je vľavo od u) či najmenších (v prípade, že sused je vpravo od u) prvok zo suseda.

Odstraňujeme 15.

1. List u nemá súrodencov, ktorí majú viac ako p prvkov. Vytvoríme teda nový list sr prvky z uzla u + prvok z predchodcu + prvky zo súrodencov u.

Odstraňujeme 12.

Tu môže nastať situácia, že v predchodcovia znova dôjde k tomu, že počet prvkov bude p-1. Rieši sa to rovnako, záleží na súrodencoch. Môžeme sa tak dostať až ku koreňu, ak zlúčime uzol s koreňom, v ktorom bol len jeden prvok, novo vzniknutý uzol sa stáva koreňom.

A teraz ukážem príklad so zmenou koreňa. Vezmeme si tento strom, ktorý bude mať kapacitu 4 a odstránime prvok v koreni - 60.

Odstránime prvok 60 a presunieme prvok 59 (najväčší prvok v ľavom podstrome) na miesto v koreňoch, mohli by sme presunúť aj 62, ale zbytočne by sa nám rozbila podmienka, ktorá určuje, že musí byť aspoň z polovice zaplnený.

Vidíme, že všetky vlastnosti B stromu platí.

A to je všetko

Na záver pre záujemcov uvediem časovú zložitosť. U vyhľadávanie zložitosť závisí aké veľké máme ra akú metódu vyhľadávania použijeme v jednotlivých uzloch. Keď zvolíme binárne vyhľadávanie, má logaritmickou zložitosť. Ďalej musíme započítať prechádzanie uzlov od koreňa k listu, tu výška stromu závisí logaritmicky od počtu prvkov. Vyhľadávanie má teda logaritmickou zložitosť. Základom pridanie a odobratie prvku je vyhľadávanie a ďalej (možný) priechod hore. Tu je priechod hore zas závislý na výške stromu. Teda všetky operácie majú logaritmickou zložitosť, ktorá je už celkom príjemná