** 'Ştergere':treapuri#stergere
** 'Split':treapuri#split
** 'Join':treapuri#join

* '4. Implementare':treapuri#cod

* '4. Concluzii':treapuri#concluzii
* '5. Aplicaţii':treapuri#aplicatii
* '6. Bibliografie':treapuri#bibliografie

În acest articol voi prezenta o alternativă pentru arborii binari de căutare echilibraţi, precum $AVL$, $Red-Black Trees$, $Splay Trees$ şi $B-Trees$.

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)$.

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;
    T *left, *right;
} *R, *nil;
 
void init(T* &R)
{
    srand(unsigned(time(0)));
 
    R = nil = new T();
    nil->key = nil->priority = 0,
        nil->left = nil->right = NULL;
}
==
 

h3(#cautare). Căutare
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:

Complexitate: $O(log N)$.

h2(#cod). Implementare
 
Mai jos este codul în $C++$ pentru unele operaţii prezentate anterior. Puteţi face o comparaţie între funcţiile $erase$ sau $balance$ din articolul următor despre arborii '$AVL$':multe-smenuri-de-programare-in-cc-si-nu-numai#AVL şi cele ale treapurilor.
 
== code(cpp) |
 
struct T {
    int key;
    int priority;
    T *left, *right;
} *R, *nil;
 
void init(T* &R)
{
    srand(unsigned(time(0)));
 
    R = nil = new T();
    nil->key = nil->priority = 0,
        nil->left = nil->right = NULL;
}
 
void rotleft(T* &n)
{
    T *t = n->left;
    n->left = t->right, t->right = n;
    n = t;
}
 
void rotright(T* &n)
{
    T *t = n->right;
    n->right = t->left, t->left = n;
    n = t;
}
 
void balance(T* &n)
{
    if (n->left->priority > n->priority)
        rotleft(n);
    else if (n->right->priority > n->priority)
        rotright(n);
}
 
void insert(T* &n, int key)
{
    if (n == nil)
    {
        n = new T();
        n->key = key, n->priority = rand() + 1,
                    n->left = n->right = nil;
        return;
    }
    if (key < n->key)
        insert(n->left, key);
    else if (key > n->key)
        insert(n->right, key);

h2(#concluzii). Concluzii

    balance(n);
}

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$ sau $balance$ din articolul următor despre arborii '$AVL$':multe-smenuri-de-programare-in-cc-si-nu-numai#AVL şi cele ale treapurilor.

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

h2(#aplicatii). Aplicaţii

    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 {
            delete n->left;
            n->left = NULL;
        }
    }
}
==

h2(#bibliografie). Bibliografie