Note de curs, probleme algoritmică, clasa IX/X, 12 iunie 2015
În acest curs am prezentat structura de date numită Treap. Aceasta este o combinație între un arbore binar de căutare și un heap. Fiecare nod conține două informații: o valoare și o cheie (generată aleator) și, bineînțeles adresele fiului stâng și fiului drept. Pe baza acestor două informații, treap-ul are structura unui arbore binar de căutare în funcție de valorile nodurilor și, în același timp, structura unui heap în funcție de cheile nodurilor.
O observație interesantă este aceea că pentru o listă dată de perechi (valoare, cheie) există un treap și numai unul. Pe baza acestei demonstrații se poate demonstra că, dacă cheile sunt alese aleator, atunci adâncimea maximă a unui treap cu N noduri, pe cazul mediu (expected value) va fi O(log N).
În continuare avem implementarea operațiilor de inserare și ștergere pe un treap persistent implementat în paradigma programării funcționale.
Definirea nodului treap-ului
Vom începe prin crearea unei clase pentru nodurile treap-urilor:
#include <cstdio>
#include <cstdlib>
#include <ctime>
class Node {
public:
const Node* const left;
const Node* const right;
const int value;
const long long key;
Node(const Node* const left, const Node* const right,
const int value, const long long key) :
left(left),
right(right),
value(value),
key(key) {
;
}
};
Pentru simplificarea implementării, vom defini un nod santinelă care să joace rolul de fiu al nodurilor care nu au unul din fii sau ambii fii.
const Node* const NIL = new Node(NULL, NULL, 0, -1);
Definirea treap-ului
Singura informație conținută într-un treap va fi un pointer către nodul rădăcină.
class Treap {
const Node* root;
Treap(const Node* const root) :
root(root) {
;
}
Implementarea operațiilor elementare
Pentru inserarea unei valori noi va trebui să avem posiblitatea creării unui nod nou cu o valoare dată și o cheie aleasă aleator.
const Node* const createNode(const int value) const {
return new Node(
NIL,
NIL,
value,
(long long)rand() | ((long long)rand() << 31));
}
Pentru a menține proprietatea de heap a treap-ului și, în consecință, pentru a-l echilibra, va trebui să avem la dispoziție operațiile de rotire la dreapta și la stânga:
const Node* const rotateRight(const Node* const root) const {
const Node* const A = root->left;
const Node* const B = root;
const Node* const b = A->right;
return new Node(
A->left,
new Node(
b,
B->right,
B->value,
B->key),
A->value,
A->key);
}
const Node* const rotateLeft(const Node* const root) const {
const Node* const A = root;
const Node* const B = root->right;
const Node* const b = B->left;
return new Node(
new Node(
A->left,
b,
A->value,
A->key),
B->right,
B->value,
B->key);
}
Implementarea inserării
Acum putem implementa inserarea. Am ales o implementare recursivă: se inserează un nod deja creeat (value) într-un subarbore al treap-ului dat prin nodul său rădăcină (root).
Se disting 3 cazuri:
- Se inserează un nod într-un subarbore vid: rezultatul este noul nod;
- Se inserează un nod cu o valoare mai mică decât valoarea rădăcinii subarborelui: se inserează noul nod în fiul stâng al subarborelui;
- Se inserează un nod cu o valoare mai mare sau egală cu valoarea rădăcinii subarborelui: se inserează noul nod în fiul drept al subarborelui.
În ultimele două cazuri, după efectuarea inserăii trebuie avut grijă ca proprietarea de heap să se conserve. Iar dacă nu se conservă, trebuie efectuată una dintre rotații, după caz.
const Node* const insert(const Node* const root, const Node* const value) const {
if (root == NIL) {
return value;
} else if (value->value < root->value) {
const Node* const newNode = new Node(
this->insert(root->left, value),
root->right,
root->value,
root->key);
if (newNode->key < newNode->left->key) {
return this->rotateRight(newNode);
} else {
return newNode;
}
} else {
const Node* const newNode = new Node(
root->left,
this->insert(root->right, value),
root->value,
root->key);
if (newNode->key < newNode->right->key) {
return this->rotateLeft(newNode);
} else {
return newNode;
}
}
}
Implementarea ștergerii
În continuare vom implementa șteregrea în mod recursiv: se caută nodul care trebuie șters și, odată găsit se disting 2 cazuri:
- nodul este frunză: se înlocuiește cu noul santinelă;
- nodul nu este frunză: se efectuează una dintre rotații, astfel încât fiul cu cheia mai mare să devină rădăcină iar nodul se șterge recusiv din noul fiu corespunzător.
const Node* const erase(const Node* const root, int value) const {
if (root != NIL) {
if (value == root->value) {
if (root->left == NIL && root->right == NIL) {
return NIL;
} else {
if (root->left->key > root->right->key) {
const Node* const newRoot = rotateRight(root);
return new Node(
newRoot->left,
erase(newRoot->right, value),
newRoot->value,
newRoot->key);
} else {
const Node* const newRoot = rotateLeft(root);
return new Node(
erase(newRoot->left, value),
newRoot->right,
newRoot->value,
newRoot->key);
}
}
} else if (value < root->value) {
return new Node(
this->erase(root->left, value),
root->right,
root->value,
root->key);
} else { // root->value < value
return new Node(
root->left,
this->erase(root->right, value),
root->value,
root->key);
}
}
return NIL;
}
Afișarea structurii de date
Pentru a putea verifica corectitudinea implementării și pentru a putea identifica mai ușor eventualele greșeli de implementare, se recomandă implementarea unei funcții (recursive) care să afișeze structura treap-ului.
Parametrul offset are rolul de a stoca adâncimea nodului root pentru a putea afișa nodurile in mod indentat. Treap-ul va fi parcurs și afișat în inordine iar pentru un nod se vor afișa valoarea și cheia sa.
void dump(const Node* const root, int offset = 0) const {
if (root != NIL) {
this->dump(root->left, offset + 1);
for (int i = 0; i < offset; ++i) {
printf(" ");
}
printf("%d\t %20lld\n", root->value, root->key);
this->dump(root->right, offset + 1);
}
}
Funcțiile publice ale treap-ului
Pentru a definitiva clasa Treap, vom implementa constructorul fără parametri (care creează un treap gol), funcțiile insert și erase (care realizează inserarea și ștergerea) și funcția dump (care afișează structura treap-ului).
public:
Treap() {
this->root = NIL;
}
Treap* insert(int value) const {
return new Treap(this->insert(this->root, this->createNode(value)));
}
Treap* erase(int value) const {
return new Treap(this->erase(this->root, value));
}
void dump() const {
this->dump(this->root);
printf("\n");
}
};
Testarea implementării
Îm încheiere avem un cod de testare a funcțiilor structurii de date, care creează un treap gol, inserează în el 7 valori distincte și apoi șterge una dintre ele. În final, sunt afișate toate versiunile de treap create anterior, pentru a se putea verifica dacă operațiile sunt efectuate corect și dacă toate versiunile sunt stocate în memorie.
int main() {
srand(time(NULL));
const Treap* const t0 = new Treap();
const Treap* const t1 = t0->insert(4);
const Treap* const t2 = t1->insert(2);
const Treap* const t3 = t2->insert(7);
const Treap* const t4 = t3->insert(9);
const Treap* const t5 = t4->insert(3);
const Treap* const t6 = t5->insert(5);
const Treap* const t7 = t6->insert(6);
const Treap* const t8 = t7->erase(6);
t0->dump();
t1->dump();
t2->dump();
t3->dump();
t4->dump();
t5->dump();
t6->dump();
t7->dump();
t8->dump();
return 0;
}
