* **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