Diferente pentru arbori-de-intervale intre reviziile #14 si #15

Nu exista diferente intre titluri.

Diferente intre continut:

* **INSEREAZA(y)** : insereaza capatul $y$
* **STERGE(y)** : sterge capatul $y$
* **INTEROGARE(y1,y2)** : intoarce numarul de capete cuprinse in intervalul $[y1, y2]$
* **INTEROGARE(y1,y2)** : intoarce numarul de capete cuprinse in intervalul $[y{~1~}, y{~2~}]$
p<>. Fie $MAXC$ valoarea maxima a coordonatelor capetelor de segmente. Folosind un vector pentru a implementa aceste operatiile descrise mai sus vom obtine o complexitate $O(1)$ pentru primele doua operatii si $O(MAXC)$ pentru cea de-a treia. Astfel, complexitatea  va fi $O(N*MAXC)$ in cazul cel mai defavorabil. Putem comprima spatiul $[0...MAXC]$ observand ca doar maxim N din valori din acest interval conteaza, si anume capetele segmentelor orizontale, astfel reducand a treia operatie la $O(N)$, dar algoritmul va avea complexitatea $O(N^2^)$, ceea ce nu aduce nici o imbunatatire fata de algoritmul trivial.
h3. Proprietate:
Un arbore de intervale este un arbore binar echilibrat(diferenta absoluta intre adancimea subarborelui stang si cea a subarborelui drept este cel mult 1). Astfel, adancimea unui arbore de intervale care conţine N intervale este $[log$~2~$N]+1$.
Un arbore de intervale este un arbore binar echilibrat(diferenta absoluta intre adancimea subarborelui stang si cea a subarborelui drept este cel mult 1). Astfel, adancimea unui arbore de intervale care conţine N intervale este $[log$~2~$N]+1$.
[poza]
h3. Actualizare unui interval intr-un arbore de intervale
Vom prezenta pseudocodul unei proceduri recursive care insereaza un interval [a,b] intr-un arbore de intervale T(st,dr) cu rădăcina in nodul nod. Cea mai eficienta metoda de stocare in memorie a unui arbore de intervale este sub forma unui vector folosind aceeaşi codificare a nodurilor ca la heap-uri.
Vom prezenta pseudocodul unei proceduri recursive care insereaza un interval [a,b] intr-un arbore de intervale T(st,dr) cu r�d�cina in nodul nod. Cea mai eficienta metoda de stocare in memorie a unui arbore de intervale este sub forma unui vector folosind aceea�i codificare a nodurilor ca la heap-uri.
procedura ACTUALIZARE(nod, st, dr, a, b)
   daca (a ≤ st) si (dr ≤ b) atunci
   daca (a � st) si (dr � b) atunci
      modifica structura auxiliara din nod
   altfel
      mij = (st+dr)/2
      daca (a <= mij) atunci ACTUALIZARE(2*nod, st, mij, a, b)
      daca (b > mij) atunci ACTUALIZARE(2*nod+1, mij+1, dr, a, b)
      actualizează structura auxiliara din nodul nod
      actualizeaz� structura auxiliara din nodul nod

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.