Zdrojový kód: INCLUDE\UTIL\RBTREE.INC, UTIL\RBTREE.ASM
RBTREE - Red-Black vyvážený strom
Binární stromy slouží k rychlému přístupu do tříděného seznamu objektů. Při prohledávání binárního stromu se strom prochází po uzlech, ve kterých se porovnává třídicí klíč s klíčem v uzlu a podle výsledku porovnání se rozhodne, zda další hledání bude pokračovat v levé nebo pravé větvi stromu nebo zda byla nalezena hledaná položka.
V tomto průvodci bude struktura stromů vykreslována zdola nahoru, oproti běžným konvencím shora dolů, neboť - strom rostoucí shora dolů je poněkud neobvyklý.
Základem binárního stromu je kořen (root). Každý prvek stromu se nazývá uzel (node). Každý uzel má svou hodnotu - třídicí klíč. Z uzle mohou vycházet další dvě větve - levý a pravý potomek (child), uzel je pro potomky rodičem (parent). Uzel, ze kterého nevychází další větve, se nazývá listem (leaf). Platí, že všechny uzly s menší hodnotou klíče leží v levé větvi a všechny uzly s větší hodnotou klíče v pravé větvi. Dva uzly nemohou mít stejnou hodnotu klíče. Je-li potřeba vyhledat uzel s určitou hodnotou klíče, vychází hledání z kořene stromu. V každém uzlu je porovnána hodnota klíče uzlu s hledanou hodnotou klíče. Je-li hledaný klíč menší, pokračuje se dále levou větví (levým potomkem). Je-li hledaný klíč větší, pokračuje se pravou větví. Je-li klíč shodný, požadovaný uzel byl nalezen. Pokud v daném směru nenavazuje další potomek, hodnota klíče nebyla nalezena.
Vyváženým stromem označujeme takový binární strom, který umožňuje vyhledat položku co nejkratší cestou. Existuje mnoho algoritmů, jak udržovat strom ve vyváženém stavu. Jedním ze zástupců automaticky vyvažovaných binárních stromů je tzv. "Red-Black vyvážený strom" (nebo-li červeno-černý strom, dále zkráceně RB-strom). Větve stromu jsou automaticky vyvažovány při vkládání nebo rušení položek.
Každý uzel RB-stromu je označen červenou nebo černou barvou. Pro RB-strom platí následující pravidla:
každý uzel je buď červený nebo černý,
kořen (root) je vždy černý,
nulové listy (které neukazují na další uzel, tj. NULL) jsou černé,
oba potomci každého červeného uzlu jsou černí,
všechny cesty z daného uzlu k jeho listům obsahují stejný počet černých uzlů (buď včetně nulových listů nebo bez nulových listů).
Uvedené podmínky zajišťují základní vlastnost RB-stromu, tj. že nejdelší cesta od kořene k listům není více než 2x delší než nejkratší cesta, díky tomu můžeme považovat RB-strom za dobře vyvážený.
Struktura popisovačů RB-stromu
