Izkliedes koki ir pašbalansējoši vai pašregulēti binārie meklēšanas koki. Citiem vārdiem sakot, mēs varam teikt, ka izkliedes koki ir bināro meklēšanas koku varianti. Priekšnoteikums izkliedēšanas kokiem, kas mums būtu jāzina par binārajiem meklēšanas kokiem.
Kā mēs jau zinām, binārā meklēšanas koka laika sarežģītība katrā gadījumā. Binārā meklēšanas koka laika sarežģītība vidējā gadījumā ir O(pieteikties) un laika sarežģītība sliktākajā gadījumā ir O(n). Binārajā meklēšanas kokā kreisā apakškoka vērtība ir mazāka par saknes mezglu, bet labā apakškoka vērtība ir lielāka par saknes mezglu; tādā gadījumā laika sarežģītība būtu O(pieteikties) . Ja binārais koks ir šķībs pa kreisi vai pa labi, tad laika sarežģītība būtu O(n). Lai ierobežotu šķībumu, AVL un Red-Black koks ienāca attēlā, kam O(pieteikties ) laika sarežģītība visām operācijām visos gadījumos. Mēs varam arī uzlabot šo laika sarežģītību, veicot praktiskākas ieviešanas, tāpēc jaunais koks Kas ir Splay Tree?
Izplešanās koks ir pašbalansējošs koks, bet AVL un Red-Black koki tad arī ir pašbalansējoši koki. Kas padara splay koku unikālu divi koki. Tam ir viena papildu īpašība, kas padara to unikālu, ir izkliedēšana.
Atvēršanas koks satur tādas pašas darbības kā a Binārais meklēšanas koks , t.i., ievietošana, dzēšana un meklēšana, bet tajā ir arī vēl viena darbība, t.i., izkliedēšana. Tātad. visām operācijām spēlēšanas kokā seko izspēle.
Splejas koki nav stingri līdzsvaroti koki, bet tie ir aptuveni līdzsvaroti koki. Sapratīsim meklēšanas darbību izkliedēšanas kokā.
Pieņemsim, ka mēs vēlamies meklēt 7 elementu kokā, kas parādīts zemāk:
Lai meklētu jebkuru elementu spēlēšanas kokā, vispirms mēs veiksim standarta binārā meklēšanas koka darbību. Tā kā 7 ir mazāks par 10, mēs nonāksim pa kreisi no saknes mezgla. Pēc meklēšanas darbības veikšanas mums ir jāveic izspēlēšana. Šeit izspēlēšana nozīmē, ka darbībai, ko veicam jebkuram elementam, pēc dažu pārkārtojumu veikšanas jākļūst par saknes mezglu. Koka pārkārtošana tiks veikta, izmantojot rotācijas.
Piezīme. Izplešanās koku var definēt kā pašregulētu koku, kurā jebkura elementam veiktā darbība pārkārtotu koku tā, lai elements, kuram ir veikta darbība, kļūtu par koka saknes mezglu.
Rotācijas
Izspiešanai tiek izmantoti sešu veidu rotācijas:
- Zig rotācija (pa labi)
- Zag pagriešana (pa kreisi)
- Zig zags (Zig, kam seko zags)
- Zag zig (Zag, kam seko zig)
- Zig zig (divi pagriezieni pa labi)
- Zag zag (divi pagriezieni pa kreisi)
Faktori, kas nepieciešami, lai izvēlētos rotācijas veidu
Lai izvēlētos rotācijas veidu, tiek izmantoti šādi faktori:
- Vai mezglam, kuru cenšamies pagriezt, ir vecvecāks?
- Vai mezgls ir vecāka kreisais vai labais bērns?
- Vai mezgls ir vecvecāka kreisais vai labais bērns?
Rotāciju futrāļi
1. gadījums: Ja mezglam nav vecvecāka un ja tas ir vecāka labais bērns, mēs veicam kreiso rotāciju; pretējā gadījumā tiek veikta pareizā rotācija.
2. gadījums: Ja mezglam ir vecvecāks, tad, pamatojoties uz šādiem scenārijiem; rotācija tiks veikta:
1. scenārijs: Ja mezglam ir vecāka tiesības un vecākam ir arī tā vecāka tiesības, tad zig zig pa labi rotācija tiek veikta.
2. scenārijs: Ja mezgls ir pa kreisi no vecāka, bet vecāks ir pa labi no tā vecāka, tad zig zag pa labi pa kreisi rotācija tiek veikta.
3. scenārijs: Ja mezglam ir tiesības no vecāka un vecākam ir tiesības no tā vecāka, tad zig zig pa kreisi rotācija tiek veikta.
4. scenārijs: Ja mezgls atrodas pa labi no vecāka, bet vecāks ir pa kreisi no vecāka, tad zig zag pa labi-pa kreisi rotācija tiek veikta.
Tagad sapratīsim iepriekš minētās rotācijas ar piemēriem.
Lai pārkārtotu koku, mums ir jāveic dažas rotācijas. Tālāk ir norādīti griešanās veidi izkliedēšanas kokā:
Zig rotācijas tiek izmantotas, ja meklējamais vienums ir vai nu saknes mezgls, vai saknes mezgla atvasinājums (t.i., pa kreisi vai pa labi).
Tālāk ir norādīti gadījumi, kas meklēšanas laikā var pastāvēt spēles kokā:
1. gadījums: Ja meklēšanas vienums ir koka saknes mezgls.
2. gadījums: Ja meklēšanas vienums ir saknes mezgla atvasinātais vienums, tur būs divi scenāriji:
- Ja bērns ir kreisais bērns, tiks veikta rotācija pa labi, kas pazīstama kā zig pa labi.
- Ja bērns ir pareizais bērns, tiks veikta pagriešana pa kreisi, kas pazīstama kā zig pa kreisi.
Apskatīsim divus iepriekš minētos scenārijus, izmantojot piemēru.
Apsveriet tālāk sniegto piemēru:
Iepriekš minētajā piemērā mums ir jāmeklē 7 elementi kokā. Mēs izpildīsim tālāk norādītās darbības.
1. darbība: Pirmkārt, mēs salīdzinām 7 ar saknes mezglu. Tā kā 7 ir mazāks par 10, tas ir saknes mezgla kreisais bērns.
2. darbība: Kad elements ir atrasts, mēs veiksim izspēli. Pareiza rotācija tiek veikta tā, lai 7 kļūtu par koka saknes mezglu, kā parādīts zemāk:
Apskatīsim citu piemēru.
Iepriekš minētajā piemērā mums ir jāmeklē 20 elementi kokā. Mēs izpildīsim tālāk norādītās darbības.
1. darbība: Pirmkārt, mēs salīdzinām 20 ar saknes mezglu. Tā kā 20 ir lielāks par saknes mezglu, tas ir saknes mezgla pareizais bērns.
2. darbība: Kad elements ir atrasts, mēs veiksim izspēli. Kreisā rotācija tiek veikta tā, lai 20 elementi kļūtu par koka saknes mezglu.
Dažkārt rodas situācija, kad pārmeklējamai precei ir gan viens no vecākiem, gan vecvecākiem. Šajā gadījumā mums ir jāveic četras rotācijas, lai izspēlētu.
Izpratīsim šo gadījumu, izmantojot piemēru.
Pieņemsim, ka mums ir jāmeklē 1 elements kokā, kas parādīts zemāk:
1. darbība: Pirmkārt, mums ir jāveic standarta BST meklēšanas darbība, lai meklētu 1 elementu. Tā kā 1 ir mazāks par 10 un 7, tā būs pa kreisi no mezgla 7. Tāpēc elementam 1 ir vecāks, t.i., 7, kā arī vecvecāks, t.i., 10.
2. darbība: Šajā solī mums ir jāveic izspēle. Mums ir jāpadara 1. mezgls par saknes mezglu ar dažu rotāciju palīdzību. Šajā gadījumā mēs nevaram vienkārši veikt zig vai zag rotāciju; mums ir jāievieš zig zig rotācija.
Lai mezglu 1 padarītu par saknes mezglu, mums ir jāveic divas pareizās rotācijas, kas pazīstamas kā zig zig rotācijas. Kad mēs veiksim pareizo rotāciju, 10 pārvietosies uz leju, bet mezgls 7 nāks uz augšu, kā parādīts zemāk esošajā attēlā:
Atkal mēs veiksim zig pa labi, mezgls 7 pārvietosies uz leju, un mezgls 1 nāks uz augšu, kā parādīts zemāk:
Iepriekš redzamajā attēlā redzams, ka mezgls 1 ir kļuvis par koka saknes mezglu; tāpēc meklēšana ir pabeigta.
Pieņemsim, ka mēs vēlamies meklēt 20 zemāk esošajā kokā.
Lai meklētu 20, mums ir jāveic divas pagriešanas pa kreisi. Lai meklētu 20 mezglu, jāveic šādas darbības:
1. darbība: Pirmkārt, mēs veicam standarta BST meklēšanas darbību. Tā kā 20 ir lielāks par 10 un 15, tas būs pa labi no mezgla 15.
2. darbība: Otrais solis ir izspēlēt. Šajā gadījumā tiktu veiktas divas pagriešanas pa kreisi. Pirmajā rotācijā mezgls 10 pārvietosies uz leju, bet mezgls 15 virzīsies uz augšu, kā parādīts tālāk:
Otrajā pagriezienā pa kreisi mezgls 15 pārvietosies uz leju, un mezgls 20 kļūst par koka saknes mezglu, kā parādīts zemāk:
Kā mēs novērojām, tiek veiktas divas kreisās rotācijas; tāpēc to sauc par zig zig pa kreisi rotāciju.
Līdz šim esam lasījuši, ka gan vecāki, gan vecvecāki ir vai nu RR, vai LL attiecībās. Tagad mēs redzēsim RL vai LR attiecības starp vecāku un vecvecāku.
Izpratīsim šo gadījumu, izmantojot piemēru.
Pieņemsim, ka mēs vēlamies meklēt 13 elementu kokā, kas parādīts zemāk:
1. darbība: Pirmkārt, mēs veicam standarta BST meklēšanas darbību. Tā kā 13 ir lielāks par 10, bet mazāks par 15, 13. mezgls būs 15. mezgla kreisais atvasinātais.
2. darbība: Tā kā mezgls 13 atrodas pa kreisi no 15 un mezgls 15 atrodas pa labi no mezgla 10, pastāv RL attiecības. Pirmkārt, mēs veicam pareizo rotāciju mezglā 15, un 15 pārvietosies uz leju, un mezgls 13 tiks pacelts, kā parādīts zemāk:
Tomēr mezgls 13 nav saknes mezgls, bet 13. atrodas pa labi no saknes mezgla, tāpēc mēs veiksim rotāciju pa kreisi, kas pazīstama kā zag rotācija. Mezgls 10 pārvietosies uz leju, un 13 kļūs par saknes mezglu, kā parādīts tālāk:
Kā mēs varam novērot iepriekš minētajā kokā, mezgls 13 ir kļuvis par saknes mezglu; tāpēc meklēšana ir pabeigta. Šajā gadījumā mēs vispirms esam veikuši zig rotāciju un pēc tam zag rotāciju; tātad tas ir pazīstams kā zig-zag rotācija.
Izpratīsim šo gadījumu, izmantojot piemēru.
Pieņemsim, ka mēs vēlamies meklēt 9 elementu kokā, kas parādīts zemāk:
1. darbība: Pirmkārt, mēs veicam standarta BST meklēšanas darbību. Tā kā 9 ir mazāks par 10, bet lielāks par 7, tas būs 7. mezgla pareizais atvasinātais.
2. darbība: Tā kā mezgls 9 atrodas pa labi no mezgla 7 un mezgls 7 atrodas pa kreisi no mezgla 10, pastāv LR saistība. Vispirms mēs veicam 7. mezgla pagriešanu pa kreisi. 7. mezgls pārvietosies uz leju, bet 9. mezgls virzīsies uz augšu, kā parādīts tālāk:
Tomēr mezgls 9 nav saknes mezgls, bet 9 atrodas pa kreisi no saknes mezgla, tāpēc mēs veiksim pareizo rotāciju, kas pazīstama kā zig rotācija. Pēc pareizās rotācijas veikšanas mezgls 9 kļūst par saknes mezglu, kā parādīts zemāk:
Kā mēs varam novērot iepriekš minētajā kokā, mezgls 13 ir saknes mezgls; tāpēc meklēšana ir pabeigta. Šajā gadījumā mēs vispirms esam veikuši zig rotāciju (griešanu pa kreisi), un pēc tam tiek veikta zig pagriešana (pa labi), tāpēc to sauc par zig rotāciju.
Splay koka priekšrocības
- Atklāšanas kokā mums nav jāuzglabā papildu informācija. Turpretim AVL kokos mums ir jāsaglabā katra mezgla līdzsvara koeficients, kam nepieciešama papildu vieta, un sarkanmelnajiem kokiem ir jāsaglabā arī viens papildu informācijas bits, kas apzīmē mezgla krāsu — sarkanu vai melnu.
- Tas ir ātrākais binārās meklēšanas koka veids dažādiem praktiskiem lietojumiem. Tas tiek izmantots Windows NT un GCC kompilatori .
- Tas nodrošina labāku veiktspēju, jo bieži pieejamie mezgli pārvietosies tuvāk saknes mezglam, kā rezultātā elementiem var ātri piekļūt izkliedēšanas kokos. To izmanto kešatmiņas ieviešanā, jo nesen piekļūtie dati tiek glabāti kešatmiņā, tāpēc mums nav jādodas uz atmiņu, lai piekļūtu datiem, un tas aizņem mazāk laika.
Splay koka trūkums
Lielākais izplešanās koka trūkums būtu tas, ka koki nav stingri līdzsvaroti, t.i., tie ir aptuveni līdzsvaroti. Dažreiz izkliedes koki ir lineāri, tāpēc tas prasīs O(n) laika sarežģītību.
Ievietošanas darbība Splay kokā
Iekš ievietošana operāciju, mēs vispirms ievietojam elementu kokā un pēc tam veicam izspēlēšanas darbību ievietotajam elementam.
15, 10, 17, 7
1. darbība: Vispirms kokā ievietojam mezglu 15. Pēc ievietošanas mums ir jāveic izspēle. Tā kā 15 ir saknes mezgls, mums nav jāveic izkliedēšana.
2. darbība: Nākamais elements ir 10. Tā kā 10 ir mazāks par 15, mezgls 10 būs 15. mezgla kreisais atvasinātais, kā parādīts tālāk:
Tagad mēs uzstājamies izspēle . Lai izveidotu 10 kā saknes mezglu, mēs veiksim pareizo rotāciju, kā parādīts zemāk:
3. darbība: Nākamais elements ir 17. Tā kā 17 ir lielāks par 10 un 15, tas kļūs par 15. mezgla pareizo atvasi.
Tagad mēs veiksim izspēli. Tā kā 17 gadus vecam ir gan vecāki, gan vecvecāki, mēs veiksim zig zig rotācijas.
Iepriekš redzamajā attēlā mēs varam novērot, ka 17 kļūst par koka saknes mezglu; tāpēc ievietošana ir pabeigta.
4. darbība: Nākamais elements ir 7. Tā kā 7 ir mazāks par 17, 15 un 10, mezgls 7 tiks atstāts kā 10 bērns.
Tagad mums ir jāizmet koks. Tā kā 7 gadījumam ir gan vecāki, gan vecvecāki, mēs veiksim divas pareizās rotācijas, kā parādīts tālāk:
Tomēr mezgls 7 nav saknes mezgls, tas ir saknes mezgla kreisais atvasinātais, t.i., 17. Tātad mums ir jāveic vēl viena pagriešana pa labi, lai mezglu 7 padarītu par saknes mezglu, kā parādīts tālāk:
Ievietošanas darbības algoritms
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)
Iepriekš minētajā algoritmā T ir koks un n ir mezgls, kuru mēs vēlamies ievietot. Mēs esam izveidojuši pagaidu mainīgo, kas satur saknes mezgla adresi. Mēs izpildīsim while cilpu, līdz temp vērtība kļūst NULL.
Kad ievietošana ir pabeigta, tiks veikta izkliedēšana
Atskaņošanas darbības algoritms
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
Iepriekš minētajā realizācijā x ir mezgls, uz kura tiek veikta rotācija, bet y ir mezgla x kreisais bērns.
Rotācijas pa kreisi (T, x) ieviešana
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
Iepriekš minētajā realizācijā x ir mezgls, uz kura tiek veikta rotācija, un y ir mezgla x labais atvasinātais.
Dzēšana Splay kokā
Kā mēs zinām, ka izvēršanas koki ir binārā meklēšanas koka varianti, tāpēc dzēšanas darbība izvēršanas kokā būtu līdzīga BST, taču vienīgā atšķirība ir tāda, ka dzēšanas operācijai izvēršanas kokos seko izspēlēšanas darbība.
Dzēšanas veidi:
Izklāšanas kokos ir divu veidu dzēšana:
- No apakšas uz augšu
- Spēlēšana no augšas uz leju
Izspēle no apakšas uz augšu
Atskaņojot no apakšas uz augšu, vispirms mēs izdzēšam elementu no koka un pēc tam veicam izspēli dzēstajā mezglā.
Sapratīsim dzēšanu Splay kokā.
Pieņemsim, ka mēs vēlamies dzēst 12, 14 no tālāk redzamā koka:
cik daudz ir neiespējamās misijas filmu
- Pirmkārt, mēs vienkārši veicam standarta BST dzēšanas darbību, lai izdzēstu 12 elementu. Tā kā 12 ir lapas mezgls, mēs vienkārši izdzēšam mezglu no koka.
Dzēšana joprojām nav pabeigta. Mums ir jāatklāj dzēstā mezgla vecāks, t.i., 10. Mums ir jāveic Spēle (10) uz koka. Kā redzams iepriekš minētajā kokā, 10 atrodas pa labi no mezgla 7, bet mezgls 7 atrodas pa kreisi no mezgla 13. Tātad, vispirms mēs veicam 7. mezgla pagriešanu pa kreisi un pēc tam veicam mezgla labo rotāciju. 13, kā parādīts zemāk:
Tomēr mezgls 10 nav saknes mezgls; mezgls 10 ir saknes mezgla kreisais bērns. Tātad, mums ir jāveic pareizā rotācija saknes mezglā, t.i., 14, lai mezglu 10 padarītu par saknes mezglu, kā parādīts tālāk:
- Tagad mums ir jāizdzēš 14 elements no koka, kas parādīts zemāk:
Kā mēs zinām, mēs nevaram vienkārši izdzēst iekšējo mezglu. Mēs aizstāsim mezgla vērtību, izmantojot vai nu pasūtījuma priekštecis vai rīkojuma pēctecis . Pieņemsim, ka mēs izmantojam secības pēcteci, kurā vērtību aizstājam ar zemāko vērtību, kas pastāv labajā apakškokā. Mazākā vērtība 14. mezgla labajā apakškokā ir 15, tāpēc vērtību 14 aizstājam ar 15. Tā kā 14. mezgls kļūst par lapas mezglu, mēs varam to vienkārši izdzēst, kā parādīts tālāk:
Tomēr dzēšana nav pabeigta. Mums ir jāveic vēl viena darbība, t.i., izkliedēšana, kurā mums jāpadara dzēstā mezgla vecāks par saknes mezglu. Pirms dzēšanas mezgla 14 vecākais bija saknes mezgls, t.i., 10, tāpēc šajā gadījumā mums ir jāveic jebkāda izvēršana.
Spēlēšana no augšas uz leju
Skatoties no augšas uz leju, mēs vispirms veicam atskaņošanu, kurā jāveic dzēšana, un pēc tam izdzēšam mezglu no koka. Kad elements ir dzēsts, mēs veiksim savienošanas darbību.
Izpratīsim no augšas uz leju, izmantojot piemēru.
Pieņemsim, ka mēs vēlamies dzēst 16 no koka, kas parādīts zemāk:
1. darbība: Spēlē no augšas uz leju vispirms veicam izspēli uz mezglu 16. Mezglam 16 ir gan vecāks, gan vecvecāks. Mezgls 16 atrodas pa labi no tā vecākmezgla un vecākmezgls atrodas arī pa labi no tā vecāka, tāpēc šī ir zag-zag situācija. Šajā gadījumā vispirms mēs veiksim pagriešanu pa kreisi mezglā 13 un pēc tam 14, kā parādīts zemāk:
Mezgls 16 joprojām nav saknes mezgls, un tas ir saknes mezgla labais atvasinātais, tāpēc mums ir jāveic 12. mezgla rotācija pa kreisi, lai mezglu 16 padarītu par saknes mezglu.
Kad mezgls 16 kļūs par saknes mezglu, mēs izdzēsīsim mezglu 16 un iegūsim divus dažādus kokus, t.i., kreiso apakškoku un labo apakškoku, kā parādīts tālāk:
Kā zināms, kreisā apakškoka vērtības vienmēr ir mazākas nekā labā apakškoka vērtības. Kreisā apakškoka sakne ir 12, bet labā apakškoka sakne ir 17. Vispirms ir jāatrod maksimālais elements kreisajā apakškokā. Kreisajā apakškokā maksimālais elements ir 15, un tad mums ir jāveic atskaņošanas darbība uz 15.
Kā mēs varam novērot iepriekš minētajā kokā, elementam 15 ir gan vecāks, gan vecvecāks. Mezgls atrodas pa labi no tā vecākmezgla, un vecākmezgls ir arī pa labi no tā vecāka, tāpēc mums ir jāveic divas pagriešanas pa kreisi, lai mezglu 15 padarītu par saknes mezglu, kā parādīts tālāk:
Pēc divu rotāciju veikšanas kokā 15. mezgls kļūst par saknes mezglu. Kā redzam, 15. labais atvasinātais ir NULL, tāpēc mēs pievienojam 17. mezglu 15 labajā daļā, kā parādīts zemāk, un šī darbība ir pazīstama kā pievienoties darbība.
Piezīme: Ja elements nav atrodams izspēlēšanas kokā, kas ir jāizdzēš, tiks veikta atskaņošana. Atskaņošana tiks veikta pēdējam piekļūtam elementam, pirms tiek sasniegts NULL.
Dzēšanas darbības algoritms
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
Iepriekš minētajā algoritmā mēs vispirms pārbaudām, vai sakne ir Null vai nav; ja sakne ir NULL, tas nozīmē, ka koks ir tukšs. Ja koks nav tukšs, mēs veiksim izspēlēšanas darbību elementam, kuru paredzēts dzēst. Kad atskaņošanas darbība būs pabeigta, mēs salīdzināsim saknes datus ar dzēšamo elementu; ja abi nav vienādi, tas nozīmē, ka elements kokā nav. Ja tie ir vienādi, var rasties šādi gadījumi:
1. gadījums : Saknes kreisā puse ir NULL, saknes labā puse kļūst par saknes mezglu.
2. gadījums : Ja eksistē gan kreisais, gan labais, tad kreisajā apakškokā mēs izspēlējam maksimālo elementu. Kad atskaņošana ir pabeigta, maksimālais elements kļūst par kreisā apakškoka sakni. Labais apakškoks kļūtu par kreisā apakškoka saknes labo bērnu.