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 :-)).
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.
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.