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
Avantaje
heapuri si arbori de cautare sunt usor de implementat si de inteles, iar treapurile sunt o combinatie acestor doua concepte. Astfel e deajuns sa intelegi invariantul si apoi implementarea unui treap merge in 20 de minute, fara antrenament. De obicei la structuri ca arbori rosu negrii trebuie folosite serii de rotatii stanga si dreapta complexe si analizate o gramada de cazuri, pe cand la treapuri facem doar cate o rotatie stanga sau o rotatie dreapta la fiecare pas al algoritmului. Ei nu sunt predati pentru ca arborii rosu negrii sau avl au demonstratia ca merg in O(log n) si sunt exemple didactice, dar treapurile desi cu o demonstratie mai grea sunt mult mai usori la implementare si poate si putin mai rapizi ca arborii avl.
#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;
}