Revizia anterioară Revizia următoare
 Aceasta pagina nu este finalizata. Te rugam sa o imbunatatesti. |
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.
Proprietăţile cele mai importante ale acestei structuri de date sunt următoarele:
- dacă parcurgem arborele în inordine, atunci vom obţine nodurile sortate;
- prioritatea fiecărui nod este mai mare decât cea a fiilor săi.
Î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.
