Splayträd är de självbalanserande eller självjusterade binära sökträden. Med andra ord kan vi säga att spridningsträden är varianterna av de binära sökträden. Förutsättningen för spridningsträden som vi bör känna till om de binära sökträden.
Som vi redan vet, tidskomplexiteten för ett binärt sökträd i varje fall. Tidskomplexiteten för ett binärt sökträd i genomsnittsfallet är O(logga) och tidskomplexiteten i värsta fall är O(n). I ett binärt sökträd är värdet på det vänstra underträdet mindre än rotnoden, och värdet på det högra underträdet är större än rotnoden; i ett sådant fall skulle tidskomplexiteten vara O(logga) . Om det binära trädet är vänster- eller höger-sned, då skulle tidskomplexiteten vara O(n). För att begränsa skevheten AVL och röd-svart träd kom in i bilden, efter att ha O(logn ) tidskomplexitet för alla operationer i alla fall. Vi kan också förbättra denna tidskomplexitet genom att göra mer praktiska implementeringar, så det nya trädet Vad är ett splayträd?
Ett splayträd är ett självbalanserande träd, men AVL och Röd-Svarta träd är också självbalanserande träd då. Vad gör splayträdet unikt två träd. Den har en extra egenskap som gör den unik är splaying.
Ett splayträd innehåller samma operationer som en Binärt sökträd , dvs infogning, radering och sökning, men den innehåller också ytterligare en operation, dvs spridning. Så. alla operationer i splayträdet följs av splaying.
Splayträd är inte strikt balanserade träd, men de är grovt balanserade träd. Låt oss förstå sökoperationen i splay-trädet.
Anta att vi vill söka efter 7 element i trädet, vilket visas nedan:
För att söka i valfritt element i splayträdet kommer vi först att utföra den vanliga binära sökträdsoperationen. Eftersom 7 är mindre än 10 så kommer vi till vänster om rotnoden. Efter att ha utfört sökoperationen måste vi utföra spridning. Här betyder spridning att operationen som vi utför på något element ska bli rotnoden efter att ha utfört några omarrangemang. Omarrangeringen av trädet kommer att göras genom rotationerna.
Notera: Spridningsträdet kan definieras som det självjusterade trädet där varje operation som utförs på elementet skulle omordna trädet så att elementet som operationen har utförts på blir trädets rotnod.
Rotationer
Det finns sex typer av rotationer som används för spridning:
- Zigrotation (högerrotation)
- Zag-rotation (vänsterrotation)
- Zig zag (sick följt av zag)
- Zag zig (Zag följt av zig)
- Zig zig (två högerrotationer)
- Zag zag (två vänsterrotationer)
Faktorer som krävs för att välja en typ av rotation
Följande är de faktorer som används för att välja en typ av rotation:
- Har noden som vi försöker rotera en morförälder?
- Är noden vänster eller höger barn till föräldern?
- Är noden vänster eller höger barn till morföräldern?
Fall för rotationerna
Fall 1: Om noden inte har en farförälder och om det är förälderns högra barn, utför vi vänsterrotationen; annars utförs rätt rotation.
Fall 2: Om noden har en farförälder, baserat på följande scenarier; rotationen skulle utföras:
Scenario 1: Om noden är förälderns rätt och föräldern också har rätt till sin förälder, då zig zig höger rotation utförs.
Scenario 2: Om noden är vänster om en förälder, men föräldern är höger om sin förälder, då sicksack höger vänster rotation utförs.
Scenario 3: Om noden är höger om föräldern och föräldern har höger om sin förälder, då zig zig vänster rotation till vänster utförs.
Scenario 4: Om noden är till höger om en förälder, men föräldern är vänster om sin förälder, då sicksack höger-vänster rotation utförs.
Låt oss nu förstå rotationerna ovan med exempel.
För att ordna om trädet måste vi utföra några rotationer. Följande är typerna av rotationer i splayträdet:
Zickrotationerna används när objektet som ska sökas är antingen en rotnod eller barnet till en rotnod (d.v.s. vänster eller höger underordnat).
Följande är fallen som kan finnas i splayträdet när du söker:
Fall 1: Om sökobjektet är en rotnod i trädet.
Fall 2: Om sökobjektet är ett barn till rotnoden, kommer de två scenarierna att finnas där:
- Om barnet är ett vänsterbarn skulle den högra rotationen utföras, känd som en zig högerrotation.
- Om barnet är ett högerbarn, skulle vänsterrotationen utföras, känd som en zig vänsterrotation.
Låt oss titta på ovanstående två scenarier genom ett exempel.
Tänk på exemplet nedan:
I exemplet ovan måste vi söka efter 7 element i trädet. Vi kommer att följa stegen nedan:
Steg 1: Först jämför vi 7 med en rotnod. Eftersom 7 är mindre än 10, så är det ett vänster underordnat av rotnoden.
Steg 2: När elementet har hittats kommer vi att utföra splaying. Den högra rotationen utförs så att 7 blir trädets rotnod, som visas nedan:
Låt oss överväga ett annat exempel.
I exemplet ovan måste vi söka efter 20 element i trädet. Vi kommer att följa stegen nedan:
Steg 1: Först jämför vi 20 med en rotnod. Eftersom 20 är större än rotnoden, så är det ett högra barn till rotnoden.
Steg 2: När elementet har hittats kommer vi att utföra splaying. Vänsterrotationen utförs så att 20 element blir trädets rotnod.
Ibland uppstår situationen när föremålet som ska sökas har en förälder såväl som en morförälder. I det här fallet måste vi utföra fyra rotationer för spridning.
Låt oss förstå detta fall genom ett exempel.
Anta att vi måste söka efter ett element i trädet, vilket visas nedan:
Steg 1: Först måste vi utföra en standard BST-sökningsoperation för att söka i 1-elementet. Eftersom 1 är mindre än 10 och 7, så kommer det att vara till vänster om noden 7. Därför har element 1 en förälder, dvs. 7 såväl som en farförälder, dvs. 10.
Steg 2: I det här steget måste vi utföra splaying. Vi behöver göra nod 1 som en rotnod med hjälp av några rotationer. I det här fallet kan vi inte bara utföra en zig- eller zagrotation; vi måste implementera zig zig rotation.
För att göra nod 1 till en rotnod måste vi utföra två högerrotationer som kallas zig zig-rotationer. När vi utför rätt rotation kommer 10 att röra sig nedåt, och nod 7 kommer uppåt som visas i bilden nedan:
Återigen kommer vi att utföra sicksackrotation åt höger, nod 7 kommer att röra sig nedåt och nod 1 kommer uppåt som visas nedan:
Som vi observerar i ovanstående figur att nod 1 har blivit trädets rotnod; därför är sökningen avslutad.
Anta att vi vill söka efter 20 i trädet nedan.
För att söka 20 måste vi utföra två vänsterrotationer. Följande är stegen som krävs för att söka 20 nod:
Steg 1: Först utför vi standard BST-sökningsoperationen. Eftersom 20 är större än 10 och 15, så kommer det att vara till höger om nod 15.
Steg 2: Det andra steget är att utföra splaying. I detta fall skulle två vänsterrotationer utföras. I den första rotationen kommer nod 10 att röra sig nedåt, och nod 15 flyttas uppåt som visas nedan:
I den andra vänsterrotationen kommer nod 15 att röra sig nedåt, och nod 20 blir trädets rotnod, som visas nedan:
Som vi har observerat utförs två vänsterrotationer; så det är känt som en zig zig vänster rotation.
Hittills har vi läst att både förälder och farförälder är antingen i RR eller LL relation. Nu kommer vi att se RL- eller LR-relationen mellan föräldern och morföräldern.
Låt oss förstå detta fall genom ett exempel.
Anta att vi vill söka efter 13 element i trädet som visas nedan:
Steg 1: Först utför vi standard BST-sökning. Eftersom 13 är större än 10 men mindre än 15, så kommer nod 13 att vara det vänstra barnet till nod 15.
Steg 2: Eftersom nod 13 är till vänster om 15 och nod 15 är till höger om nod 10, så existerar ett RL-förhållande. Först utför vi rätt rotation på nod 15, och 15 kommer att röra sig nedåt, och nod 13 kommer uppåt, som visas nedan:
Ändå är nod 13 inte rotnoden, och 13 är till höger om rotnoden, så vi kommer att utföra vänsterrotation känd som en zag-rotation. Noden 10 kommer att flyttas nedåt och 13 blir rotnoden enligt nedan:
Som vi kan observera i ovanstående träd att nod 13 har blivit rotnoden; därför är sökningen avslutad. I det här fallet har vi först utfört zigrotationen och sedan zagrotationen; så, det är känt som en zig zag rotation.
Låt oss förstå detta fall genom ett exempel.
Anta att vi vill söka efter 9 element i trädet, vilket visas nedan:
Steg 1: Först utför vi standard BST-sökningsoperationen. Eftersom 9 är mindre än 10 men större än 7, så kommer det att vara det rätta barnet till nod 7.
Steg 2: Eftersom nod 9 är till höger om nod 7 och nod 7 är till vänster om nod 10, så existerar ett LR-förhållande. Först utför vi vänsterrotationen på nod 7. Nod 7 kommer att röra sig nedåt, och nod 9 rör sig uppåt som visas nedan:
Fortfarande är noden 9 inte en rotnod, och 9 är till vänster om rotnoden, så vi kommer att utföra den högra rotationen som kallas zig-rotation. Efter att ha utfört rätt rotation blir nod 9 rotnoden, som visas nedan:
Som vi kan observera i ovanstående träd att nod 13 är en rotnod; därför är sökningen avslutad. I det här fallet har vi först utfört zag-rotationen (vänsterrotation), och sedan utförs zig-rotation (högerrotation), så det är känt som en zag-sick-rotation.
Fördelar med Splay tree
- I splayträdet behöver vi inte lagra den extra informationen. Däremot måste vi i AVL-träd lagra balansfaktorn för varje nod som kräver extra utrymme, och röd-svarta träd kräver också att lagra en extra bit information som anger färgen på noden, antingen röd eller svart.
- Det är den snabbaste typen av binärt sökträd för olika praktiska tillämpningar. Den används i Windows NT- och GCC-kompilatorer .
- Det ger bättre prestanda eftersom de ofta åtkomliga noderna kommer att flytta sig närmare rotnoden, vilket gör att elementen kan nås snabbt i splayträd. Den används i cache-implementeringen eftersom den nyligen åtkomna datan lagras i cachen så att vi inte behöver gå till minnet för att komma åt data, och det tar mindre tid.
Nackdelen med Splay tree
Den stora nackdelen med splayträdet skulle vara att träden inte är strikt balanserade, dvs de är grovt balanserade. Ibland är splayträden linjära, så det kommer att ta O(n) tidskomplexitet.
Insättningsoperation i Splay tree
I den införande operation, infogar vi först elementet i trädet och utför sedan spridningsoperationen på det infogade elementet.
15, 10, 17, 7
Steg 1: Först sätter vi in nod 15 i trädet. Efter insättningen måste vi utföra spridning. Eftersom 15 är en rotnod, så behöver vi inte utföra splaying.
Steg 2: Nästa element är 10. Eftersom 10 är mindre än 15, så kommer nod 10 att vara det vänstra barnet till nod 15, som visas nedan:
Nu uppträder vi splaying . För att göra 10 som en rotnod kommer vi att utföra rätt rotation, som visas nedan:
Steg 3: Nästa element är 17. Eftersom 17 är större än 10 och 15 så kommer det att bli det rätta barnet till nod 15.
Nu ska vi spela splaying. Eftersom 17 har en förälder såväl som en morförälder så kommer vi att utföra zig zig rotationer.
I figuren ovan kan vi observera att 17 blir trädets rotnod; därför är insättningen klar.
Steg 4: Nästa element är 7. Eftersom 7 är mindre än 17, 15 och 10, kommer nod 7 att lämnas under 10.
Nu måste vi kasta ut trädet. Eftersom 7 har en förälder såväl som en morförälder så kommer vi att utföra två högerrotationer som visas nedan:
Fortfarande är noden 7 inte en rotnod, den är ett vänster underordnat av rotnoden, dvs. 17. Så vi måste utföra ytterligare en högerrotation för att göra nod 7 till en rotnod som visas nedan:
Algoritm för insättningsoperation
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 ovanstående algoritm är T trädet och n är noden som vi vill infoga. Vi har skapat en tempvariabel som innehåller adressen till rotnoden. Vi kör while-slingan tills värdet på temp blir NULL.
När insättningen är klar kommer spridning att utföras
Algoritm för 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 implementeringen ovan är x den nod på vilken rotationen utförs, medan y är det vänstra barnet till 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 ovan är x den nod på vilken rotationen utförs och y är det högra barnet till noden x.
Radering i Splay-trädet
Eftersom vi vet att spridningsträd är varianterna av det binära sökträdet, så skulle raderingsoperationen i spridningsträdet likna BST, men den enda skillnaden är att borttagningsoperationen följs i spridningsträden av spridningsoperationen.
Typer av raderingar:
Det finns två typer av borttagningar i splayträden:
- Bottom-up spridning
- Top-down splaying
Bottom-up spridning
I bottom-up splaying tar vi först bort elementet från trädet och sedan utför vi splaying på den borttagna noden.
Låt oss förstå raderingen i Splay-trädet.
Anta att vi vill ta bort 12, 14 från trädet som visas nedan:
exempel på binära träd
- Först utför vi helt enkelt standard BST-raderingsoperationen för att ta bort 12 element. Eftersom 12 är en lövnod, så tar vi helt enkelt bort noden från trädet.
Borttagningen är fortfarande inte slutförd. Vi måste sprida föräldern till den borttagna noden, dvs 10. Vi måste utföra Splay(10) på trädet. Som vi kan observera i ovanstående träd att 10 är till höger om nod 7 och nod 7 är till vänster om nod 13. Så först utför vi vänsterrotationen på nod 7 och sedan utför vi högerrotationen på nod 13, som visas nedan:
Ändå är nod 10 inte en rotnod; nod 10 är det vänstra barnet till rotnoden. Så vi måste utföra rätt rotation på rotnoden, d.v.s. 14 för att göra nod 10 till en rotnod som visas nedan:
- Nu måste vi ta bort elementet 14 från trädet, vilket visas nedan:
Som vi vet kan vi inte bara ta bort den interna noden. Vi kommer att ersätta nodens värde antingen genom att använda inorder föregångare eller efterträdare i ordning . Anta att vi använder inorder successor där vi ersätter värdet med det lägsta värdet som finns i det högra underträdet. Det lägsta värdet i det högra underträdet av nod 14 är 15, så vi ersätter värdet 14 med 15. Eftersom nod 14 blir lövnoden, så kan vi helt enkelt ta bort den enligt nedan:
Ändå är borttagningen inte slutförd. Vi måste utföra ytterligare en operation, dvs. splaying där vi måste göra föräldern till den borttagna noden som rotnod. Före raderingen var föräldern till nod 14 rotnoden, dvs 10, så vi behöver utföra någon spridning i detta fall.
Top-down splaying
I top-down splaying utför vi först spridningen som raderingen ska utföras på och tar sedan bort noden från trädet. När elementet har tagits bort kommer vi att utföra joinoperationen.
Låt oss förstå hur man sprider ett exempel uppifrån och ner.
Anta att vi vill ta bort 16 från trädet som visas nedan:
Steg 1: I top-down splaying utför vi först splaying på nod 16. Nod 16 har både förälder och farförälder. Noden 16 är till höger om sin förälder och föräldernoden är också till höger om sin förälder, så detta är en zag-zag-situation. I det här fallet kommer vi först att utföra vänsterrotationen på nod 13 och sedan 14 som visas nedan:
Noden 16 är fortfarande inte en rotnod, och den är ett högerunderlag till rotnoden, så vi måste utföra vänsterrotation på noden 12 för att göra nod 16 till en rotnod.
När noden 16 väl blir en rotnod kommer vi att ta bort noden 16 och vi kommer att få två olika träd, dvs vänster underträd och höger underträd som visas nedan:
Som vi vet att värdena för det vänstra underträdet alltid är mindre än värdena för det högra underträdet. Roten till det vänstra underträdet är 12 och roten i det högra underträdet är 17. Det första steget är att hitta det maximala elementet i det vänstra underträdet. I det vänstra underträdet är det maximala elementet 15, och sedan måste vi utföra spridningsoperation på 15.
Som vi kan observera i ovanstående träd att elementet 15 har en förälder såväl som en morförälder. En nod är höger om sin förälder, och föräldernoden är också höger om sin förälder, så vi måste utföra två vänsterrotationer för att göra nod 15 till en rotnod som visas nedan:
Efter att ha utfört två rotationer på trädet blir nod 15 rotnoden. Som vi kan se är det högra underordnade av 15:an NULL, så vi fäster nod 17 vid den högra delen av 15:an som visas nedan, och denna operation är känd som en Ansluta sig drift.
Obs: Om elementet inte finns i splayträdet, som ska raderas, kommer splaying att utföras. Spridningen skulle utföras på det senast öppnade elementet innan NULL nåddes.
Algoritm för raderingsoperation
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 ovanstående algoritm kontrollerar vi först om roten är Null eller inte; om roten är NULL betyder det att trädet är tomt. Om trädet inte är tomt kommer vi att utföra spridningsoperationen på elementet som ska raderas. När spridningsoperationen är klar kommer vi att jämföra rotdata med elementet som ska raderas; om båda inte är lika betyder det att elementet inte finns i trädet. Om de är lika kan följande fall inträffa:
Fall 1 : Den vänstra delen av roten är NULL, den högra om roten blir rotnoden.
Fall 2 : Om både vänster och höger finns, så sprider vi det maximala elementet i det vänstra underträdet. När spridningen är klar blir det maximala elementet roten till det vänstra underträdet. Det högra underträdet skulle bli det högra barnet till roten till det vänstra underträdet.