Traverzování kolem stromu #2

Traverzování kolem stromu je jeden ze způsobů, jak ukládat stromovou strukturu dat v relační databázi. V tomto článku si ukážeme jak lze z vytvořeného stromu mazat uzly a jak můžeme jednotlivé uzly mezi sebou přesouvat.

Článek volně navazuje na předchozí článek „Traverzování kolem stromu #1“, ve kterém byly vysvětleny základní principy algoritmu a ukázali jsme si základní principy vytváření stromu. Pokud jste článek nečetli, doporučuji vám si jej přečíst.

Máme tedy v databázi, ke které se připojujeme, vytvořenou tabulku, a v ní uloženou strukturu dat. U každého prvku (uzlu) máme uložený pravý a levý index a index vnoření ve stromu.

Mazání uzlů ze stromu

Traverzování kolem stromu je algoritmus velice příjemný, pokud se na něj podíváme z pohledu výběru dat. ovšem z pohledu editace stromu nelze téměř žádnou operaci zvládnout jedním SQL dotazem.

Stejně tak je tomu i u mazání uzlů ze stromu. Není možné jenom jednoduše vymazat jeden řádek z tabulky, protože kdybychom tak učinili, nesouhlasili by pravé a levé index. Důležité tedy je, abychom po vymazání každého uzlu zase zkontrolovali index a přečíslovali strom.

Metoda, kterou si vytvoříme jako první, bude kontrolovat, zda v uzlu, který chceme vymazat, nejsou žádné další uzly. Samozřejmě by nebyl problém mazat i celé části stromu, ale je to naprosto zbytečné. Pokud chceme smazat jednu celou část stromu, můžeme ji odmazat po jednotlivých uzlech.

Naše třída bude tedy umožňovat mazat pouze ty uzly, které se již dále nevětví, to znamená, jenom ty, které jsou na konci stromu.

Metoda pro ověření, zda se uzel dále nevětví, bude velice jednouchá. Princip spočívá v tom, že budeme znát pravý a levý index uzlu, který mažeme, a musíme zjistit, zda neexistuje uzel, který má levý index v rozmezí těchto dvou indexů. V metodě tedy musíme znát jak pravý, tak levý index uzlu, který mažeme.

Levý index bude vstupní parametr celé metody pro mazání uzlu a pravý si zjistíme pomocí metody „select_parent“, kterou jsme vytvořili v minulém článku.

Známe tedy oba dva indexy a konečně můžeme vytvořit metodu:

Metoda _chekcTree má návratovou hodnotu 1 nebo 0, a to v případě nalezení, či nenalezení uzlů. Další metoda, kterou budeme potřebovat, bude upravovat pravý a levý index po vymazání.

V minulém článku o traverzování jsme si vytvořili metodu „_update_tree($left)“, která se starala o přečíslování indexů po přidání uzlu. Jistě již tušíte jak bude vypadat metoda pro přečíslování po vymazání. Metoda bude téměř identická, jenom s tím rozdílem, že namísto toho abychom indexy zvyšovali je budeme nyní snižovat:

Zase potřebujeme v metodě znát oba indexy, abychom mohli přečíslovat jenom správné uzly. Přečíslujeme jenom ty, které mají větší index než smazaný uzel.

Nyní, když máme vytvořeny metody pro kontrolu a přečíslování stromu, můžeme konečně mazat uzly. Před mazáním budeme kontrolovat, zda se uzel dále nevětví a těsně před mazáním přečíslujeme strom. Tuto operaci provedeme před mazáním z toho důvodu, že kdyby přečíslování neproběhlo správně (metoda _renumberTree vrací 0), nedojde ke smazání:

Metoda vrací v případě úspěchu hodnotu 1. V případě, že existují další uzly, které jsou vnořené v mazaném uzlu, vrací hodnotu -1. V ostatních případech vrací hodnotu 0, která symbolizuje neúspěch.

Přesouvání uzlů ve stromu

Přesouvání uzlů je asi ta nejsložitější operace, kterou budeme ve stromu provádět. Pro přesouvání dvou uzlů budeme muset znát jejich levé indexy. Levé indexy budou přímo vstupními parametry metody pro přesouvání. Tyto vstupní parametry musíme zkontrolovat, zda mají stejnou úroveň vnoření. Pokud nebude tato skutečnost splněna, nebude se přesouvat. Budeme tedy zase omezeni na to, že dva uzly, které přesouváme, musí mít stejnou úroveň vnoření.

Levý index známe, neznáme ovšem pravý index a úroveň vnoření. Jako první si tedy vytvoříme metodu pro zjištění těchto hodnot:

Metoda vrací pole, ve kterém jsou uloženy pravý index a úroveň vnoření obou uzlů. Tuto metodu voláme další metodou, kterou potřebujeme.

Metoda _checkingTree kontroluje hodnoty vnoření a navíc kontroluje indexy. Návratová hodnota je pole, které obsahuje hodnoty z metody _select_parent_check.

Nyní známe všechny potřebné hodnoty pro to, abychom mohli dva uzly mezi sebou přesunout. Při přesouvání nám může vzniknou několik situací:

První z nich nastane v případě že jsou dva uzly hned vedle sebe a neobsahují další vnořené uzly. Tento případ je nejjednodušší a stačí pouze přehodit indexy u těchto uzlů.

Další případ nastane v případě, že dva uzly jsou vedle sebe, ale mají v sobě vnořené další uzly. V tomto případě musíme navíc změnit indexy i na uzlech, které jsou uvnitř uzlů, které přesouváme. Je to logické, protože pravý a levý uzel nemusí obsahovat stejný počet vnořených uzlů a tím pádem musí být změněny všechny indexy.

Nejsložitější případ nastane v situaci, kdy oba uzly které přesouváme obsahují další uzly a navíc jsou další uzly mezi nimi. V tomto případě musíme změnit indexy ve všech poduzlech pravého uzlu, ve všech poduzlech levého uzlu a nakonec ještě změnit indexy ve všech uzlech, které jsou mezi těmito dvěma uzly.

Na všechny tyto případy musíme brát ohled a všechny tyto případy řádně ošetři. Nyní máme vytvořeny pouze
metody pro zjištění informací, které potřebujeme pro přesun.

Ti chytřejší si přesun dodělají sami, ostatní si musí počkat na další článek.

Na závěr se ještě podívejme co už máme hotovo: