www.www.zaachi.com »  Blog/Php  »  Traverzování kolem stromu #1

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ů.

 

Reklama
Pokud mě chcete podpořit a jste milovník jedné stopy, navštivte můj projekt: MotoArena.cz

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:

Traverzování kolem stromu

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: 


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:


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:


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í:

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): 



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): 

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: 

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: 

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á: 

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: 

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: 

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;
    }
}

 

 


linkuj topclanky
Komentáře (12)

Autor: Zaachi
Publikováno: 18.7.2009 19:26:53


Mohlo by vás zajímat:
Traverzování kolem stromu #2
Traverzování kolem stromu #3
Traverzování kolem stromu #4 (operace nad stromem)
TOPLIST.cz
rss coments img img img