Diferente pentru treapuri intre reviziile #137 si #147

Nu exista diferente intre titluri.

Diferente intre continut:

h2(#avantaje). Avantaje
Structurile de date de heap şi de arbori binari de căutare sunt uşor de implementat şi de înţeles, iar treapurile sunt o combinaţie a acestor două concepte. Astfel, este suficient să fie înţeleşi cei doi invarianţi, după care implementarea se poate face cu uşurinţă în 20 de minute, fără antrenament. De obicei, la structuri ca $Arborii Roşu-Negru$ trebuie folosite serii de rotaţii stânga şi dreapta complexe şi analizată o multitudine de cazuri, pe când la treapuri facem doar câte o rotaţie stânga sau dreapta la fiecare pas al algoritmului. Ei nu sunt predaţi pentru că se preferă ca exemple didactice $Arborii Roşu-Negru$ sau cei $AVL$ care au o demonstraţie accesibilă că limita celei mai lente operaţii este $O(log N)$. Dar treapurile, deşi cu o demonstraţie mai grea pentru limita de $O(log N)$, ce implică probabilităţi, sunt mult mai uşor de implementat, iar în practică, cu siguranţă este greu de decis care sunt mai rapizi. Sunt, deci, o opţiune demnă de luat în seamă. Pe de altă parte, treapurile suportă şi alte două operaţii pe care nu le putem face cu $Arborii Roşu-Negru$ sau cu arborii $AVL$. Aceste operaţii sunt '$join$':treapuri#join şi '$split$':treapuri#split.
Structurile de date de heap şi de arbori binari de căutare sunt uşor de implementat şi de înţeles, iar treapurile sunt o combinaţie a acestor două concepte. Astfel, este suficient să fie înţeleşi cei doi invarianţi, după care implementarea se poate face cu uşurinţă în 20 de minute, fără antrenament. De obicei, la structuri ca $Arborii Roşu-Negru$ trebuie folosite serii de rotaţii stânga şi dreapta complexe şi analizată o multitudine de cazuri, pe când la treapuri facem doar câte o rotaţie stânga sau dreapta la fiecare pas al algoritmului. Ei nu sunt predaţi pentru că se preferă ca exemple didactice $Arborii Roşu-Negru$ sau cei $AVL$ care au o demonstraţie accesibilă că limita celei mai lente operaţii este $O(log N)$. Dar treapurile, deşi cu o demonstraţie mai grea pentru limita de $O(log N)$, ce implică probabilităţi, sunt mult mai uşor de implementat, iar în practică este greu de decis care sunt cei mai rapizi. Sunt, deci, o opţiune demnă de luat în seamă. Pe de altă parte, treapurile suportă şi alte două operaţii pe care nu le putem face cu $Arborii Roşu-Negru$ sau cu arborii $AVL$. Aceste operaţii sunt '$join$':treapuri#join şi '$split$':treapuri#split.
h2(#operatii). Operaţii
    T *left, *right;
    T() {}
    T(int key, int priority, T* left, T* right) {
        this->key = key, this->priority = priority;
        this->key = key;
        this->priority = priority;
        this->left = left, this->right = right;
    }
} *R, *nil; // nil indică un nod 'gol'
} *R, *nil; // nil indica un nod 'gol'
void init(T* &R) {
    srand(unsigned(time(0)));
Rotaţiile sunt cărămizile de la baza structurii de treap.
p=. !treapuri?Fig1.png!
p=. !treapuri?Fig1-ok.png!
p=. _*Descriere:* 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=. _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 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.
p=. !treapuri?Fig2.png!
p=. _*Descriere:* 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$._
p=. _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 a lui $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 erase(T* &n, int key) {
    if (n == nil) return ;
    if (n == nil) return;
    if (key < n->key)
        erase(n->left, key);
    else if (key > n->key)
        erase(n->right, key);
    else {
        (n->left->priority > n->right->priority) ? rotleft(n) : rotright(n);
        if (n != nil)
            erase(n, key);
    else {
        if (n->left == nil && n->right == nil)
            delete n, n = nil;
        else {
            delete n->left;
            n->left = NULL;
            (n->left->priority > n->right->priority) ? rotleft(n) : rotright(n);
            erase(n, key);
        }
    }
}
h2(#aplicatii). Aplicaţii
* 'Secv8':problema/secv8, info{_arena_}
* 'Order':problema/order, info{_arena_}
* 'Schi':problema/schi, info{_arena_}
* 'Zeap':problema/zeap, info{_arena_}
* 'Bile4':problema/bile4, info{_arena_}
* 'Vmem':http://campion.edu.ro/problems/3/444/vmem_ro.htm, .campion
* 'Bile':http://campion.edu.ro/problems/3/443/bile_ro.htm, .campion
* 'Trains':http://campion.edu.ro/problems/3/432/trains_ro.htm, .campion
h2(#bibliografie). Bibliografie
* 'Fast Set Operations Using Treaps':http://www.cs.cmu.edu/afs/cs.cmu.edu/project/scandal/public/papers/treaps-spaa98.pdf, operaţiile '$split$':treapuri#split şi '$join$':treapuri#join sub altă formă
* 'Treaps and Skip Lists':http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/06-treaps.pdf
* 'Balanced Search Trees':http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-s07/www/lecture_notes/lect0208.pdf
 
h2. Discuţii pe forum
 

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.