[PHP] Zamiana tablicy danych w drzewo

Mam następującą tablicę (ID, IDRodzica, Tekst):

t = array(
    (0, -1, 'Tekst0'),
    (1,  0, 'Tekst1'),
    (2,  1, 'Tekst2'),
    (3, -1, 'Tekst3'),
    (4,  3, 'Tekst4'),
    (5,  3, 'Tekst5')
);

To uproszczony przykład, ale elementów ma być około tysiąca. Potrzebuję znaleźć jak najszybszy (dlatego pytam właśnie!) algorytm, by przekształcić to na tablicę, jak poniżej. IDRodzica = -1 oznacza, że element jest głównym w drzewie (nie jest podelementem innego).

t = array(
    ( 0, -1, 'Tekst0', array((1, 0, 'Tekst1', array((2, 1, 'Tekst2', array())))) ),
    ( 3, -1, 'Tekst3', array((4, 3, 'Tekst4', array()), (5, 3, 'Tekst5',array())) )
);

Każdy element ma w ostatnim parametrze tablicę (choćby pustą) elementów, które mają ustawione IDRodzica, na jego ID. Tych podelementów może być wiele (kolejność dowolna) albo zero. Podelementy też moga posiadać podelementy.

Podkreślam, że zależy mi na szybkości. Przekształcenie potrzebuję, aby dane zaprezentować użytkownikowi graficznie właśnie w formie drzewa.

Obecnie kod jest rozbudowany (więc wklejał nie będę). Działa w taki sposób:

Bierze z tablicy wejściowej element i przegląda wyjściową tablicę elementów, ich tablice podelementów, itd (rekurencyjnie). Jeśli znajdzie element wyjściowy o ID równym jego IDRodzica, element wejściowy daje jako jego podelement. Jak przejdzie całą tablicę wyjściową i nie znajdzie, element dodaje jako nowy główny. (Nie istnieje element o ID = -1, więc taki element wejściowy zawse będzie dodany jako główny na wyjściu). Przy dużej liczbie elementów może to trwać bardzo długo.. za długo.

myślę że zrobiłbym to tak:

<?php

function krok_pierwszy($in, &$out){
  foreach($in as $w){
    $k = $w[0];
    $w[3] = Array();
    $out[$k] = $w;
  }
}

function krok_drugi($in, &$out){
  foreach($in as $k => $w){
    $out[$w[1]][3][$k] = $k;
  }
}

function krok_trzeci(&$in, $id, &$out){
  if(isset($in[$id]) && is_array($in[$id]))
    foreach($in[$id][3] as $k){
      $out[3][$k] = $in[$k];
      krok_trzeci($in, $k, $out[3][$k]);
    }
}

function przeksztalc(&$t){
  $w = Array();
  krok_pierwszy($t, $w);
  $t = $w;
  krok_drugi($t, $w);
  $t = Array();
  krok_trzeci($w, -1, $t);
  if(isset($t[3]))
    $t = $t[3];
}

?>

Przykład:

<pre><?php

$t = array(
    array(0, -1, 'Tekst0'),
    array(1,  0, 'Tekst1'),
    array(2,  1, 'Tekst2'),
    array(3, -1, 'Tekst3'),
    array(4,  3, 'Tekst4'),
    array(5,  3, 'Tekst5')
);

przeksztalc($t);
print_r($t);

?></pre>

chociaż dobrze tego nie przetestowałem ...
po prostu najpierw przekształca tablicę na tablicę o nazwie klucza jak pierwszy indeks (id), dodaje trzeci indeks gdzie będą dzieci, w drugim kroku szuka dzieci i przypisuje rodzicom do trzeciego indeksu w tablicy ich indeksy, w kroku trzecim "składa" tablicę w żądaną postać

Zrobłem taki miks z mojej procedurki oraz z powyższego kodu Adamo i śmiga aż miło. Dzięki. Powstały kod, jakby ktoś był ciekaw, wygląda tak:

function dodaj_array($element, &$list)
{
	foreach($list as $id => $item)
	{
		if ($item['ID'] == $element['Parent'])
		{
			$list[$id]['Items'][] = $element;
			return true;
		}
		else
		{
			if (dodaj_array($element, $list[$id]['Items']))
				return true;
		}
	}
	return false;
}

function przeksztalc(&$in)
{
	$result = array();
	foreach($in as $item)
	{
		$item['Items'] = array();
		if (!dodaj_array($item, $result))
			$result[] = $item;
	}
	$in = $result;
}

Jeśli ktoś widzi błąd, dajcie znać, a jeśli chodzi o samą odpowiedź na moje pytanie, temat uważam za zamknięty.