Tablica w PHP ma jedną wadę: każdy nowy element dodawany jest zawsze na jej koniec bez względu na numer indeksu. Ulokowanie go gdzie indziej jest praktycznie niewykonalne bez dostępu do kodu źródłowego interpretera. Wystarczy spojrzeć sobie na taki prosty skrypt udowadniający:

<?php
	$x = array();
	$x[3] = 'a';
	$x[1] = 'b';
	$x[2] = 'c';
	$x[0] = 'd';
	
	foreach($x as $id => $value)
	{
		echo $id.': '.$value.'<br/>';
	}
?>

Istnieje grupa zagadnień, w których możliwość wstawienia elementu w dowolne miejsce listy jest bardzo pożądana. Przykładem jest drzewo, hierarchiczna struktura, gdzie każdy element posiada kilka rozgałęzień do elementów pochodnych. Wielu programistów implementuje ją czasem nieświadomie, czasem świadomie, po prostu jako zbiór zagnieżdżonych w sobie tablic. Jeżeli naprawdę nie potrzeba im więcej, jest OK, ale zazwyczaj tracą w ten sposób dużo funkcjonalności; wprawdzie mogłaby być ona zaimplementowana, lecz elegancja i jakość rozwiązania pozostawiałyby wiele do życzenia.

Tematem efektywnej implementacji drzewa w PHP zainteresowałem się stosunkowo niedawno, przy pracach nad opisywanymi jakiś czas temu w Dziennikach Sandboxami, które okazują się być niczym innym, jak wirtualnym systemem plików eliminującym konieczność wykonywania wielu powolnych operacji dyskowych, oferując w zamian możliwość uzyskania wielu danych bezpośrednio z pamięci operacyjnej. Powstało wtedy pytanie: która struktura może zagwarantować taki właśnie wzrost wydajności? Z oczywistych przyczyn chciałem, aby mój VFS automatycznie umieszczał nowe obiekty w swym katalogu w posortowanym zbiorze, dzięki czemu pobranie jego zawartości ograniczy się tylko do odczytania wszystkiego, bez uruchamiania żadnych funkcji sortujących. Wybór padł na specjalną odmianę drzew, zwaną drzewami binarnymi. Każdy węzeł może posiadać maksymalnie dwa podwęzły, przy czym istotne jest, który z nich jest prawy, a który lewy. Przyjąłem, że jeśli przejdziemy w lewo, przeskoczymy na kolejny plik w obrębie danego katalogu. Ruch w prawo oznaczał zejście do katalogu podrzędnego.

Teraz przyznajcie się sobie szczerze: ilu z was pomyślało, żeby drzewo takie złożyć z zagnieżdżonych tablic? Na praktycznym przykładzie pokażę, ile problemów sprawiłoby takie rozwiązanie:

1. Wstawienie nowego elementu do drzewa w dowolne miejsce oznaczałoby dla PHP mega-kopiowanie wszystkich węzłów podrzędnych.
2. Poruszanie się po drzewie bez funkcji rekurencyjnych i bez zabawy z referencjami jest w najlepszym wypadku bardzo trudne.
3. PHP nie posiada rekurencyjnego odpowiednika funkcji count().
4. Odnajdywanie elementu według jego indeksu - jeśli ten będzie przydzielany bez specjalnego ładu, pozostaje jedynie metoda brute-force.

Bardziej przystępny sposób polega na wykonaniu zwyczajnej listy, do której wrzucać będziemy małe, czteroelementowe tablice:

<?php
$drzewo[$indeks] = array(
  'd' => 'Dane',
  'p' => NULL, // indeks rodzica
  'l' => NULL, // indeks lewego elementu
  'p' => NULL //indeks prawego elementu
);

Zauważmy, kolejność elementu na naszej liście nie ma żadnego znaczenia dla kształtu drzewa. Ten określany jest poprzez zawarte w każdym węźle wskaźniki "l" i "r" zawierające numery indeksu odpowiednich węzłów. Indeksem elementu wewnątrz drzewa jest jego indeks na liście, dzięki czemu czas odnalezienia dowolnego elementu zależy już tylko i wyłącznie od wydajności algorytmów w samym sercu PHP:

<?php
		public function findNode($id)
		{
			if(!isset($this -> nodes[$id]))
			{
				return false;
			}
			return $this -> nodes[$id]['d'];
		} // end findNode();
?>

Dodawanie nowego elementu może wydawać się skomplikowane, ale wielkość kodu wynika tylko z mnogości czynników, które musimy uwzględnić:

1. Kiedy drzewo jest puste (nie ma w nim węzłów), wykonanie operacji INSERT spowoduje zawsze utworzenie korzenia.
2. Kiedy chcemy stworzyć nowy korzeń drzewa, musimy określić, do której gałęzi (lewej czy prawej) podpiąć to, co mieliśmy dotychczas
3. Jeśli podpinamy węzeł do już istniejącego, a dana gałąź jest wolna, po prostu podpinamy do niej nasz nowy węzeł.
4. Jeśli podpinamy węzeł do już istniejącego i dana gałąź jest zajęta, musimy dokonać "wpięcia" nowego węzła między dwa już istniejące.

<?php
		public function insertNode($data, $parent, $direction = NULL)
		{
			if($parent == BinaryTree::ROOT)
			{
				// Sytuacja 1
				if($this -> amount == 0)
				{
					$this -> nodes[0] = array(
						'd' => $data,
						'l' => NULL,
						'r' => NULL,
						'p' => NULL,
					);
					// Ustawiamy korzen drzewa
					$this -> root = 0;
					$this -> amount++;
				}
				else
				{
				// Sytuacja 2
					$this -> nodes[$this -> amount] = array(
						'd' => $data,
						'l' => ($direction == BinaryTree::LEFT ? $this -> root : NULL),
						'r' => ($direction == BinaryTree::RIGHT ? $this -> root : NULL),
						'p' => NULL,
					);
					$this -> nodes[$this -> root]['p'] = $this->amount;
					// Teraz ten wezel jest korzeniem
					$this -> root = $this -> amount;
					$this -> amount++;
				}
			}
			else
			{
				if(!isset($this -> nodes[$parent]))
				{
					return false;
				}
				// Sytuacja 3
				if(is_null($this -> nodes[$parent][$direction]))
				{
					$this -> nodes[$this -> amount] = array(
						'd' => $data,
						'l' => NULL,
						'r' => NULL,
						'p' => $parent
					);
					$this -> nodes[$parent][$direction] = $this -> amount;
					$this -> amount++;
				}
				else
				{
				// Sytuacja 4
					$this -> nodes[$this -> amount] = array(
						'd' => $data,
						'l' => NULL,
						'r' => NULL,
						'p' => $parent
					);
					// Tutaj wpinamy nasz nowy wezel
					// miedzy juz istniejace
					$oldChild = $this -> nodes[$parent][$direction];
					$this -> nodes[$parent][$direction] = $this -> amount;
					$this -> nodes[$oldChild]['p'] = $this -> amount;
					$this -> nodes[$this -> amount][$direction] = $oldChild;					
					$this -> amount++;
				}			
			}
			// To jest ID nowego wezla
			return $this->amount-1;
		} // end insertNode();
?>

Jest to fragment kodu źródłowego klasy, którą napisałem do obsługi drzewa binarnego. Pole amount pełni w nim dwa zadania. Po pierwsze, określa ilość znajdujących się aktualnie w drzewie węzłów. Po drugie, w trakcie dodawania węzła tymczasowo reprezentuje jego ID (wynika to z faktu składowania węzłów w zwykłej liście i pole to pokazuje wtedy indeks ostatnio dodanego elementu, dopóki po wykonaniu wszystkich duperszmitów nie zwiększymy go o 1, z powrotem wracając do funkcji licznika).

Drzewo binarne w takiej postaci bardzo ładnie poddaje się wszelkim zabiegom zarządzania. Znalezienie ścieżki od dowolnego węzła do korzenia czy implementacja przechodzenia przez drzewo metodą np. preorder nie stanowią wielkich trudności. Kod jest bardzo zwięzły i czytelny, a ponadto daje dostęp do kilku interesujących rozwiązań. Podobną sztuczkę z "własnym" indeksowaniem kolejności można też wykorzystać do stworzenia tablic, w których da się wpływać na kolejność.

Powrót

Na Zyxist.com panuje swoboda wyrażania opinii oraz krytyki pod dowolnym adresem. Jedyny warunek: musi być ona kulturalna i rzeczowa. Na chamstwo, prostactwo lub jawne obrażanie kogokolwiek nie ma tu miejsca i takie komentarze są bardzo szybko usuwane. Jeśli zamierzasz polemizować z treścią wpisu, wpierw uważnie ją przeczytaj.