p=. !treapuri?Fig1.png!

p=. _*Figura 1*: Rotaţiile într-un arbore binar de căutare. Nodurile sunt reprezentate de cercuri iar subarborii de triunghiuri. Ambele operaţii de rotaţie menţin invariantul arborilor de căutare._

p=. _*Figura 1*: Rotaţiile într-un arbore binar de căutare. Nodurile sunt reprezentate de cercuri, iar subarborii de triunghiuri. Ambele operaţii de rotaţie menţin invariantul arborilor de căutare._

Să urmărim efectul rotaţiilor asupra structurii de heap a unui treap care respectă doar invariantul arborilor de căutare. Aşadar, să presupunem că arborele din figura din stânga are o structură de heap cu excepţia lui $w$ care are o prioritate mai mare decât a lui $z$. Dacă îl rotim pe $w$ spre dreapta vedem în figura din dreapta că structura de heap este satisfăcută. Din moment ce $A$ era un subarbore valid al lui $w$, va rămâne în continuare un subarbore valid. Cum $B$ şi $C$ se aflau iniţial sub $z$ ei aveau o prioritate mai mică decât a lui $z$, şi, astfel, după rotaţie ei sunt subarbori valizi pentru $z$. Este clar că $z$ este un fiu valid al lui $w$, prin presupunerea făcută iniţial.

Să urmărim efectul rotaţiilor asupra structurii de heap a unui treap care respectă doar invariantul arborilor de căutare. Aşadar, să presupunem că arborele din figura din stânga are o structură de heap cu excepţia lui $w$ care are o prioritate mai mare decât a lui $z$. Dacă îl rotim pe $w$ spre dreapta vedem în figura a doua că structura de heap este satisfăcută. Din moment ce $A$ era un subarbore valid al lui $w$, va rămâne în continuare un subarbore valid. Cum $B$ şi $C$ se aflau iniţial sub $z$ ei aveau o prioritate mai mică decât a lui $z$, şi, astfel, după rotaţie ei sunt subarbori valizi pentru $z$. Este clar că $z$ este un fiu valid al lui $w$, prin presupunerea făcută iniţial.

Să urmărim dacă invariantul arborilor de căutare se menţine în urma unei astfel de rotaţii.
* În arborele din figura din stânga avem inegalităţile următoare: $A < w < B; z < C; w, A, B < z$. Din acestea se obţine: $A < w < B < z < C$.
* În arborele din figura din dreapta avem inegalităţile următoare: $A < w; B < z < C; w < z, B, C$. Din acestea se obţine: $A < w < B < z < C$.

Cum am obţinut acelaşi şir de inegalităţi, am arătat existenţa invariantului arborilor de căutare.

Întrucât am obţinut acelaşi şir de inegalităţi, am arătat existenţa invariantului arborilor de căutare.

Reţineţi că această rotaţie împreună cu imaginea sa în oglindă, rotaţia spre stânga dacă urmărim desenul de la dreapta spre stânga, stau la baza algoritmilor de '$inserare$':treapuri#inserare şi '$ştergere$':treapuri#stergere!

Reţineţi că această rotaţie împreună cu imaginea sa în oglindă stau la baza algoritmilor de '$inserare$':treapuri#inserare şi '$ştergere$':treapuri#stergere!

Pentru o rotaţie sunt necesare doar câteva operaţii cu pointeri.
== code(cpp) |

void rotleft(T* &n)
{

void rotleft(T* &n) {

    T *t = n->left;
    n->left = t->right, t->right = n;

    n = t;

    n = t;

}

void rotright(T* &n)
{

void rotright(T* &n) {

    T *t = n->right;
    n->right = t->left, t->left = n;

    n = t;

    n = t;

}

void balance(T* &n)
{

void balance(T* &n) {

    if (n->left->priority > n->priority)
        rotleft(n);
    else if (n->right->priority > n->priority)

p=. _*Figura 2*: De la stânga la dreapta: inserarea nodului $z$. De la dreapta la stânga: ştergerea nodului $z$. Deoarece $z$ are prioritatea cea mai mare dintre toate nodurile, această inserare poate fi privită şi ca o operaţie de $split$. Subarborii stâng şi drept ai rădăcinii din ultima figură sunt chiar treapurile căutate: $T{~<~}$ şi $T{~>~}$. Invers, din $T{~<~}$ şi $T{~>~}$ se obţine, prin ştergerea rădăcinii, rezultatul operaţiei $join$._

Cheile formează un arbore de căutare, dar priorităţile pot să nu mai formeze un heap. Pentru a redobândi această proprietate, cât timp nodul de inserat, are prioritatea mai mare decât a părintelui său, se va executa o '$rotaţie$':treapuri#rotatii în $z$, o operaţie locală care scade nivelul lui $z$ cu $1$ şi creşte nivelul părintelui lui $z$ cu $1$, şi care menţine invariantul arborilor de căutare. Timpul de inserare al lui $z$ este proporţional cu adâncimea lui înainte de rotaţii - trebuie să coborâm după care să urcăm înapoi efectuând rotaţiile necesare.

Cheile formează un arbore de căutare, dar priorităţile pot să nu mai formeze un heap. Pentru a redobândi această proprietate, cât timp nodul de inserat, are prioritatea mai mare decât a părintelui său, se va executa o '$rotaţie$':treapuri#rotatii în $z$, o operaţie locală care scade nivelul lui $z$ cu $1$ şi creşte nivelul părintelui lui $z$ cu $1$, şi care menţine invariantul arborilor de căutare. Timpul de inserare al lui $z$ este proporţional cu adâncimea lui înainte de rotaţii - trebuie să coborâm, după care să urcăm înapoi efectuând rotaţiile necesare.

== code(cpp) |

void insert(T* &n, int key, int priority)
{

void insert(T* &n, int key, int priority) {

    if (n == nil) {
        n = new T(key, priority, nil, nil);
        return;
    }

    if (key <= n->key)

    if (key < n->key)

        insert(n->left, key, priority);
    else if (key > n->key)
        insert(n->right, key, priority);

Operaţia de ştergere este inversul operaţiei de inserare. Scopul este să aducem acest nod, fie el $z$, în poziţia unei frunze pentru a-l şterge. Astfel, pentru a menţine cei doi invarianţi (făcând excepţie de $z$) vom alege fiul cu prioritatea mai mare şi îl vom '$roti$':treapuri#rotatii în locul lui $z$, cât timp acesta nu este frunză. Atunci când $z$ devine frunză îl vom şterge.
== code(cpp) |

void erase(T* &n, int key)
{
    if (n == nil)   return ;

void erase(T* &n, int key) {
    if (n == nil) return ;

    if (key < n->key)
        erase(n->left, key);
    else if (key > n->key)
        erase(n->right, key);

    else {

    else {

        (n->left->priority > n->right->priority) ? rotleft(n) : rotright(n);

        if (n != nil)

        if (n != nil)

            erase(n, key);
        else {
            delete n->left;

h3(#split). Split

Uneori dorim să despărţim treapul $T$ în două treapuri $T{~<~}$ şi $T{~>~}$ astfel încât cheile din $T{~<~}$ să conţină cheile din $T$ mai mici decât o cheie $key$ dată, iar $T{~>~}$ să conţină cheile din $T$ mai mari decât aceeaşi cheie $key$. Soluţia constă în inserarea unui nod ajutător $z$ a cărui cheie este $key$ şi prioritate $infinit$. După inserare, $z$ va fi rădăcina arborelui, având prioritatea cea mai mare iar subarborii stâng şi drept ai rădăcănii vor fi exact treapurile căutate. Pe $z$ îl vom şterge, deoarece nu mai avem nevoie de el.

Uneori dorim să despărţim treapul $T$ în două treapuri $T{~<~}$ şi $T{~>~}$ astfel încât cheile din $T{~<~}$ să conţină cheile din $T$ mai mici decât o cheie $key$ dată, iar $T{~>~}$ să conţină cheile din $T$ mai mari decât aceeaşi cheie $key$. Soluţia constă în inserarea unui nod ajutător $z$ a cărui cheie este $key$ şi prioritate $infinit$. După inserare, $z$ va fi rădăcina arborelui, având prioritatea cea mai mare, iar subarborii stâng şi drept ai rădăcănii vor fi exact treapurile căutate. Pe $z$ îl vom şterge, deoarece nu mai avem nevoie de el.

Costul operaţiei $split$ este egal cu costul operaţiei de '$inserare$':treapuri#inserare a lui $z$.
== code(cpp) |

void split(T* &R, T* &Ts, T* &Tg, int key)
{

void split(T* &R, T* &Ts, T* &Tg, int key) {

    insert(R, key, infinity);
    Ts = R->left, Tg = R->right;
    delete R, R = nil;

Costul operaţiei $join$ este egal cu costul operaţiei de '$ştergere$':treapuri#stergere a lui $z$.
== code(cpp) |

void join(T* &R, T* Ts, T* Tg, int key)
{

void join(T* &R, T* Ts, T* Tg, int key) {

    R = new T(key, 0, Ts, Tg);
    erase(R, R->key);
}

h3(#alte-operatii). Alte operaţii

Structura de date de Treap suportă, pe lângă operaţiile prezentate, şi operaţia de determinarea a celei de a $K$-a chei, precum şi determinarea maximului, a minimului, a succesorului sau predecesorului unei chei, sau de tipărire a conţinutului cheilor pe baza relaţiei de ordine stabilite.

Structura de date de treap suportă, pe lângă operaţiile prezentate, şi operaţia de determinare a celei de a $K$-a chei, precum şi determinarea maximului, a minimului, a succesorului sau predecesorului unei chei, sau de tipărire a conţinutului cheilor pe baza relaţiei de ordine stabilite.

h2(#concluzii). Concluzii

Nu întotdeauna $STL$ ne scapă din încurcătură. Nu avem în această librărie o structură de date pentru determinarea celei de a $K$-a chei în timp logaritmic şi nici nu ne putem folosi de structura arborescentă a lui $set$ şamd. Exemple grăitoare, în care se foloseşte structura arborescentă a treapurilor, sunt aplicaţiile prezentate mai jos. Cât despre alternative, puteţi face o comparaţie între funcţiile '$erase$':treapuri#stergere sau '$balance$':treapuri#rotatii cu cele din articolul următor despre arborii '$AVL$':multe-smenuri-de-programare-in-cc-si-nu-numai#AVL.

Nu întotdeauna $STL$ ne scapă din încurcătură. Nu avem în această bibliotecă o structură de date pentru determinarea celei de a $K$-a chei în timp logaritmic şi nici nu ne putem folosi de structura arborescentă a lui $set$. Exemple grăitoare, în care se foloseşte structura arborescentă a treapurilor, sunt aplicaţiile prezentate mai jos. Cât despre alternative, puteţi face o comparaţie a funcţiilor '$erase$':treapuri#stergere sau '$balance$':treapuri#rotatii cu cele din articolul următor despre arborii '$AVL$':multe-smenuri-de-programare-in-cc-si-nu-numai#AVL.

h2(#aplicatii). Aplicaţii