Rekurzija - kako napraviti tree

[ bert @ 13.04.2005. 06:24 ] @

Pozdrav,

interesira me šta krivo radim...

imam tablicu (mysql)

| id | parent_id | naziv

želim dobiti tree od tih podataka

moja funkcija izgleda ovako - ulazi mi u beskonačnu petlju

Code:

function cat_tree($cid, $tree = "", $index = 0)
{
    global $db;

    $sql = "
        SELECT
            `id`,
            `naziv`,
        FROM
            `kategorije`
        WHERE
                         `parent_id` = ". $cid ."
    ";

    $result = $db->Execute("$sql");

    while ($row = $result->FetchNextObject())
    {
        $tree[$index][] = array('id' => $row->ID, 'naziv' => $row->NAZIV);
        cat_tree($row->ID, $tree, ($index+1));
    }

    return $tree;
}
cat_tree(0);

hvala

[ The Sekula @ 13.04.2005. 08:15 ] @

Proveri kakvi su ti podaci, da nemas kruznu referencu.

Generalno, svaki kod gde imas rekurzivne pozive morao bi da ima detekciju ili prevenciju mrtve petlje. Ti u ovom slucaju, posto imas neke podatke u bazi, ne mozes biti siguran da ce oni uvek predstavljati korektno stablo.

Resenje je da vodis evidenciju o cvorovima koji su vec obidjeni (u php-u najjednostavnije u jednom nizu). U slucaju da detektujes da obilazis cvor koji se vec obisao, prekines obilazak i ispises "kulturnu" poruku o gresci.

[ Goran Rakić @ 13.04.2005. 13:32 ] @

Kao sto je receno, pre nego sto ga ubacis u niz i napravis novi poziv funkcije proveri da li se takav alement (takav niz) vec nalazi u tvom nizu. Recimo funkcija in_array...

Isto tako ne bi bilo lose da imas neku kontrolu Index-a, pa ako dodje do neke MAXINDEX konstante ispises poruku o gresci. Ili jos bolje za Web okruzenje, da ubelezis vreme poziva prve funkcije (u neku globalnu varijablu) i onda da kontrolises u svakom 10-tom pozivu (imas index za brojac) da li je vreme rada duze od par sekundi i ako jeste prijavis gresku/prikazes do sada generisane podatke sa linkovima na dublje delove drveta...

[ bert @ 13.04.2005. 20:12 ] @

Mudro zborite!

Hvala vam!

[ LazyDog @ 14.04.2005. 03:02 ] @

Moram da pitam, da li ce ovakav pristup zauzeti mnogo resursa, Zbog ovog konstantnog slanja upita?

Video sam negde komplikovanije resenje koje zauzima mnogo manje resursa. Mogu da ga potrazim.

pozdrav

[ bert @ 14.04.2005. 08:39 ] @

Majstore ak ti ne bi bio bad bio bi ti jako zahvalan.

[ The Sekula @ 14.04.2005. 08:49 ] @

Citat:

LazyDog: Moram da pitam, da li ce ovakav pristup zauzeti mnogo resursa, Zbog ovog konstantnog slanja upita?

Nije srecno resenje u svakom slucaju.

Jedna od mogucih optimizacija bi bila da se u jednom upitu dohvate redom sve veze, pa da se onda to "prepakuje" u strukuturu kakva vec odgovara za dalje procesiranje. Sad zavisi da li ce se uvek dohvatati celo stablo, ili mozda samo jedan mali njegov deo.

Prema nekom mom iskustvu, za pamcenje iole vecih stabala u relacionoj bazi, i za njihovo efikasno dohvatanje, neophodno je da svaki cvor pamti svoju putanju do root-a, u vidu jednog varchar polja.

Ideja je jednostavna, ako recimo imas putanju do root-a sledecu (gde su cetvorocifreni brojevi id-evi cvorova i to id-evi fiksne duzine)

0001|0002|0005|0007

Onda svi cvorovi podstabla tog cvora imaju taj prefiks, recimo

0001|0002|0005|0007|0008
0001|0002|0005|0007|0009
i sl.

I onda ih mozes dohvatati u jednom upitu.

Postoje dve male mane ovog pristupa. Jedna je da moras imati ogranicenje brojeva cvorova u stablu. Nebitno da li je to 10, 100 ili 100000, ali zbog fiksne duzine id-eva ogranicenje mora postojati.

Druga mana je da prilikom promene strukture stabla (dodavanje cvorova, brisanje cvorova, premestanje podstabala) moras lepo osmisliti upit koji ce azurirati sve putanje u cvorovima koji su "pogodjeni" to promenom. Nije komplikovano, ali je, da kazem, pipavo.

[ noviKorisnik @ 14.04.2005. 08:54 ] @

modified preorder tree traversal algorithm

[ LazyDog @ 14.04.2005. 11:31 ] @

Da, to je to. Nazalost komplikovanije je, ali je i manje zahtevno resursa.

[ afwt @ 14.04.2005. 13:11 ] @

Nije uopste komplikovanije. Kad shvatish koncepciju, dobijesh dosta pogodnosti od tog modela.
A mozesh i da ih kombinujesh. ;-)
Postoji rad na tu temu, pisao ga Joe Celco, moze se skinuti.