Traverzování kolem stromu #4 (operace nad stromem)

Traverzování kolem stromu je jeden ze způsobů, jak ukládat stromovou strukturu dat v relační databázi. V tomto čtvrtém díle si ukážeme základní operace nad stromem.

Čtvrté pokračování volně navazuje na předchozí články ohledně traverzování kolem stromu ( #1, #2,
#3). V předchozích dílech jsme si vytvořili třídu, která traverzování umožňuje. Pomocí hotových metod můžeme data vypisovat a různě přeskupovat. Nyní si vytvoříme několik užitečných funkcí pro toto ovládání.

Výpis stromu

Hlavní výhodou je výpis stromu. Při traverzování se nám automaticky ohodnocuje každý uzel dvěma indexy, které jsou v celém stromu unikátní. Podle těchto indexů jsme schopni vypsat jakoukoli část stromu.

První funkce na kterou se tedy zaměříme je vypsání celého stromu:

Data, která získáte jsou přesně uspořádána tak jak je potřebujete a tak jak jste je uložili. Tato funkce vybere všechny uzly ve stromu a uspořádá je přesně tak, jak po sobě následují. Právě tohle nám zařídí seřazení dle levého indexu.

Nyní není problém abychom vypsali pouze strom do určitého vnoření nebo jenom několik prvních uzlů. Vše záleží na vaší představivosti.

Pokud máme všechna data vybrána, vytvoříme si jednoduchou metodu pro výpis těchto dat:

Metoda vypisuje hloubku vnoření ve stromu, název a dále odkaz na vypsání podstromu.
Pro vypsání podstromu budeme potřebovat znát pravý a levý index. Pokud totiž známe pravý a levý index tak známe všechny indexy uzlů, které jsou jako podstrom v tomto daném uzlu.
Všechny tyto indexy musí mít větší levý a menší pravý index.

Vše je patrné z SQL dotazu v této metodě:

Opět by bylo možné si jednoduše omezit hloubku zanoření a jednoduše tak vypisovat celý strom.

Vidíte že všechny SQL dotazy jsou velice jednoduché a není problém si velice jednoduše zjistit jakoukoli strukturu.

Cesta k uzlu

Stejně jako není problém vypsat celý strom nebo jeho část, tak není problém vypsat cestu k jednomu uzlu od počátku stromu, nebo od určitého zanoření.

Na příkladu si ukážeme výpis od počátku stromu, tedy od uzlu s nejmenším levým a největším pravým indexem, ale pro vás jistě nebude problém si dotaz upravit dle potřeby:

Opět potřebujeme znát jak levý tak pravý index toho uzlu, ke kterému chceme znát cestu. Vznikne nám zase jednoduchý SQL dotaz, který vrací data přesně tak jak je potřebujeme.
Všechny uzly, které jsou v cestě nad daným uzlem musí mít menší levý a větší pravý index. Všechny takové uzly musíme projít abychom se dostaly k danému uzlu.

Data řadíme dle vnoření, abychom je dostaly seřazené od počátku do konce.

Přidávání uzlů

Pokud jste četli předchozí díly, tak jistě víte že pro přidávání uzlů jsme si vytvořili metodu addTree. Její vstupní parametry jsou:

• název nového uzlu
• levý index uzlu za který přidáváme
• pozice na kterou přidáváme (h – nahoru, e- dolů).

Přidáme si tedy do výpisu tabulky jednoduchý formulář, pomocí něhož budeme moci přidat další uzel.

Pro jednoduchost bude příklad umožňovat přidávání pouze na začátek podstromu, ale pro vás není opět problém si příklad rozšířit:

Formulář se bude defaultně odesílat pomocí GET a odešle nám všechny potřebné hodnoty. Pro uložení použijeme metodu ze třídy pro traverzování:

Tím tento čtvrtý díl ukončím.

Jak je vidět jsou všechny operace nad stromem velice jednoduché a vystačíte si s jedním SQL dotazem pro všechny základní výběry, které budete potřebovat.

V dalším díle si vytvoříme rozhraní pro podrobnější editaci stromu, které bude umožňovat přidávání uzlů, přesouvání uzlů a podobně.

Vše co jsme si dnes vytvořili ještě jednou na závěr shrnu: