Autor Zpráva
Petr Ká
Profil
Ahoj, už nějakou dobu přemýšlím nad takovou celkem zajímavou banalitou, která by se dala vyjádřit poměrně dobře na velkých strukturách, nicméně pokusím se popsat co nejjednodušeji příklad:

- Mám strukturu položek (založené na ID a PARENT_ID)
- Každá položka může mít neomezeně podpoložek
- potřebuji z tohoto vygenerovat strukturu tak, že každá položka může mít MAX 3 podpoložky a ty ostatní doplnit do dalšího podlevelu (pouze pokud tam bude "místo" => přednost mají přímé podpoložky - PARENT_ID)

Pro příklad (neřešme, co na těch obrázkách je, ale jak jsou data strukturována):

Mám toto (každá položka může mít neomezeně podpoložek):


A potřebuji toto (každá položka může mít MAX 3 podpoložky, pokud má víc, doplní se do "children" větve zas do limitu 3, pokud jsou už v "children" větvi 3 přímé podpoložky, fronta jde do další úrovně níže):


Volání by mělo být nejlépe rekurzivně


Ještě dodám, že mi je jedno z jakého array by se to generovalo.

Buď z "plochého" nebo zanořeného :)

Díky!
Virtus
Profil
Zdravím,

Petr Ká:
Mám strukturu položek (založené na ID a PARENT_ID)
podle prvního obrázku a této citované věty to vypadá, že aktuálně tedy máte Hierarchicko síťový model (logicky organizovanou bázi dat), a podle druhého obrázku z této struktury chcete udělat ,,něco" naprosto neorganizovaného, osobně mi to nedává moc smysl a rád bych se tedy zeptal na co konkrétně toto potřebujete? Ideální by bylo přiložit dva podobné obrázky s konkrétními daty, na které to chcete/potřebujete aplikovat.

Ps: Pokud někdo jiný pochopil co potřebujete a napíše sem očekávanou odpověď považujte moje požadavky/přípomínky za bezpředmětné.
mimochodec
Profil
Petr Ká:
Já nebudu pátrat, k čemu by to bylo dobré. Chápu, jak má vypadat výstup. Ale nikde nepopisuješ, podle jakého klíče se mají položky načítat na vstupu.
Připadá mi, že tě vazba rodič-potomek vůbec nezajímá a chceš ji opustit. Řešení vidím takové, že rekurzivně projdeš všechny vstupní položky, postupně je všechny nasypeš do jednorozměrného pole a to pak v cyklu přeložíš do nového pole ID, parent_ID, přičemž toho rodiče si pohlídáš nějakým pomocným polem s FIFO logikou.

// edit: teď vidím "přednost mají přímé podpoložky", pardon. Pokud se toto má zohlednit, trochu se to komplikuje. Jak moc, teď hned nevím, je moc hodin. Napíšu zítra.
Petr Ká
Profil
mimochodec:
Úplně přesně jsi mě pochopil, je potřebs FIFO logika a přednost mají přímé položky, pokud jich je méně než 3 doplní se ze zásobníku...


Virtus:
Psal jsem neřešme co na tech obrázkách je, ale jak je strukturovaný :)
mimochodec
Profil
Petr Ká:
přednost mají přímé položky

Pak se ale ty dva principy tlučou. Když v tom stromu na vstupu bude mít ten nejvyšší uzel pět potomků a každý z nich dalších pět, velmi rychle o tu vazbu potomek-rodič přijdeš a už od nějaké páté nebo šesté položky to odbavuješ prostě sériově.
Petr Ká
Profil
mimochodec
Ano, to je přesně cíl, takhle to potřebuju, proste aby se "přesahovací" položky doplnovali pouze tam, kam se vejdou, ale právě tou logikou FIFO (prvně jde ta, která je tam nejdéle v "cache")
Petr Ká
Profil
Ani nic že?
1Pupik1989
Profil
Já pořád nějak nepochopil, co se stane se dvěma potomky, co z listu zbydou. Ty se vloží jako potomek toho prvního, čili o úroveň níž?

Nebo první se prostě prohlásí za root node a další 3 za ním jsou potomci? Další tři budou potomci toho prvního ze třech a tak dále?
juriad
Profil
Zkoušel jsem to implementovat a také mi vůbec není jasné, co se má s přebývajícími položkami stát. Jediné, co je jasné, je, že mají být přesunuty někam do podstromu.
Ale, co když v podstromu již není místo? Viz přiklad jen s jednou hlavní položkou a pěti podřízenými.
Má se to snažit o nějaké vyvažovaní? Nebo prostě přebývající položky předávat rekurzivně prvnímu potomkovi? Tedy levá větev bude šíleně hluboká.

Nebuď tak líný a ukaž jak budou vypadat ty stromy na obrázku Navigation tree.
Možná by pomohlo vysvětlit, k čemu je to dobré. Pokud chceš vytvořit strom, který obsahuje v každém vrcholu maximálně tři potomky a zároveň je vyvážený, použij 2-3-strom, který má přesně takové vlastnosti.
1Pupik1989
Profil
Právě to přesně nechápu. Nebo to má být stylem postupného plnění? Jako zvolení root node a pak rovnoměrně naplňuji, dokud zásobník nebude prázdný? Takže kořen bude mít 3 sub potomky, pak se zase vyplní úroveň 2 a tak dále, dokud nebude hotovo?

Má ten strom definované nějaké pevné vazby?
Petr Ká
Profil
Ano, má se to vyplnovat do nejakeho limit (max 3 children node, max 5 children node...). Prednost mají přímé. Tzn. Pokud nejaky root bude mít pouze 2 prime, tak se treti (pri limitu 3) doplni z "cache". Doplni se nejstarsi zaznam a smaze z "cache" (array_shift???).

Vaše odpověď

Mohlo by se hodit


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: