h1. Cautari ortogonale: Structuri de date si aplicatii

(Categoria _Structuri de date_, autor _Cosmin Negruseri_)

(Categoria _Structuri de date_, autor _Cosmin Negruseri_)
 
h2. Introducere
 
In acest articol voi discuta despre cateva structuri de date folositoare pentru probleme de geometrie, in special pentru probleme ortogonale. **Problema de baza** ce va fi rezolvata suna in felul urmator: avem n puncte in plan si pentru un anumit dreptunghi ne intereseaza numarul de puncte din acel dreptunghi, sau diverse alte operatii pentru punctele din interiorul sau, cum ar fi suma cheilor punctelor, minimul sau maximul cheilor (daca punctele au asociate cate o cheie). Folosind arbori de intervale putem rezolva aceasta problema, dar vreau sa exemplific ce alte variante mai avem si avantajele lor, precum si aplicatii practice pentru cautarea pe domenii ortogonale. In general, abordarile prezentate mai jos se pot extinde de la cazul unidimensional sau bidimensional, cu usurinta, la cazuri N-dimensionale.
Pentru a intelege cat mai bine ideile si structurile de date prezentate mai departe recomand citirea articolelor [1] si [2].
Structurile prezentate sunt in general statice, adica formam intai structura si apoi rezolvam problema. Structurile de date se pot modifica pentru a suporta inserari si stergeri de puncte, devenind dinamice, dar astfel implementarea se complica. Pentru a simula dinamismul putem insera toate datele de la inceput si sa mai avem un camp boolean in care marcam cu true daca data a fost logic inserata si cu false daca data din nodul respectiv nu a fost inca logic inserata. Aceasta pastreaza complexitatea operatiilor pe structura si ne ajuta in echilibrarea structurilor pentru o eficienta buna a operatiilor.
 
h2. QuadTree
 
_QuadTree_ este o structura care organizeaza informatii pentru date multidimensionale, fiind folosita in cartografie, procesarea imaginilor, grafica pe calculator etc. Structura este un arbore ce reprezinta o zona din spatiul N-dimensional (in cazul in care suntem noi interesati, N=2), fiecare nod al arborelui pastreaza o informatie pentru o zona din spatiu, iar nodul are 2^N^ fii care reprezinta fiecare o zona de 2^N^ ori mai mica decat zona parintelui. Zonele fiilor sunt **disjuncte**, iar reuniunea lor formeaza zona parintelui.
 
Pentru un _QuadTree_ radacina reprezinta un patrat, iar fii reprezinta cele patru patrate **disjuncte si congruente** in care se poate imparti patratul initial. Din cate am prezentat pana acum, un _QuadTree_ este infinit, dar pe noi ne intereseaza de obicei intervale foarte mici din plan, si atunci putem sa folosim numai cateva nivele din _QuadTree_. Cateodata unele noduri din _QuadTree_ nu contin insa nici o informatie si atunci nu avem nevoie sa le folosim pentru ca am folosi memorie in plus.
 
In +problema 3+ a zilei 2 a **Balcaniadei de Informatica** din 1997, se da un _QuadTree_ care reprezinta o imagine colorata alb-negru, de dimensiune 2^N^ * 2^N^. Daca patratul reprezentat de informatia dintr-un nod al arborelui era de aceeasi culoare, in nod se pastra informatia culorii si nodul nu avea nici un fiu, altfel nodul avea starea indecisa/nedeterminata si avea patru fii.