Diferente pentru treapuri intre reviziile #102 si #147

Nu exista diferente intre titluri.

Diferente intre continut:

** '- Ştergere':treapuri#stergere
** '- Split':treapuri#split
** '- Join':treapuri#join
** '- Alte operaţii':treapuri#alte-operatii
* '{*} Concluzii':treapuri#concluzii
* '{*} Aplicaţii':treapuri#aplicatii
* '{*} Bibliografie':treapuri#bibliografie
În consecinţă, treapul este un arbore binar de căutare pentru chei şi un max-heap pentru priorităţi.
În continuare, vom presupune că toate cheile şi priorităţile din treapul $T$ sunt distincte. În practică, presupunerea aceasta are un impact neglijabil.
În continuare, vom presupune că oricare două chei din treapul $T$ sunt distincte. Cazul când avem nevoie de chei egale se va trata relativ uşor după ce acest articol va fi înţeles.
Astfel, din moment ce $T$ este un heap, nodul $v$ cu prioritatea cea mai mare trebuie să fie rădăcina. Cum este şi un arbore binar de căutare, orice nod $u$ cu $cheie(u) < cheie(v)$ se găseşte în subarborele stâng al lui $v$, şi orice nod $w$ cu $cheie(w) > cheie(v)$ se găseşte în subarborele drept.
Astfel, din moment ce $T$ este un heap, nodul $v$ cu prioritatea cea mai mare trebuie să fie rădăcina. Întrucât este şi un arbore binar de căutare, orice nod $u$ cu $cheie(u) < cheie(v)$ se găseşte în subarborele stâng al lui $v$, şi orice nod $w$ cu $cheie(w) > cheie(v)$ se găseşte în subarborele drept.
Cheile şi priorităţile determină în mod unic forma unui treap. Prin inducţie se demonstrează că treapul este arborele binar obţinut prin inserarea cheilor în ordinea descrescătoare a priorităţilor. Algoritmul de inserare este cel obişnuit pentru arborii de căutare. Astfel, cum fiecare set de priorităţi asociat nodurilor va aranja arborele într-un singur mod, probabilitatea ca arborele să fie echilibrat este rezonabil de mare, fapt datorat numărului mic al arborilor rău echilibraţi în comparaţie cu cei echilibraţi. Iată şi secretul acestei structuri de date: probabilitatea infimă de a se găsi o serie de priorităţi generate aleator care să nu menţină arborele echilibrat.
Cheile şi priorităţile asociate lor, in condiţiile în care ambele sunt distincte, determină în mod unic forma unui treap. Prin inducţie se demonstrează că treapul este arborele binar obţinut prin inserarea cheilor în ordinea descrescătoare a priorităţilor. Algoritmul de inserare este cel obişnuit pentru arborii de căutare. Astfel, cum fiecare set de priorităţi asociat nodurilor va aranja arborele într-un singur mod, probabilitatea ca arborele să fie echilibrat este rezonabil de mare, fapt datorat numărului mic al arborilor rău echilibraţi în comparaţie cu cei echilibraţi. Iată şi secretul acestei structuri de date: probabilitatea infimă de a se găsi o serie de priorităţi generate aleator care să nu menţină arborele echilibrat.
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 $Arbori Roşu-Negrii$ trebuie folosite serii de rotaţii stânga şi dreapta complexe şi analizate 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ă $Arborii Roşu-Negrii$ sau $AVL$ au demonstraţia că limita celei mai lente operaţii este $O(log N)$ şi sunt exemple didactice, 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-Negrii$ 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
Costul operaţiilor de mai jos este proporţional cu adâncimea unui nod din treap. După cum am menţionat mai sus, cu ajutorul teoriei probabilităţilor se poate deduce că adâncimea aşteptată a oricărui nod este $O(log N)$, ceea ce implică costul celor mai lente operaţii să fie $O(log N)$.
Costul operaţiilor de mai jos este proporţional cu adâncimea unui nod din treap. După cum am menţionat mai sus, cu ajutorul teoriei probabilităţilor se poate deduce că adâncimea medie aşteptată a oricărui nod este $O(log N)$, ceea ce implică costul celor mai lente operaţii să fie, în medie, $O(log N)$.
Mai jos avem definiţia în cod $C++$ a unui treap şi o funcţie de iniţializare, care marchează că treapul cu rădăcina $R$ este gol.
== code(cpp) |
struct T {
    int key;
    int priority;
    int key, priority;
    T *left, *right;
    T() {}
    T(int key, int priority, T* left, T* right) {
        this->key = key, this->priority = priority,
                    this->left = left, this->right = right;
        this->key = key;
        this->priority = priority;
        this->left = left, this->right = right;
    }
} *R, *nil;     // R radacina; nil arata un nod `gol`
} *R, *nil; // nil indica un nod 'gol'
void init(T* &R)
{
void init(T* &R) {
    srand(unsigned(time(0)));
 
    R = nil = new T();
    nil->key = nil->priority = 0,
        nil->left = nil->right = NULL;
    R = nil = new T(0, 0, NULL, NULL);
}
==
Căutarea într-un treap este identică cu cea într-un arbore binar de căutare. Pentru a verifica dacă o cheie există putem proceda în felul următor:
== code(cpp) |
int search(T* n, int key)
{
    if (n == nil)  return 0;
    if (key == n->key)  return 1;
int search(T* n, int key) {
    if (n == nil) return 0;
    if (key == n->key) return 1;
    if (key < n->key)
        return search(n->left, key);
    else
h3(#rotatii). Rotaţii
Rotaţiile sunt cărămizile de la baza structurii de Treap.
Rotaţiile sunt cărămizile de la baza structurii de treap.
p=. !treapuri?Fig1d.png!
p=. !treapuri?Fig1-ok.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=. _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.
Pentru o rotaţie este necesar un număr constant de 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)
În cadrul operaţiei de inserare vom atribui unui nod nou o prioritate aleatoare şi îl vom insera, conform algoritmului standard de inserare într-un arbore binar, la baza arborelui. Să presupunem că dorim să inserăm nodul $z$ cu cheia $9$ şi prioritatea $51$.
p=. !treapuri?Fig2c.png!
p=. !treapuri?Fig2.png!
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$._
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 î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 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 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);
}
==
Un nod poate fi inserat în modul următor:
== code(cpp) |
...
insert(R, key, rand() + 1); // adăugăm 1 deoarece prioritatea 0 o are doar nodul nil
...
==
 
unde $R$ este rădăcina, iar $key$ este cheia de inserat.
 
Complexitate: $O(log N)$.
h3(#stergere). Ştergere
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 {
        (n->left->priority > n->right->priority) ? rotleft(n) : rotright(n);
        if (n != nil)
            erase(n, key);
        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);
        }
    }
}
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. Dacă ştergem rădăcina, subarborele stâng şi cel drept vor fi exact treapurile căutate.
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;
}
==
h3(#join). Join
Operaţia $join$ constă în unirea a două treapuri $T{~<~}$ şi $T{~>~}$, unde fiecare cheie din $T{~<~}$ este mai mică decât o cheie $key$ iar oricare cheie din $T{~>~}$ este mai mare decât aceeaşi cheie $key$, într-un singur super-treap. $Join$ se realizează în mod invers operaţiei de $split$ prin crearea unei rădăcini $z$ cu cheia $key$ şi prioritate oricât, ce are ca subarbore stâng pe $T{~<~}$ iar ca subarbore drept pe $T{~>~}$, pe care o vom suprima.
Operaţia $join$ constă în unirea a două treapuri $T{~<~}$ şi $T{~>~}$, unde fiecare cheie din $T{~<~}$ este mai mică decât o cheie $key$, iar fiecare cheie din $T{~>~}$ este mai mare decât aceeaşi cheie $key$, într-un singur super-treap. $Join$ se realizează în mod invers operaţiei de $split$ prin crearea unei rădăcini $z$ cu cheia $key$ şi o prioritate aleatoare, ce are ca subarbore stâng pe $T{~<~}$, iar ca subarbore drept pe $T{~>~}$, pe care o vom suprima.
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);
}
Complexitate: $O(log N)$.
h3(#alte-operatii). Alte operaţii
 
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
Mai sus aţi văzut codul în $C++$ pentru cele mai importante operaţii. 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. Structura de date de Treap supor, pe lân operaţiile prezentate, şi operaţii precum 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. Şi s-ar putea să mai existe. :-) Chinezii şi ruşii foloseau intens această structură de date, în special în $Pascal$ unde nu există o librărie echivalencu $STL$.
Nu întotdeauna $STL$ ne sca din încurtură. 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 comparie 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
* 'Order':http://infoarena.ro/problema/order, info{_arena_}
* 'Schi':http://infoarena.ro/problema/schi, info{_arena_}
* '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
* 'Trains':http://campion.edu.ro/problems/3/432/trains_ro.htm, .campion
h2(#bibliografie). Bibliografie
* 'Eternally Confuzzled':http://eternallyconfuzzled.com/jsw_home.aspx
* 'Eternally Confuzzled':http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_bst2.aspx
* '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
* 'Balanced Search Trees':http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-s07/www/lecture_notes/lect0208.pdf
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3442