Lucrarea de laborator nr. 7

Arbori SPLAY

1.1 Prezentare generala

Arborii splay sunt arbori binari de căutare care au pus în aplicare un mecanism de auto-reglare. Acest mecanism se efectuează în felul următor: de fiecare dată când am accesat un nod din arbore, fie pentru introducerea sau extragerea,vom efectua rotatii (ca şi în arbori AVL), si ridicam toate nodurile accesate până la capăt, astfel încât acesta devine rădăcină de arbore modificat. Nodurile de pe modul în care sunt rotită astfel încât arborele devine mai echilibrat. Arborele splay nu este un arbore de înălţime echilibrată, deoarece există situaţii când un nod poate avea ca factor de echilibru diferit de -1, 0 sau 1.

Nodurile care sunt frecvent accesate vor fi ridicate pentru a deveni radacina, şi nu vor deriva prea departe din poziţia de top. Nodurile inactive, pe de altă parte, vor fi lent împinse mai departe de la rădăcină. Este posibil ca arborii splay sa poata deveni extrem de dezechilibrati, astfel încât un singur acces la un nod de arbore poate fi destul de scump. Mai târziu în această secţiune, cu toate acestea, vom demonstra că, peste o secvenţă lungă de accesări, arborii splay nu sunt deloc scumpi si sunt garantate de a solicita, nu multe operaţiuni chiar mai mult decat arborii de analiză amortizat AVL. Instrument analitic utilizat se numeste analiza algoritmului cu amortizare, deoarece, ca şi calculele de asigurare,puţine cazuri sunt scumpe, în medie cu multe cazuri, mai puţin costisitoare pentru a obţine performanţe excelente într-un lung şir de operaţii. Operaţiunile care sunt efectuate sunt rotaţii de o formă similară cu cele utilizatepentru arbori AVL, dar acum cu mai multe rotaţii efectuate pentru fiecare introducerea sau extragerea din arbore. În fapt,rotaţii sunt făcut toate de-a lungul unui drum de la rădăcină la nodul ţintă care este accesat. Să discutam exact modul în care aceste rotaţii continua.

Structura unui nod splay este similară cu cea care a fost folosit la arbori binari de căutare. Notămun astfel de arbore astfel:

struct NodeSplay{int key;nod *left, *right, *parent;};

Unde:- cheie reprezintă eticheta de nod (număr întreg)- dreapta la stânga, şi părinte reprezintă indicii pentru copiii stânga şi la dreapta şi la nodul părinte.

1.2 Domeniu de utilizare al arborilor SPLAY

Arborii splay sunt de obicei folositi în punerea în aplicare a cache-ului, alocare de memorie, routere, colectoare de memroie, de compresie de date, streamuri (înlocuirea şirul de caractere folosit pentru siruri de caractere de text lung), în Windows NT (în memorie virtuală, crearea de reţele, şi fişier de cod de sistem), etc. Un arbore splay este o implementare eficientă a unui arbore binar echilibrat de căutare care profită de localizare din cheile folosite în cererile primite de căutare. Pentru multe aplicaţii, nu există localizare excelent cheie.Un bun exemplu este un router reţea. Un router reţea primeşte pachete de reţea la o rată ridicată de la conexiunile de intrare şi trebuie să decidă rapid pe care fir de ieşire pentru a trimite fiecare pachet, bazat peAdresa IP în pachet. Router-ul are nevoie de o masă mare (o harta) care poate fi folosita pentru a căuta o adresă IP şi afla ce conexiune de ieşire trebuie utilizata. În cazul în care o adresă IP a fost folosit o singură dată, este foarte probabil să fi utilizata din nou sau poate de mai multe ori. Arbori splay pot oferi performanţe bune în această situaţie.

Un alt exemplu de domeniu în care arborii splay sunt utilizati sunt sistemele de detectare a intruziunilor (IDS)care sunt o parte esenţială a infrastructurii de securitate. Ele sunt utilizate pentru a detecta, identifica şi a opri intruşii. Administratorii pot să se bazeze pe ele pentru a afla atacuri de succes şi pentru a preveni o utilizare viitoare. IDS sunt, de asemenea, considerate ca o solutie complementara pentru firewall tehnologie prin recunoaşterea atacurilor împotriva reţelei, care sunt pierdute de firewall. Cu toate acestea, IDS sunt afectate cu false alerte pozitiv, permiţându-profesionişti de securitate care urmează să fie copleşiti de sarcinile de analiză. Prin urmare, IDS folosesc mai multe tehnici pentru a spori probabilitatea detectării ameninţărilor suspecte reducând în acelaşi timp riscul de fals pozitive. Aceasta conduce la construirea unui arbore de decizie, cum ar fi arbore splay folosit pentru averifica traficul. Strategia propusă pentru a detecta intruziunile analizeaza folosind protocolul constă în extragerea de date de la fiecare pachet primit, dipozitive apoi un arbore de decizie pre-construite.Procesul de clasificare a pachetelor în în routere, firewall-uri, etc filtre de pachete, este numit de pachete de clasificare. Pachete de clasificare sunt utilizate într-o varietate de aplicaţii, cum ar fi securitate, monitorizare. Aceste aplicaţii multimedia funcţionează pe fluxurile de pachet sau un set de fluxuri. Prin urmare, aceste noduri trebuie să clasifice pachetele care travereseaza prin aceasta, pentru a atribui un flux identificator, numit ca Flow ID. Rapid şi tehnici eficiente de pachete de clasificare sunt esenţiale pentru proiectarea de routere de mare viteză, şi diversealte aplicaţii. În scopul de a realiza acest lucru, este folosita tehnica aşa-numitului proces Tree Packet Clasification (ST-PC), care constă în utilizarea primitiva de design si modele cu arbore splay şi metode de conversie.

1.3 Operatii cu arbori Splay

Când o rotaţie unica este efectuata într-un arbore binar de căutare, unele noduri trec spre un nivel mai mare în arbore şi unele spre nivele mai mici. Într-o rotaţie la stânga, nodul părinte şi copilul se mută din dreapta jos si se mişcă în sus cu un nivel. O dubla rotaţie, este alcătuită din două rotaţii singure, şi un nod de miscare cu două niveluri, în timp ce toţi ceilalţi copii se mişca in sus sau în jos cu cel mult un singur nivel. Incepând cu nodul-ţintă sunt accesate acele noduri până la rădăcină, am putea face o singură rotaţie la fiecare pas, astfel ridicarea ţintă nodul tot drumul la rădăcină. Această metodă ar atinge scopul de a face nod ţintă în rădăcină, dar, se pare,performanţa de arbore amortizare peste accesează multe nu poate fi bun. În schimb, ideea-cheie a splaying este de a muta obiectivul nodul două niveluri până arbore la fiecare pas. În primul rând unele simple terminologie: luaţi în considerare calea care merge de la radacina pana la nodul accesat. De fiecare dată când avem un nod vom deplasa la stânga mergand pe această cale, spunem că facem o rotatie zig, şi de fiecare dată ne deplasam spre dreapta spunem că avem un zag. O mutare de două etape stânga (merge în jos) este apoi numita zig-zig, doi pasi dreapta zag-zag, apoi la dreapta la stânga zig-zag,dreapta la stânga şi apoi zag-zig. Aceste patru cazuri sunt singurele posibilităţi în mişcare doi paşi pe cale. În cazul în care lungimea drumului este impara, cu toate acestea, va fi un pas necesar, la sfârşitul său, fie un zig (stânga)muta, sau un zag (dreapta) a muta. Rotaţiile efectuate în splaying pentru fiecare din zig-zig, zig-zag, şi se mută zig sunt afişate următoarele cifre. Alte trei cazuri, zag-zag, zig-zag, şi zag sunt figurate mai jos.

Zig-Zig

Figure 1. Zig-Zig move

Zig-Zag

Figure 2. Zig-Zag move

Zig

Figure 3. Zig move

1.3.2 Pseudocode pentru operatiile cu arbori Splay

MEMBER (S, k) {if ( *S == NIL )then return 0current = *Spred = NILwhile ( current != NIL ){if (k == curent->element)then breakpred = curentif ( k < curent->element )then current = curent->leftelsecurrent = curent->right}//end whileif ( current != NIL )then{splay(S, curent)return 1}else{splay(S, pred)return 0}// end MEMBER function

INSERT (S, k){if (*S == NIL )then (*S)->left = (*S)->right = (*S)->parent=NIL(*S)->element = kreturncurrent = *Santerior = NILwhile ( current != NIL ){if ( k == curent->element )returnanterior = curentif ( k < curent->element )then directie=LEFTcurrent = curent->leftelsedirectie = RIGHTcurrent = curent->rightcurent->element = kcurent->left = curent->right = NILcurent->parent = anteriorif ( directie == LEFT )then anterior->left = curentelseanterior->right = curentsplay(S, curent)}

DELETE (S, k) {if ( MEMBER(S, k) ){then SL = (*S)->leftif ( SL )then SL->parent = NILSR = (*S)->rightif ( SR )then SR->parent = NILjoin(SL, SR, S)}}JOIN (SL, SR, S){if ( SL )then member( &SL, PLUS_INFINIT)SL->right = SRif ( SR )then SR->parent = SL*S = SLelseif ( SR )then *S = SRelse*S = NILreturn}SPLIT (S, SL, SR, in){If ( S )then MEMBER( &S, in)*SL = S*SR = S->right(*SL)->right = NILelse*SR = *SL = NILreturn}SINGLEROTATE ( x ){if ( x->parent->left = x )then zig_left(&x)elsezig_right(&x)}DOUBLEROTATE( x ){if ( x->parent->left == x and x->parent->parent->left == x->parent)then zig_zig_left(&x)returnif ( x->parent->left == x and x->parent->parent->right == x->parent)then zig_zag_left(&x)returnif (x->parent->right == x and x->parent->parent->right == x->parent)then zig_zig_right(&x)return

if ( x->parent->right == x and x->parent->parent->left == x->parent)then zig_zag_right(&x)return

}

SPLAY( S, crt){father = crt->parentwhile ( father != NIL){if ( father->parent == NIL)then SINGLEROTATE(crt)elseDOUBLEROTATE(crt)father = crt->parent}//end while*S = crt}ZIG_LEFT(x){splay_node *p, *bp = (*x)->parentb = (*x)->right(*x)->right = p(*x)->parent = NILif ( b != NIL )b->parent = pp->left = bp->parent = (*x)}ZIG_RIGHT(x){splay_node *p, *bp = (*x)->parentb = (*x)->left(*x)->left = p(*x)->parent = NILif ( b != NIL )b->parent = pp->right = bp->parent = (*x)}ZIG_ZIG_LEFT(x){splay_node *p, *g, *ggpsplay_node *b, *cp = (*x)->parentg = p->parentb = (*x)->rightc = p->rightggp = g->parent(*x)->right = pp->parent = (*x)p->right = gg->parent = pif ( b != NIL )b->parent = p

p->left = bif ( c != NIL )c->parent = gg->left = c(*x)->parent = ggp

if ( ggp != NIL )if ( ggp->left == g )ggp->left = (*x)elseggp->right = (*x)}

ZIG_RIGHT(x){splay_node *p, *g, *ggpsplay_node *b, *cp = (*x)->parentg = p->parentb = (*x)->leftc = p->leftggp = g->parent(*x)->left = pp->parent = (*x)p->left = gg->parent = pif ( b != NIL )b->parent = pp->right = bif ( c != NIL )c->parent = gg->right = c(*x)->parent = ggpif ( ggp != NIL )if ( ggp->left == g )ggp->left = (*x)elseggp->right = (*x)}ZIG_ZAG_LEFT (x){splay_node *p, *g, *ggpsplay_node *a, *bp = (*x)->parentg = p->parentggp = g->parenta = (*x)->leftb = (*x)->right(*x)->left = gg->parent = (*x)(*x)->right = pp->parent = (*x)if ( a != NIL )a->parent = gg->right = aif ( b != NIL )

b->parent = pp->left = b(*x)->parent = ggpif ( ggp != NIL )

if ( ggp->left == g )ggp->left = (*x)elseggp->right = (*x)}

ZIG_ZAG_RIGHT(x){splay_node *p, *g, *ggpsplay_node *a, *bp = (*x)->parentg = p->parentggp = g->parenta = (*x)->leftb = (*x)->right(*x)->right = gg->parent = (*x)(*x)->left = pp->parent = (*x)if ( a != NIL )a->parent = pp->right = aif ( b != NIL )b->parent = gg->left = b(*x)->parent = ggpif ( ggp != NIL)if ( ggp->left == g)ggp->left = (*x)elseggp->right = (*x)}

1.3.2 Exemple cu operatii in arbori Splay

1.3.3.1 Insert

Figura 4.a prezintă arbore splay iniţială în care acesta va fi efectuat de introducerea tasta 4. La primul pas, cheie 4 se inserează ca nod frunză. Figura 4.b prezintă forma de arbore splay după setarea nod cu tasta 4 ca copilul a plecat de nod cu tasta 5. După acest pas nu vor fi efectuate, care va împinge nodul cu tasta 4 până la poziţia de radacina.Figura 4.c prezintă arbore splay după efectuarea unei zig-zag rotaţie pe nod cu tasta 4. Efectul acestei rotaţii este ridicarea nodului cu cheie 4 cu două niveluri.Figura 4.d prezintă arbore splay după efectuarea unei zig rotaţie pe nod cu tasta 4. Efectul deaceastă rotaţie este ridicarea nodul cu cheie 4 cu un nivel în poziţia rădăcină.

Fig. 4

1.3.3.2 Join

Există doi arbori splay. Acestea sunt prezentati în figurile 5.a şi 5.b. Cifra 5.c. prezintă rezultatele unui arbore. Primul pas este de a efectua o operaţiune de membru pe cea mai mare cheie din arborele splay. Aceasta operaţiunea va aduce nodul cu cheia 15 în poziţia rădăcină de arbore splay primul. Al doilea pas este de a lega rădăcină de arbore splay doua astefel incat copilul din dreapta obţinut anterior sa devina rădăcină de arbore dupa inlaturarea primului. După acest pasvom avea arborele din figura 5.c.

Fig.5

1.3.3.2 Split

Se da un arbore splay şi o cheie care îi aparţine. Figura 6.a prezintă acest arbore splay iniţial şi cheia de divizare este de 6. Funcţia split va produce doi arbori splay: unul cu taste mai mici de 6 şi unul cu taste mai mari de 6.Primul pas este de a efectua o operaţiune MEMBRE pe nod cu cheie 6. După această operaţie efectuata arborele splay va arata ca in figura 6.b.Odată ce cheia de divizare a fost înălţat ca root nod copac necesare splay la stânga şi la dreapta arbore splay sunt reprezentate de copiii stânga şi la dreapta de la rădăcină.

a)

b)

1.3.3.2 Delete

Se da un arbore splay asa cum este prezentat în figura 7.a. Sarcina este de a şterge nodul cu cheia 63 din arborele splay. Primul pas este de a efectua o operaţiune MEMBRE pe nod cu cheie 63. Acest pas va aduce nodul cu cheie 63 ca nod rădăcină. După această operaţie arborele splay va arăta ca în figura 7.b