Traverzování kolem stromu – přesuny uzlů
Školení, která pořádám 
V článku Traverzování kolem stromu prakticky jsem popsal základní operace se stromem, ve kterém je hierarchie řešena pomocí tohoto postupu. Ten má ve srovnání s pouhým ukládáním informace o rodiči záznamu kromě vyšší výkonnosti také tu výhodu, že data mohou být ve stromě libovolně seřazena.
Přidání předchůdce uzlu
Kromě již popsaného přidání posledního potomka uzlu se nový prvek dá přidat také před libovolný uzel:
<?php mysql_query("START TRANSACTION"); $row = mysql_fetch_assoc(mysql_query("SELECT * FROM strom WHERE id = " . intval($_GET["nasledujici"]) . " FOR UPDATE")); mysql_query("UPDATE strom SET lft = lft + 2 WHERE lft >= $row[lft]"); mysql_query("UPDATE strom SET rgt = rgt + 2 WHERE rgt > $row[lft]"); mysql_query("INSERT INTO strom (lft, rgt, hloubka, nadpis) VALUES ($row[lft], $row[lft]+1, $row[hloubka], '" . mysql_real_escape_string($_POST["nadpis"]) . "')"); mysql_query("COMMIT"); ?>
Nový prvek bude mít lft uzlu, před který je vložen, rgt o jedničku vyšší a stejnou hloubku. Následující uzly musíme posunout.
Editace uzlu
Pokud chceme umožnit přesuny uzlu, musíme nejprve uživateli prezentovat, kde se uzel momentálně nachází, a nechat ho vybrat, na jaké místo chce uzel přesunout.
Jako nejlepší se mi jeví zobrazit uživateli strom stávajících uzlů s výjimkou vlastního podstromu doplněný o hlavní kořen a nechat ho zvolit vztah k vybranému uzlu.
<?php $strom = mysql_get_vals("SELECT id, CONCAT(REPEAT('- ', hloubka), nadpis) FROM strom WHERE lft < $row[lft] OR rgt > $row[rgt] ORDER BY lft"); $vztah = "predchudce"; list($pribuzny) = mysql_fetch_row(mysql_query("SELECT id FROM strom WHERE lft = $row[rgt] + 1")); if (!$pribuzny) { $vztah = "potomek"; list($pribuzny) = mysql_fetch_row(mysql_query("SELECT id FROM strom WHERE lft < $row[lft] AND rgt > $row[rgt] ORDER BY lft DESC LIMIT 1")); } echo "Vztah: <select name='vztah'>" . optionlist(array("predchudce" => "předchůdce", "potomek" => "potomek"), $vztah) . "</select>\n"; echo "Příbuzný: <select name='pribuzny' size='8'><option></option>" . optionlist($strom, $pribuzny) . "</select>\n"; ?>
Strom kromě vlastního podstromu jsou ty uzly, které mají lft menší než já nebo rgt větší než já.
Pokud jsem předchůdcem nějakého uzlu, tak tento uzel má lft o jedničku vyšší než moje rgt. Pokud takový uzel neexistuje, tak jsem posledním potomkem svého rodiče. Rodič je ten uzel, který má největší menší lft a větší rgt.
Přesun uzlu
<?php $pribuzny = mysql_fetch_assoc(mysql_query("SELECT lft, rgt, hloubka FROM strom WHERE id = " . intval($_POST["pribuzny"]))); $row = mysql_fetch_assoc(mysql_query("SELECT lft, rgt, hloubka FROM strom WHERE id = " . intval($_GET["id"]))); $rozdil = $row["rgt"] - $row["lft"] + 1; if (!$pribuzny) { $lft = mysql_result(mysql_query("SELECT IFNULL(MAX(rgt) + 1, 1) FROM strom"), 0); $hloubka = 0; } elseif ($_POST["vztah"] == "predchudce") { $lft = $pribuzny["lft"]; $hloubka = $pribuzny["hloubka"]; } else { $lft = $pribuzny["rgt"]; $hloubka = $pribuzny["hloubka"] + 1; } if ($lft > $row["lft"]) { $lft -= $rozdil; } if ($lft != $row["lft"]) { $min_lft = min($lft, $row["lft"]); $max_rgt = max($lft + $rozdil - 1, $row["rgt"]); $posun = $lft - $row["lft"]; if ($lft > $row["lft"]) { $rozdil = -$rozdil; } mysql_query(" UPDATE strom SET hloubka = hloubka + IF(@podstrom := lft >= $row[lft] AND rgt <= $row[rgt], " . ($hloubka - $row["hloubka"]) . ", 0), lft = lft + IF(@podstrom, $posun, IF(lft >= $min_lft, $rozdil, 0)), rgt = rgt + IF(@podstrom, $posun, IF(rgt <= $max_rgt, $rozdil, 0)) WHERE rgt >= $min_lft AND lft <= $max_rgt "); } ?>
Přesun uzlu není zrovna triviální operace. Nejprve si zjistíme lft, rgt a hloubku svého rodiče a své původní hodnoty. V dalším kroku určíme své nové lft a hloubku:
- Pokud jsme potomkem kořene, bude
lfto jedničku větší než maximálnírgta hloubka nulová. - Pokud jsme předchůdcem jiného uzlu, bude naše nové
lftjeholfta hloubka bude stejná. - Pokud jsme posledním potomkem jiného uzlu, bude naše
lftjehorgta hloubka bude o jedničku vyšší.
Pokud uzel přesouváme dopředu, musíme lft snížit o velikost vlastního podstromu ($rozdil). Poté již následuje vlastní přepočítání všech ovlivněných uzlů – svůj podstrom přesuneme o $posun, ostatní ovlivněné uzly o $rozdil. Vyřešeno to je v jednom velkém dotazu, kde se nejprve do proměnné @podstrom přiřadí, zda je modifikovaný uzel v našem podstromu a potom se na základě toho upraví hodnoty hloubka, lft a rgt. Proměnná je nezbytná, protože pokud bychom test prováděli v každém přiřazení, testovala by se už nová hodnota nastavená v předchozích přiřazeních.
Ovlivněné jsou ty uzly, které mají lft nebo rgt mezi starou a novou hodnotou těchto čísel.
Diskuse
David Grudl:
Nevím, jestli neobjevuju Ameriku, takže to jen zkouším.
Tento způsob zápisu hierarchie má jedno velké mínus - není SQL nativní a tudíž je nutné tabulku udržovat extra kódem. Buď pomocí triggerů nebo k tomu určenému administračnímu rozhraní - pak ale nelze použít třeba phpMyAdmin.
Nebylo by možné podporu takových stromů implementovat do phpMinAdmin? Například tím způsobem, že tabulka by nesla příznak (zapsaný třeba v komentáři), že jde o strom, pole pro uložení klíčů by zjistila autodetekcí (lft*, rgt*, parent*), pokud by nebyly explicitně určeny v tom komentáři.
Co myslíš? Pro mě by to byla killer feature :-)
David Grudl: 
Jakub Vrána 
:
To je přesně vlastnost, která se nehodí do phpMinAdminu (který je určen na nízkoúrovňovou práci s daty), ale do Admineru (který je vysokoúrovňový). A co bys řek' – má to tam: http://www.adminer.org/cs/pro/documentation/#col-LFT.
Jakub Vrána : 
zaachi:
Je to už dávno co jsem řešil traverzování kolem stromu.
Nejsložitější operace je, když chcete prohodit dva podstromy mezi sebou, kdy musí být přečíslovány indexy indexy pravého stromu, indexy levého stromu a dle počtu uzlů v novém levém stromu přečíslovány indexy uzlů mezi stromy.
http://www.zaachi.com/cs/search?word=traverzov%…&x=0&y=0
zaachi: Jakub Vrána :
Spíše než prohození dvou podstromů je podle mě přirozenější přesun jednoho podstromu na nové místo. A to přesně řeší jeden dotaz v tomto článku, který na rozdíl od tebou popsaných čtyř dotazů nemá ani omezení na stejnou hloubku přesouvaného podstromu.
Jakub Vrána : zaachi:
Díky. Tehdy jsem to řešil dost krkolomným způsobem. Bohužel
zaachi: Robert Vlach:
Před nedávnem jsem se stromovou strukturou webového katalogu znovu detailně zaobíral pro účely portálu Na volné noze. Konkrétně mi přestala vyhovovat přílišná svázanost stromu s předem danou koncepcí jeho tvůrce. Používal jsem samozřejmě jako ostatní křížové odkazy, ale ani to nevedlo k uspokojivému výsledku.
Výsledkem mých úvah byl inovativní koncept webového katalogu, který staví na kombinování tagů neboli štítků, je plně hypertextový a tedy search-engine-friendly. Technicky to sice bylo docela náročné, ale výsledek docela stojí za vyzkoušení:
http://navolnenoze.cz/katalog/
Jakub Vrána :
Nálepky jsou šikovné, ale mají jiné vlastnosti než stromy. Někdy to může být výhoda, jindy nevýhoda, u katalogu mám o výhodách zrovna jisté pochybnosti.
Někdo třeba zvládne překládat z němčiny a angličtiny, ale tlumočit jen z angličtiny. Dostane nálepky Němčina, Angličtina, Tlumočení, Překlady, takže se zobrazí i v kategorii Tlumočení+Němčina.
Tvůj koncept se mi líbí, poukazuji jen na nevýhodu.
Zajímalo by mě, jakým způsobem vybíráš kategorie, které je možno přidat k aktuálnímu zobrazení.
Jakub Vrána : Robert Vlach:
Jasně je to tak, jak naznačuješ: každý systém má své výhody a nevýhody.
Zatímco stromový katalog je na můj vkus příliš omezený a tato omezenost dále vzrůstá s jeho složitostí, systém tagů či štítků může naopak trpět přílišnou otevřeností. Tomu je dle mého názoru dobré předcházet tím, že se štítky vytvářejí kontrolovaně a s určitou předvídavostí.
Například ten problém, který zmiňuješ, nastvává v praxi celkem běžně, ale to už je pak zase otázkou řazení, aby nejméně relevantní záznamy vyjížděly ve výpisu níže. Já toho momentálně dociluji tak, že čím více štítků záznam má, tím nižší dostane prioritu, což vyvažuje jeho výskyt ve vícero sekcích.
Jinak pokud jde o tu kontextovou nabídku dalších štítků k aktuálnímu výběru, postupuji podle několika jednoduchých pravidel:
1) Nabízím do kombinace jen takové štítky, které vracejí v dané kombinaci minimální požadovaný počet záznamů (např. 4).
2) Nenabízím do kombinace štítky, jejichž přidáním by se výběr nezúžil na nižší počet, což by odporovalo základnímu pravidlu dobré navigace, že každé kliknutí by mělo uživatele přiblížit jeho cíli.
3) Je-li štítků do kombinace příliš mnoho (např. více než 30), omezím výběr na tento mezní počet s tím, že vypustím ty štítky, které v kombinaci vracejí nejmenší počet záznamů.
Jakub Vrána :
Díky za objasnění. Skupiny na titulku jsou vybrané ručně?
Jakub Vrána : Robert Vlach:
Ano, to jsou, ale jinak je k nim přistupováno jako k normálním štítkům, takže je lze kombinovat i odebírat. Výjimku tvoří také štítky oblastí, kde výše uvedená omezení neplatí. Z hlediska principu je ale užití štítků oblastí identické a počítá se i s podoblastmi (okresy):
> katalog/grafika/
> katalog/grafika+moravskoslezsky-kraj/
> katalog/grafika+okres-ostrava/
Robert Vlach:
PS: Z výše uvedeného celkem logicky plyne, že aby byl záznam z úvodní stránky doklikatelný, musí být označen alespoň jedním z hlavních štítků ;-)
Jakub Vrána :
Myslím, že ne nutně. Vlezu do hlavní kategorie, přidám vedlejší štítek a odeberu hlavní.
Jakub Vrána : Robert Vlach:
Ano, to je sice pravda, ale běžný uživatel štítky pravděpodobně příliš odebírat nebude (rozsáhlejší uživatelský test příští měsíc to zřejmě potvrdí). Takže pro lepší dohledatelnost je dobré ty top štítky používat a podpořit tím funkcionalitu podobnou běžnému katalogu.
Mimochodem docela zajímavou kompenzační výhodou této koncepce katalogu je také to, že ze zobrazených záznamů (prezentací) je možné kliknout přímo na jednotlivé štítky a tím si nechat okamžitě zobrazit další záznamy v kontextu, který mne zajímá nebo výběr posléze dále kombinovat:
http://navolnenoze.cz/prezentace/jakub-vrana/
http://navolnenoze.cz/prezentace/robert-vlach/
Jakub Vrána :
To přece není výhoda tohoto přístupu. Když by záznamy byly rozřazeny do hierarchických kategorií (jeden záznam může být ve více kategoriích), funkčnost by byla úplně stejná.
Jakub Vrána : Robert Vlach:
Jo, to jsem si uvědomil, až jsem to odeslal, že jsem se nevyjádřil úplně přesně :-) Měl jsem samozřejmě na mysli kompenzaci toho problému s horší dohledatelností záznamů, které jsou v nejběžnějších kombinacích až někde dole. Zároveň jsem tím poukazoval na skutečnost, že takto koncipovaný katalog je de facto možné plnohodnotně procházet z jakéhokoliv bodu jakožto výchozího, zatímco u běžného stromového katalogu by uživatel vstupoval do jedné dílčí větve.
Robert Vlach:
PS: Nestraním jednoznačně ani jednomu řešení, protože je ve jasné, že strom i peer-to-peer kombinace štítků mají své plusy a minusy. Na druhou stranu mi přišlo podnětné do této diskuse takto přispět, protože mnozí designéři často ani nezvažují ke klasickému stromu jinou alternativu, zatímco ve světě stále více serverů přechází na tu či onu formu štítkování (podle mého subjektivního odhadu, přesná čísla neznám ;-)
Tecka:
U přesunu uzlu nemá být jenom: "$max_rgt = max($row["rgt"]);"? Jakub Vrána :
To ne, ale $rgt není definované, takže je potřeba to zapsat jako $lft + $rozdil. Díky za upozornění, opravil jsem to.
Jakub Vrána : ia:
Pri presúvaní uzla ako posledného potomka vzniká chyba - pri úprave lft a rgt nového rodiča algoritmus nezohľadňuje fakt, že nový rodič bude mať väčší rozdiel rgt-lft ako mal predtým (spôsobuje to neostrá nerovnosť v podmienke nastavenia lft a rgt). Jakub Vrána :
Díky za upozornění, opravil jsem to.
Jakub Vrána : Ivo:
Pokud přesouvám z předních pozic na následující s nastaveným vztahem předchůdce, tak pak kategorie na novém místě má stejné lft jako kategorie na kterou jsme se navazovali. Neví někdo kde je chyba?Ale je to vždy jen pokud přesouvám z hora dolů, naopak to funguje dobře.
Ivo:
Nakonec mi pomohlo upravit UPDATE dotaz takto:WHERE rgt >= $min_lft AND lft < $max_rgt
RoW:
Nebolo by dobre vyriešiť celu tuto problematiku presunu na strane DB? Podľa mňa by sa mal držať čistý nezávislý návrh DB a PHP. Niekoľko procedúr a fukcií by MySQL malo zvládnuť a čisto teoreticky by celý tento presun mal trvať aj kratšie (usudzujem podľa vlastných skúseností s využívaním procedúr / triggerov / funkcií) V mnohých prípadoch som sa dostal na úroveň úspory do 25 ~ 30% času, čo je podľa mňa dosť zaujímavé číslo na uvažovanie presunu niečoho takého z PHP priamo na DB. Čo vy na to? Jakub Vrána :
Souhlasím. Pokud budeš uloženou proceduru vytvářet, tak ji sem potom prosím dej.
Jakub Vrána : xyzop:
Zdravím, chtěl bych poprosit o pomoc, vzhledem k tomu, že to tady nikdo neřeší, tak musím mít někde chybu já. Problém je v tom, že se mi neupraví pravá strana rodičů uzlu pod které jsem nový uzel přidal. Mám na to metodu, do které posílám id uzlu který přesouvám a id uzlu pod který ho chci přidat.Kód vypadá následovně:
<?php
function moveTree($id_uzel, $id_uzel_to)
{
// presovany uzel
$select = $this->getAdapter()->select()
->from('strom','*')
->where('id = ?', (int)$id_uzel)
->forUpdate(true);
$row = $this->getAdapter()->fetchRow($select);
// rodic prp presouvany uzel
$select = $this->getAdapter()->select()
->from('strom','*')
->where('id = ?', (int)$id_uzel_to)
->forUpdate(true);
$row_to = $this->getAdapter()->fetchRow($select);
$rozdil = $row[traverz_right] - $row[traverz_left] + 1;
// pokud jsem to dobre pochopil, staci pouze tohle,
/ protoze uzel bude vzdy jako potomek
$lft = $row_to["traverz_right"];
$hloubka = $row_to["traverz_parent"] + 1;
if ($lft > $row["traverz_left"]) {
$lft -= $rozdil;
}
if ($lft != $row["traverz_left"]) {
$min_lft = min($lft, $row["traverz_left"]);
$max_rgt = max($lft + $rozdil, $row["traverz_right"]);
$posun = $lft - $row["traverz_left"];
if ($lft > $row["traverz_left"]) {
$rozdil = -$rozdil;
}
$this->getAdapter()->query("
UPDATE strom
SET traverz_parent = traverz_parent + IF(@podstrom := traverz_left >= $row[traverz_left] AND traverz_right <= $row[traverz_right], " . ($hloubka - $row[traverz_parent]) . ", 0),
traverz_left = traverz_left + IF(@podstrom, $posun, IF(traverz_left >= $min_lft, $rozdil, 0)),
traverz_right = traverz_right + IF(@podstrom, $posun, IF(traverz_right <= $max_rgt, $rozdil, 0))
WHERE traverz_right >= $min_lft AND traverz_left <= $max_rgt
");
}
}
?>
Whitek:
xyzop: Jakub opravil chybicku v clanku - neodecitala se tam 1 v <?php $max_rgt = max($lft + $rozdil - 1, $row["rgt"]); ?>
Jarda:
Napadá někoho, jak jednoduše všechny větve uspořádat dle abecedy?pj.cz:
<?phppublic function getNamesOrderedTree($direction)
{
if($direction != 'ASC' && $direction != 'DESC') {
$direction = 'ASC';
}
$nodes = $this->table->order('depth ASC, parent_id ASC, name '.$direction);
$tree = Array();
$parents = Array();
$i = 0;
$depth = 0;
$parent_id = 0;
foreach($nodes as $node) {
if($depth < $node->depth || $parent_id < $node->parent_id) {
$i = $parents["{$node->parent_id}"] + 1;
}
$tree[$i] = $node;
$childnodes = ($node->rgt - $node->lft - 1) / 2;
if($childnodes > 0) {
$parents["{$node->id}"] = $i;
}
$depth = $node->depth;
$parent_id = $node->parent_id;
$i += $childnodes + 1;
}
ksort($tree);
return $tree;
}
?>
Pedro:
Ahoj,zajímalo by mne jestli existuje nějaké řešení také pro PostgreSQL databázi. Jde mi hlavně o to, že v PostgreSQL nelze ukládat proměnné v SQL výrazu (alespoň jsem to nikde nenašel, pokud to lze tak to všechno vyřeší). Díky.
Jakub Vrána :
Určitě by se to dalo přepsat na více příkazů.
Jakub Vrána : 
Ondřej Mirtes:
Ahoj, díky za skvělý článek/návod, vyřešilo to většinu problémů, které jsem s implementací hierarchických komentářů měl. Ale nevím, jak implementovat obrácení výpisu, jako je to např. na idnesu - seřadí se sestupně (časově) první úroveň hloubky, všechny reakce už jsou zas vzestupně. Když zavolám ORDER BY lfg, je vše vzestupně (tzn. jako tady). Chci to mít zapnuté volitelně, tzn. že změnou struktury DB to nejde.
Ondřej Mirtes: Jakub Vrána :
Já bych tento způsob nedoporučoval, protože je nelogický. Když přijde čtenář k diskuzi seřazené jako na tomto blogu, může ji číst odshora dolů. Pokud je první úroveň seřazena obráceně, tak se příspěvek může odkazovat na komentáře, které jsou teprve pod ním. Diskuse se tedy nedá číst lineárně.
Dalo by se to udělat tak, že kromě lft a rgt by v tabulce bylo ještě pořadí prvního příspěvku, které by se při založení nového příspěvku zvyšovalo a u reakcí by zůstalo stejné jako u rodiče. lft a rgt by bylo samostatné pro každý thread_order. Řadilo by se pak buď podle thread_order, lft nebo thread_order DESC, lft (na to nicméně MySQL nedokáže použít celý index).
Jakub Vrána : Mirek:
Zdravím, potřeboval bych menší pomoc kde dělám chybu. Snažím se upravit dotaz pro stávající uzly s výjimkou vlastního podstromu, kterýbudu přesouvat. Funkce mysql_get_vals a optionlist jsem na webu dohledal a je mi již jasné.
Pokud použiji následující dotaz z článku a samozřejmě změním na své tabulky a sloupce, tak dostanu při volbě procesory 2 11 správný
výsledek 1 3 6 7
<?php
$strom = mysql_get_vals("SELECT cat_id, CONCAT(REPEAT('- ', depth_id), cat_name)
FROM categories
WHERE lft < 2 OR rgt > 11
ORDER BY lft");
?>
Pokud však použiji úpravu pro načtení názvu kategorie z druhé tabulky místo id (na základě id), tak se mi vrací první název a to vždy ten z konce tabulky.
V tomto případě 9 tedy duron.
<?php
$strom = mysql_get_vals("SELECT c.cat_id, CONCAT(REPEAT('- ', c.depth_id), cd.cat_name)
FROM categories c, categories_desc cd
WHERE lft < 2 OR rgt > 11
AND c.cat_id = cd.cat_id
AND c.depth_id > 0 (zde chci nezobrazovat hlavní kořen)
ORDER BY lft");
?>
Chybný výpis:
Duron (c.cat_id je ale opravdu 1, ale cd.cat_id je 9 a nevím proč)
- Paměti
- - DDR
- - SIMM
1 zboží 1 18
2 procesory 2 11
4 intel 3 4
5 amd 5 10
8 athlon 6 7
9 duron 8 9
3 paměti 12 17
6 ddr 13 14
7 simm 15 16
Jirka:
Při přesunutí uzlu se uzel přesune na konec větve. Nastává otázka jak udělat přesun v rámci větve například ze třetího místa na první ?příklad:
-ovoce
--jablko
--hruška
--pomeranč
--grep
Jak posunout pomeranč na první místo tak aby jablko bylo na druhém místě .... ?
Jakub:
Musím říci, že řeším podobný problém, používám stromovou strukturu krom jiného také na menu a to znamená, že při každé změně (pokud chci změnit pořadí) musím prakticky přepsat celé menu...Napadá někoho jak udělat řazení v rámci větve?
Diskuse je zrušena z důvodu spamu.
© 2005-2024 