Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-11-20 08:28:02.
Revizia anterioară   Revizia următoare  

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

#include <cstdio>
#include <algorithm>

using namespace std;

struct T {
    int key;
    int priority;
    T *left, *right;
} *R, *nil;     // R radacina; nil arata un nod `gol`

void init(void)
{
    srand(unsigned(time(0)));
    R = nil = new T();
    nil->key = nil->priority = 0,
        nil->left = nil->right = NULL;
}

T* rotleft(T *n)    // roteste fiul stang
{
    T *t = n->left;
    n->left = t->right, t->right = n;
    return t;       // noua radacina
}

T* rotright(T *n)   // roteste fiul drept
{
    T *t = n->right;
    n->right = t->left, t->left = n;
    return t;       // noua radacina
}

T* balance(T *n)    // restabileste invariantul heapurilor
{
    // balance() e apelat dupa un insert(), deci doar cel mult unul din cei doi fii nu respecta invariantul heapurilor
    if (n->left->priority > n->priority)
        return rotleft(n);

    if (n->right->priority > n->priority)
        return rotright(n);

    return n;       // altfel nu face nimic
}

T* insert(T *n, int key)
{
    if (n == nil)   // am gasit locul in care trebuie inserata cheia key
    {
        n = new T();
        n->key = key, n->priority = rand() + 1,
                    n->left = n->right = nil;
        return n;
    }
    if (key < n->key)
        n->left = insert(n->left, key);
    else if (key > n->key)
        n->right = insert(n->right, key);
    // altfel e un duplicat; nu face nimic
    return balance(n);      // restabileste invariantul heapurilor
}

T* erase(T *n, int key)
{
    if (n != nil)
    {
        if (key < n->key)
            n->left = erase(n->left, key);
        else if (key > n->key)
            n->right = erase(n->right, key);
        else {
            // am gasit cheia; pune fiul cu prioritatea cea mai mare ca radacina in locul lui `n`
            n = (n->left->priority > n->right->priority) ? rotleft(n) : rotright(n);
            if (n != nil)   // continua
                n = erase(n, key);
            else {
                delete n->left;
                n->left = NULL;
            }
        }
    }
    return n;
}

T* empty(T *n)
{
    if (n != nil)
    {
        empty(n->left), empty(n->right);
        delete n;
    }
    return nil;
}

void print(T *n)
{
    if (n != nil)
    {
        print(n->left);
        printf("%d ", n->key);
        print(n->right);
    }
}

int main(void)
{
    init();
    // 1 s pentru a insera un milion de numere
    for (int i = 1 << 20; i >= 1; -- i)
        R = insert(R, i);
    // 0.5 s pentru a sterge un milion de numere
    for (int i = 1; i <= 1 << 20; ++ i)
        R = erase(R, i);

    R = empty(R);
    return 0;
}