Splay-trær er de selvbalanserende eller selvjusterte binære søketrærne. Med andre ord kan vi si at splay-trærne er variantene av de binære søketrærne. Forutsetningen for splay-trærne som vi bør vite om de binære søketrærne.
Som vi allerede vet, er tidskompleksiteten til et binært søketre i alle tilfeller. Tidskompleksiteten til et binært søketre i gjennomsnittstilfellet er O(logn) og tidskompleksiteten i verste fall er O(n). I et binært søketre er verdien av det venstre undertreet mindre enn rotnoden, og verdien til det høyre undertreet er større enn rotnoden; i et slikt tilfelle vil tidskompleksiteten være O(logn) . Hvis det binære treet er venstre- eller høyreskjevt, vil tidskompleksiteten være O(n). For å begrense skjevheten AVL og Rød-Sort tre kom inn i bildet, har O(logn ) tidskompleksitet for alle operasjonene i alle sakene. Vi kan også forbedre denne tidskompleksiteten ved å gjøre mer praktiske implementeringer, så det nye Treet What is a Splay Tree?
Et splaytre er et selvbalanserende tre, men AVL og Rød-Sorte trær er også selvbalanserende trær da. Hva gjør splaytreet unikt to trær. Den har en ekstra egenskap som gjør den unik er spredning.
Et splay-tre inneholder de samme operasjonene som en Binært søketre , dvs. innsetting, sletting og søking, men den inneholder også en operasjon til, dvs. splaying. Så. alle operasjonene i splay-treet etterfølges av splaying.
Splaytrær er ikke strengt balanserte trær, men de er grovt balanserte trær. La oss forstå søkeoperasjonen i splay-treet.
Anta at vi vil søke etter 7 element i treet, som er vist nedenfor:
For å søke i et hvilket som helst element i splaytreet, vil vi først utføre den standard binære søketreoperasjonen. Siden 7 er mindre enn 10, vil vi komme til venstre for rotnoden. Etter å ha utført søkeoperasjonen, må vi utføre splaying. Her betyr splaying at operasjonen vi utfører på ethvert element skal bli rotnoden etter å ha utført noen omorganiseringer. Omorganiseringen av treet vil skje gjennom rotasjonene.
Merk: Splaytreet kan defineres som det selvjusterte treet der enhver operasjon utført på elementet vil omorganisere treet slik at elementet som operasjonen er utført på blir rotnoden til treet.
Rotasjoner
Det er seks typer rotasjoner som brukes for splaying:
- Zig-rotasjon (høyre rotasjon)
- Zag-rotasjon (venstrerotasjon)
- Zig zag (sikk etterfulgt av zag)
- Zag zig (Zag etterfulgt av zig)
- Zig zig (to høyre rotasjoner)
- Zag Zag (to venstre rotasjoner)
Faktorer som kreves for å velge en type rotasjon
Følgende er faktorene som brukes for å velge en type rotasjon:
- Har noden som vi prøver å rotere en besteforeldre?
- Er noden venstre eller høyre barn til forelderen?
- Er noden venstre eller høyre barn til besteforelderen?
Saker for Rotasjonene
Tilfelle 1: Hvis noden ikke har en besteforeldre, og hvis det er det høyre barnet til forelderen, utfører vi venstrerotasjonen; ellers utføres riktig rotasjon.
Tilfelle 2: Hvis noden har en besteforeldre, så basert på følgende scenarier; rotasjonen vil bli utført:
Scenario 1: Hvis noden er retten til forelderen og forelderen har også rett til forelderen sin, da sikk sikk høyre høyre rotasjon er utført.
Scenario 2: Hvis noden er til venstre for en forelder, men forelderen er til høyre for forelderen, da sikksakk høyre venstre rotasjon er utført.
Scenario 3: Hvis noden er høyre for forelderen og forelderen har rett til forelderen, da sikk sikk venstre rotasjon til venstre er utført.
Scenario 4: Hvis noden er til høyre for en forelder, men forelderen er til venstre for forelderen, da sikksakk høyre-venstre rotasjon er utført.
La oss nå forstå rotasjonene ovenfor med eksempler.
For å omorganisere treet, må vi utføre noen rotasjoner. Følgende er typene rotasjoner i splaytreet:
Sikk-rotasjonene brukes når elementet som skal søkes i enten er en rotnode eller barnet til en rotnode (dvs. venstre eller høyre barn).
Følgende er tilfellene som kan eksistere i splaytreet mens du søker:
Tilfelle 1: Hvis søkeelementet er en rotnode i treet.
Tilfelle 2: Hvis søkeelementet er et barn av rotnoden, vil de to scenariene være der:
- Hvis barnet er et venstrebarn, vil høyrerotasjonen bli utført, kjent som en zig høyrerotasjon.
- Hvis barnet er et høyre barn, vil venstre rotasjon bli utført, kjent som en sikk venstre rotasjon.
La oss se på de to scenariene ovenfor gjennom et eksempel.
Tenk på eksemplet nedenfor:
I eksemplet ovenfor må vi søke etter 7 element i treet. Vi følger trinnene nedenfor:
Trinn 1: Først sammenligner vi 7 med en rotnode. Siden 7 er mindre enn 10, så er det et venstre underordnet av rotnoden.
Steg 2: Når elementet er funnet, vil vi utføre splaying. Høyre rotasjon utføres slik at 7 blir rotnoden til treet, som vist nedenfor:
La oss vurdere et annet eksempel.
I eksemplet ovenfor må vi søke etter 20 element i treet. Vi følger trinnene nedenfor:
Trinn 1: Først sammenligner vi 20 med en rotnode. Ettersom 20 er større enn rotnoden, så er det et høyre underordnet av rotnoden.
Steg 2: Når elementet er funnet, vil vi utføre splaying. Venstrerotasjonen utføres slik at 20 element blir rotnoden til treet.
Noen ganger oppstår situasjonen når gjenstanden som skal søkes i har en forelder så vel som en besteforeldre. I dette tilfellet må vi utføre fire rotasjoner for splaying.
La oss forstå denne saken gjennom et eksempel.
Anta at vi må søke 1 element i treet, som er vist nedenfor:
Trinn 1: Først må vi utføre en standard BST-søkeoperasjon for å søke i 1-elementet. Ettersom 1 er mindre enn 10 og 7, vil den være til venstre for noden 7. Derfor har element 1 en forelder, dvs. 7, så vel som en besteforeldre, dvs. 10.
Steg 2: I dette trinnet må vi utføre splaying. Vi må lage node 1 som en rotnode ved hjelp av noen rotasjoner. I dette tilfellet kan vi ikke bare utføre en sikk- eller zag-rotasjon; vi må implementere sikk-sikk-rotasjon.
For å gjøre node 1 til en rotnode, må vi utføre to høyrerotasjoner kjent som sikksikkrotasjoner. Når vi utfører riktig rotasjon vil 10 bevege seg nedover, og node 7 vil komme oppover som vist i figuren nedenfor:
Igjen vil vi utføre zig høyre rotasjon, node 7 vil bevege seg nedover, og node 1 vil komme oppover som vist nedenfor:
Som vi observerer i figuren ovenfor at node 1 har blitt rotnoden til treet; derfor er søket fullført.
Anta at vi ønsker å søke 20 i treet nedenfor.
For å søke 20, må vi utføre to venstrerotasjoner. Følgende er trinnene som kreves for å søke i 20 node:
Trinn 1: Først utfører vi standard BST-søkeoperasjonen. Siden 20 er større enn 10 og 15, vil den være til høyre for node 15.
Steg 2: Det andre trinnet er å utføre splaying. I dette tilfellet vil to venstrerotasjoner bli utført. I den første rotasjonen vil node 10 bevege seg nedover, og node 15 vil bevege seg oppover som vist nedenfor:
I den andre venstrerotasjonen vil node 15 bevege seg nedover, og node 20 blir rotnoden til treet, som vist nedenfor:
Som vi har observert at det utføres to venstrerotasjoner; så det er kjent som en sikk sikk venstre rotasjon.
Til nå har vi lest at både foreldre og besteforeldre er enten i RR- eller LL-forhold. Nå vil vi se RL- eller LR-forholdet mellom forelderen og besteforelderen.
La oss forstå denne saken gjennom et eksempel.
Anta at vi vil søke etter 13 element i treet som er vist nedenfor:
Trinn 1: Først utfører vi standard BST-søkeoperasjon. Siden 13 er større enn 10, men mindre enn 15, vil node 13 være det venstre barnet til node 15.
Steg 2: Siden node 13 er til venstre for 15 og node 15 er til høyre for node 10, så eksisterer RL-relasjonen. Først utfører vi riktig rotasjon på node 15, og 15 vil bevege seg nedover, og node 13 vil komme oppover, som vist nedenfor:
Node 13 er likevel ikke rotnoden, og 13 er til høyre for rotnoden, så vi vil utføre venstrerotasjon kjent som en zag-rotasjon. Noden 10 vil bevege seg nedover, og 13 blir rotnoden som vist nedenfor:
Som vi kan observere i treet ovenfor, har node 13 blitt rotnoden; derfor er søket fullført. I dette tilfellet har vi først utført sikkrotasjon og deretter zagrotasjon; så det er kjent som en sikksakk-rotasjon.
La oss forstå denne saken gjennom et eksempel.
Anta at vi vil søke etter 9 element i treet, som er vist nedenfor:
Trinn 1: Først utfører vi standard BST-søkeoperasjonen. Siden 9 er mindre enn 10, men større enn 7, vil det være det riktige barnet til node 7.
Steg 2: Siden node 9 er til høyre for node 7, og node 7 er til venstre for node 10, så eksisterer LR-relasjonen. Først utfører vi venstrerotasjonen på node 7. Node 7 vil bevege seg nedover, og node 9 beveger seg oppover som vist nedenfor:
Node 9 er fortsatt ikke en rotnude, og 9 er til venstre for rotnoden, så vi vil utføre høyrerotasjonen kjent som sikkrotasjon. Etter å ha utført riktig rotasjon, blir node 9 rotnoden, som vist nedenfor:
Som vi kan observere i treet ovenfor at node 13 er en rotnode; derfor er søket fullført. I dette tilfellet har vi først utført zag-rotasjon (venstrerotasjon), og deretter zig-rotasjon (høyre rotasjon), så det er kjent som en zag-sikk-rotasjon.
Fordeler med Splay tree
- I splaytreet trenger vi ikke å lagre den ekstra informasjonen. I kontrast, i AVL-trær, må vi lagre balansefaktoren til hver node som krever ekstra plass, og rød-svarte trær krever også å lagre en ekstra bit informasjon som angir fargen på noden, enten rød eller svart.
- Det er den raskeste typen binært søketre for ulike praktiske bruksområder. Den brukes i Windows NT og GCC kompilatorer .
- Det gir bedre ytelse ettersom de ofte åpnede nodene vil bevege seg nærmere rotnoden, noe som gjør at elementene kan nås raskt i splay-trær. Den brukes i cache-implementeringen da de nylig åpnede dataene lagres i cachen slik at vi ikke trenger å gå til minnet for å få tilgang til dataene, og det tar kortere tid.
Ulempen med Splay tree
Den største ulempen med splaytreet vil være at trær ikke er strengt balansert, dvs. de er grovt balansert. Noen ganger er splay-trærne lineære, så det vil ta O(n) tidskompleksitet.
Innsettingsoperasjon i Splay-treet
I innsetting operasjon, setter vi først inn elementet i treet og utfører deretter sprøyteoperasjonen på det innsatte elementet.
15, 10, 17, 7
Trinn 1: Først setter vi inn node 15 i treet. Etter innsetting må vi utføre splaying. Siden 15 er en rotnode, trenger vi ikke å utføre splaying.
Steg 2: Det neste elementet er 10. Ettersom 10 er mindre enn 15, vil node 10 være venstre underordnede av node 15, som vist nedenfor:
Nå opptrer vi splaying . For å lage 10 som en rotnode, vil vi utføre riktig rotasjon, som vist nedenfor:
Trinn 3: Det neste elementet er 17. Ettersom 17 er større enn 10 og 15, vil det bli det riktige barnet til node 15.
Nå skal vi utføre splaying. Ettersom 17 har en forelder så vel som en besteforeldre, så vil vi utføre sikk-sikk-rotasjoner.
I figuren ovenfor kan vi observere at 17 blir rotnoden til treet; derfor er innsettingen fullført.
Trinn 4: Det neste elementet er 7. Siden 7 er mindre enn 17, 15 og 10, vil node 7 være underordnet 10.
Nå må vi kaste treet. Siden 7 har en forelder så vel som en besteforeldre, vil vi utføre to høyrerotasjoner som vist nedenfor:
Node 7 er fortsatt ikke en rotnude, den er et venstre underordnet av rotnoden, det vil si 17. Så vi må utføre en høyrerotasjon til for å gjøre node 7 til en rotnode som vist nedenfor:
Algoritme for innsettingsoperasjon
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)
I algoritmen ovenfor er T treet og n er noden vi ønsker å sette inn. Vi har laget en temp-variabel som inneholder adressen til rotnoden. Vi kjører while-løkken til verdien av temp blir NULL.
Når innsettingen er fullført, vil splaying bli utført
Algoritme for Splaying-operasjon
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
I implementeringen ovenfor er x noden som rotasjonen utføres på, mens y er det venstre barnet til noden x.
Implementering av left.rotation(T, x)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
I implementeringen ovenfor er x noden som rotasjonen utføres på, og y er det høyre barnet til noden x.
Sletting i Splay-treet
Siden vi vet at splay-trær er variantene av det binære søketreet, vil sletteoperasjonen i splay-treet være lik BST, men den eneste forskjellen er at sletteoperasjonen følges i splay-trær av spre-operasjonen.
Typer slettinger:
Det er to typer slettinger i splay-trærne:
- Spredning nedenfra og opp
- Spredning ovenfra og ned
Spredning nedenfra og opp
I bottom-up splaying sletter vi først elementet fra treet og deretter utfører vi splayingen på den slettede noden.
La oss forstå slettingen i Splay-treet.
Anta at vi ønsker å slette 12, 14 fra treet vist nedenfor:
streng reversering i c
- Først utfører vi bare standard BST-slettingsoperasjonen for å slette 12 element. Ettersom 12 er en bladnode, så sletter vi ganske enkelt noden fra treet.
Slettingen er fortsatt ikke fullført. Vi må spre overordnet til den slettede noden, dvs. 10. Vi må utføre Splay(10) på treet. Som vi kan observere i treet ovenfor at 10 er til høyre for node 7, og node 7 er til venstre for node 13. Så først utfører vi venstrerotasjonen på node 7 og deretter utfører vi høyrerotasjonen på noden 13, som vist nedenfor:
Node 10 er likevel ikke en rotnode; node 10 er det venstre barnet til rotnoden. Så vi må utføre riktig rotasjon på rotnoden, det vil si 14 for å gjøre node 10 til en rotnode som vist nedenfor:
- Nå må vi slette 14-elementet fra treet, som er vist nedenfor:
Som vi vet at vi ikke bare kan slette den interne noden. Vi vil erstatte verdien av noden enten ved å bruke inorder forgjenger eller etterfølger i rekkefølge . Anta at vi bruker inorder successor der vi erstatter verdien med den laveste verdien som finnes i det høyre undertreet. Den laveste verdien i det høyre undertreet til node 14 er 15, så vi erstatter verdien 14 med 15. Siden node 14 blir bladnoden, så kan vi ganske enkelt slette den som vist nedenfor:
Likevel er slettingen ikke fullført. Vi må utføre en operasjon til, dvs. splaying der vi må gjøre forelderen til den slettede noden som rotnoden. Før sletting var forelderen til node 14 rotnoden, dvs. 10, så vi trenger å utføre spredning i dette tilfellet.
Spredning ovenfra og ned
I top-down splaying utfører vi først splayingen som slettingen skal utføres på og sletter deretter noden fra treet. Når elementet er slettet, vil vi utføre sammenføyningsoperasjonen.
La oss forstå ovenfra og ned spraying gjennom et eksempel.
Anta at vi ønsker å slette 16 fra treet som er vist nedenfor:
Trinn 1: I top-down splaying utfører vi først splaying på node 16. Node 16 har både foreldre og besteforeldre. Noden 16 er til høyre for sin overordnede og overordnede node er også til høyre for sin overordnede, så dette er en zag zag-situasjon. I dette tilfellet vil vi først utføre venstrerotasjonen på node 13 og deretter 14 som vist nedenfor:
Noden 16 er fortsatt ikke en rotnode, og den er et høyre barn av rotnoden, så vi må utføre venstrerotasjon på noden 12 for å gjøre node 16 til en rotnode.
Når noden 16 blir en rotnode, vil vi slette noden 16 og vi vil få to forskjellige trær, dvs. venstre undertre og høyre undertre som vist nedenfor:
Som vi vet at verdiene til venstre undertre alltid er mindre enn verdiene til høyre undertre. Roten til venstre undertre er 12 og roten til høyre undertre er 17. Det første trinnet er å finne maksimumselementet i venstre undertre. I det venstre undertreet er det maksimale elementet 15, og så må vi utføre spredningsoperasjon på 15.
Som vi kan observere i treet ovenfor at elementet 15 har en forelder så vel som en besteforeldre. En node er til høyre for sin overordnede, og den overordnede node er også til høyre for sin overordnede, så vi må utføre to venstrerotasjoner for å gjøre node 15 til en rotnode som vist nedenfor:
Etter å ha utført to rotasjoner på treet, blir node 15 rotnoden. Som vi kan se er det riktige barnet av 15 NULL, så vi fester node 17 på høyre del av 15 som vist nedenfor, og denne operasjonen er kjent som en bli med operasjon.
Merk: Hvis elementet ikke er tilstede i splaytreet, som skal slettes, vil splaying bli utført. Spredningen vil bli utført på det sist åpnede elementet før du når NULL.
Algoritme for sletteoperasjon
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
I algoritmen ovenfor sjekker vi først om roten er Null eller ikke; hvis roten er NULL betyr det at treet er tomt. Hvis treet ikke er tomt, vil vi utføre spleiseoperasjonen på elementet som skal slettes. Når splayoperasjonen er fullført, vil vi sammenligne rotdataene med elementet som skal slettes; hvis begge ikke er like betyr at elementet ikke er tilstede i treet. Hvis de er like, kan følgende tilfeller oppstå:
Sak 1 : Venstre for roten er NULL, høyre for roten blir rotnoden.
Tilfelle 2 : Hvis både venstre og høyre eksisterer, så sprer vi det maksimale elementet i det venstre undertreet. Når splayingen er fullført, blir det maksimale elementet roten til det venstre undertreet. Det høyre undertreet ville bli det høyre barnet til roten til det venstre undertreet.