B-strom

Dnes mě zaujal algoritmus o B-stromu, tak o tom zkusím stručně napsat, abych do budoucna na to nezapomněl. Veškeré poznatky a obrázky jsou z kurzu Algorithms, Part I z webu Coursera.org

Binární strom

Binární strom je graf, kdy má každý uzel (kromě listů) 2 větve s potomky. Uzel je tvořen klíčem a hodnotou (key-value), kdy klíče lze mezi sebou porovnávat.

Binární vyhledávací strom

uzel (předchůdce) má 2 větve - levá větev obsahuje jen potomky s menším klíčem a pravá větev jen  potomky s větší klíčem.

2-3 vyhledávací strom

- tento strom je perfektně vyvážený = všechny cesty z kořene (root) stromu k listům jsou stejně dlouhé

- strom může obsahovat uzel s jedním klíčem (binární strom) nebo s dvěma klíči a třemi větvemi, kde:

1. levá větev obsahuje potomky s menším klíčem
2. prostřední větev obsahuje klíče větší než první klíč a menší než druhý klíč z předchůdce
3. třetí větev obsahuje potomky s větším klíčem

Přidání nového prvku:
- musíme zajistit, aby strom byl pořád pefektně vyvážený - strom musí růst směrem z kořene nahoru. Existuje několik situací:

Přidání prvku (klíč-hodnota) tam, kde uzel obsahuje jen 1 klíč - přidáme do toho samého uzlu a nový klíč umístíme buď nalevo (pro klíče menší) nebo napravo (pro klíče větší) od klíče, který tam už bylo.

1. chci přidat K - vyhledám místo, kam ho přidám - do uzlu obsahující L
2. přidám ho nalevo od L, protože K je menší než L

Přidání prvku tam, kde uzel obsahuje 2 klíče - přidáme klíč do příslušného uzlu jak v předchozím příkladě. Jenže pak vznikne uzel s třemi klíči a 4 větvemi a to by nešlo. Tento uzel se třemi klíči rozdělíme do třech uzlů - prostřední prvek posuneme nahoru a do spodních dvou rozdělíme po dvou 4 větve.

1. chci přidat prvek s klíčem Z - přidám ho do uzlu, který obsahuje klíče S a X
2. vznikl uzel se 3 klíči S, X a Z a 4 větvemi - a to by nešlo
3. rozdělíme tento uzel do 3 uzlů - prostřední klíč posuneme o úroveň výš a zbývající 2 klíče se stanou následnými uzly nalevo (menší klíč) a napravo (větší klíč) od prostředního klíče

Přidání prvku tam, kde uzel a jeho rodič obsahuje 2 klíče - viz předchozí příklad. Ten se opakuje do té doby, než se vše dostane až do kořene. Kořen se 3 prvky rozdělíme tak, že prostřední posuneme o úroveň nahoru, a tak fakticky vznikne nový kořen a strom vzroste o 1 úroveň.

1. chci přidat D - přidám do uzlu obsahující A a C
2. mám uzel s klíči A, C a D a 4 větve - jedna pro prvky menší než A, druhá pro prvky mezi A a C, třetí mezi C a D a čtvrtá větší než D -> to by ale nešlo
3. proto rozdělíme tento uzel na 3 různé uzly - prostřední uzel obsahující klíč C posunu o úroveň nahoru, uzly s klíči A a D budou jeho levými (A) a pravými potomky
4. pokračuji, dokud je strom správně vyvážený a uzly obsahující max. 2 klíče
5. pokud dojdu až na kořen, tak se strom zvýší o jednu úroveň

B-strom

- důvod: zrychlení vyhledávání dat

- zobecnění 2-3 stromu - uzly mohou mít mnoho klíčů

- listy obsahují skutečné klíče, rodiče obsahují kopie těchto klíčů a vytváří tak odkaz na listy

Vyhledávání klíče E - B-strom o velikosti uzlu max. 6 klíčů

1. kořen obsahuje kopie klíčů * a K. E je větší než * a menší než K - půjdeme do uzlu potomka, který začíná znakem * (tzn. obsahuje klíče, které jsou větší nebo rovna znaku *). Znak * je úplně nejmenším znakem, proto je to hned první větev.
2. druhý uzel také obsahuje kopie klíčů * D H, protože to není list. E je větší než D a menší než H - půjdeme do druhé větve.
3. následující uzel už je listem, proto zde najdeme již klíč E

Vkládání nového klíče

1. chci vložit klíč A - vyhledám příslušný list a vložím
2. v tomto případě je list plný - rozdělí se na dva stejně velké listy * A B a C E F - do rodičovského uzlu jde kopie prvního klíče z druhého listu - v tomto případě je to prvek C
3. rodičovský uzel (zároveň kořen) je taky plný - taky se rozdělí na dva stejně veliké uzly * C H a K Q U. Kopie prvního klíče z prvního a druhého listu vytvoří nový kořen.

Složitost

Binární strom - v průměru má bin. strom složitost 1.39 lg N (logaritmus o základu 2). Logaritmus dvou má proto, že počet uzlů o úroveň níž se zvětšuje vždy o mocniny dvou (1 - 2 - 4 - 8 atd.), 1.39 je asi nějaká konstanta udávající nejpravděpodobnější podoba stromu.

Binární strom může mít složitost až N, když jsou prvky, které jdou do stromu, již předem seřazené. 

2-3 strom - díky vyváženosti má složitost v nejhorším případě lg N (když obsahují všechny uzly jen 2 klíče), v nejlepším log₃N (když obsahují všechny uzly 3 klíče).

B-strom - záleží na počtu klíčů v uzlu. Pokud má uzel M klíčů, tak složitost je mezi log_M-1N (log_MN nejde, protože se uzel rozpadne na 2 stejně velké uzly) a log_M/2N (to je případ hned po rozpadu na 2 velké části - což je nejhorší případ).