Hlavní navigace

GLib: Binární stromy

Michal Burda

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?