Els arbres Splay són els arbres de cerca binaris autoequilibrats o autoajustats. En altres paraules, podem dir que els arbres splay són les variants dels arbres de cerca binaris. El requisit previ per als arbres de desplegament que hem de conèixer sobre els arbres de cerca binaris.
Com ja sabem, la complexitat temporal d'un arbre de cerca binari en tots els casos. La complexitat temporal d'un arbre de cerca binari en el cas mitjà és O (inici de sessió) i la complexitat temporal en el pitjor dels casos és O(n). En un arbre de cerca binari, el valor del subarbre esquerre és més petit que el node arrel i el valor del subarbre dret és més gran que el node arrel; en aquest cas, la complexitat temporal seria O (inici de sessió) . Si l'arbre binari està inclinat a l'esquerra o a la dreta, aleshores la complexitat del temps seria O(n). Per limitar la sessió, el AVL i arbre vermell-negre va entrar a la imatge, tenint O (inici de sessió ) complexitat temporal de totes les operacions en tots els casos. També podem millorar aquesta complexitat temporal fent implementacions més pràctiques, per tant, el nou Tree Què és un Splay Tree?
Un arbre splay és un arbre autoequilibrat, però Aleshores, els arbres AVL i Red-Black també són arbres autoequilibrats. Què fa que l'arbre splay sigui únic en dos arbres. Té una propietat addicional que el fa únic és el desplegament.
Un arbre splay conté les mateixes operacions que a Arbre de cerca binari , és a dir, Inserció, supressió i cerca, però també conté una operació més, és a dir, desplegar. Tan. totes les operacions de l'arbre de desplegament són seguides per desplegament.
Els arbres Splay no són arbres estrictament equilibrats, però són arbres aproximadament equilibrats. Entenem l'operació de cerca a l'arbre de desplegament.
Suposem que volem cercar 7 elements a l'arbre, que es mostra a continuació:
Per cercar qualsevol element de l'arbre de desplegament, primer, realitzarem l'operació estàndard de cerca binària de l'arbre. Com 7 és menor que 10, arribarem a l'esquerra del node arrel. Després de realitzar l'operació de cerca, hem de realitzar el desplegament. Aquí el desplegament significa que l'operació que estem realitzant en qualsevol element hauria de convertir-se en el node arrel després de realitzar alguns reordenaments. La reordenació de l'arbre es farà mitjançant les rotacions.
Nota: l'arbre de desplegament es pot definir com l'arbre autoajustat en el qual qualsevol operació realitzada sobre l'element reordenaria l'arbre de manera que l'element sobre el qual s'ha realitzat l'operació esdevingui el node arrel de l'arbre.
Rotacions
Hi ha sis tipus de rotacions que s'utilitzen per desplegar:
- Rotació en zig (giració dreta)
- Rotació Zag (giració esquerra)
- Zig-zag (zig seguit de zag)
- Zag zig (Zag seguit de zig)
- Zig zig (dues rotacions a la dreta)
- Zag zag (dues rotacions a l'esquerra)
Factors necessaris per seleccionar un tipus de rotació
Els factors que s'utilitzen per seleccionar un tipus de rotació són els següents:
- El node que estem intentant girar té un avi?
- El node és fill esquerre o dret del pare?
- El node és fill esquerre o dret de l'avi?
Casos per a les Rotacions
Cas 1: Si el node no té un avi, i si és el fill dret del pare, llavors fem la rotació a l'esquerra; en cas contrari, es realitza la rotació correcta.
Cas 2: Si el node té un avi, es basa en els escenaris següents; la rotació es realitzarà:
Escenari 1: Si el node és el dret del pare i el pare també és el dret del seu pare, aleshores zig zig dreta rotació dreta es realitza.
Escenari 2: Si el node està a l'esquerra d'un pare, però el pare és a la dreta del seu pare, aleshores zig-zag rotació dreta esquerra es realitza.
Escenari 3: Si el node és el dret del pare i el pare és el dret del seu pare, aleshores zig zig esquerra rotació esquerra es realitza.
Escenari 4: Si el node és a la dreta d'un pare, però el pare és a l'esquerra del seu pare, aleshores rotació en zig-zag dreta-esquerra es realitza.
Ara, anem a entendre les rotacions anteriors amb exemples.
Per reordenar l'arbre, hem de fer algunes rotacions. A continuació es mostren els tipus de rotacions a l'arbre de desplegament:
Les rotacions en zig s'utilitzen quan l'element que s'ha de cercar és un node arrel o el fill d'un node arrel (és a dir, el fill esquerre o dret).
A continuació es mostren els casos que poden existir a l'arbre splay durant la cerca:
Cas 1: Si l'element de cerca és un node arrel de l'arbre.
Cas 2: Si l'element de cerca és un fill del node arrel, hi haurà els dos escenaris:
- Si el nen és un nen esquerre, es realitzaria la rotació dreta, coneguda com a rotació en zig a la dreta.
- Si el nen és un nen dret, es realitzaria la rotació a l'esquerra, coneguda com a rotació en zig a l'esquerra.
Vegem els dos escenaris anteriors mitjançant un exemple.
Considereu l'exemple següent:
A l'exemple anterior, hem de cercar 7 elements a l'arbre. Seguirem els passos següents:
Pas 1: Primer, comparem 7 amb un node arrel. Com que 7 és menor que 10, és un fill esquerre del node arrel.
Pas 2: Un cop trobat l'element, realitzarem el desplegament. La rotació correcta es realitza de manera que 7 es converteixi en el node arrel de l'arbre, tal com es mostra a continuació:
Considerem un altre exemple.
A l'exemple anterior, hem de cercar 20 elements a l'arbre. Seguirem els passos següents:
Pas 1: Primer, comparem 20 amb un node arrel. Com 20 és més gran que el node arrel, per tant és un fill dret del node arrel.
Pas 2: Un cop trobat l'element, realitzarem el desplegament. La rotació a l'esquerra es realitza de manera que l'element 20 es converteixi en el node arrel de l'arbre.
De vegades es produeix la situació quan l'element a cercar té un pare i un avi. En aquest cas, hem de realitzar quatre girs per a l'abraçament.
Entenem aquest cas a través d'un exemple.
Suposem que hem de cercar 1 element a l'arbre, que es mostra a continuació:
Pas 1: Primer, hem de realitzar una operació estàndard de cerca BST per cercar l'element 1. Com 1 és menor que 10 i 7, per tant estarà a l'esquerra del node 7. Per tant, l'element 1 té un pare, és a dir, 7, així com un avi, és a dir, 10.
Pas 2: En aquest pas, hem de realitzar el desplegament. Hem de fer el node 1 com a node arrel amb l'ajuda d'algunes rotacions. En aquest cas, no podem realitzar simplement una rotació en zig o zag; hem d'implementar la rotació en zig zig.
Per tal de fer el node 1 com a node arrel, hem de realitzar dues rotacions a la dreta conegudes com a rotacions zig zig. Quan fem la rotació correcta, el 10 es mourà cap avall i el node 7 pujarà com es mostra a la figura següent:
De nou, farem una rotació en zig a la dreta, el node 7 es mourà cap avall i el node 1 pujarà com es mostra a continuació:
Com observem a la figura anterior que el node 1 s'ha convertit en el node arrel de l'arbre; per tant, la cerca s'ha completat.
Suposem que volem cercar 20 a l'arbre següent.
Per cercar 20, hem de fer dues rotacions a l'esquerra. A continuació es mostren els passos necessaris per cercar el node 20:
Pas 1: Primer, realitzem l'operació estàndard de cerca BST. Com 20 és més gran que 10 i 15, serà a la dreta del node 15.
Pas 2: El segon pas és realitzar el desplegament. En aquest cas, es realitzarien dues rotacions a l'esquerra. En la primera rotació, el node 10 es mourà cap avall, i el node 15 es mourà cap amunt com es mostra a continuació:
En la segona rotació a l'esquerra, el node 15 es mourà cap avall i el node 20 es converteix en el node arrel de l'arbre, tal com es mostra a continuació:
Com hem observat que es fan dues rotacions a l'esquerra; per això es coneix com a rotació a l'esquerra en zig zig.
Fins ara, hem llegit que tant pares com avis estan en relació RR o LL. Ara, veurem la relació RL o LR entre el pare i l'avi.
Entenem aquest cas a través d'un exemple.
Suposem que volem cercar 13 elements a l'arbre que es mostra a continuació:
Pas 1: En primer lloc, realitzem una operació de cerca BST estàndard. Com 13 és més gran que 10 però menor que 15, el node 13 serà el fill esquerre del node 15.
Pas 2: Com que el node 13 es troba a l'esquerra del 15 i el node 15 es troba a la dreta del node 10, existeix una relació RL. Primer, fem la rotació correcta al node 15, i el 15 es mourà cap avall i el node 13 pujarà, tal com es mostra a continuació:
Tot i així, el node 13 no és el node arrel, i el 13 es troba a la dreta del node arrel, de manera que realitzarem una rotació a l'esquerra coneguda com a rotació zag. El node 10 es mourà cap avall i el 13 es converteix en el node arrel tal com es mostra a continuació:
Com podem observar a l'arbre anterior que el node 13 s'ha convertit en el node arrel; per tant, la cerca s'ha completat. En aquest cas, primer hem realitzat la rotació en zig i després la rotació en zag; per tant, es coneix com a rotació en zig-zag.
Entenem aquest cas a través d'un exemple.
Suposem que volem cercar 9 elements a l'arbre, que es mostra a continuació:
Pas 1: Primer, realitzem l'operació estàndard de cerca BST. Com 9 és menor que 10 però més gran que 7, serà el fill correcte del node 7.
Pas 2: Com que el node 9 es troba a la dreta del node 7 i el node 7 es troba a l'esquerra del node 10, existeix una relació LR. Primer, realitzem la rotació a l'esquerra al node 7. El node 7 es mourà cap avall i el node 9 es mourà cap amunt com es mostra a continuació:
Tot i així, el node 9 no és un node arrel, i el 9 es troba a l'esquerra del node arrel, de manera que realitzarem la rotació dreta coneguda com a rotació en zig. Després de realitzar la rotació correcta, el node 9 es converteix en el node arrel, tal com es mostra a continuació:
Com podem observar a l'arbre anterior que el node 13 és un node arrel; per tant, la cerca s'ha completat. En aquest cas, primer hem realitzat la rotació en zig (giració a l'esquerra), i després es realitza la rotació en zig (rotació dreta), per la qual cosa es coneix com a rotació en zig zag.
Avantatges de l'arbre Splay
- A l'arbre splay, no necessitem emmagatzemar la informació addicional. En canvi, als arbres AVL, hem d'emmagatzemar el factor d'equilibri de cada node que requereix espai addicional, i els arbres vermell-negre també requereixen emmagatzemar un bit addicional d'informació que denota el color del node, ja sigui vermell o negre.
- És el tipus més ràpid d'arbre de cerca binària per a diverses aplicacions pràctiques. S'utilitza en Compiladors de Windows NT i GCC .
- Proporciona un millor rendiment, ja que els nodes d'accés freqüent s'aproparan al node arrel, de manera que es pot accedir ràpidament als elements als arbres de desplegament. S'utilitza en la implementació de la memòria cau ja que les dades a les quals s'ha accedit recentment s'emmagatzemen a la memòria cau de manera que no necessitem anar a la memòria per accedir a les dades, i triga menys temps.
Inconvenient de l'arbre de Splay
El principal inconvenient de l'arbre d'esplanada seria que els arbres no estan estrictament equilibrats, és a dir, estan aproximadament equilibrats. De vegades, els arbres de desplegament són lineals, de manera que necessitarà complexitat de temps O(n).
Operació d'inserció a l'arbre de Splay
En el inserció operació, primer inserim l'element a l'arbre i després realitzem l'operació de desplegament sobre l'element inserit.
15, 10, 17, 7
Pas 1: Primer, inserim el node 15 a l'arbre. Després de la inserció, hem de realitzar el desplegament. Com que 15 és un node arrel, no cal que realitzem l'allargament.
Pas 2: El següent element és 10. Com 10 és menor que 15, el node 10 serà el fill esquerre del node 15, tal com es mostra a continuació:
Ara, actuem desplegant . Per fer 10 com a node arrel, realitzarem la rotació correcta, tal com es mostra a continuació:
Pas 3: El següent element és 17. Com 17 és més gran que 10 i 15, es convertirà en el fill dret del node 15.
Ara, farem el splaying. Com que el 17 té un pare i un avis, farem rotacions en zig zig.
A la figura anterior, podem observar que 17 es converteix en el node arrel de l'arbre; per tant, la inserció s'ha completat.
Pas 4: El següent element és 7. Com que 7 és menor que 17, 15 i 10, el node 7 quedarà fill de 10.
Ara, hem d'escampar l'arbre. Com que el 7 té un pare i un avis, farem dues rotacions a la dreta com es mostra a continuació:
Tot i així, el node 7 no és un node arrel, és un fill esquerre del node arrel, és a dir, 17. Per tant, hem de fer una rotació més a la dreta per fer que el node 7 sigui un node arrel tal com es mostra a continuació:
Algorisme per a l'operació d'inserció
Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n)
En l'algorisme anterior, T és l'arbre i n és el node que volem inserir. Hem creat una variable temporal que conté l'adreça del node arrel. Executarem el bucle while fins que el valor de temp es converteixi en NULL.
Un cop finalitzada la inserció, es realitzarà el desplegament
Algorisme per al funcionament de Splaying
Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y
En la implementació anterior, x és el node sobre el qual es realitza la rotació, mentre que y és el fill esquerre del node x.
Implementació de left.rotation(T, x)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
En la implementació anterior, x és el node sobre el qual es realitza la rotació i y és el fill dret del node x.
Supressió a l'arbre de Splay
Com sabem que els arbres de desplegament són les variants de l'arbre de cerca binari, per tant l'operació de supressió a l'arbre de desplegament seria semblant a la BST, però l'única diferència és que l'operació de supressió és seguida en els arbres de desplegament per l'operació de desplegament.
Tipus d'eliminacions:
Hi ha dos tipus d'eliminacions als arbres de desplegament:
- Extensió de baix a dalt
- Extensió de dalt a baix
Extensió de baix a dalt
En el desplegament de baix a dalt, primer eliminem l'element de l'arbre i després realitzem el desplegament al node suprimit.
Entenem l'eliminació a l'arbre de Splay.
Suposem que volem suprimir 12, 14 de l'arbre que es mostra a continuació:
sistemes operatius mac
- En primer lloc, simplement realitzem l'operació estàndard de supressió BST per eliminar 12 elements. Com que 12 és un node fulla, simplement eliminem el node de l'arbre.
L'eliminació encara no s'ha completat. Hem de desplegar el pare del node suprimit, és a dir, 10. Hem de realitzar Splay (10) a l'arbre. Com podem observar a l'arbre anterior que 10 es troba a la dreta del node 7, i el node 7 es troba a l'esquerra del node 13. Per tant, primer, fem la rotació a l'esquerra al node 7 i després fem la rotació dreta al node. 13, com es mostra a continuació:
Tot i així, el node 10 no és un node arrel; el node 10 és el fill esquerre del node arrel. Per tant, hem de fer la rotació correcta al node arrel, és a dir, 14 per fer del node 10 un node arrel tal com es mostra a continuació:
- Ara, hem de suprimir l'element 14 de l'arbre, que es mostra a continuació:
Com sabem que no podem esborrar simplement el node intern. Reemplaçarem el valor del node utilitzant predecessor de l'ordre o successor en ordre . Suposem que utilitzem un successor d'ordre en què substituïm el valor pel valor més baix que existeix al subarbre dret. El valor més baix del subarbre dret del node 14 és 15, de manera que substituïm el valor 14 per 15. Atès que el node 14 es converteix en el node fulla, simplement podem eliminar-lo tal com es mostra a continuació:
Tot i així, l'eliminació no s'ha completat. Hem de realitzar una operació més, és a dir, splaying en què hem de fer que el pare del node suprimit sigui el node arrel. Abans de la supressió, el pare del node 14 era el node arrel, és a dir, 10, de manera que hem de realitzar qualsevol desplegament en aquest cas.
Extensió de dalt a baix
En el desplegament de dalt a baix, primer realitzem el desplegament sobre el qual s'ha de realitzar la supressió i després suprimim el node de l'arbre. Un cop esborrat l'element, realitzarem l'operació d'unió.
Entenem el desplegament de dalt a baix a través d'un exemple.
Suposem que volem suprimir 16 de l'arbre que es mostra a continuació:
Pas 1: En el desplegament de dalt a baix, primer realitzem el desplegament al node 16. El node 16 té tant pare com avi. El node 16 es troba a la dreta del seu pare i el node pare també està a la dreta del seu pare, de manera que aquesta és una situació de zag zag. En aquest cas, primer, realitzarem la rotació a l'esquerra al node 13 i després al 14 tal com es mostra a continuació:
El node 16 encara no és un node arrel, i és un fill dret del node arrel, de manera que hem de fer la rotació a l'esquerra al node 12 per fer que el node 16 sigui un node arrel.
Un cop el node 16 es converteixi en un node arrel, suprimirem el node 16 i obtindrem dos arbres diferents, és a dir, el subarbre esquerre i el subarbre dret com es mostra a continuació:
Com sabem que els valors del subarbre esquerre sempre són menors que els valors del subarbre dret. L'arrel del subarbre esquerre és 12 i l'arrel del subarbre dret és 17. El primer pas és trobar l'element màxim al subarbre esquerre. Al subarbre esquerre, l'element màxim és 15, i després hem de realitzar l'operació de desplegament a 15.
Com podem observar a l'arbre anterior que l'element 15 té un pare i un avi. Un node es troba a la dreta del seu pare i el node pare també està a la dreta del seu pare, de manera que hem de fer dues rotacions a l'esquerra per fer del node 15 un node arrel tal com es mostra a continuació:
Després de realitzar dues rotacions a l'arbre, el node 15 es converteix en el node arrel. Com podem veure, el fill dret del 15 és NULL, així que adjuntem el node 17 a la part dreta del 15 com es mostra a continuació, i aquesta operació es coneix com a uneix-te funcionament.
Nota: Si l'element no està present a l'arbre de desplegament, que s'ha de suprimir, es realitzarà la desplegament. El desplegament es realitzaria a l'últim element accedit abans d'arribar al NULL.
Algoritme de l'operació Suprimeix
If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root
En l'algorisme anterior, primer comprovem si l'arrel és nul·la o no; si l'arrel és NULL vol dir que l'arbre està buit. Si l'arbre no està buit, realitzarem l'operació de desplegament sobre l'element que s'ha d'esborrar. Un cop finalitzada l'operació de desplegament, compararem les dades de l'arrel amb l'element que s'ha d'esborrar; si tots dos no són iguals vol dir que l'element no està present a l'arbre. Si són iguals, es poden donar els casos següents:
Cas 1 : L'esquerra de l'arrel és NULL, la dreta de l'arrel es converteix en el node arrel.
Cas 2 : Si existeixen tant l'esquerra com la dreta, aleshores desplegarem l'element màxim al subarbre esquerre. Quan s'ha completat el desplegament, l'element màxim es converteix en l'arrel del subarbre esquerre. El subarbre dret es convertiria en el fill dret de l'arrel del subarbre esquerre.