Traverzování kolem stromu #3

Traverzování kolem stromu je jeden ze způsobů, jak ukládat stromovou strukturu dat v relační databázi. V tomto třetím díle dokončíme přesouvání uzlů a navíc doplníme naši třídu o velice jednoduchou metodu pro přejmenování uzlů.

Článek opět volně navazuje na předchozí články o Traverzování kolem stromu ( #1, #2 ). V minulém článku jsme se začali věnovat přesouvání jednotlivých uzlů ve stromu.

Při traverzování nám vzniká strom dost složitý pro editaci uzlů, protože si musíme neustále hlídat indexy. U přesouvání uzlů je to o to obtížnější, že musíme přečíslování většinou rozdělit do několika částí.

V minulém článku jsme si řekli, že nám může vznikat několik případů při přesouvání:

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.

Toto jsou tří základní případy a pokud všechny ošetříme, nebude problém ve stromu přesouvat.

Přesouvání uzlů ve stromu

Dost bylo teorie a nyní se podíváme na praxi. Nebudeme se zabývat jednotlivými případy přesouvání ale vytvoříme si univerzální metody, které nám ošetří automaticky všechny tři případy bez ohledu na to, zda jsou uzly hned vedle sebe, nebo nikoli.

Metodu pro přesun pojmenujeme changeTree a jako vstupní parametry budou levé indexy mezi sebou přesouvaných uzlů. Tato metoda nebude zatím nic přesouvat, ale pouze připraví proměnné pomocí dalších metod, které jsme si vytvořili minule:

Metoda vytvoří pole $parametrs, které bude obsahovat levé a pravé indexy uzlů pro přesun. Pro zjištění indexů použijeme metodu _checkingTree, která zároveň kontroluje, zda mají oba uzly stejnou úroveň vnoření ve stromu
Na konci je volána metoda _edit_TREE, která už bude přesouvat uzly. Než si ji napíšeme budeme potřebovat další metodu, která nám zjistí ID uzlů, které leží v prvním přesouvaném podstromu a mezi oběma přesouvanými stromy, pokud takové existují. Vždy musí existovat minimálně jeden takový uzel:

Všimněte si, že pokud se některá operace nepodaří, metoda vždy vrací hodnotu „nula“ a nic dalšího se nestane.

Tím máme hotový základ a můžeme se vrhnout na metodu pro přesun.

Meodta _edit_TREE nejprve přečísluje pravý podstrom, který leží více vpravo ( má větší pravý index ) na místo levého podstromu, potom zjistí, zda existují mezi těmito dvěma podstromy další uzly a v případě že ano, přečísluje je.
Nakonec přečísluje i levý strom na místo pravého.

Žádné další uzly přečíslovávat nemusí (tím myslím uzly které jsou před levým podstromem nebo za pravým podstromem), protože tyto uzly musí i dále souhlasit tak jako byli před přesouváním.

Funkce _edit_TREE:

Všimněte si, že metoda volá další metodu, _edit_bettwen. Tato metoda bude právě přečíslovávat uzly mezi dvěma stromu a musíme ji nyní dopsat:

Volána by nebyla, kdyby dva podstromy, které přesouváme měli stejný počet poduzlů. V takovém případě by indexy mezi stromy souhlasily. Bohužel toto nemusí být vždy pravda. Metoda _edit_bettwen nám tento případ zabezpečí.

Posun nahoru || dolů

Pro případ, že bychom chtěli přesouvat uzly jenom o jeden uzel vedle si můžeme vytvořit dvě jednoduché metody, které budou využívat hotovou metodu _edit_TREE, ovšem nikdy se nebude volat metoda _edit_bettwen.

Abychom si zjednodušili práci s uživatelským prostředím, tak si vytvoříme ještě jednu metodu, která bude mít první vstupní parametr levý index přesouvaného uzlu a druhý bude směr, kam se bude přesouvat.

V metodě jsou použity výrazy nahoru a dolů, toto je myšleno podle velikosti levého indexu:

Volány jsou dvě metody, které si budou velmi podobné. Nejprve se zjistí levý index uzlu na který chceme přesouvat a v případě že takový uzel existuje a vyhovuje, volá se metoda changeTree:

Tím máme hotovu celou operaci přesouvání uzlů. Na závěr si ještě doplníme naši třídu o jednoduché přejmenování uzlu.

Přejmenování uzlu

Metoda pro přejmenování je v naší třídě jenom jako takové doplnění, protože tuto funkci můžete v budoucnu potřebovat:

V příští části se podíváme na ovládání celé třídy. Vytvoříme si funkce pro vypsání stromu a vytvoříme si jednoduchý kód pro snadné ovládání přesunu a podobně.

Na závěr se zase můžeme podívat co máme hotové: