Traverzování kolem stromu #1
Traverzování kolem stromu je jeden ze způsobů, jak ukládat stromovou strukturu dat v relační databázi. Způsobů, jak ukládat stromová data je samozřejmě spousta, ovšem ne všechny jsou dostatečně efektivní. Můžeme například používat různé rekurzivní způsoby, jež jsou většinou při větší velikosti stromu velice pomalé neboť pro získání celého stromu bude zapotřebí minimálně tolik SQL dotazů, kolik je úrovní rozvětvení. Další možností je použít zásobník, který je sice rychlejší než rekurze, ale i tak při větší velikosti stromu budeme na databázi chrlit spousty SQL dotazů.
Způsob, u kterého si většinou
vystačíme s jedním nebo dvěma SQL dotazy pro jakoukoli operaci, se nazývá
Traverzování kolem stromu.
Základní princip celého
algoritmu je velice jednoduchý. Úkolem je ohodnotit všechny uzly stromu pořadovými
čísly, podle nichž procházíme celým stromem. Pro lepší představu ohodnocení si
prohlédněte obrázek:
Pořadová čísla, kterými
ohodnocujeme strom začínají od nejnižšího čísla a při každém dalším uzlu toto
číslo narůstá o hodnotu 1. Celým stromem procházíme zleva doprava a tím
získáváme celou jeho strukturu.
Home (1, 16) -> First (2, 7) -> Thrid (3, 4) -> Fourth(5, 6) -> First(3, 7) -> Second(8, 12)
-> Fifth(9, 14) -> Sixth (10,
11) -> Seventh(12, 13) -> Fifth(9, 14) -> Second(8, 12)
-> Home(1, 16)
Každý uzel má nyní dva indexy
– pravý a levý. Při ohodnocení uzlů tímto způsobem nám vzniká efekt, který bude
pro naši práci se stromem velice důležitý. Uzel, ve kterém jsou poduzly, má
vždy menší levý index než všechny tyto poduzy a jeho pravý index je větší než
všechny jeho poduzly. Patrné je to z kořene celého stromu, který má
nejmenší levý index a největší pravý index v celém stromu.
Výhoda spočívá v tom, že
nyní pro nás není problém získat kterýkoliv podstrom seřazený přesně podle toho
jak jej máme uložený v databázi, pouze jedním SQL dotazem.
Pro naprogramování tohoto
algoritmu jsem zvolil kombinaci PHP 5 a MySQL 4.1:
Tabulka v databázi
Před samotným ukládáním dat si
musíme vytvořit tabulku v databázi. Všechno co v tabulce potřebujeme
je jméno položky, pravý a levý index a navíc budeme ukládat ještě velikost
vnoření položky ve stromu. Popřípadě můžeme ještě ukládat prefix pro jazykovou
mutaci ( v celém kódu budeme předpokládat že prefix jazykové mutace je
uložen v poli SESSION). Struktura tabulky může potom vypadat například
nějak takto:
|
1 2 3 4 5 6 7 8 |
CREATE TABLE preorder_tree_traversal ( id_traverz INTEGER NOT NULL AUTO_INCREMENT, traverz_name VARCHAR(100), traverz_parent SMALLINT, traverz_left SMALLINT, traverz_right SMALLINT, lang VARCHAR(6), PRIMARY KEY( id_traverz ); |
Modified Preorder
Tree Traversal class
Pokud máme vytvořenou
tabulku, můžeme si vytvořit třídu pro obsluhu celého algoritmu. U traverzování
je sice obsluha dat v databázi trochu složitější, než je tomu u jiných
algoritmů, ale přístup k těmto prvkům (jednotlivým uzlům) je o to více
efektivní.
Problém při editaci je právě
v tom, že při každé změně se musí přečíslovat indexy uzlů, aby nám
nevznikali kolize ve stromu.
Celá třída se bude skládat
z metod, které budou obsluhovat traverzování. Jako první si nadefinujeme
konstruktor, do kterého můžeme předat jako parametr název tabulky, ve které je
připravena požadovaná struktura:
|
1 2 3 4 5 6 |
class traverz extends connect{ function __construct( $table_name ){ $this->table_name = $table_name; parent::__construct(); } } |
Pro připojení k databázi
využijeme třídu connect, kterou si do naší třídy pomocí dědičnosti nadědíme.
Jako první si vytvoříme
metodu, která vloží do tabulky první prvek stromu – kořen. Kořen bude musí mít,
za předpokladu že ve stromu nejsou žádné uzly, indexy 1 a 2. Přitom index
parent nastavíme na hodnotu 0, ze které budeme vycházet:
|
1 2 3 4 5 6 7 8 |
function _insert_first(){ $insert = "INSERT INTO " . $this->table_name . "(traverz_name, traverz_parent, traverz_left, traverz_right, lang ) VALUES( 'HOME', '0', '1', '2', '" . $_SESSION['lang_prefix'] . "' )"; mysql_query($insert, $this->link); return ( mysql_affected_rows($this->link) == 1 ? 1 : 0); } |
Pro kontrolu, zda má být
metoda volána můžeme vytvořit funkci, která zkontroluje, zda je tabulka
prázdná, nebo neobsahuje-li žádný uzel s danou jazykovou mutací:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function _check_num_of_rows(){ $select = "SELECT COUNT(*) FROM " . $this->table_name . " WHERE lang = '" . $_SESSION['lang_prefix'] . "'"; if( mysql_result( mysql_query( $select, $this->link ), 0, 0) == 0 ){ self::_insert_first(); return 0; } else{ return 0; } } } else{ return 0; } } |
Přidání uzlu
Jedna z nejdůležitějších
metod v celé třídě bude přidávání uzlů. Důležité je myslet na to, že při
každém přidání uzlu musíme přečíslovat všechny uzly, které budou za přidaným
uzlem. Jsou to všechny, které mají levý index větší než index prvku, za který
přidáváme, o hodnotu i+1.
Při ukládání uzlu máme
možnost si vybrat za který uzel bude nový uzel vložen. Pro jednoduchost bude
třída umožňovat pouze přidání uzlu, který bude vnořen jako do našeho uzlu.
Budeme si ovšem moci vybrat, zda chceme vložit na začátek uzlu nebo na jeho
konec.
Vysvětlím to ještě jednou na
obrázku. Podívejte se na obrázek, který je uložen na začátku článku a chtějme
vložit další uzel za uzel „First“. Třída nám umožní uložit uzel před uzel
„Thrid“ (na začátek) nebo za uzel „Fourth“ (na konec) s tím, že vložený
uzel bude mít stejný parent index jako uzly „Thrid“ nebo „Fourht“.
Funkce addTree bude mít tedy
tři vstupní parametry: Jméno nového uzlu, levý index uzlu, za který vkládáme a
pozici kam chceme vkládat (na začátek nebo na konec):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
function addTree ( $name, $left, $position = 0 ){ if( gettype( $position ) == 'string' ) $position = self::_setup_position( $position ); $position = abs( intval( $position) ); if( $position > 2 ) return 0; $parent = self::select_parent($left, 1); switch( $position ){ case 0 : { if( self::_addTree_h( $name, $left, $parent ) == 1 ) return 1; else return 0; break; } case 1 :{ if( self::_addTree_e( $name, $left, $parent, ( $this->traverz_right - 1 ) ) == 1 ) return 1; else return 0; break; } } return 1; } |
Metoda addTree volá nejprve
metodu _setup_position, která je zde jenom z důvodu příjemnějšího
vstupního parametru pro pozici. Hodnota tohoto vstupního parametru, který může
být zadán buď jako hodnota 0, 1, nebo jako hodnoty H, E ( Home, End):
|
1 2 3 4 5 6 7 |
function _setup_position( $position ){ switch( strtolower( $position ) ){ case 'h' : return 0; break; case 'e' : return 1; break; default: return 0; } } |
Dále je zde volána self::select_parent($left,
1), která zjistí parent hodnotu uzlu, za který vkládáme:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function select_parent($left, $info = 0){ $select = "SELECT traverz_parent, traverz_right, id_traverz FROM " . $this->table_name . " WHERE traverz_left = '" . $left . "' AND lang = '" . $_SESSION['lang_prefix'] . "' LIMIT 1;"; $data = mysql_query($select, $this->link); if( $info == 1 ){ $this->traverz_right = @mysql_result($data, 0, 1); $this->id_traverz = @mysql_result( $data, 0, 2 ); } return ( @mysql_result($data, 0, 0) + 1 ); } |
Nepovinný parametr je $info.
Pomocí nějž si uložíme hodnotu pravého indexu a hodnotu ID prvku, pro další
práci.
Nyní již konečně můžeme
vkládat uzel. Pro vkládání musíme vytvořit dvě metody, jednu pro vložení uzlu
na začátek a druhou pro vložení uzlu na konec. Obě metody si budou dost podobné
a nebyl by problém z nich vytvořit jenom jednu metodu, ale pro přehlednost
si vytvoříme metody dvě.
Nejprve metoda pro vložení
poduzlu nazačátek:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
function _addTree_h( $name, $left, $parent ){ $insert = "INSERT INTO " . $this->table_name . "(traverz_name, traverz_parent, traverz_left, traverz_right, lang) VALUES( '" . trim( htmlspecialchars($name) ) . "', '" . intval( $parent ) . "', '" . ( intval( $left ) + 1 ) . "', '" . ( intval( $left ) + 2 ) . "', '" . $_SESSION['lang_prefix'] . "', );"; mysql_query($insert, $this->link); if( mysql_affected_rows($this->link) == 1 ) return (self::_update_tree(mysql_insert_id(), $left) == 1 ? 1 : 0 ); else return 0; } |
V SQL dotazu vidíme
vkládaná data. Hodnota parent je hodnota, kterou jsme zjistili metodou
_select_parent a předali si ji jako parametr. Stejně tak jsme si předali
hodnotu názvu. Hodnota levého indexu bude předaná hodnota $left + 1, protože
index $left je hodnota levého indexu uzlu, za který vkládáme. Hodnota pravého
uzlu bude o jednu větší než hodnota levého uzlu, protože tento uzel neobsahuje
žádné poduzly.
Důležitá je zde funkce _update_tree,
do které si předáme dva parametry – ID vloženého prvku a levý index prvku, za
který vkládáme. Metoda upraví tabulku tak, že přečísluje všechny indexy uzlů za
uzlem za který vkládáme s výjimkou uzlu, který jsme nyní uložili, protože
zde jsou indexy již nastaveny správně.
Po vysvětlení se metoda zdá
možná složitá ale je velmi jednoduchá:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
function _update_tree($id, $left){ $sql[] = "UPDATE " . $this->table_name . " SET traverz_left = (traverz_left + 2) WHERE ( traverz_left > '" . $left . "') AND id_traverz != '" . $id . "' AND lang = '" . $_SESSION['lang_prefix'] . "'"; $sql[] = "UPDATE " . $this->table_name . " SET traverz_right = (traverz_right + 2) WHERE ( traverz_right > '" . ($left - 1) . "') AND id_traverz != '" . $id . "' AND lang = '" . $_SESSION['lang_prefix'] . "'"; foreach($sql as $value){ mysql_query($value, $this->link); if(mysql_affected_rows($this->link) == 0 ) return 0; } } |
Po zavolání metody se
provedou dva SQL dotazy. Jeden upraví pravý a druhý levý index uzlů.
Nyní už vytvoříme pouze
metodu pro vložení uzlu na konec, která je vlastně stejná jako metoda pro
vložení, jenom s drobnými úpravami:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
function _addTree_e( $name, $left, $parent ){ $insert = "INSERT INTO " . $this->table_name . "(traverz_name, traverz_parent, traverz_left, traverz_right, lang) VALUES( '" . trim( htmlspecialchars( $name ) ) . "', '" . intval( $parent ) . "', '" . intval( $this->traverz_right ) . "', '" . ( intval( $this->traverz_right ) + 1 ) . "', '" . $_SESSION['lang_prefix'] . "', );"; mysql_query($insert, $this->link); if( mysql_affected_rows($this->link) == 1 ) return (self::_update_tree(mysql_insert_id(), $this->traverz_right) == 1 ? 1 : 0 ); else return 0; } |
Nyní máme hotový základ celé
třídy. Můžeme ukládat nové uzly. V příštím článku se podíváme na to, jak můžeme
uzly mazat a přesouvat.
Všechno co je nyní hotovo si
můžete ještě jednou prohlídnout:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
class traverz extends connect{ public $traverz_right = NULL; public $id_traverz = NULL; public $parametrs = array(); public $ids = array(); public $table = NULL; function __construct( $table_name ){ $this->table_name = $table_name; parent::__construct(); self::_check_num_of_rows(); } function _check_num_of_rows(){ $select = "SELECT COUNT(*) FROM " . $this->table_name . " WHERE lang = '" . $_SESSION['lang_prefix'] . "'"; if( mysql_result( mysql_query( $select, $this->link ), 0, 0) == 0 ){ self::_insert_first(); return 0; } else{ return 0; } } //Insert HOME into Traverz_table function _insert_first(){ $insert = "INSERT INTO " . $this->table_name . "( traverz_name, traverz_parent, traverz_left, traverz_right, lang ) VALUES( 'HOME', '0', '1', '2', '" . $_SESSION['lang_prefix'] . "', 'home' )"; mysql_query($insert, $this->link); return ( mysql_affected_rows($this->link) == 1 ? 1 : 0); } function _update_tree($id, $left){ $sql[] = "UPDATE " . $this->table_name . " SET traverz_left = (traverz_left + 2) WHERE ( traverz_left > '" . $left . "') AND id_traverz != '" . $id . "' AND lang = '" . $_SESSION['lang_prefix'] . "'"; $sql[] = "UPDATE " . $this->table_name . " SET traverz_right = (traverz_right + 2) WHERE ( traverz_right > '" . ($left - 1) . "') AND id_traverz != '" . $id . "' AND lang = '" . $_SESSION['lang_prefix'] . "'"; foreach($sql as $value){ mysql_query($value, $this->link); if(mysql_affected_rows($this->link) == 0 ) return 0; } } function select_parent($left, $info = 0){ $select = "SELECT traverz_parent, traverz_right, id_traverz FROM " . $this->table_name . " WHERE traverz_left = '" . $left . "' AND lang = '" . $_SESSION['lang_prefix'] . "' LIMIT 1;"; $data = mysql_query($select, $this->link); if( $info == 1 ){ $this->traverz_right = @mysql_result($data, 0, 1); $this->id_traverz = @mysql_result( $data, 0, 2 ); } return ( @mysql_result($data, 0, 0) + 1 ); } function _setup_position( $position ){ switch( strtolower( $position ) ){ case 'h' : return 0; break; case 'e' : return 1; break; default: return 0; } } function addTree ( $name, $left, $position = 0 ){ if( gettype( $position ) == 'string' ) $position = self::_setup_position( $position ); $position = abs( intval( $position) ); if( $position > 2 ) return 0; $parent = self::select_parent($left, 1); switch( $position ){ case 0 : { if( self::_addTree_h( $name, $left, $parent ) == 1 ) return 1; else return 0; break; } case 1 :{ if( self::_addTree_e( $name, $left, $parent, ( $this->traverz_right - 1 ) ) == 1 ) return 1; else return 0; break; } } return 1; } function _addTree_h( $name, $left, $parent ){ $insert = "INSERT INTO " . $this->table_name . "( traverz_name, traverz_parent, traverz_left, traverz_right, lang ) VALUES( '" . trim( htmlspecialchars($name) ) . "', '" . intval( $parent ) . "', '" . ( intval( $left ) + 1 ) . "', '" . ( intval( $left ) + 2 ) . "', '" . $_SESSION['lang_prefix'] . "', );"; mysql_query($insert, $this->link); if( mysql_affected_rows($this->link) == 1 ) return (self::_update_tree(mysql_insert_id(), $left) == 1 ? 1 : 0 ); else return 0; } function _addTree_e( $name, $left, $parent ){ $insert = "INSERT INTO " . $this->table_name . "(traverz_name, traverz_parent, traverz_left, traverz_right, lang) VALUES( '" . trim( htmlspecialchars( $name ) ) . "', '" . intval( $parent ) . "', '" . intval( $this->traverz_right ) . "', '" . ( intval( $this->traverz_right ) + 1 ) . "', '" . $_SESSION['lang_prefix'] . "', );"; mysql_query($insert, $this->link); if( mysql_affected_rows($this->link) == 1 ) return (self::_update_tree(mysql_insert_id(), $this->traverz_right) == 1 ? 1 : 0 ); else return 0; } } |
"Můžeme například používat různé rekurzivní způsoby, jež jsou většinou při větší velikosti stromu velice pomalé neboť pro získání celého stromu bude zapotřebí minimálně tolik SQL dotazů, kolik je úrovní rozvětvení"
To je trosku chabe tvrzeni, nikomu nebrani si nechat cely strom vyhodit do pole v uritem poradi ktere se mu pak bude velice pekne rekurzivne spravovat. Tzn. na takovyto vypis staci jediny dotaz a pote uz si strom jen chytre predzpracovat a pak jen rekurzi projit.
Dobra. Samozrejme v pripade ze se jedna o maly strom, ktery obsahuje nekolik desitek zaznamu tak to neni problem, ovsem pokud bychom meli velky strom, o nekolika tisicich zaznamu, tak potom zase nebude moc efektivni nacitat z databaze vzdy takovy pocet dat, ktery si budeme radit dle nejakeho algoritmu do pole, abychom z nej potom dostali jenom urcitou vetev.
Samozrejme mate pravdu a jde to udelat i jednim SQL dotazem, ale zase na ukor neceho dalsiho.
Bylo by hezké vysvětlit třídu connect. Dokud jsem si nevygooglil tvůj komentář na http://php.vrana.cz/pripojeni-k-dat abazi.php tak mi nedocházelo odkud se tam ta třída bere a jak by asi mohla vypadat. Jinak, fajn článek(y)
Třída connect slouží pouze pro připojení k databázi.
Ve třídě vznikde proměnná (vlastnost) $link, která je typu public. Tato proměnná nás zajímá.
class connect
{
public $user;
public $hostitel;
public $pass;
public $databaze;
public $link;
//konstruktor
public function __construct()
{
require "data.php";
//do promenych se priradi hodnoty z data.txt
$this -> user = $user;
$this -> pass = $pass;
$this -> hostitel = $hostitel;
$this -> databaze = $databaze;
self ::connect();
}
public function connect()
{
//fu nkce pro pripojeni k databazi
if (!($this->link = mysql_connect($this- >hostitel, $this->user, $this->pass))) {
die ("spojeni s databazi selhalo");
}
//byber databaze
if(!mysql _select_db("$this->d atabaze", $this->link))
die ("vyber databaze selhal");
mysql_qu ery("SET CHARACTER SET utf8 ", $this->link);
}
Stejně tak si můžete vytvořit připojení jakýmkoli jiným způsobem a předat identifikátor do konstruktoru třeba jenom jako referenci.
Data se načítají z externího souboru data.php, ketrý má následující strukturu:
<?php
$hostitel = "localhost";
$user = "root";
$pass = "root";
$databaze = "minirs";
?>
Tak jsem se rozhodl použít tuto strukturu pro univerzální diskusi pro svůj web. Můžu se ještě zeptat, polužíváš ji v těchto komentářích, nebo tu to běží na něčem jiném?
A jestli je nejlepší, když mám u článků komentáře, tak dát jednoho rodiče (1,max) a ke každéme článku další prvek, který by byl rodičem všech komentářů k danému článku (a v ideálním případě by měl stejné ID jako článek, pro zjednodušení vyhledávání)?
Jestli by jsem ti mohl poradit, tak u komentaru traverzovani nepouzivej.
Myslim si ze pro komentare jsou mnohem jednoduzsi algoritmy.
Traverzovani je dle meho nazoru pro tuto vec az zbytecne slozite, protoze pri kazdem komentovani budes muset prepsat vsechny indexy.
Na tomto webu pouzivam traverzovani pro vytvoreni menu.
Pokud by jsi mel zajem, muzu ti zde zverejnit, jak mam resene komentare.
Zdálo se mi to jako ideální řešení. I když přepis 1000 indexů by asi nebyl nejrychlejší, jak si to teď tak uvědomuji. Na menu mi to přijde jako pěkná věc. Také asi v budoucnu využuji.
Za zveřejnění nějakého nápadu na komentáře bych byl vděčný. pokouším se kromě komentářů udělat i návštěvní knihu, ale žádné "čístší" řešení se mi nepovedlo vymyslet (jen se dvěma sloupci na řazení a to se nedalo nastránkovat, také jsem chtěl více úrovní odpovědí a jednoduchý výběr z DB).
Ahoj.
Tak jsem se rozhodl použít tuto strukturu ale nedaří se mi vypsat celé menu do seznamu
<ul><li>…
Nevíte někdo jak to udělat?
muzes tedy napsat prosim jak mas resene ty komentare? popripade algoritmus ktery je podle tebe pro komentare idealni. dekuji.
jinak tohle je opravdu skvely clanek
U metody _check_num_of_rows(){ je chybka, 2x se tam opakuje # else{
# return 0;
# }
Ahoj, jsem lamka co toho o php moc nevi, toto traverzovani se zda efektivni metoda, nicmene ten kod je daleko nad moje php schopnosti, nemate nekdo tento script funkcni, pochybuju ze bych to dal nekdy dohromady…
diky predem za ochotu