A Splay fák önkiegyensúlyozó vagy önbeállított bináris keresőfák. Más szóval azt mondhatjuk, hogy a splay fák a bináris keresőfák változatai. A splay fák előfeltétele, amit tudnunk kell a bináris keresőfákról.
Mint már tudjuk, egy bináris keresőfa időbonyolultsága minden esetben. Egy bináris keresőfa időbonyolultsága átlagos esetben az O(bejelentkezés) az időbonyolultság pedig legrosszabb esetben O(n). Egy bináris keresési fában a bal oldali részfa értéke kisebb, mint a gyökércsomóponté, a jobb oldali részfa értéke pedig nagyobb, mint a gyökércsomóponté; ilyen esetben az időbonyolítás az lenne O(bejelentkezés) . Ha a bináris fa balra vagy jobbra ferde, akkor az időbonyolultság O(n) lenne. A ferdeség korlátozására a AVL és vörös-fekete fa bejött a képbe, miután O(logn ) időbonyolultsága az összes művelethez minden esetben. Ezen az időbonyolításon is javíthatunk gyakorlatiasabb megvalósításokkal, így az új Tree Mi az a Splay Tree?
A splay fa önkiegyensúlyozó fa, de Ekkor az AVL és a Red-Black fák is önkiegyensúlyozó fák. Amitől a splay fa egyedi két fa. Van egy extra tulajdonsága, ami egyedivé teszi, a splaying.
A játékfa ugyanazokat a műveleteket tartalmazza, mint a Bináris keresőfa , azaz beszúrás, törlés és keresés, de tartalmaz még egy műveletet, azaz a kijátszást. Így. a splay fában szereplő összes műveletet kijátszás követi.
A fák nem szigorúan kiegyensúlyozott fák, de nagyjából kiegyensúlyozott fák. Értsük meg a keresési műveletet a splay-fában.
Tegyük fel, hogy 7 elemet akarunk keresni a fában, ami alább látható:
A játékfa bármely elemének kereséséhez először végrehajtjuk a szabványos bináris keresési fa műveletet. Mivel a 7 kisebb, mint 10, így a gyökércsomóponttól balra kerülünk. A keresési művelet végrehajtása után el kell végeznünk a rájátszást. Itt a splay azt jelenti, hogy a művelet, amelyet bármely elemen végrehajtunk, bizonyos átrendezések végrehajtása után gyökércsomóponttá válik. A fa átrendezése a forgatásokon keresztül történik.
Megjegyzés: A splay fa úgy definiálható, mint egy önbeállított fa, amelyben az elemen végrehajtott műveletek átrendeznék a fát úgy, hogy az az elem, amelyen a műveletet végrehajtották, a fa gyökércsomópontjává váljon.
Forgatások
Hat fajta forgatást használnak a kidobáshoz:
- Zig-forgatás (jobbra forgatás)
- Zag forgatás (balra forgatás)
- Cikkcakk (cikk, majd zag)
- Zag zig (Zag, majd zig)
- Zig zig (két jobb elforgatás)
- Zag zag (két balra forgatás)
A forgatás típusának kiválasztásához szükséges tényezők
A forgatás típusának kiválasztásához a következő tényezőket kell használni:
- Van-e nagyszülője annak a csomópontnak, amelyet forgatni próbálunk?
- A csomópont a szülő bal vagy jobb gyermeke?
- A csomópont bal vagy jobb gyermeke a nagyszülőnek?
Tokok a forgatásokhoz
1. eset: Ha a csomópontnak nincs nagyszülője, és az a szülő jobb gyermeke, akkor a balra forgatást hajtjuk végre; ellenkező esetben a megfelelő forgatás történik.
2. eset: Ha a csomópontnak van nagyszülője, akkor a következő forgatókönyvek alapján; a forgatást végrehajtanák:
1. forgatókönyv: Ha a csomópont a szülő joga, és a szülő egyben a szülő joga is, akkor zig zig jobbra forgás előadott.
2. forgatókönyv: Ha a csomópont egy szülőtől balra, de a szülő jobbra van a szülőtől, akkor cikcakk jobbra balra forgatás előadott.
3. forgatókönyv: Ha a csomópont jobb a szülőnek, a szülő pedig a szülőjének, akkor zig zig balra forgatás előadott.
4. forgatókönyv: Ha a csomópont jobbra van a szülőtől, de a szülő bal a szülőtől, akkor cikkcakk jobbra-balra forgatás előadott.
Most pedig értsük meg a fenti forgatásokat példákkal.
A fa átrendezéséhez néhány forgatást kell végrehajtanunk. A következő típusú forgatások szerepelnek a splay fában:
A zig-forgatások akkor használatosak, ha a keresendő elem egy gyökércsomópont vagy egy gyökércsomópont gyermeke (azaz bal vagy jobb oldali gyermek).
A következő esetek fordulhatnak elő a játékfában keresés közben:
1. eset: Ha a keresett elem a fa gyökércsomópontja.
2. eset: Ha a keresési elem a gyökércsomópont gyermeke, akkor a két forgatókönyv lesz ott:
- Ha a gyermek bal oldali gyermek, akkor a jobb oldali forgatást hajtják végre, amelyet ciklikus jobbra forgatásnak neveznek.
- Ha a gyermek jobb oldali gyermek, akkor a balra forgatást hajtják végre, amelyet ciklikus balra forgatásnak neveznek.
Nézzük meg a fenti két forgatókönyvet egy példán keresztül.
Tekintsük az alábbi példát:
A fenti példában 7 elemet kell keresnünk a fában. Az alábbi lépéseket követjük:
1. lépés: Először is összehasonlítjuk a 7-et egy gyökércsomóponttal. Mivel a 7 kisebb, mint 10, így a gyökércsomópont bal gyermeke.
2. lépés: Miután megtaláltuk az elemet, végrehajtjuk a széthúzást. A megfelelő forgatást úgy hajtjuk végre, hogy a 7 legyen a fa gyökércsomópontja, az alábbiak szerint:
Nézzünk egy másik példát.
A fenti példában 20 elemet kell keresnünk a fában. Az alábbi lépéseket követjük:
1. lépés: Először is összehasonlítjuk a 20-at egy gyökércsomóponttal. Mivel a 20 nagyobb, mint a gyökércsomópont, így a gyökércsomópont jobb gyermeke.
2. lépés: Miután megtaláltuk az elemet, végrehajtjuk a széthúzást. A balra forgatást úgy hajtjuk végre, hogy 20 elem legyen a fa gyökércsomópontja.
Néha olyan helyzet adódik, amikor a keresendő tárgynak szülője és nagyszülője is van. Ebben az esetben négy forgatást kell végrehajtanunk a széthúzáshoz.
Értsük meg ezt az esetet egy példán keresztül.
Tegyük fel, hogy 1 elemet kell keresnünk a fában, ami alább látható:
1. lépés: Először is végre kell hajtanunk egy szabványos BST keresési műveletet, hogy megkeressük az 1 elemet. Mivel 1 kisebb, mint 10 és 7, így a 7 csomópont bal oldalán lesz. Ezért az 1. elemnek van szülője, azaz 7, valamint nagyszülője, azaz 10.
2. lépés: Ebben a lépésben splayinget kell végrehajtanunk. Az 1-es csomópontot gyökércsomópontként kell létrehoznunk néhány forgatás segítségével. Ebben az esetben nem végezhetünk egyszerűen cikk- vagy zag-forgatást; zig zig forgatást kell megvalósítanunk.
Ahhoz, hogy az 1-es csomópontot gyökércsomóponttá tegyük, két jobbra forgatást kell végrehajtanunk, amelyeket zig-zig-forgatásnak nevezünk. Ha a megfelelő elforgatást hajtjuk végre, akkor a 10-es lefelé, a 7-es csomópont pedig felfelé fog mozogni, ahogy az alábbi ábrán látható:
Ismét zig jobbra forgatást hajtunk végre, a 7-es csomópont lefelé, az 1-es csomópont pedig felfelé fog jönni, az alábbiak szerint:
Ahogy a fenti ábrán megfigyeljük, az 1. csomópont a fa gyökércsomópontja lett; ezért a keresés befejeződött.
Tegyük fel, hogy 20-at akarunk keresni az alábbi fában.
A 20 kereséséhez két balra forgatást kell végrehajtanunk. A következő lépések szükségesek a 20 csomópont kereséséhez:
1. lépés: Először a szabványos BST keresési műveletet hajtjuk végre. Mivel a 20 nagyobb, mint 10 és 15, így a 15. csomópont jobb oldalán lesz.
2. lépés: A második lépés a rájátszás végrehajtása. Ebben az esetben két balra forgatást kell végrehajtani. Az első forgatásnál a 10-es csomópont lefelé, a 15-ös pedig felfelé, az alábbiak szerint:
A második balra forgatásnál a 15. csomópont lefelé mozog, és a 20. csomópont lesz a fa gyökércsomópontja, amint az alább látható:
Amint megfigyeltük, két balra forgatást hajtunk végre; tehát ciklikus zig balra forgatásnak nevezik.
Eddig azt olvastuk, hogy mind a szülő, mind a nagyszülő RR vagy LL kapcsolatban áll. Most látni fogjuk az RL vagy LR kapcsolatot a szülő és a nagyszülő között.
Értsük meg ezt az esetet egy példán keresztül.
Tegyük fel, hogy 13 elemet akarunk keresni az alábbi fában:
1. lépés: Először szabványos BST keresési műveletet hajtunk végre. Mivel a 13 nagyobb, mint 10, de kisebb, mint 15, így a 13. csomópont a 15. csomópont bal gyermeke lesz.
2. lépés: Mivel a 13. csomópont a 15. csomóponttól balra, a 15. csomópont pedig a 10. csomóponttól jobbra található, így RL kapcsolat létezik. Először a 15-ös csomóponton hajtjuk végre a megfelelő elforgatást, és a 15-ös lefelé, a 13-as pedig felfelé fog mozogni, amint az alább látható:
Ennek ellenére a 13-as csomópont nem a gyökércsomópont, a 13-as pedig a gyökércsomópont jobb oldalán található, ezért balra forgatást hajtunk végre, amelyet zag-forgatásnak nevezünk. A 10-es csomópont lefelé fog mozogni, a 13-as pedig gyökércsomóponttá válik az alábbiak szerint:
Amint azt a fenti fában láthatjuk, a 13-as csomópont lett a gyökércsomópont; ezért a keresés befejeződött. Ebben az esetben először a zig-forgatást, majd a zag-forgatást hajtottuk végre; szóval cikk-cakk forgásnak nevezik.
Értsük meg ezt az esetet egy példán keresztül.
Tegyük fel, hogy 9 elemet akarunk keresni a fában, ami alább látható:
1. lépés: Először a szabványos BST keresési műveletet hajtjuk végre. Mivel a 9 kisebb, mint 10, de nagyobb, mint 7, így ez lesz a 7-es csomópont megfelelő gyermeke.
2. lépés: Mivel a 9. csomópont a 7. csomóponttól jobbra, a 7. csomópont pedig a 10. csomóponttól balra található, így LR kapcsolat létezik. Először a 7-es csomóponton végezzük el a balra forgatást. A 7-es csomópont lefelé, a 9-es pedig felfelé, az alábbiak szerint:
Ennek ellenére a 9-es csomópont nem gyökércsomópont, a 9-es pedig a gyökércsomóponttól balra található, ezért a zig-rotációnak nevezett jobb elforgatást hajtjuk végre. A megfelelő elforgatás végrehajtása után a 9-es csomópont lesz a gyökércsomópont, az alábbiak szerint:
Amint azt a fenti fában láthatjuk, a 13. csomópont gyökércsomópont; ezért a keresés befejeződött. Ebben az esetben először a zig-forgatást (balra forgatást) végeztük el, majd a zig-forgatást (jobbra forgatást) hajtjuk végre, így ez zig-forgatás néven ismert.
A Splay fa előnyei
- A játékfában nem kell tárolnunk a plusz információkat. Ezzel szemben az AVL fákban minden egyes csomópont egyensúlytényezőjét el kell tárolnunk, amely extra helyet igényel, és a vörös-fekete fák esetében is szükség van egy plusz információ tárolására, amely a csomópont színét jelöli, akár piros, akár fekete.
- Ez a leggyorsabb típusú bináris keresőfa különféle gyakorlati alkalmazásokhoz. ben használják Windows NT és GCC fordítók .
- Jobb teljesítményt nyújt, mivel a gyakran elért csomópontok közelebb kerülnek a gyökércsomóponthoz, aminek köszönhetően az elemek gyorsan elérhetők a splay fákban. A cache implementációban használatos, mivel a legutóbb elért adatok a gyorsítótárban tárolódnak, így nem kell a memóriába mennünk az adatok eléréséhez, és ez kevesebb időt vesz igénybe.
A Splay fa hátránya
A splay fa legnagyobb hátránya az lenne, hogy a fák nincsenek szigorúan kiegyensúlyozottak, azaz nagyjából kiegyensúlyozottak. Néha a splay fák lineárisak, ezért O(n) időbe telik a bonyolultság.
Beillesztési művelet a Splay fában
Ban,-ben beillesztés művelettel először beszúrjuk az elemet a fába, majd a beillesztett elemen végrehajtjuk a kijátszási műveletet.
15, 10, 17, 7
1. lépés: Először beillesztjük a 15-ös csomópontot a fába. A beillesztés után el kell végeznünk a szaggatást. Mivel a 15 egy gyökércsomópont, így nem kell splayinget végrehajtanunk.
2. lépés: A következő elem a 10. Mivel a 10 kisebb, mint 15, így a 10. csomópont a 15. csomópont bal gyermeke lesz, amint az alább látható:
Most pedig fellépünk szétszórva . Ahhoz, hogy a 10-et gyökércsomópontként hozzuk létre, végrehajtjuk a megfelelő forgatást, az alábbiak szerint:
3. lépés: A következő elem a 17. Mivel a 17 nagyobb, mint 10 és 15, így ez lesz a 15. csomópont megfelelő gyermeke.
Most játszunk. Mivel 17 évesnek van egy szülője és egy nagyszülője is, ezért cikk-cikk-forgatásokat hajtunk végre.
A fenti ábrán megfigyelhetjük, hogy a 17 lesz a fa gyökércsomópontja; ezért a beillesztés befejeződött.
4. lépés: A következő elem a 7. Mivel a 7 kisebb, mint 17, 15 és 10, így a 7. csomópont a 10 gyermeke marad.
Most ki kell dobnunk a fát. Mivel a 7-nek van egy szülője és egy nagyszülője is, ezért két megfelelő forgatást hajtunk végre az alábbiak szerint:
Ennek ellenére a 7-es csomópont nem gyökércsomópont, hanem a gyökércsomópont bal gyermeke, azaz a 17. Tehát még egy jobbra forgatást kell végrehajtanunk, hogy a 7-es csomópont gyökércsomóponttá váljon az alábbiak szerint:
Algoritmus a beillesztési művelethez
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)
A fenti algoritmusban T a fa, n pedig az a csomópont, amelyet be akarunk szúrni. Létrehoztunk egy temp változót, amely tartalmazza a gyökércsomópont címét. A while ciklust addig futtatjuk, amíg a temp értéke NULL lesz.
A beillesztés befejezése után a széthúzást hajtják végre
A lejátszási művelet algoritmusa
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
A fenti megvalósításban x az a csomópont, amelyen a forgatás történik, míg y az x csomópont bal gyermeke.
A left.rotation(T, x) megvalósítása
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
A fenti megvalósításban x az a csomópont, amelyen a forgatás történik, y pedig az x csomópont jobb gyermeke.
Törlés a Splay fában
Mint tudjuk, hogy a splay fák a bináris keresési fa változatai, így a törlési művelet a splay fában hasonló lenne a BST-hez, de az egyetlen különbség az, hogy a törlési műveletet a splay fákban követi a lejátszási művelet.
A törlések típusai:
Kétféle törlés létezik a megjelenítési fákban:
- Alulról felfelé húzás
- Felülről lefelé játszás
Alulról felfelé húzás
Az alulról felfelé történő lejátszáskor először töröljük az elemet a fából, majd a törölt csomóponton hajtjuk végre a feljátszást.
Értsük meg a törlést a Splay fában.
Tegyük fel, hogy törölni akarjuk a 12, 14 számokat az alábbi fából:
formázza a dátumot karakterláncra
- Először egyszerűen végrehajtjuk a szabványos BST törlési műveletet a 12 elem törléséhez. Mivel a 12 egy levél csomópont, ezért egyszerűen töröljük a csomópontot a fából.
A törlés még mindig nem fejeződött be. Meg kell jelenítenünk a törölt csomópont szülőjét, azaz a 10-et. Játék (10) a fán. Ahogy a fenti fán is láthatjuk, hogy a 10 a 7-es csomóponttól jobbra, a 7-es pedig a 13-as csomóponttól balra található. Tehát először a 7-es csomóponton balra, majd a jobbra forgatjuk a 7-es csomópontot. 13, az alábbiak szerint:
Ennek ellenére a 10-es csomópont nem gyökércsomópont; A 10-es csomópont a gyökércsomópont bal gyermeke. Tehát el kell végeznünk a megfelelő forgatást a gyökércsomóponton, azaz a 14-et, hogy a 10-es csomópontot gyökércsomóponttá tegyük, az alábbiak szerint:
- Most törölnünk kell a 14 elemet a fából, amely alább látható:
Mint tudjuk, a belső csomópontot nem tudjuk egyszerűen törölni. A csomópont értékét bármelyik használatával lecseréljük rend elődje vagy rend utódja . Tegyük fel, hogy sorkövetőt használunk, amelyben az értéket a megfelelő részfában található legalacsonyabb értékre cseréljük. A 14-es csomópont jobb oldali részfájában a legalacsonyabb érték 15, ezért a 14-et 15-re cseréljük. Mivel a 14-es csomópont lesz a levél csomópontja, ezért egyszerűen törölhetjük az alábbiak szerint:
Ennek ellenére a törlés nem fejeződött be. El kell végeznünk még egy műveletet, azaz a splayinget, amelyben a törölt csomópont szülőjét kell gyökércsomópontként megtenni. A törlés előtt a 14-es csomópont szülője a gyökércsomópont volt, azaz a 10-es, tehát ebben az esetben el kell végeznünk az esetleges kiosztást.
Felülről lefelé játszás
A felülről lefelé történő lejátszásnál először azt a feljátszást hajtjuk végre, amelyen a törlést végre kell hajtani, majd töröljük a csomópontot a fából. Az elem törlése után végrehajtjuk az összekapcsolási műveletet.
Értsük meg a felülről lefelé mutató játékot egy példán keresztül.
Tegyük fel, hogy törölni akarjuk a 16-ot az alábbi ábrán látható fából:
1. lépés: A felülről lefelé történő lejátszáskor először a 16 csomóponton hajtjuk végre a kijátszást. A 16 csomópontnak van szülője és nagyszülője is. A 16-os csomópont a szülője jobbján van, és a szülőcsomópont is a szülője jobbján van, tehát ez egy zag-zag helyzet. Ebben az esetben először a 13-as, majd a 14-es csomóponton végezzük el a balra forgatást az alábbiak szerint:
A 16 csomópont még mindig nem gyökércsomópont, hanem a gyökércsomópont jobb oldali gyermeke, ezért balra kell forgatni a 12 csomópontot, hogy a 16 csomópontot gyökércsomópontként hozzuk létre.
Miután a 16 csomópont gyökércsomóponttá válik, töröljük a 16 csomópontot, és két különböző fát kapunk, azaz a bal oldali részfát és a jobb oldali részfát az alábbiak szerint:
Mint tudjuk, a bal oldali részfa értékei mindig kisebbek, mint a jobb oldali részfa értékei. A bal oldali részfa gyökere 12, a jobb oldali részfa gyökere pedig 17. Első lépésként meg kell találni a maximális elemet a bal oldali részfában. A bal oldali részfában a maximális elem 15, majd a 15-ösön kell végrehajtani a kijátszási műveletet.
Amint azt a fenti fában láthatjuk, a 15-ös elemnek szülője és nagyszülője is van. Egy csomópont jobbra van a szülőjétől, és a szülőcsomópont is jobbra van a szülőjétől, ezért két balra forgatást kell végrehajtanunk, hogy a 15-ös csomópontot gyökércsomóponttá tegyük az alábbiak szerint:
A fán végzett két forgatás után a 15. csomópont lesz a gyökércsomópont. Amint látjuk, a 15-ös jobb gyermeke NULL, ezért a 17-es csomópontot a 15-ös jobb oldali részéhez csatoljuk, az alábbiak szerint, és ezt a műveletet csatlakozik művelet.
Megjegyzés: Ha az elem nem szerepel a törlendő splay-fában, akkor a kijátszás végrehajtásra kerül. A lejátszás az utoljára elért elemen történik, mielőtt elérné a NULL értéket.
A törlési művelet algoritmusa
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
A fenti algoritmusban először ellenőrizzük, hogy a gyökér nulla-e vagy sem; ha a gyökér NULL, azt jelenti, hogy a fa üres. Ha a fa nem üres, akkor a törlendő elemen végrehajtjuk a kijátszási műveletet. Miután a lejátszási művelet befejeződött, összehasonlítjuk a gyökéradatokat a törölni kívánt elemmel; ha mindkettő nem egyenlő, azt jelenti, hogy az elem nincs jelen a fában. Ha egyenlőek, akkor a következő esetek fordulhatnak elő:
1. eset : A gyökér bal oldala NULL, a gyökér jobb oldala lesz a gyökércsomópont.
2. eset : Ha bal és jobb is létezik, akkor a maximális elemet a bal oldali részfában játsszuk ki. Amikor a feljátszás befejeződött, a maximális elem lesz a bal oldali részfa gyökere. A jobb oldali részfa lesz a bal oldali részfa gyökerének jobb gyermeke.