Splay-bomen zijn de zelfbalancerende of zelfaanpassende binaire zoekbomen. Met andere woorden, we kunnen zeggen dat de splay-bomen de varianten zijn van de binaire zoekbomen. De voorwaarde voor de splay-bomen die we moeten kennen over de binaire zoekbomen.
Zoals we al weten, is de tijdscomplexiteit van een binaire zoekboom in elk geval groot. De tijdscomplexiteit van een binaire zoekboom is in het gemiddelde geval O(login) en de tijdscomplexiteit in het ergste geval is O(n). In een binaire zoekboom is de waarde van de linker subboom kleiner dan het hoofdknooppunt, en is de waarde van de rechter subboom groter dan het hoofdknooppunt; in dat geval zou de tijdscomplexiteit dat zijn O(login) . Als de binaire boom links- of rechtsscheef is, dan zou de tijdscomplexiteit O(n) zijn. Om de scheefheid te beperken, is de AVL en rood-zwarte boom kwam in beeld, met O(log ) tijdcomplexiteit voor alle bewerkingen in alle gevallen. We kunnen deze tijdscomplexiteit ook verbeteren door meer praktische implementaties te doen, dus de nieuwe Tree Wat is een Splay Tree?
Een spreidboom is een zelfbalancerende boom, maar AVL- en Rood-Zwarte bomen zijn dan ook zelfbalancerende bomen. Wat de splay tree uniek maakt, zijn twee bomen. Het heeft één extra eigenschap die het uniek maakt: de spreiding.
Een splay tree bevat dezelfde bewerkingen als a Binaire zoekboom , dat wil zeggen invoegen, verwijderen en zoeken, maar het bevat ook nog een bewerking, namelijk splaying. Dus. alle bewerkingen in de splay-boom worden gevolgd door splaying.
Splay-bomen zijn geen strikt uitgebalanceerde bomen, maar het zijn ruwweg uitgebalanceerde bomen. Laten we de zoekbewerking in de splay-tree begrijpen.
Stel dat we 7 elementen in de boom willen doorzoeken, zoals hieronder weergegeven:
Om een element in de spreidingsboom te doorzoeken, zullen we eerst de standaard binaire zoekboombewerking uitvoeren. Omdat 7 kleiner is dan 10, komen we links van het hoofdknooppunt. Na het uitvoeren van de zoekbewerking moeten we splaying uitvoeren. Spreiding betekent hier dat de bewerking die we op een willekeurig element uitvoeren, het hoofdknooppunt moet worden na het uitvoeren van enkele herschikkingen. De herschikking van de boom zal gebeuren door middel van rotaties.
Opmerking: De splay-boom kan worden gedefinieerd als de zelfaangepaste boom waarin elke bewerking die op het element wordt uitgevoerd, de boom herschikt, zodat het element waarop de bewerking is uitgevoerd het hoofdknooppunt van de boom wordt.
Rotaties
Er worden zes soorten rotaties gebruikt voor spreiden:
- Zig-rotatie (rechtsdraaien)
- Zag-rotatie (linksdraaien)
- Zigzag (zigzag gevolgd door zag)
- Zag zig (Zag gevolgd door zig)
- Zig-zig (twee rotaties naar rechts)
- Zagzag (twee rotaties naar links)
Factoren die nodig zijn voor het selecteren van een type rotatie
Hieronder volgen de factoren die worden gebruikt bij het selecteren van een type rotatie:
- Heeft het knooppunt dat we proberen te roteren een grootouder?
- Is het knooppunt het linker- of rechterkind van de ouder?
- Is het knooppunt het linker- of rechterkind van de grootouder?
Cases voor de rotaties
Zaak 1: Als het knooppunt geen grootouder heeft en het rechterkind van de ouder is, voeren we de linkerrotatie uit; anders wordt de juiste rotatie uitgevoerd.
Geval 2: Als het knooppunt een grootouder heeft, dan op basis van de volgende scenario's; de rotatie zou worden uitgevoerd:
Scenario 1: Als het knooppunt het recht van de ouder is en de ouder ook het recht van zijn ouder, dan zig zig rechts rechts draaien is uitgevoerd.
Scenario 2: Als het knooppunt zich links van een ouder bevindt, maar de ouder zich rechts van zijn ouder bevindt, dan zigzag rechts links draaien is uitgevoerd.
Scenario 3: Als het knooppunt rechts van de ouder staat en de ouder rechts van zijn ouder, dan zig zig links links draaien is uitgevoerd.
Scenario 4: Als het knooppunt zich rechts van een ouder bevindt, maar de ouder links van zijn ouder, dan zigzag rechts-links draaien is uitgevoerd.
Laten we nu de bovenstaande rotaties begrijpen met voorbeelden.
Om de boom opnieuw te rangschikken, moeten we enkele rotaties uitvoeren. Hieronder volgen de soorten rotaties in de spreidingsboom:
De zig-rotaties worden gebruikt wanneer het te doorzoeken item een hoofdknooppunt is of het onderliggende knooppunt van een hoofdknooppunt (dat wil zeggen het linker- of rechterkind).
Hieronder volgen de gevallen die tijdens het zoeken in de splay-boom kunnen voorkomen:
Zaak 1: Als het zoekitem een hoofdknooppunt van de boom is.
Geval 2: Als het zoekitem een onderliggend item van het hoofdknooppunt is, zijn er twee scenario's:
- Als het kind een linkskind is, wordt de rechterrotatie uitgevoerd, ook wel een zig-rechtsrotatie genoemd.
- Als het kind een rechterkind is, wordt de linkerrotatie uitgevoerd, ook wel een zig-linksrotatie genoemd.
Laten we de bovenstaande twee scenario's bekijken aan de hand van een voorbeeld.
Beschouw het onderstaande voorbeeld:
In het bovenstaande voorbeeld moeten we 7 elementen in de boom zoeken. We zullen de onderstaande stappen volgen:
Stap 1: Eerst vergelijken we 7 met een hoofdknooppunt. Omdat 7 kleiner is dan 10, is het dus een linkerkind van het hoofdknooppunt.
Stap 2: Zodra het element is gevonden, voeren we spreiding uit. De rotatie naar rechts wordt uitgevoerd zodat 7 het hoofdknooppunt van de boom wordt, zoals hieronder weergegeven:
Laten we een ander voorbeeld bekijken.
In het bovenstaande voorbeeld moeten we 20 elementen in de boom doorzoeken. We zullen de onderstaande stappen volgen:
Stap 1: Eerst vergelijken we 20 met een hoofdknooppunt. Omdat 20 groter is dan het hoofdknooppunt, is het dus een rechterkind van het hoofdknooppunt.
Stap 2: Zodra het element is gevonden, voeren we spreiding uit. De rotatie naar links wordt uitgevoerd zodat 20 elementen het hoofdknooppunt van de boom worden.
Soms doet zich de situatie voor dat het te doorzoeken item zowel een ouder als een grootouder heeft. In dit geval moeten we vier rotaties uitvoeren voor het spreiden.
Laten we deze zaak begrijpen aan de hand van een voorbeeld.
Stel dat we 1 element in de boom moeten zoeken, zoals hieronder weergegeven:
Stap 1: Eerst moeten we een standaard BST-zoekoperatie uitvoeren om het 1-element te doorzoeken. Omdat 1 kleiner is dan 10 en 7, bevindt deze zich dus links van knooppunt 7. Daarom heeft element 1 zowel een ouder, d.w.z. 7, als een grootouder, d.w.z. 10.
Stap 2: In deze stap moeten we spreiding uitvoeren. We moeten knooppunt 1 als hoofdknooppunt maken met behulp van enkele rotaties. In dit geval kunnen we niet eenvoudigweg een zig- of zagrotatie uitvoeren; we moeten zig-zig-rotatie implementeren.
Om knooppunt 1 als hoofdknooppunt te maken, moeten we twee rotaties naar rechts uitvoeren, ook wel zig-zig-rotaties genoemd. Wanneer we de juiste rotatie uitvoeren, zal 10 naar beneden bewegen en knooppunt 7 naar boven komen, zoals weergegeven in de onderstaande afbeelding:
Opnieuw zullen we een zig-rechtsrotatie uitvoeren, knooppunt 7 zal naar beneden bewegen en knooppunt 1 zal naar boven komen, zoals hieronder weergegeven:
Zoals we in de bovenstaande figuur zien, is knooppunt 1 het hoofdknooppunt van de boom geworden; daarom is het zoeken voltooid.
Stel dat we 20 willen zoeken in de onderstaande boom.
Om 20 te zoeken, moeten we twee rotaties naar links uitvoeren. Hieronder volgen de stappen die nodig zijn om 20 knooppunten te doorzoeken:
Stap 1: Eerst voeren we de standaard BST-zoekbewerking uit. Omdat 20 groter is dan 10 en 15, bevindt deze zich dus rechts van knooppunt 15.
Stap 2: De tweede stap is het uitvoeren van spreiding. In dit geval zouden twee rotaties naar links worden uitgevoerd. Bij de eerste rotatie zal knooppunt 10 naar beneden bewegen en knooppunt 15 naar boven, zoals hieronder weergegeven:
Bij de tweede rotatie naar links beweegt knooppunt 15 naar beneden en wordt knooppunt 20 het hoofdknooppunt van de boom, zoals hieronder weergegeven:
Zoals we hebben gezien worden er twee rotaties naar links uitgevoerd; dus het staat bekend als een zig-zig-rotatie naar links.
Tot nu toe hebben we gelezen dat zowel de ouder als de grootouder een RR- of LL-relatie hebben. Nu zullen we de RL- of LR-relatie tussen de ouder en de grootouder zien.
Laten we deze zaak begrijpen aan de hand van een voorbeeld.
Stel dat we 13 elementen willen doorzoeken in de boom die hieronder wordt weergegeven:
Stap 1: Eerst voeren we de standaard BST-zoekbewerking uit. Omdat 13 groter is dan 10 maar kleiner dan 15, zal knooppunt 13 het linkerkind van knooppunt 15 zijn.
Stap 2: Omdat knooppunt 13 zich links van knooppunt 15 bevindt en knooppunt 15 rechts van knooppunt 10, bestaat er dus een RL-relatie. Eerst voeren we de juiste rotatie uit op knooppunt 15, en 15 zal naar beneden bewegen, en knooppunt 13 zal naar boven komen, zoals hieronder weergegeven:
Toch is knooppunt 13 niet het hoofdknooppunt en bevindt 13 zich aan de rechterkant van het hoofdknooppunt, dus we zullen een rotatie naar links uitvoeren, ook wel een zagrotatie genoemd. Knooppunt 10 beweegt naar beneden en 13 wordt het hoofdknooppunt, zoals hieronder weergegeven:
Zoals we in de bovenstaande boom kunnen zien, is knooppunt 13 het hoofdknooppunt geworden; daarom is het zoeken voltooid. In dit geval hebben we eerst de zig-rotatie uitgevoerd en vervolgens de zag-rotatie; het staat dus bekend als een zigzagrotatie.
Laten we deze zaak begrijpen aan de hand van een voorbeeld.
Stel dat we 9 elementen in de boom willen doorzoeken, zoals hieronder weergegeven:
Stap 1: Eerst voeren we de standaard BST-zoekbewerking uit. Omdat 9 kleiner is dan 10 maar groter dan 7, zal dit het juiste kind van knooppunt 7 zijn.
Stap 2: Omdat knooppunt 9 zich rechts van knooppunt 7 bevindt en knooppunt 7 zich links van knooppunt 10 bevindt, bestaat er dus een LR-relatie. Eerst voeren we de rotatie naar links uit op knooppunt 7. Knooppunt 7 beweegt naar beneden en knooppunt 9 beweegt naar boven, zoals hieronder weergegeven:
Toch is knooppunt 9 geen hoofdknooppunt, en bevindt 9 zich links van het hoofdknooppunt, dus zullen we de rotatie naar rechts uitvoeren die bekend staat als zig-rotatie. Na het uitvoeren van de rechterrotatie wordt knooppunt 9 het hoofdknooppunt, zoals hieronder weergegeven:
Zoals we in de bovenstaande boom kunnen zien, is knooppunt 13 een hoofdknooppunt; daarom is het zoeken voltooid. In dit geval hebben we eerst de zag-rotatie (rotatie naar links) uitgevoerd en vervolgens de zig-rotatie (rotatie naar rechts), dus dit staat bekend als een zag-zig-rotatie.
Voordelen van Splay-boom
- In de splay tree hoeven we de extra informatie niet op te slaan. In AVL-bomen moeten we daarentegen de balansfactor opslaan van elk knooppunt dat extra ruimte nodig heeft, en rood-zwarte bomen moeten ook een extra stukje informatie opslaan dat de kleur van het knooppunt aangeeft, rood of zwart.
- Het is het snelste type binaire zoekboom voor verschillende praktische toepassingen. Het wordt gebruikt bij Windows NT- en GCC-compilers .
- Het levert betere prestaties omdat de vaak gebruikte knooppunten dichter bij het hoofdknooppunt komen, waardoor de elementen snel toegankelijk zijn in splay-trees. Het wordt gebruikt in de cache-implementatie omdat de recentelijk geopende gegevens in de cache worden opgeslagen, zodat we niet naar het geheugen hoeven te gaan om toegang te krijgen tot de gegevens, en het kost minder tijd.
Nadeel van Splay-boom
Het grootste nadeel van de gespreide boom zou zijn dat bomen niet strikt in balans zijn, dat wil zeggen dat ze grofweg in balans zijn. Soms zijn de spreidingsbomen lineair, dus het zal O(n) tijdcomplexiteit vergen.
Invoegbewerking in Splay-boom
In de plaatsing Bij deze bewerking voegen we eerst het element in de boom in en voeren vervolgens de spreidbewerking uit op het ingevoegde element.
15, 10, 17, 7
Stap 1: Eerst voegen we knooppunt 15 in de boom in. Na het inbrengen moeten we spreiding uitvoeren. Omdat 15 een hoofdknooppunt is, hoeven we geen spreiding uit te voeren.
Stap 2: Het volgende element is 10. Omdat 10 kleiner is dan 15, zal knooppunt 10 het linkerkind van knooppunt 15 zijn, zoals hieronder weergegeven:
Nu treden wij op spreiden . Om 10 als hoofdknooppunt te maken, voeren we de juiste rotatie uit, zoals hieronder weergegeven:
Stap 3: Het volgende element is 17. Omdat 17 groter is dan 10 en 15, wordt dit het rechterkind van knooppunt 15.
Nu zullen we spreiding uitvoeren. Omdat 17 zowel een ouder als een grootouder heeft, zullen we zig-zig rotaties uitvoeren.
In de bovenstaande figuur kunnen we zien dat 17 het wortelknooppunt van de boom wordt; daarom is het invoegen voltooid.
Stap 4: Het volgende element is 7. Omdat 7 kleiner is dan 17, 15 en 10, zal knooppunt 7 het kind van 10 blijven.
Nu moeten we de boom spreiden. Omdat 7 zowel een ouder als een grootouder heeft, zullen we twee rotaties naar rechts uitvoeren, zoals hieronder weergegeven:
Toch is knooppunt 7 geen hoofdknooppunt, het is een linkerkind van het hoofdknooppunt, d.w.z. 17. We moeten dus nog een rotatie naar rechts uitvoeren om knooppunt 7 als hoofdknooppunt te maken, zoals hieronder weergegeven:
Algoritme voor invoegbewerking
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)
In het bovenstaande algoritme is T de boom en n het knooppunt dat we willen invoegen. We hebben een temp-variabele gemaakt die het adres van het hoofdknooppunt bevat. We zullen de while-lus uitvoeren totdat de waarde van temp NULL wordt.
Zodra het inbrengen is voltooid, wordt het spreiden uitgevoerd
Algoritme voor spreidbewerking
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
In de bovenstaande implementatie is x het knooppunt waarop de rotatie wordt uitgevoerd, terwijl y het linkerkind van knooppunt x is.
Implementatie van left.rotation(T, x)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
In de bovenstaande implementatie is x het knooppunt waarop de rotatie wordt uitgevoerd en is y het rechterkind van het knooppunt x.
Verwijdering in de Splay-boom
Omdat we weten dat splay-bomen de varianten zijn van de binaire zoekboom, zou de verwijderbewerking in de splay-boom vergelijkbaar zijn met de BST, maar het enige verschil is dat de verwijderbewerking in splay-bomen wordt gevolgd door de splay-bewerking.
Soorten verwijderingen:
Er zijn twee soorten verwijderingen in de splay-bomen:
- Bottom-up-spreiding
- Top-down spreiding
Bottom-up-spreiding
Bij bottom-up-spreiding verwijderen we eerst het element uit de boom en voeren we vervolgens de spreiding uit op het verwijderde knooppunt.
Laten we de verwijdering in de Splay-boom begrijpen.
Stel dat we 12, 14 willen verwijderen uit de onderstaande boom:
int naar string-conversie
- Eerst voeren we eenvoudigweg de standaard BST-verwijderingsbewerking uit om 12 elementen te verwijderen. Omdat 12 een bladknooppunt is, verwijderen we eenvoudigweg het knooppunt uit de boom.
De verwijdering is nog steeds niet voltooid. We moeten de ouder van het verwijderde knooppunt spreiden, d.w.z. 10. We moeten presteren Verspreiding(10) op de boom. Zoals we in de bovenstaande boom kunnen zien, bevindt 10 zich rechts van knooppunt 7 en knooppunt 7 links van knooppunt 13. Dus voeren we eerst de linkerrotatie uit op knooppunt 7 en daarna voeren we de rechterrotatie uit op knooppunt 7. 13, zoals hieronder weergegeven:
Toch is knooppunt 10 geen hoofdknooppunt; knooppunt 10 is het linkerkind van het hoofdknooppunt. We moeten dus de juiste rotatie uitvoeren op het hoofdknooppunt, d.w.z. 14 om van knooppunt 10 een hoofdknooppunt te maken, zoals hieronder weergegeven:
- Nu moeten we de 14 elementen uit de boom verwijderen, die hieronder wordt weergegeven:
Zoals we weten, kunnen we het interne knooppunt niet zomaar verwijderen. We zullen de waarde van het knooppunt vervangen door inorde voorganger of inorde opvolger . Stel dat we een opvolger gebruiken waarin we de waarde vervangen door de laagste waarde die in de rechter subboom bestaat. De laagste waarde in de rechter subboom van knooppunt 14 is 15, dus vervangen we de waarde 14 door 15. Omdat knooppunt 14 het bladknooppunt wordt, kunnen we het eenvoudigweg verwijderen, zoals hieronder weergegeven:
Toch is de verwijdering nog niet voltooid. We moeten nog een bewerking uitvoeren, namelijk splaying, waarbij we de ouder van het verwijderde knooppunt als het hoofdknooppunt moeten maken. Vóór verwijdering was de ouder van knooppunt 14 het hoofdknooppunt, d.w.z. 10, dus we moeten in dit geval enige spreiding uitvoeren.
Top-down spreiding
Bij top-down spreiding voeren we eerst de spreiding uit waarop de verwijdering moet worden uitgevoerd en verwijderen vervolgens het knooppunt uit de boom. Zodra het element is verwijderd, voeren we de join-bewerking uit.
Laten we de top-down-spreiding begrijpen aan de hand van een voorbeeld.
Stel dat we 16 willen verwijderen uit de boom die hieronder wordt weergegeven:
Stap 1: Bij top-down spreiding voeren we eerst spreiding uit op knooppunt 16. Knooppunt 16 heeft zowel een ouder als een grootouder. Het knooppunt 16 bevindt zich rechts van zijn ouderknooppunt en het ouderknooppunt bevindt zich ook rechts van zijn ouder, dus dit is een zagzagsituatie. In dit geval voeren we eerst de rotatie naar links uit op knooppunt 13 en vervolgens op knooppunt 14, zoals hieronder weergegeven:
Het knooppunt 16 is nog steeds geen hoofdknooppunt, en het is een rechterkind van het hoofdknooppunt, dus we moeten een linkerrotatie uitvoeren op het knooppunt 12 om knooppunt 16 als een hoofdknooppunt te maken.
Zodra knooppunt 16 een hoofdknooppunt wordt, verwijderen we knooppunt 16 en krijgen we twee verschillende bomen, d.w.z. de linker subboom en de rechter subboom, zoals hieronder weergegeven:
Zoals we weten zijn de waarden van de linker deelboom altijd kleiner dan de waarden van de rechter deelboom. De wortel van de linker deelboom is 12 en de wortel van de rechter deelboom is 17. De eerste stap is het vinden van het maximale element in de linker deelboom. In de linker subboom is het maximale element 15, en dan moeten we een spreidingsbewerking uitvoeren op 15.
Zoals we in de bovenstaande boom kunnen zien, heeft het element 15 zowel een ouder als een grootouder. Een knooppunt bevindt zich rechts van zijn ouderknooppunt, en het ouderknooppunt bevindt zich ook rechts van zijn ouderknooppunt, dus we moeten twee rotaties naar links uitvoeren om van knooppunt 15 een hoofdknooppunt te maken, zoals hieronder weergegeven:
Na twee rotaties in de boom te hebben uitgevoerd, wordt knooppunt 15 het hoofdknooppunt. Zoals we kunnen zien, is het rechterkind van de 15 NULL, dus bevestigen we knooppunt 17 aan het rechtergedeelte van de 15, zoals hieronder weergegeven, en deze bewerking staat bekend als een meedoen operatie.
Opmerking: Als het element niet aanwezig is in de spreidingsboom, die moet worden verwijderd, wordt spreiding uitgevoerd. De spreiding zou worden uitgevoerd op het laatst gebruikte element voordat de NULL wordt bereikt.
Algoritme van verwijderbewerking
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
In het bovenstaande algoritme controleren we eerst of de root Null is of niet; als de root NULL is, betekent dit dat de boom leeg is. Als de boom niet leeg is, voeren we de spreidingsbewerking uit op het element dat moet worden verwijderd. Zodra de spreidingsbewerking is voltooid, vergelijken we de rootgegevens met het element dat moet worden verwijderd; als beide niet gelijk zijn, betekent dit dat het element niet aanwezig is in de boom. Als ze gelijk zijn, kunnen de volgende gevallen optreden:
Zaak 1 : De linkerkant van de root is NULL, de rechterkant van de root wordt het rootknooppunt.
Geval 2 : Als zowel links als rechts bestaan, spreiden we het maximale element in de linker subboom. Wanneer de spreiding is voltooid, wordt het maximale element de wortel van de linker subboom. De rechter deelboom zou het rechterkind worden van de wortel van de linker deelboom.