Treap-uri

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

Ce este un Treap?

Treap-ul este un arbore binar în care fiecare nod conţine două informaţii:

• cheie;

• prioritate.

Structura de date respectă doi invarianţi:

• dacă parcurgem arborele în inordine, atunci vom obţine nodurile sortate; (invariantul arborilor de căutare)

• prioritatea fiecărui nod este mai mare decât cea a fiilor săi. (invariantul heapurilor)

În consecinţă, treap-ul este un arbore binar de căutare pentru chei şi un max-heap pentru priorităţi.

În continuare, vom presupune, pentru uşurinţă, că toate cheile din treap-ul T sunt distincte. Cazul în care avem nevoie să inserăm şi valori ce se repetă se va trata cu uşurinţă 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.

Operaţii

Vor urma în curând... :)

De adăugat: insert, remove, split, join, lookup, rotleft, rotright, print, balance, meld O(mlog(n/m)) - unirea a două treapuri T1 şi T2 fără nicio relaţie de ordine între ele, difference O(mlog(n/m)) - din T1 şi T2 rezultă un T care conţine cheile din T1 care nu sunt în T2.

Avantaje

Heapurile şi arborii de căutare sunt uşor de implementat şi de înţeles, iar treapurile sunt o combinaţie a acestor două concepte. Astfel, e suficient să fie înţeles invariantul, după care implementarea unui treap 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 mulţime de cazuri, pe când la treapuri facem doar câte o rotaţie stânga sau o rotaţie dreapta la fiecare pas al algoritmului. Ei nu sunt predaţi pentru că arborii roşu negrii sau AVL au demonstraţia că merg în O(log N) şi sunt exemple didactice, dar treapurile deşi cu o demonstraţie mai grea sunt mult mai uşori de implementat şi poate şi puţin mai rapizi ca arborii AVL.

Vă puteţi uita, ca şi comparaţie, la funcţiile erase sau balance din articolul următor despre arborii AVL.

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);

    balance(n);
}

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