„Splay“ medžiai yra savaime išsibalansuojantys arba savaime sureguliuoti dvejetainiai paieškos medžiai. Kitaip tariant, galime sakyti, kad sklaidos medžiai yra dvejetainių paieškos medžių variantai. Prielaida, kurią turėtume žinoti apie dvejetainius paieškos medžius.
Kaip jau žinome, dvejetainio paieškos medžio sudėtingumas laiko atžvilgiu kiekvienu atveju. Dvejetainės paieškos medžio laiko sudėtingumas vidutiniu atveju yra O (prisijungti) o laiko sudėtingumas blogiausiu atveju yra O(n). Dvejetainiame paieškos medyje kairiojo pomedžio reikšmė yra mažesnė nei šakninio mazgo, o dešiniojo pomedžio reikšmė yra didesnė už šakninio mazgo; tokiu atveju laikas būtų sudėtingas O (prisijungti) . Jei dvejetainis medis yra pasviręs į kairę arba į dešinę, laiko sudėtingumas būtų O(n). Norėdami apriboti iškrypimą, AVL ir raudonai juodas medis atėjo į paveikslą, turėdamas O (prisijungti ) laiko sudėtingumas visoms operacijoms visais atvejais. Taip pat galime pagerinti šį laiko sudėtingumą atlikdami praktiškesnius diegimus, todėl naujasis medis Kas yra „Splay Tree“?
Plyšio medis yra savaime išsibalansuojantis medis, bet AVL ir raudonai juodi medžiai taip pat yra savaime išsibalansuojantys medžiai. Kuo medelis yra unikalus, du medžiai. Jis turi vieną papildomą ypatybę, dėl kurios jis yra unikalus, yra pleiskanojimas.
Atkūrimo medyje yra tos pačios operacijos kaip ir a Dvejetainis paieškos medis , ty įterpimas, trynimas ir paieška, bet jame taip pat yra dar viena operacija, t. Taigi. po visų operacijų splay medyje seka splay.
Spygliuočių medžiai nėra griežtai subalansuoti medžiai, tačiau jie yra maždaug subalansuoti medžiai. Supraskime paieškos operaciją splay-medyje.
Tarkime, kad norime ieškoti 7 elemento medyje, kuris parodytas žemiau:
Norėdami ieškoti bet kurio elemento paleidimo medyje, pirmiausia atliksime standartinę dvejetainio medžio paieškos operaciją. Kadangi 7 yra mažesnis nei 10, mes pateksime į kairę nuo šakninio mazgo. Atlikę paieškos operaciją, turime atlikti paleidimą. Čia „splaying“ reiškia, kad operacija, kurią atliekame su bet kuriuo elementu, po tam tikrų pertvarkymų turėtų tapti šakniniu mazgu. Medžio pertvarkymas bus atliekamas per sukimus.
Pastaba: Išsklaidymo medį galima apibrėžti kaip savaime sureguliuotą medį, kuriame bet kuri su elementu atlikta operacija pertvarkytų medį taip, kad elementas, su kuriuo buvo atlikta operacija, taptų šakniniu medžio mazgu.
Pasukimai
Yra šeši sukimosi tipai, naudojami skleidimui:
- Zig sukimas (pasukimas į dešinę)
- Zag pasukimas (pasukimas į kairę)
- Zigzagas (Zig, po kurio seka zagas)
- Zag zig (Zag ir zig)
- Zig zig (du pasukimai į dešinę)
- „Zag zag“ (du pasukimai į kairę)
Veiksniai, reikalingi renkantis sukimosi tipą
Renkantis sukimosi tipą naudojami šie veiksniai:
- Ar mazgas, kurį bandome pasukti, turi senelį?
- Ar mazgas kairysis ar dešinysis tėvų vaikas?
- Ar kairysis ar dešinysis mazgas yra senelio vaikas?
Rotacijų dėklai
1 atvejis: Jei mazgas neturi senelio, o jei tai yra dešinysis tėvo vaikas, tada atliekame sukimąsi į kairę; kitu atveju atliekamas tinkamas sukimas.
2 atvejis: Jei mazgas turi senelį, tada remiantis šiais scenarijais; sukimas būtų atliekamas:
1 scenarijus: Jei mazgas yra pirminio, o pirminis taip pat yra pirminio, tada zig zig dešinėn sukimasis į dešinę atliekamas.
2 scenarijus: Jei mazgas yra kairėje iš pirminio, bet pirminis yra dešinėje nuo pirminio, tada zigzago sukimas į dešinę į kairę atliekamas.
3 scenarijus: Jei mazgas yra dešinėje pirminio, o pirminis yra pirminio, tada zig zig sukimas į kairę atliekamas.
4 scenarijus: Jei mazgas yra dešinėje iš pirminio, o pirminis yra kairėje iš pirminio, tada zigzaginis sukimasis į dešinę į kairę atliekamas.
Dabar supraskime aukščiau pateiktus sukimus su pavyzdžiais.
Norėdami pertvarkyti medį, turime atlikti kai kuriuos pasukimus. Toliau pateikiami sukimosi tipai sklaidos medyje:
Zig pasukimai naudojami, kai ieškomas elementas yra šakninis mazgas arba šakninio mazgo antrinis (t. y. kairysis arba dešinysis antrinis).
Toliau pateikiami atvejai, kurie gali atsirasti paieškos medyje:
1 atvejis: Jei paieškos elementas yra šakninis medžio mazgas.
2 atvejis: Jei paieškos elementas yra antrinis šakninio mazgo, tada ten bus du scenarijai:
- Jei vaikas yra kairysis vaikas, bus atliekamas sukimas į dešinę, žinomas kaip sukimasis į dešinę.
- Jei vaikas yra dešinysis vaikas, bus atliekamas sukimas į kairę, žinomas kaip sukimasis į kairę.
Pažvelkime į du pirmiau minėtus scenarijus per pavyzdį.
Apsvarstykite toliau pateiktą pavyzdį:
Aukščiau pateiktame pavyzdyje turime ieškoti 7 elementų medyje. Mes atliksime toliau nurodytus veiksmus.
1 žingsnis: Pirma, lyginame 7 su šakniniu mazgu. Kadangi 7 yra mažesnis nei 10, tai yra kairysis šakninio mazgo vaikas.
2 žingsnis: Kai elementas bus rastas, atliksime skleidimą. Tinkamas sukimas atliekamas taip, kad 7 taptų medžio šaknies mazgu, kaip parodyta žemiau:
Panagrinėkime kitą pavyzdį.
Aukščiau pateiktame pavyzdyje turime ieškoti 20 elementų medyje. Mes atliksime toliau nurodytus veiksmus.
1 žingsnis: Pirmiausia palyginame 20 su šaknies mazgu. Kadangi 20 yra didesnis nei šakninis mazgas, tai yra dešinysis šakninio mazgo antrinis.
2 žingsnis: Kai elementas bus rastas, atliksime skleidimą. Kairysis sukimas atliekamas taip, kad 20 elementų taptų medžio šaknies mazgu.
Kartais susidaro situacija, kai ieškomas daiktas turi ne tik tėvus, bet ir senelius. Šiuo atveju mes turime atlikti keturis apsisukimus, kad galėtume pasukti.
Supraskime šį atvejį per pavyzdį.
Tarkime, kad turime ieškoti 1 elemento medyje, kuris parodytas žemiau:
1 žingsnis: Pirmiausia, norėdami ieškoti 1 elemento, turime atlikti standartinę BST paieškos operaciją. Kadangi 1 yra mažesnis už 10 ir 7, taip jis bus mazgo 7 kairėje. Todėl 1 elementas turi pirminį elementą, t. y. 7, taip pat senelį, t. y. 10.
2 žingsnis: Šiame žingsnyje turime atlikti paleidimą. Kai kurių pasukimų pagalba turime padaryti 1 mazgą kaip šakninį mazgą. Šiuo atveju negalime tiesiog atlikti zig arba zag pasukimo; turime įgyvendinti zig zig sukimąsi.
Kad 1 mazgas būtų šakninis mazgas, turime atlikti du teisingus pasukimus, žinomus kaip zig zig sukimai. Kai atliksime tinkamą sukimąsi, 10 pajudės žemyn, o 7 mazgas kils aukštyn, kaip parodyta toliau pateiktame paveikslėlyje:
Vėlgi, mes suksime zig į dešinę, 7 mazgas judės žemyn, o 1 mazgas kils aukštyn, kaip parodyta žemiau:
Kaip matome aukščiau esančiame paveikslėlyje, 1 mazgas tapo šakniniu medžio mazgu; todėl paieška baigta.
Tarkime, kad žemiau esančiame medyje norime ieškoti 20.
Norėdami ieškoti 20, turime atlikti du pasukimus į kairę. Norint ieškoti 20 mazgo, reikia atlikti šiuos veiksmus:
1 žingsnis: Pirmiausia atliekame standartinę BST paieškos operaciją. Kadangi 20 yra didesnis nei 10 ir 15, jis bus 15 mazgo dešinėje.
2 žingsnis: Antrasis žingsnis yra paleisti. Tokiu atveju būtų atliekami du sukimai į kairę. Pirmojo sukimo metu mazgas 10 judės žemyn, o 15 mazgas judės aukštyn, kaip parodyta toliau:
Antrame kairiajame pasukime 15 mazgas judės žemyn, o 20 mazgas taps šakniniu medžio mazgu, kaip parodyta toliau:
Kaip pastebėjome, atliekami du sukimai į kairę; todėl jis žinomas kaip zig zig sukimas į kairę.
Iki šiol skaitėme, kad tiek tėvai, tiek seneliai yra RR arba LL santykiuose. Dabar pamatysime RL arba LR santykius tarp tėvų ir senelių.
Supraskime šį atvejį per pavyzdį.
Tarkime, kad norime ieškoti 13 elementų medyje, kuris parodytas žemiau:
1 žingsnis: Pirmiausia atliekame standartinę BST paieškos operaciją. Kadangi 13 yra didesnis nei 10, bet mažesnis nei 15, todėl 13 mazgas bus kairysis 15 mazgo vaikas.
2 žingsnis: Kadangi 13 mazgas yra kairėje nuo 15, o 15 mazgas yra 10 mazgo dešinėje, tai RL ryšys egzistuoja. Pirmiausia atliekame teisingą 15 mazgo pasukimą, o 15 pajudės žemyn, o 13 mazgas kils aukštyn, kaip parodyta toliau:
Vis dėlto 13 mazgas nėra šakninis mazgas, o 13 yra šakninio mazgo dešinėje, todėl atliksime sukimąsi į kairę, žinomą kaip zaginis sukimas. 10 mazgas judės žemyn, o 13 taps šakniniu mazgu, kaip parodyta toliau:
Kaip matome aukščiau esančiame medyje, 13 mazgas tapo šaknies mazgu; todėl paieška baigta. Šiuo atveju pirmiausia atlikome ziginį pasukimą, o tada – zaginį pasukimą; taigi, tai žinoma kaip sukimasis zigzagu.
Supraskime šį atvejį per pavyzdį.
Tarkime, kad norime ieškoti 9 elementų medyje, kuris parodytas žemiau:
1 žingsnis: Pirmiausia atliekame standartinę BST paieškos operaciją. Kadangi 9 yra mažesnis nei 10, bet didesnis nei 7, tai bus tinkamas 7 mazgo vaikas.
2 žingsnis: Kadangi 9 mazgas yra 7 mazgo dešinėje, o 7 mazgas yra 10 mazgo kairėje, tai LR ryšys egzistuoja. Pirmiausia atliekame 7 mazgo pasukimą į kairę. 7 mazgas judės žemyn, o 9 – aukštyn, kaip parodyta toliau:
Vis dėlto mazgas 9 nėra šakninis mazgas, o 9 yra šakninio mazgo kairėje, todėl atliksime tinkamą sukimąsi, žinomą kaip zig sukimas. Atlikus tinkamą sukimąsi, 9 mazgas tampa šakniniu mazgu, kaip parodyta toliau:
Kaip matome aukščiau esančiame medyje, 13 mazgas yra šakninis mazgas; todėl paieška baigta. Šiuo atveju pirmiausia atlikome ziginį sukimąsi (sukimas į kairę), o tada atliekamas ziginis sukimas (sukimas į dešinę), todėl jis žinomas kaip ziginis sukimasis.
Splay medžio privalumai
- Skaičiavimo medyje mums nereikia saugoti papildomos informacijos. Priešingai, AVL medžiuose turime saugoti kiekvieno mazgo, kuriam reikia papildomos vietos, balanso koeficientą, o raudonai juodi medžiai taip pat reikalauja saugoti vieną papildomą informacijos bitą, nurodantį mazgo spalvą – raudoną arba juodą.
- Tai greičiausias dvejetainės paieškos medžio tipas įvairiems praktiniams pritaikymams. Jis naudojamas Windows NT ir GCC kompiliatoriai .
- Tai užtikrina geresnį našumą, nes dažnai pasiekiami mazgai judės arčiau šakninio mazgo, todėl elementus galima greitai pasiekti išskleidimo medžiuose. Jis naudojamas talpyklos diegime, nes neseniai pasiekti duomenys yra saugomi talpykloje, todėl mums nereikia eiti į atmintį norint pasiekti duomenis ir tai užtrunka mažiau laiko.
Splay medžio trūkumas
Pagrindinis skliauto medžio trūkumas būtų tas, kad medžiai nėra griežtai subalansuoti, t. y. jie yra maždaug subalansuoti. Kartais tarpo medžiai yra linijiniai, todėl tai užtruks O (n) laiko sudėtingumo.
Įterpimo operacija Splay medyje
Viduje įterpimas operaciją, pirmiausia įterpiame elementą į medį, o po to atliekame įterpto elemento pakeitimo operaciją.
15, 10, 17, 7
1 žingsnis: Pirmiausia į medį įterpiame 15 mazgą. Po įdėjimo turime atlikti paleidimą. Kadangi 15 yra šakninis mazgas, mums nereikia atlikti keitimo.
2 žingsnis: Kitas elementas yra 10. Kadangi 10 yra mažesnis nei 15, 10 mazgas bus kairysis 15 mazgo antrinis, kaip parodyta toliau:
Dabar mes koncertuojame svaidymasis . Norėdami sukurti 10 kaip šakninį mazgą, atliksime tinkamą sukimąsi, kaip parodyta toliau:
3 veiksmas: Kitas elementas yra 17. Kadangi 17 yra didesnis nei 10 ir 15, jis taps tinkamu 15 mazgo antriniu elementu.
Dabar atliksime grojimą. Kadangi 17 metų turi tėvus ir senelius, todėl atliksime zig zig sukimus.
Aukščiau pateiktame paveikslėlyje galime pastebėti, kad 17 tampa medžio šaknies mazgu; todėl įterpimas baigtas.
4 veiksmas: Kitas elementas yra 7. Kadangi 7 yra mažesnis nei 17, 15 ir 10, 7 mazgas bus paliktas antrinis iš 10.
Dabar mes turime išbarstyti medį. Kadangi 7 turi vieną iš tėvų ir senelių, todėl atliksime du teisingus pasukimus, kaip parodyta toliau:
Vis dėlto mazgas 7 nėra šakninis mazgas, jis yra kairysis šakninio mazgo antrinis, t.
Įterpimo operacijos algoritmas
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)
Aukščiau pateiktame algoritme T yra medis, o n yra mazgas, kurį norime įterpti. Sukūrėme laikinąjį kintamąjį, kuriame yra šakninio mazgo adresas. Vykdysime while kilpą, kol temp reikšmė taps NULL.
Kai įterpimas bus baigtas, bus atliktas paleidimas
Žaidimo operacijos algoritmas
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
Aukščiau pateiktame įgyvendinime x yra mazgas, kuriame atliekamas sukimas, o y yra kairysis mazgo x vaikas.
Į kairę.sukimo(T, x) įgyvendinimas
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
Aukščiau pateiktame įgyvendinime x yra mazgas, kuriame atliekamas sukimas, o y yra dešinysis mazgo x vaikas.
Ištrynimas Splay medyje
Kaip žinome, kad keitimo medžiai yra dvejetainio paieškos medžio variantai, todėl ištrynimo operacija pakeitimo medyje būtų panaši į BST, tačiau vienintelis skirtumas yra tas, kad po trynimo operacijos keitimo medžiuose seka ir paleidimo operacija.
Ištrynimų tipai:
Ištrynimo medžiuose yra dviejų tipų ištrynimai:
- Spardymas iš apačios į viršų
- Žaidimas iš viršaus į apačią
Spardymas iš apačios į viršų
Atkuriant iš apačios į viršų, pirmiausia ištriname elementą iš medžio ir tada atliekame ištrynimo mazgo paleidimą.
Supraskime ištrynimą „Splay“ medyje.
Tarkime, kad norime ištrinti 12, 14 iš toliau pateikto medžio:
konvertuoti nfa į dfa
- Pirma, mes tiesiog atliekame standartinę BST ištrynimo operaciją, kad pašalintume 12 elementų. Kadangi 12 yra lapo mazgas, mes tiesiog pašaliname mazgą iš medžio.
Ištrynimas vis dar nebaigtas. Turime atskleisti ištrinto mazgo pirminį elementą, t. y. 10. Turime atlikti Žaidimas (10) ant medžio. Kaip matome aukščiau esančiame medyje, 10 yra 7 mazgo dešinėje, o 7 mazgas yra 13 mazgo kairėje. Taigi pirmiausia atliekame 7 mazgo pasukimą į kairę, o tada atliekame mazgo sukimąsi dešinėje pusėje. 13, kaip parodyta žemiau:
Vis dėlto 10 mazgas nėra šakninis mazgas; 10 mazgas yra kairysis šakninio mazgo vaikas. Taigi, turime atlikti tinkamą šakninio mazgo pasukimą, ty 14, kad 10 mazgas taptų šakniniu mazgu, kaip parodyta toliau:
- Dabar turime ištrinti 14 elementą iš medžio, kuris parodytas žemiau:
Kaip žinome, negalime tiesiog ištrinti vidinio mazgo. Mazgo vertę pakeisime naudodami įsakymo pirmtakas arba įsakymo įpėdinis . Tarkime, kad naudojame eilės įpėdinį, kuriame reikšmę pakeičiame mažiausia reikšme, esančia dešiniajame pomedyje. Mažiausia 14 mazgo dešiniojo pomedžio reikšmė yra 15, todėl 14 reikšmę pakeičiame 15. Kadangi 14 mazgas tampa lapo mazgu, todėl galime jį tiesiog ištrinti, kaip parodyta toliau:
Vis dėlto ištrynimas nebaigtas. Turime atlikti dar vieną operaciją, t. y. paleisti, kai ištrinto mazgo pirminį elementą turime padaryti kaip šakninį mazgą. Prieš ištrynimą 14 mazgo pirminis mazgas buvo šakninis mazgas, t. y. 10, todėl šiuo atveju turime atlikti bet kokį pakeitimą.
Žaidimas iš viršaus į apačią
Iš viršaus į apačią iš pradžių atliekame paleidimą, kuriame turi būti atliktas trynimas, o tada ištriname mazgą iš medžio. Kai elementas bus ištrintas, atliksime sujungimo operaciją.
Supraskime iš viršaus į apačią per pavyzdį.
Tarkime, kad norime ištrinti 16 iš medžio, kuris parodytas žemiau:
1 žingsnis: Iš viršaus į apačią, pirmiausia atliekame išjungimą 16 mazge. 16 mazgas turi ir pirminį, ir senelį. 16 mazgas yra pirminio mazgo dešinėje, o pirminis mazgas taip pat yra pirminio mazgo dešinėje, todėl tai yra zag zag situacija. Tokiu atveju pirmiausia atliksime 13 ir 14 mazgo pasukimą į kairę, kaip parodyta žemiau:
16 mazgas vis dar nėra šakninis mazgas, o dešinysis šakninio mazgo antrinis, todėl turime atlikti 12 mazgo pasukimą į kairę, kad 16 mazgas būtų šakninis mazgas.
Kai mazgas 16 taps šaknies mazgu, ištrinsime 16 mazgą ir gausime du skirtingus medžius, t. y. kairįjį pomedį ir dešinįjį pomedį, kaip parodyta toliau:
Kaip žinome, kairiojo pomedžio reikšmės visada yra mažesnės nei dešiniojo pomedžio reikšmės. Kairiojo pomedžio šaknis yra 12, o dešiniojo pomedžio šaknis yra 17. Pirmiausia reikia rasti maksimalų elementą kairiajame pomedyje. Kairiajame pomedyje didžiausias elementas yra 15, o tada turime atlikti 15 paleidimo operaciją.
Kaip matome aukščiau esančiame medyje, 15 elementas turi ir tėvą, ir senelį. Mazgas yra dešinėje nuo pirminio, o pagrindinis mazgas taip pat yra dešinėje nuo pirminio, todėl turime atlikti du pasukimus į kairę, kad 15 mazgas taptų šakniniu mazgu, kaip parodyta toliau:
Atlikus du medžio pasukimus, 15 mazgas tampa šaknies mazgu. Kaip matome, dešinysis 15 antrinis skaičius yra NULL, todėl 17 mazgą pridedame dešinėje 15 dalyje, kaip parodyta toliau, ir ši operacija žinoma kaip prisijungti operacija.
Pastaba: Jei elemento nėra keitimo medyje, kuris turi būti ištrintas, bus atliktas pakeitimas. Paleidimas būtų atliktas paskutiniame prieiga prie elemento prieš pasiekiant NULL.
Ištrynimo operacijos algoritmas
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
Aukščiau pateiktame algoritme pirmiausia patikriname, ar šaknis yra Null, ar ne; jei šaknis yra NULL, tai reiškia, kad medis tuščias. Jei medis nėra tuščias, mes atliksime paleidimo operaciją elementui, kurį norime ištrinti. Kai paleidimo operacija bus baigta, mes palyginsime šakninius duomenis su elementu, kurį reikia ištrinti; jei abu nėra lygūs, reiškia, kad elemento medyje nėra. Jei jie yra vienodi, gali atsirasti šie atvejai:
1 atvejis : Kairė šaknies pusė yra NULL, dešinė šaknies dalis tampa šaknies mazgu.
2 atvejis : Jei egzistuoja ir kairysis, ir dešinysis, tada kairiajame pomedyje paskleidžiame maksimalų elementą. Baigus paleisti, maksimalus elementas tampa kairiojo pomedžio šaknimi. Dešinysis pomedis taptų kairiojo pomedžio šaknies dešiniuoju pomedžiu.