|
|||
Typy stromů a jejich implementace
Implementuje se obvykle jako seznam zřetězených prvků, kde každý uzel stromu obsahuje pole ukazatelů na následníky (syny).
mít nejvýše dva následníky (syny). Implementuje se jako seznam zřetězených prvků, někdy jako pole.
Pozice vrcholů binárního stromu lze očíslovat následujícím způsobem:
Začneme kořenem, kterému přiřadíme 1, dále jeho levému následníku 2, pravému následníku 3, a v číslování pokračujeme na každé úrovni zleva až do konce, kde přejdeme na další úroveň.
Tyto čísla jsou pak indexy uvedených pozic v binárním stromu. Pokud se na pozici skutečně nachází vrchol, prvek pole obsahuje klíč. V opačném případě je prvek pole označen jako nepoužit, například jsou-li hodnoty vrcholů nezáporná celá čísla, může být jeho hodnota -1.
Má-li vrchol hodnotu indexu i, potom
levý následník má index 2i
pravý následník má index 2i + 1
předchůdce, pokud existuje, má index i/2 (celočíselně).
Obecně, tato implementace není efektivní, protože nejenom musíme vytvořit pole pro předpokládanou maximální velikost stromu, ale navíc musí obsahovat i prvky pro pozice neobsazené vrcholy.
Poznamenejme, že uvedené vztahy platí, má-li kořen stromu index 1. Pokud by jsme ho umístnili do prvku pole s indexem 0, tyto vztahy nutno upravit.
Vrchol binárního stromu můžeme implementovat obdobně jako prvek seznamu, jenomže namísto položky dalsi budou v implementaci vrcholu polozky levy a pravy
class Vrchol {
int klic;
Vrchol levy;
Vrchol pravy;
...
void tiskVrcholu() {
System.out.print(klic+” “);
}
}
V případě seznamu, když jsme potřebovali projít (navštívit) všechny jeho prvky, například pro jejich vytištění, postupovali jsme od prvního k dalšímu pomocí ukazatele dalsi, atd.
V případě stromu začneme kořenem, ale pro další systematický postup máme tři možnosti
Přímý průchod (preorder) navštívíme vrchol, potom levý a pravý podstrom
Vnitřní průchod (inorder) navštívíme levý podstrom, vrchol a pravý podstrom
Zpětný průchod (postorder) navštívíme levý a pravý podstrom a potom vrchol
Binární strom je definován rekurzivně a následně můžeme rekurzivně vyjádřit jeho průchody.
Rekurzivní průchod stromem
void pruchodR(Vrchol v) {
if (v == null)
return;
v.tiskVrcholu();
pruchodR(v.levy);
pruchodR(v.pravy);
}
Vrchol koren;
pruchodR (koren);
Uvedená metoda implementuje průchod preorder, posunutím řádku s tiskem mezi rekurzivní volání získáme implementaci průchodu inorder a jeho posunutím za obě rekurzivní získáme implementaci průchodu postorder.
Čas průchodu stromem je pro prázdný strom dán vyhodnocením podmínky
T(0) = cpor
Trvá-li tisk ctisk a má-li levý strom m vrcholů a prvý strom n-m vrcholů, potom
T(n) = T(m) + T(n-m) + ctisk pro n > 0
Její řešení je T(n) = (cpor + ctisk)n + cpor čas průchodu stromem je O(n).
Použitím abstraktního zásobníku, do kterého můžeme ukládat klíče anebo stromy můžeme vytvořit nerekurzivní implementace průchodů.
1. Do zásobníku vložíme procházený strom
2. Dokud zásobník není prázdný, v cyklu vybereme prvek ze zásobníku a je-li ním klíč vytiskneme ho, jinak do zásobníku vložíme
pro preorder: pravý podstrom, levý podstrom, klíč vrcholu
pro inorder: pravý podstrom, klíč vrcholu, levý podstrom
pro postorder: klíč vrcholu, pravý podstrom, levý podstrom
Pro preorder průchod je při vkládání jako poslední vložen klíč a ten je tedy vybrán na začátku uvedeného cyklu a vytisknut.
Nerekurzivní preorder průchod pak je
void pruchod(Vrchol v) {
VZasobnik z = new VZasovnik();
z.push(v);
while (!z.jePrazdny()) {
v = z.pop();
v.tiskVrcholu();
if (v.pravy != null) z.push(v.pravy);
if (v.levy != null) z.push(v.levy);
}
}
Binární vyhledávací strom je takový strom pro který platí (kromě toho, že je binární):
Nechť x je vrchol stromu.
Je-li y vrchol v levém podstromu, potom hodnota vrcholu y (klíč) < hodnota vrcholu x.
Je-li y vrchol v pravém podstromu, potom hodnota vrcholu y (klíč) > hodnota vrcholu x.
Od toho se odvíjí i vkládání prvku do stromu 
.
Příklad BVS stromu zobrazuje obrázek 
Nevýhody BVS
1.složitost vyhledávání závisí na pořadí vkládání prvků do stromu
2.složité rušení prvku
Rušení prvku
1.v listu - není problém
2.ve vnitřním uzlu - prvek nahradíme symetrickým předchůdcem ("nejpravějším" uzlem z levého podstromu) nebo symetrickým následovníkem ("nejlevějším" uzlem z pravého podstromu). Problém jsme tak převedli na rušení prvku v listu. Obdobně se postupuje i u AVL - stromů. Ale to už trochu předbíhám.
Vkládání a rušení prvku v BVS ukazuje obrázek .
Symetrický následovník a předchůdce jsou zakresleny na obrázku 
Možnosti (volby mezi sym. následovníkem a předchůdcem):
(a) zvolíme "napevno" předchůdce, nebo následovníka ->usíme zajistit jeho existenci ->problém
(b) ten samý přístup, ale pokud předchůdce, případně následovník neexistuje, zvolíme druhou alternativu
(c) zjistíme, který strom je větší, a z té strany vezmeme "náhradní uzel" (zaručuje existenci předchůdce, příp. následovníka uzlu, který chceme odebrat)
U Binárních vyhledávacích stromů rozlišujeme stejně jako u Binárních stromů tři strategie prohledávání: PreOrder (v pořadí: kořen, levý syn-následovník, pravý syn-následovník), InOrder (v pořadí levý syn, kořen, pravý syn) a PostOrder (pravý, kořen, levý). Implementace jsou popsány výše.
Viz.tabulka 
.
Zkusme si nyní implementaci BVS:
Základní operací nad BVS, je hledání hodnoty uložené ve vrcholu podle klíče. Třída Vrchol tedy bude obsahovat navíc člen data, například typu String.
class Vrchol {
int klic;
String data;
Vrchol levy;
Vrchol pravy;
Vrchol (int klic, String data) {
this.klic = klic;
this.data = data;
}
void tiskVrcholu() {
System.out.print(data+” “);
}
}
BVS strom je reprezentován svým kořenem
private Vrchol koren;
Pro prázdný strom je
koren == null
Signatura metody hledej je
String hledej(int)
Z definice BVS přímo plyne její rekurzivní implementace
private String hledejR(Vrchol v, int klic) {
if (v == null)
return null;
if (klic == v.klic)
return v.data;
if (klic < v.klic)
return hledejR(v.levy, klic);
else
return hledejR(v.pravy, klic);
}
String hledej(int klic) {
return hledejR(koren, klic);
}
Hledání v BVS je stejně efektivní jako binární hledání v uspořádané množině. Pro BVS je významné, že stejně efektivně můžeme implementovat i vkládání.
Signatura metody vloz je
void vloz(int, String)
Její rekurzivní implementaci můžeme opsat následovně.
Je-li strom prázdný, nový prvek se stane jeho kořenem. Jinak, je-li klíč nového prvku menší než klíč kořene, prvek vložíme do levého podstromu a do pravého podstromu, je-li klíč nového prvku větší než klíč kořene.
private Vrchol vlozR(Vrchol v, int klic,
String data) {
if (v == null)
return new Vrchol(klic, data);
if (klic < v.klic)
v.levy = vlozR(v.levy, klic, data);
else
v.pravy = vlozR(v.pravy, klic, data);
return v;
}
void vloz(int klic, String data) {
koren = vlozR(koren, klic, data);
}
Obě metody při každém rekurzivním volání sestoupí o jednu úroveň níž a tedy složitost uvedených algoritmů je O(h), kde h je výška stromu.
Průchod inorder BVS, sestrojeným pro posloupnost prvků jejich postupným vkládáním metodou vloz(), vytiskne tyto prvky uspořádané podle klíče.
Nerekurzivní verze uvedených metod se v cyklu rozhodují, budou-li pokračovat v levém nebo v pravém podstromu. V následující metodě vloz se nejprve najde pozice, kam nový vrchol vložit a potom se vloží. Protože proměnná x, pomocí které stromem sestupujeme má v tom okamžiku hodnotu null, udržujeme na proměnné predch (obdobně jako u seznamu) ukazatel na vrchol, ke kterému nový vrchol připojíme.
void vloz(int klic, String data) {
if (koren == null) {
koren = new Vrchol(klic, data);
return;
}
Vrchol x = koren, predch = null;
while (x != null)
if (klic < x.klic) {
predch = x;
x = x.levy;
}
else {
predch = x;
x = x.pravy;
}
if (klic < predch.klic)
predch.levy = new Vrchol(klic, data);
else
predch.pravy = new Vrchol(klic, data);
}
hashovací - vznikly "zkřížením" hash-tabulek se stromovými grafy.
Princip:
hodnoty hash-funkce se interpretují jako bitové řetězce, jimiž se kódují přístupové cesty v patřičném stromu (0 = levý syn, 1 = pravý syn).
Viz obr. 
bitové - vzniknou z hashovacích, položíme-li h(x) = x , prvky umístíme do listů (na konec cesty) odpovídajícím bitovým řetězcům.
Příklad: Adresní strom reprezentující množinu {01001, 01010, 01011, 11010} je zobrazen na obrázku 
.