Aruncarea copacului

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Un arbore splay este un arbore de căutare binar cu proprietatea că cele mai recent accesate obiecte tind să fie cele mai apropiate de rădăcină. În acest fel, căutarea lor este mai eficientă decât într-un copac binar normal și uneori chiar mai mult decât într-un copac echilibrat . Pentru a obține această proprietate, arborele este lărgit (în engleză splay ), astfel încât nodul care conține cheia căutată este mutat la rădăcină prin rotații. Aceste rotații, pe lângă aducerea nodului la rădăcină, scurtează distanța dintre rădăcină și toate nodurile vizitate în timpul căutării cu aproximativ jumătate. Cu toate acestea, acestea nu garantează că arborele rezultat este echilibrat și, în cel mai rău caz, accesul la un nod poate necesita vizita tuturor nodurilor din arbore (complexitate liniară); costul amortizat este în schimb .

Arborii Splay sunt preferați pentru implementarea în cache, unde informațiile nu sunt accesate uniform (acces aleatoriu), dar unele elemente sunt accesate mai frecvent decât altele (acces localizat). La fiecare acces, algoritmul de afișare mută acest nod în rădăcină și, în consecință, elementele cele mai frecvent accesate sunt întotdeauna situate lângă rădăcina arborelui, făcându-l accesibil mai rapid și îmbunătățind semnificativ timpul de acces general la cache în operațiunile de căutare și anulare. În ciuda avantajului de performanță față de un copac AVL , există mai multe implementări și biblioteci mai bune de al doilea tip, datorită simplității sale mai mari și a faptului că blocajul multor cache este accesul la disc (mai lent decât trei ordine de mărime) și nu operații pe structura datelor.

Informatică Portal IT : accesați intrările Wikipedia care se ocupă cu IT