Hlavní navigace

GLib: Binární stromy

Michal Burda 17. 8. 2000

Binární stromy, podobně jako hashe, slouží k rychlé orientaci v datech. Umožňují promptní vyhledávání a procházení daty podle různých kritérií.

Strom

je takové uspořádání prvků (uzlů, nodes), ve kterém lze rozeznat předchůdce (rodiče – parent) a následovníky (děti – children). Každý prvek může mít nejvýše jednoho předchůdce a několik následovníků (binární stromy nejvíce dva).

Kořenem (root) nazýváme takový prvek, který nemá předchůdce. V každém stromu se nachází jen jeden kořen.

Naopak listy (leafs) jsou takové prvky, které nemají žádného následovníka. Má-li strom jen jeden prvek, je tento kořenem i listem zároveň (patrně zvláštní genetická vada; botanikové prominou :-)).

Ukázka binárního stromu

Obrázek 1 – Ukázka binárního stromu

Strom na obrázku 1, kromě toho, že je binární (každý prvek má nejvýše dva následovníky), je navíc vyvážený (balanced). Vyvážený znamená, že vzdálenost od kořene ke každému listu je nejmenší možná (přesněji: minimální).

Dobrá, řekli jsme si, co to jsou stromy, ale co to má společného s uchováváním dat? Je to vymyšleno takhle: data se do stromu uchovávají jako jednotlivé uzly tak, že jsou v jistém smyslu seřazeny. Pro každý uzel pak platí, že jeho levý následovník je menší a pravý následovník větší než on sám.

Z takového uložení dat vyplývá, že nalézt hledanou položku (x) v binárním stromu bude velmi snadné. Stačí začít strom procházet od kořene. (Aktuální uzel zvolíme kořen.) Porovnáme hodnotu uloženou v aktuálním uzlu a x. Je-li x rovno hodnotě v aktuálním uzlu, končíme. Je-li x menší, potom za aktuální uzel zvolíme levého následovníka. Podobně, je-li x větší, za aktuální uzel vybereme pravého následovníka. A tak se bude neustále pokračovat, dokud hledanou položku (x) nenalezneme nebo nedojdeme až k listům stromu.

Vyvážený binární strom naplněný daty

Obrázek 2 – Vyvážený binární strom naplněný daty

Binární stromy knihovny GLib jsou reprezentovány strukturou GTree. Všechny položky této struktury jsou skryté, což znamená, že by se se stromem mělo pracovat jen pomocí vymezené sady funkcí, kterou si v této a následující části popíšeme.

Do stromu GTree se ukládají dvojice klíč–data. GTree je neustále vyvažován, takže cesta od kořene k listům je vždy nejmenší možná. To je předpokladem dobré efektivity vyhledávacího algoritmu.

Vytvoření nového GTree

Nový binární strom vytvoříte funkcí

GTree* g_tree_new(GCompareFunc key_compare_func); 

Jako jediný parametr se jí předává funkce key_compare_func, která musí odpovídat (pravidelným čtenářům již dobře známému) předpisu  GCompareFunc:

gint (*GCompareFunc) (gconstpointer a, gconstpointer b); 

Při práci se stromy se od key_compare_func očekává, že vrátí zápornou hodnotu, jestliže první argument ( a) patří před druhý ( b) (jinými slovy, pokud a je menší než b), nulu, pokud jsou a i b  shodné a kladnou hodnotu, pokud a patří za b ( a je větší než  b).

Funkce key_compare_func slouží k porovnávání klíčů.

Přidávání prvků do GTree

void g_tree_insert(GTree *tree, gpointer key, gpointer value); 

Tato funkce vloží do binárního stromu tree pod klíčem key data value. Jestliže prvek s klíčem key ve stromu již existuje, budou jeho stará data nahrazena novými.

Strom je automaticky „vyvážen“, takže vzdálenost listů od kořene zůstává co nejmenší.

Podobně jako s hash tabulkami, i zde vznikají problémy, použijete-li dynamicky alokované klíče či data. Klíče i data jsou ve stromu uchovávány v podobě předaných odkazů. Neexistuje-li ve stromu klíč s hodnotou key, je vše v pořádku: předané pointery key a value se uloží do nového uzlu stromu. Jestliže položka s klíčem key však ve stromu již existuje, aktualizuje se pouze pointer na data (hodnotou value). V takovém případě je však nutno stará data dealokovat stejně tak jako „nově“ předávaný klíč.

Získávání dat z  GTree

gpointer g_tree_lookup(GTree *tree, gpointer key); 

…vyhledá v binárním stromu tree uzel s klíčem key a vrátí jemu přiřazená data.

Vyhledání dat podle klíče je velmi rychlé, protože strom je v každém okamžiku „vyvážen“ (balanced).

Uvolnění GTree z paměti

void g_tree_destroy(GTree *tree); 

Uvolní binární strom tree z paměti. Pokud jste ale používali dynamicky alokované klíče nebo data, musíte je ještě před voláním g_tree_destroy() dealokovat sami.

Ukázali jsme si základní funkce pro práci s  GTree. Příště povídání o binárních stromech dokončíme. Navazovat pak budou kapitoly o obecných, několikanásobných stromech.

Našli jste v článku chybu?
Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: Na poslední chvíli šokuje vyjímkami v EET

Na poslední chvíli šokuje vyjímkami v EET

Lupa.cz: Na koho se v Křišťálové Lupě nedostalo?

Na koho se v Křišťálové Lupě nedostalo?

Podnikatel.cz: Babiše přesvědčila 89letá podnikatelka?!

Babiše přesvědčila 89letá podnikatelka?!

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

DigiZone.cz: Rádio Šlágr má licenci pro digi vysílání

Rádio Šlágr má licenci pro digi vysílání

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube

Vitalia.cz: Dáte si jahody s plísní?

Dáte si jahody s plísní?

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

120na80.cz: Jak oddálit Alzheimera?

Jak oddálit Alzheimera?

Podnikatel.cz: Prodává přes internet. Kdy platí zdravotko?

Prodává přes internet. Kdy platí zdravotko?

Podnikatel.cz: Babiš: E-shopy z EET možná vyjmeme

Babiš: E-shopy z EET možná vyjmeme

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Vitalia.cz: Chtějí si léčit kvasinky. Lék je jen v Německu

Chtějí si léčit kvasinky. Lék je jen v Německu