Splay-træer er de selvbalancerende eller selvjusterede binære søgetræer. Med andre ord kan vi sige, at spredningstræerne er varianterne af de binære søgetræer. Forudsætningen for spredningstræerne skal vi kende til de binære søgetræer.
Som vi allerede ved, er tidskompleksiteten af et binært søgetræ i hvert tilfælde. Tidskompleksiteten af et binært søgetræ i gennemsnitstilfældet er O(logn) og tidskompleksiteten i værste fald er O(n). I et binært søgetræ er værdien af det venstre undertræ mindre end rodknuden, og værdien af det højre undertræ er større end rodknuden; i et sådant tilfælde ville tidskompleksiteten være O(logn) . Hvis det binære træ er venstre- eller højreskævt, så vil tidskompleksiteten være O(n). For at begrænse skævheden skal AVL og rød-sort træ kom ind i billedet, at have O(logn ) tidskompleksitet for alle operationer i alle sagerne. Vi kan også forbedre denne tidskompleksitet ved at lave mere praktiske implementeringer, så det nye træ Hvad er et splaytræ?
Et splaytræ er et selvbalancerende træ, men AVL og rød-sorte træer er også selvbalancerende træer. Hvad gør sprøjtetræet unikke to træer. Den har en ekstra egenskab, der gør den unik, er splaying.
Et sprøjtetræ indeholder de samme operationer som en Binært søgetræ , dvs. indsættelse, sletning og søgning, men den indeholder også en operation mere, dvs. splaying. Så. alle handlingerne i splay-træet efterfølges af splaying.
Splaytræer er ikke strengt afbalancerede træer, men de er nogenlunde balancerede træer. Lad os forstå søgeoperationen i splay-træet.
Antag, at vi vil søge efter 7 element i træet, som er vist nedenfor:
For at søge i et hvilket som helst element i splay-træet, vil vi først udføre den standard binære søgetræ-operation. Da 7 er mindre end 10, så kommer vi til venstre for rodnoden. Efter at have udført søgeoperationen, skal vi udføre splaying. Her betyder splaying, at den operation, vi udfører på ethvert element, skal blive rodnoden efter at have udført nogle omarrangeringer. Omlægningen af træet vil ske gennem rotationerne.
Bemærk: Splay-træet kan defineres som det selvjusterede træ, hvor enhver operation udført på elementet ville omarrangere træet, så det element, som operationen er udført på, bliver træets rodknude.
Rotationer
Der er seks typer rotationer, der bruges til at sprede:
- Zig-rotation (højre rotation)
- Zag rotation (venstre rotation)
- Zig zag (Zig efterfulgt af zag)
- Zag zig (Zag efterfulgt af zig)
- Zig zig (to højre rotationer)
- Zag zag (to venstre rotationer)
Faktorer, der kræves for at vælge en rotationstype
Følgende er de faktorer, der bruges til at vælge en rotationstype:
- Har den node, som vi forsøger at rotere, en bedsteforælder?
- Er knudepunktet venstre eller højre barn af forælderen?
- Er noden venstre eller højre barn af bedsteforælderen?
Sager til Rotationerne
Case 1: Hvis noden ikke har en bedsteforælder, og hvis det er det højre barn af forælderen, så udfører vi venstrerotationen; ellers udføres den rigtige rotation.
Tilfælde 2: Hvis noden har en bedsteforælder, så baseret på følgende scenarier; rotationen vil blive udført:
Scenarie 1: Hvis noden er forælderens ret, og forælderen også har ret til sin forælder, så zig zig højre højre rotation udføres.
Scenario 2: Hvis noden er til venstre for en forælder, men forælderen er til højre for sin forælder, så zig-zag højre venstre rotation udføres.
Scenarie 3: Hvis noden er højre for forælderen, og forælderen har ret til sin forælder, så zig zig venstre rotation til venstre udføres.
Scenarie 4: Hvis noden er til højre for en forælder, men forælderen er til venstre for sin forælder, så zig-zag højre-venstre rotation udføres.
Lad os nu forstå ovenstående rotationer med eksempler.
For at omarrangere træet skal vi udføre nogle rotationer. Følgende er typerne af rotationer i splay-træet:
Zig-rotationerne bruges, når det element, der skal søges i, enten er en rodknude eller underordnet af en rodknude (dvs. venstre eller højre underordnede).
Følgende er de tilfælde, der kan eksistere i splay-træet, mens du søger:
Case 1: Hvis søgeelementet er en rodknude i træet.
Tilfælde 2: Hvis søgeelementet er et barn af rodnoden, vil de to scenarier være der:
- Hvis barnet er et venstrebarn, vil den højre rotation blive udført, kendt som en zig højre rotation.
- Hvis barnet er et højre barn, vil venstre rotation blive udført, kendt som en zig venstre rotation.
Lad os se på de to ovenstående scenarier gennem et eksempel.
Overvej nedenstående eksempel:
I ovenstående eksempel skal vi søge efter 7 element i træet. Vi vil følge nedenstående trin:
Trin 1: Først sammenligner vi 7 med en rodknude. Da 7 er mindre end 10, så er det et venstre underordnet af rodknuden.
Trin 2: Når elementet er fundet, vil vi udføre splaying. Den højre rotation udføres, så 7 bliver træets rodknude, som vist nedenfor:
Lad os overveje et andet eksempel.
I ovenstående eksempel skal vi søge efter 20 elementer i træet. Vi vil følge nedenstående trin:
Trin 1: Først sammenligner vi 20 med en rodknude. Da 20 er større end rodknuden, så er det et højre underordnet af rodknuden.
Trin 2: Når elementet er fundet, vil vi udføre splaying. Den venstre rotation udføres, så 20 element bliver træets rodknude.
Nogle gange opstår situationen, når den genstand, der skal søges, har en forælder såvel som en bedsteforælder. I dette tilfælde skal vi udføre fire rotationer for at sprede.
Lad os forstå denne sag gennem et eksempel.
Antag, at vi skal søge efter 1 element i træet, som er vist nedenfor:
Trin 1: Først skal vi udføre en standard BST-søgningsoperation for at søge i 1-elementet. Da 1 er mindre end 10 og 7, så vil det være til venstre for knudepunktet 7. Derfor har element 1 en forælder, dvs. 7 såvel som en bedsteforælder, dvs. 10.
Trin 2: I dette trin skal vi udføre splaying. Vi skal lave node 1 som en rodnode ved hjælp af nogle rotationer. I dette tilfælde kan vi ikke blot udføre en zig- eller zag-rotation; vi er nødt til at implementere zig zig rotation.
For at gøre node 1 til en rodknude, skal vi udføre to højrerotationer kendt som zig zig-rotationer. Når vi udfører den rigtige rotation, vil 10 bevæge sig nedad, og node 7 vil komme opad som vist i nedenstående figur:
Igen vil vi udføre zig højre rotation, node 7 vil bevæge sig nedad, og node 1 vil komme opad som vist nedenfor:
Som vi observerer i ovenstående figur, er node 1 blevet træets rodknude; derfor er søgningen afsluttet.
Antag, at vi ønsker at søge 20 i nedenstående træ.
For at søge 20 skal vi udføre to venstrerotationer. Følgende er de nødvendige trin for at søge i 20 node:
Trin 1: Først udfører vi standard BST-søgningsoperationen. Da 20 er større end 10 og 15, så vil den være til højre for node 15.
Trin 2: Det andet trin er at udføre splaying. I dette tilfælde udføres to venstredrejninger. I den første rotation vil node 10 bevæge sig nedad, og node 15 vil bevæge sig opad som vist nedenfor:
I den anden venstrerotation vil node 15 bevæge sig nedad, og node 20 bliver træets rodknude, som vist nedenfor:
Som vi har observeret, udføres to venstre rotationer; så det er kendt som en zig zig venstre rotation.
Indtil nu har vi læst, at både forælder og bedsteforælder enten er i RR- eller LL-forhold. Nu vil vi se RL- eller LR-forholdet mellem forælderen og bedsteforælderen.
Lad os forstå denne sag gennem et eksempel.
Antag, at vi vil søge efter 13 element i træet, som er vist nedenfor:
Trin 1: Først udfører vi standard BST-søgning. Da 13 er større end 10, men mindre end 15, vil node 13 være det venstre underordnede af node 15.
Trin 2: Da node 13 er til venstre for 15 og node 15 er til højre for node 10, så eksisterer RL-relation. Først udfører vi den rigtige rotation på node 15, og 15 vil bevæge sig nedad, og node 13 vil komme opad, som vist nedenfor:
Alligevel er knude 13 ikke rodknudepunktet, og 13 er til højre for rodknudepunktet, så vi udfører venstrerotation kendt som en zag-rotation. Noden 10 vil bevæge sig nedad, og 13 bliver rodknuden som vist nedenfor:
Som vi kan observere i ovenstående træ, er node 13 blevet til rodknudepunktet; derfor er søgningen afsluttet. I dette tilfælde har vi først udført zig-rotationen og derefter zag-rotationen; så det er kendt som en zig-zag-rotation.
Lad os forstå denne sag gennem et eksempel.
Antag, at vi vil søge efter 9 element i træet, som er vist nedenfor:
Trin 1: Først udfører vi standard BST-søgningsoperationen. Da 9 er mindre end 10, men større end 7, så vil det være det rigtige barn af node 7.
Trin 2: Da node 9 er til højre for node 7, og node 7 er til venstre for node 10, så eksisterer LR-relation. Først udfører vi venstre rotation på node 7. Node 7 vil bevæge sig nedad, og node 9 bevæger sig opad som vist nedenfor:
Node 9 er stadig ikke en rodknude, og 9 er til venstre for rodknudepunktet, så vi udfører den højre rotation kendt som zig-rotation. Efter at have udført den rigtige rotation, bliver node 9 rodknuden, som vist nedenfor:
Som vi kan observere i ovenstående træ, er node 13 en rodknude; derfor er søgningen afsluttet. I dette tilfælde har vi først udført zag rotation (venstre rotation), og derefter udføres zig rotation (højre rotation), så det er kendt som en zag zig rotation.
Fordele ved Splay tree
- I splay-træet behøver vi ikke gemme de ekstra oplysninger. I modsætning hertil skal vi i AVL-træer gemme balancefaktoren for hver node, der kræver ekstra plads, og rød-sorte træer kræver også at gemme en ekstra bit information, der angiver farven på noden, enten rød eller sort.
- Det er den hurtigste type binært søgetræ til forskellige praktiske anvendelser. Det bruges i Windows NT og GCC compilere .
- Det giver bedre ydeevne, da de ofte tilgåede noder vil bevæge sig tættere på rodknuden, på grund af hvilken elementerne hurtigt kan tilgås i spredningstræer. Det bruges i cache-implementeringen, da de nyligt tilgåede data gemmes i cachen, så vi ikke behøver at gå til hukommelsen for at få adgang til dataene, og det tager kortere tid.
Ulempen ved Splay tree
Den største ulempe ved sprøjtetræet ville være, at træer ikke er strengt afbalancerede, dvs. de er nogenlunde afbalancerede. Nogle gange er spredningstræerne lineære, så det vil tage O(n) tidskompleksitet.
Indsættelsesoperation i Splay tree
I den indskud operation, indsætter vi først elementet i træet og udfører derefter sprøjteoperationen på det indsatte element.
15, 10, 17, 7
Trin 1: Først indsætter vi node 15 i træet. Efter indsættelse skal vi udføre splaying. Da 15 er en rodknude, behøver vi ikke at udføre splaying.
Trin 2: Det næste element er 10. Da 10 er mindre end 15, vil node 10 være det venstre underordnede af node 15, som vist nedenfor:
Nu optræder vi spredning . For at lave 10 som en rodknude, udfører vi den rigtige rotation, som vist nedenfor:
Trin 3: Det næste element er 17. Da 17 er større end 10 og 15, så bliver det det rigtige barn af node 15.
Nu vil vi udføre splaying. Da 17 har en forælder såvel som en bedsteforælder, så vil vi udføre zig zig rotationer.
I ovenstående figur kan vi observere, at 17 bliver træets rodknude; derfor er indsættelsen gennemført.
Trin 4: Det næste element er 7. Da 7 er mindre end 17, 15 og 10, vil node 7 blive efterladt under 10.
Nu er vi nødt til at sprænge træet. Da 7 har en forælder såvel som en bedsteforælder, så udfører vi to højrerotationer som vist nedenfor:
Node 7 er stadig ikke en rodknude, den er et venstre underordnet af rodknudepunktet, dvs. 17. Så vi skal udføre en højrerotation mere for at gøre knude 7 til en rodknude som vist nedenfor:
Algoritme for indsættelsesoperation
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 ovenstående algoritme er T træet, og n er den node, som vi ønsker at indsætte. Vi har lavet en temp-variabel, der indeholder adressen på rodnoden. Vi kører while-løkken, indtil værdien af temp bliver NULL.
Når indsættelsen er fuldført, udføres splaying
Algoritme for Splaying-operation
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 ovenstående implementering er x den knude, hvorpå rotationen udføres, hvorimod y er det venstre underordnede af knudepunktet x.
Implementering af left.rotation(T, x)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
I ovenstående implementering er x den knude, hvorpå rotationen udføres, og y er det højre underordnede af knudepunktet x.
Sletning i Splay-træet
Da vi ved, at splay-træer er varianterne af det binære søgetræ, så vil sletningsoperationen i splay-træet ligne BST, men den eneste forskel er, at slet-operationen i splay-træerne følges af splay-operationen.
Typer af sletninger:
Der er to typer sletninger i splay-træerne:
- Bottom-up spredning
- Top-down spredning
Bottom-up spredning
I bottom-up splaying sletter vi først elementet fra træet og derefter udfører vi splayingen på den slettede node.
Lad os forstå sletningen i Splay-træet.
Antag, at vi ønsker at slette 12, 14 fra træet vist nedenfor:
streng erstatte al java
- Først udfører vi simpelthen standard BST-sletningsoperationen for at slette 12 element. Da 12 er en bladnode, så sletter vi blot noden fra træet.
Sletningen er stadig ikke fuldført. Vi skal sprede forælderen til den slettede node, dvs. 10. Vi skal udføre Splay(10) på træet. Som vi kan observere i ovenstående træ, er 10 til højre for node 7, og node 7 er til venstre for node 13. Så først udfører vi venstre rotation på node 7 og derefter udfører vi højre rotation på node 13, som vist nedenfor:
Alligevel er knude 10 ikke en rodknude; node 10 er det venstre underordnede af rodknuden. Så vi skal udføre den rigtige rotation på rodknuden, dvs. 14 for at gøre knude 10 til en rodknude som vist nedenfor:
- Nu skal vi slette elementet 14 fra træet, som er vist nedenfor:
Som vi ved, at vi ikke bare kan slette den interne node. Vi vil erstatte værdien af noden enten vha inorder forgænger eller uordens efterfølger . Antag, at vi bruger inorder successor, hvor vi erstatter værdien med den laveste værdi, der findes i det højre undertræ. Den laveste værdi i højre undertræ af node 14 er 15, så vi erstatter værdien 14 med 15. Da node 14 bliver bladknuden, så kan vi simpelthen slette den som vist nedenfor:
Alligevel er sletningen ikke fuldført. Vi skal udføre en operation mere, dvs. splaying, hvor vi skal gøre forælderen til den slettede node som rodknudepunktet. Før sletning var forælderen til node 14 rodknuden, dvs. 10, så vi skal udføre enhver splaying i dette tilfælde.
Top-down spredning
I top-down splaying udfører vi først den splaying, som sletningen skal udføres på og sletter derefter noden fra træet. Når elementet er slettet, udfører vi join-operationen.
Lad os forstå top-down spredning gennem et eksempel.
Antag, at vi ønsker at slette 16 fra træet, som er vist nedenfor:
Trin 1: I top-down splaying udfører vi først splaying på node 16. Node 16 har både forældre såvel som bedsteforældre. Noden 16 er til højre for sin forælder, og forælderknuden er også til højre for sin forælder, så dette er en zag-zag-situation. I dette tilfælde vil vi først udføre venstre rotation på node 13 og derefter 14 som vist nedenfor:
Noden 16 er stadig ikke en rodknude, og den er et højre underordnet rodknudepunkt, så vi skal udføre venstrerotation på knudepunktet 12 for at gøre knude 16 til en rodknude.
Når knudepunktet 16 bliver en rodknude, vil vi slette knudepunktet 16, og vi vil få to forskellige træer, dvs. venstre undertræ og højre undertræ som vist nedenfor:
Som vi ved, at værdierne af det venstre undertræ altid er mindre end værdierne af det højre undertræ. Roden af det venstre undertræ er 12 og roden af det højre undertræ er 17. Det første trin er at finde det maksimale element i det venstre undertræ. I det venstre undertræ er det maksimale element 15, og så skal vi udføre spredningsoperation på 15.
Som vi kan observere i ovenstående træ, har elementet 15 en forælder såvel som en bedsteforælder. En node er til højre for sin forælder, og den overordnede node er også til højre for sin forælder, så vi skal udføre to venstrerotationer for at gøre node 15 til en rodnode som vist nedenfor:
Efter at have udført to rotationer på træet, bliver knude 15 rodknudepunktet. Som vi kan se, er det højre underordnede af 15'eren NULL, så vi vedhæfter node 17 i højre del af 15'eren som vist nedenfor, og denne operation er kendt som en tilslutte operation.
Bemærk: Hvis elementet ikke er til stede i splay-træet, som skal slettes, vil splaying blive udført. Spredningen ville blive udført på det sidst tilgåede element, før det nåede NULL.
Algoritme for sletning
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 ovenstående algoritme tjekker vi først, om roden er Null eller ej; hvis roden er NULL betyder det, at træet er tomt. Hvis træet ikke er tomt, udfører vi sprøjteoperationen på det element, som skal slettes. Når sprøjteoperationen er afsluttet, vil vi sammenligne roddataene med det element, der skal slettes; hvis begge ikke er ens betyder, at elementet ikke er til stede i træet. Hvis de er ens, kan følgende tilfælde forekomme:
Tilfælde 1 : Venstre for roden er NULL, højre for roden bliver til rodknude.
Tilfælde 2 : Hvis både venstre og højre findes, så spreder vi det maksimale element i det venstre undertræ. Når spredningen er fuldført, bliver det maksimale element roden af det venstre undertræ. Det højre undertræ ville blive det højre barn af roden af det venstre undertræ.