Arbori de intervale 2D

[tmac]

Se dau n puncte in plan, fiecare punct avand o valoare atasata. Vreau sa determin pentru un dreptunghi dat min/max punctelor din el folosind arbori de intervale 2D. problema e ca reprezentarea aia din ginfo nu ma ajuta deloc (lista sortata dupa y in fiecare nod). de asta va cer ajutoru !

[•Cosmin]

In loc de lista poti folosi un avl sau un arbore de intervale 1d .

[tmac]

intebari :

1. lucrez cu coordonate in arborele acela (), sau cu nr de puncte ?
2. pai atunci o sa am un arbore de intervale de 2*n-1 dimensiune in fiecare nod, deci (2*n-1) * (2*n-1) ? si cum pot sa le construiesc eficient ?

[•Cosmin]

Pai daca ai avea o lista in noduri de ce nu trebuie sa fie de lungime 2*n - 1 ? Tot de aia poti sa bagi un avl de aceiasi lungime cu cea a listei. E destul de nasol sa faci un arbore de intervale 2d la care se insereaza puncte dinamic, si de obicei solutia e sa iei toate punctele care se insereaza in arbore, si faci arborele de intervale, dar informatia de query nu o actualizezi. Deci structura contine toate punctele, dar nu contine informatie deloc. Acum in loc de avl-uri poti folosi arbori statici, de exemplu o lista pe care o sortezi si o pui pe un arbore gen heap sau arbore de intervale. De fiecare data cand in mod normal ai adauga un nod la structura practic numai adaugi informatia asociata nodului. Nu stiu cat de clar am explicat ...

[tmac]

sa spun ceam facut:

1. sortez lista dupa coord x
2. creez un arbore de intervale 1 .. n (nr de puncte), punctele fiind luate dupa x. In fiecare nod am 2 vectori (int * alocati dinamic)  unul cu lista de indici de pcte sortate dupa y si unul cu arborele de intervale a punctelor dupa y. Creeare o fac prin interclasarea listelor fiilor si setarea arborilor dupa y cu -INF , +INF, dupa caz.
3. am nevoie de lista in fiecare nod ca sa caut binar indicii pe carei voi folosi sa caut in arborele de intervale dupa y din nodul ala.

e bine sau nu ? alte idei mai bune de implementare aveti ?

[cristi8]

eu am implementat odata un arbore de intervale 2D, dar nu se comporta prea bine (era destul de lent).
era ceva asemanator cu QuadTree parca, numai ca mergea pe orice dreptunghi...
aveai primul nod pentru tot dreptunghiul, dupa aia il imparteai in 4 parti, deci aveai 4 fii (pozitii in vector: 4*pos, 4*pos+1, 4*pos+2, 4*pos+3, care retineau ce te intereseaza pe dreptunghiurile mici). si tot asa pana nodul era format dintr-o singura pozitie din dreptungi.

[•Cosmin]

Ala nu e arbore de intervale ...

[tmac]

e inspirat din versiunea din ginfo prezentata de prof dana lica (pt numarat punctele dintrun dreptunghi dat). la acela ma refeream arbori de intervale avea titlul ... ce sa zic acuma nush. poate ma lamuresti ca sunt pe un drum gresit ? 

[•Cosmin]

Ma refeream ca ce zicea cristi nu e arbore de intervale ... ce faci tu e ok, atat ca in loc de lista de elemente tii un arbore echilibrat, fiecare nod al arborelui echilibrat va avea un al doilea camp ce  pastreaza minimul dintre elementele continute in subarborele ce are ca radacina nodul curent.

[tmac]

am inteles. dar daca as avea memorie as putea face si ceva gen  arb[2*CMAX-1][2*CMAX], cmax fiind coordonata maxima, adica nu puncte ci toate coordonatele ? este mult mai simplu evident, dar si mananca memorie.