Algorytm usuwania gałęzi drzewa - Nowe podejscie, na kolejce FIFO Opcje

[Black-Berry]

Ostatnio siedziałem sporo nad utworzeniem struktury kategorii na stronie. Istnieje fajna metoda opisana tutaj - klik. Osobiście ma dla mnie to taką wadę, że nie mamy swobody przy przenoszeniu lub zamienianiu dowolnych gałęzi w drzewie. W mojej metodzie wykorzystuję uproszczoną strukturę bazy.

[SQL] pobierz, plaintext 
+--------+--------+
|   id   | parent |
+--------+--------+
[SQL] pobierz, plaintext 

Ma to spore zalety. Najtrudniejsze jest jednak np. Usuwanie całej gałęzi. Moze się komuś przyda. Proszę też o jakieś komentarze. Dzięki kolejce FIFO pozbyłem się rekurencji. Ograniczyłem też ilość zapytań do bazy do liczby węzłów zawierających dzieci. Tak więc jeśli mamy np kategorie które zawierają dużą ilość artykułów ( Zazwyczaj tak jest, że mamy o wiele mniej kategorii niż artykułów ) to jest to całkiem wydajna metoda. Udało mi się zaimplementować taki algorytm: (Testowałem i działa)

[PHP] pobierz, plaintext 
<?php
	$node_id = 5; //wybieramy jakiś węzeł
	$parents= new numeric_fifo_queue; //nowa kolejka FIFO
	$parents->push( $node_id ); //wpisujemy id wezla który chcemy usunąć
	while( !$parents->is_empty() )
	{
		while ($row = mysql_fetch_array("SELECT * FROM tree WHERE parent=".$parents->pop(), MYSQL_ASSOC))
		{
			$parents->push( $row["id"] );
			mysql_query ( "DELETE FROM tree WHERE id = ".$row["id"] );
		}
	}
	//na koniec usuwamy węzeł o id = $node_id;
	mysql_query ( "DELETE FROM tree WHERE id = ".$node_id );
?>
[PHP] pobierz, plaintext 

Można to jeszcze udoskonalić tak aby pozbyć się końcówki. Wystarczy w zapytaniu do bazy wstawić jedno 'or'. Nie będzie wtedy trzeba pamiętać o 2 różnych miejscach usuwania wpisu:

[SQL] pobierz, plaintext 
zapytanie:
	"SELECT * FROM tree WHERE parent=".$parents->pop()
zamieniamy na:
	"SELECT * FROM tree WHERE parent=".$parents->pop()." OR id=".$node_id
i już możemy usunąć ostatnie 'DELETE' query;
[SQL] pobierz, plaintext 

Ten post edytował Black-Berry 9.02.2008, 12:07:00

[cinekz]

Może byś pokazał te klasę najpierw? A tak ogólnie to ekstra.

[Black-Berry]

Nie mam klasy do drzewa. To tylko kod który można sobie dostosować. Jeśli jednak chodzi o klasę kolejki FIFO to standard dlatego nie zamieszczałem jej tutaj. Ale skoro prosisz to proszę:

[PHP] pobierz, plaintext 
<?php
	class numeric_fifo_queue
	{
		var
		$arrQueue,	   // Array of queue items
		$intBegin,	   // Begin of queue - head
		$intEnd,		 // End of queue - tail
		$intArraySize,   // Size of array
		$intCurrentSize; // Current size of array
 
		function numeric_fifo_queue( $intSize = 99999 )
		{
			$this->arrQueue	 = Array();
			$this->intArraySize = $intSize;
			$this->arrCurrentSize = 0;
			$this->intBegin = 0;
			$this->intEnd = $this->intArraySize - 1;
		}
 
		function push( $objQueueItem  )
		{
			if ( $this->intCurrentSize >= $this->intArraySize ) return false;
			if ( $this->intEnd == $this->intArraySize - 1 ){
				$this->intEnd = 0;
			}else{
				$this->intEnd++;
			}
			$this->arrQueue[ $this->intEnd ] = $objQueueItem;
			$this->intCurrentSize++;
			return true;
		}
 
		function pop()
		{
			if ( $this->is_empty() ) return false;
			$objItem = $this->arrQueue[$this->intBegin];
			if ( $this->intBegin == $this->intArraySize - 1 ){
				$this->intBegin = 0;
			}else{
				$this->intBegin++;
			}
			$this->intCurrentSize--;
			return $objItem;
		}
 
		function is_empty()
		{
			return ( $this->intCurrentSize == 0 ? true : false );
		}
	}
?>
[PHP] pobierz, plaintext 

Nie ukrywam, że klasy tej nie pisałem sam ale ściągnąłem z neta. W przyszłości postaram się jeszcze zamieścić moje metody do tworzenia rozwijanego menu z tego drzewa ale to już bajka bo usuwanie gałęzi jest najtrudniejsze jeśli nie stosujemy w bazie pól lft, right (patrz artykuł z 1 postu). Usuwanie węzła przy takiej strukturze bazy to kwestia usunięcia rekordu, a dodawanie polega na podaniu 'parenta' więc nie ma sensu o tym pisać. Pozdrawiam i czekam na dalsze opinie.