h2. Arbori de intervale

p<>. Un arbore de intervale este un arbore binar in care fiecare nod poate avea asociata o structura auxiliara(anumite informatii). Dandu-se doua numere intregi $st$ si $dr$, cu $st<dr$, atunci arborele de intervale T(st,dr) se construieste recursiv astfel:

Un arbore de intervale este un arbore binar in care fiecare nod poate avea asociata o structura auxiliara(anumite informatii). Dandu-se doua numere intregi $st$ si $dr$, cu $st<dr$, atunci arborele de intervale T(st,dr) se construieste recursiv astfel:

* consideram radacina $nod$ avand asociat intervalul $[st,dr]$
* daca $st<dr$ atunci vom avea asociat subarborele stang T(st,mij), respectiv subarborele drept T(mij+1,dr), unde $mij$ este mijlocul intervalului $[st,dr]$

p<>. Intervalul $[st,dr]$ asociat unui nod se numeste interval standard. Frunzele arborelui sunt considerate intervale elementare, ele avand lungimea $1$.

Intervalul $[st,dr]$ asociat unui nod se numeste interval standard. Frunzele arborelui sunt considerate intervale elementare, ele avand lungimea $1$.

h3. Proprietate:

p<>. 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 contine 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

p<>. Vom prezenta pseudocodul unei proceduri recursive care insereaza un interval $[a,b]$ intr-un arbore de intervale T(st,dr) cu radacina in nodul $nod$. Cea mai eficienta metoda de stocare in memorie a unui arbore de intervale este sub forma unui vector folosind aceeasi codificare a nodurilor ca si 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.

==code(c) |

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)

      actualizeaza structura auxiliara din nodul nod
==

      actualizeaz� structura auxiliara din nodul nod