Něco ke staení
Články a návody
Poezie
Odkazy
B - strom
B - strom je oblíbená datová struktura pro uložení dat na vnějších pamětech (např. na pevném disku). Slovo strom v názvu správně napovídá, že při tomto typu uložení zas budeme pracovat s uzly, které budou rozdělovat data do skupin podle nějakého porovnání s hodnotou v uzlu. Na rozdíl od binárních stromů ale v uzlu není pouze jeden klíč (neboli hodnota, podle které data rozdělujeme), ale je jich tam několik. Zcela jinak se také do B - stromu přidávají a z něho odebírají prvky.
B - strom řádu k je struktura s následujícími vlastnostmi:
- každý uzel kromě kořene obsahuje alespoň k-1 a nejvýše 2*k-1 klíčů (spodní mez neplatí pro kořen, ten musí mít alespoň 1 klíč)
- každý uzel s n klíči obsahuje n+1 odkazů na syny (pokud není listem)
- všechny listy leží ve stejné hladině (cesta z kořene do všech listů je stejně dlouhá)
- klíče v uzlu jsou setříděné
- pro kadžý klíč platí, že v jeho levém podstromu jsou pouze prvky menší nebo rovné klíči, v pravém podstromu prvky větší (ne nutně, pokud uvažujeme možnost výskytu více prvků se shodným klíčem, pak jsou prvky s klíčem shodným s uzlem v pravém podstromu)
Celá struktura se pro řád 3 dá nakreslit třeba takto:
(Ty čáry představují ukazatele mezi otci a syny, u otců začínají opravdu mezi klíčovými hodnotami, ale na syny ukazují prostě jako na celé pole, takže by spíš měly vést na první klíč pole. No prostě mi trochu pozdě došlo, že to není moc názorný obrázek)
Na předchozím obrázku si také ukážeme, jak ve stromu budeme vyhledávat prvek. Budeme hledat například číslo 13. Podíváme se do uzlu a postupně budeme porovnávat prvky s naším číslem. 4 < 13, takže nás nezajímá a podle posledního bodu definice víme, že v levém podstromu už 13 ležet nemůže. Dalším prvkem je 38, takže nemůžeme hledat ani vpravo od 38 a tak je naší jedinou možností ukazatel na podstrom mezi klíči 4 a 38. Tam se celá situace opakuje, s tím rozdílem, že hodnotu 13 nalezneme. Kdyby 13 nebyla ani v tomto uzlu, tak dál nehledáme, protože ukazatele z tohoto uzlu se rovnají NULL (prostě na nic neukazují, pro ne Céčkaře), popřípadě si můžeme také počítat výšku stromu podle ní vyhledávání ukončit.
Trochu sloužitější je vkládání prvku. Postupujeme při něm nejprve jako při vyhledávání. Pokud prvek najdeme, vkládání ukončíme (předpokládám, že si nebudeme ukádat prvek ve více kopiích, i když se to také často používá), v opačném případě skončíme v nejnižší úrovni stromu v nějakém listě. Místo toho, abychom jako při vyhledávání ukončili práci, nový uzel sem vložíme.
Tady mohou nastat dvě možnosti - ta snažší je, že v listu bude ještě místo. V tom případě odsuneme větší prvky v listu o jedno políčko vpravo a na volné místo zařadíme náš prvek a jsme hotovi.
Obtížnejší situace nastane, když chceme vložit prvek do uzlu, který má už 2*k-1 prvků a je tedy úplně plný. V tomhle případě nám nezbývá nic jiného, než vytvořit nový uzel, do kterého zkopírujeme prvních k prvků starého uzlu, posledních k prvků necháme v původním uzlu a zbylý prvkek (označíme si ho třeba t) s prostřední hodnotou pošleme otci takto děleného listu. Předpokládejme, že ukazatel na dělený strom byl mezi prvky x a y otce. Pokud je v otci místo, vložíme prvek t mezi prvky x a y. Mezi x a y byl původně ukazatel na dělený uzel, po vložení prvku t do ukazatele mezi x a t uložíme ukazatel na nový uzel s prvními k prvky a do ukazatele mezi t a y dáme ukazatel na druhou část rozštěpeného uzlu.
Pokud se nám stane, že vkládáme prvek t do otce, který je již také plný, rozštěpíme i jeho a opět jeden prvek pošleme jeho otci. To děláme tak dlouho, dokud nenarazíme na otce, do kterého se dá vkládat. Pokud takhle dojdeme až do kořenu a ten je také plný, rozštěpíme kořen a pro nahoru posílaný prvek vytvoříme nový uzel, který se stane novým kořenem obsahujícím jen jeden prvek.
Použijeme předchozí obrázek a ukážeme si na něm přidání několika prvků.
Přidáme prvek 40
Přidáme prvek 10
Přidáme prvek 11
Při posledním vkládání jsme měli vložit prvek 11 mezi 10 a 13. Protože 7 prvků se nám do stromu řádu 3 nevejde, museli jsme tento list rozdělit na dva, rozdělit jejich klíče a prostřední z nich poslat otci o patro výš. V tomto příkladě jsme měli štěstí a do otce se klíč 10 vešel. Kdyby byl otec u plný, museli bychom rozdělit otce a opět poslat prostřední prvek o patro výš. Protože v našem případě byl otec kořenem, vytvořil by se nový kořen s právě jedním prvkem, jeho ukazatele by ukazovaly na obě části rozštěpeného původního kořene.
(doufám, že je to zřejmé, vzhledem k prostorové náročnosti příkladů a své lenosti je kreslit to podrobněji vysvětlovat nebudu)
Jak jsem několikrát během popisu stromů naznačoval, existují různé verze B-stromů. Můžeme mít verze, které každý klíč mohou obsahovat nejvýše jednou, nebo se klíče mohou i opakovat (pokud budete například třídit databázi podle příjmení, tak budete chtít zachovat všechny osoby stejného příjmení). Pro některé účely se také používají stromy, které mají všechna data v listech, a pokud například použiju nějaký klíč do uzlu, který není listem, uložím si ho ještě jednou do listu (to mi bude sloužit například k tomu, že můžu pomocí B-stromu rychle hledat v databázi podle příjmení, ale pokud budu chtít hledat lidi například podle data narození, projdu sekvenčně jenom listy). Pokud zase chci používat vyhledávání podle více kritérií, pak do stromu nebudu ukládat samotná data, ale uzly budou obsahovat jen ukazatele na skutečná data. Budu si tak moci pro jedna data vytvořit zárověň více B-stromů a používat je podle potřeb uživatele.
Ještě než si ukážeme poslední příklad, zbývá ještě malá poznámka - v předchozím textu jsme při vkládání prvků sestupovali až do listu a pokud jsme měli smůlu, tak jsme se při štěpení vrátili zpět do kořene. Tomu se dá předejít pomocí drobné úpravy. Pokud bychom měli sestoupit při sestupování směrem dolu do plného uzle, tak ho nejdřív rozštěpíme. Pokud pak do něho budeme vkádat, máme zaručeno, že bude kam. Výhodou je, že si nemusíme pamatovat u každého uzlu ukazatele na otce.
No a zbývá ještě ukázat alespoň kus kódu. Protože se jedná o rozsáhlejší problém, nebudu tady rozepisovat všechno (prostě chci elegantně říct, že jsem moc líný, abych to celé přepisoval), a ukážem si jen základní datové typy. Podle nich a popsaného algoritmu byste to měli složit. Pro jednoduchost budeme předpokládat, že děláme knihovnu pro pevný řád stromu, nějakou konstantu K:
#define K 3 //definujeme si rad stromu
struct B_Uzel {
struct B_Uzel *synove[2*K];
/*
ukazatele na syny
- klic s indexem i bude mit levy podstrom synove[i], pravy synove[i+1]
*/
int klice[2*k-1];
//hodnoty klicu, samozrejme to muze byt nejaky jiny typ, ne jen int
int pocet_klicu;
//abychom vedeli, kolik polozek v poli klice mame prohledavat
};