Pirms uzzināt par binārās meklēšanas koka un AVL koka atšķirībām, mums atsevišķi jāzina par bināro meklēšanas koku un AVL koku.
Kas ir binārais meklēšanas koks?
The binārā meklēšanas koks ir koks binārais koks. Kā zināms, šim kokam var būt “n” bērnu skaits, turpretim; binārajā kokā var būt maksimāli divi bērni. Tātad binārā koka ierobežojumam seko arī binārais meklēšanas koks. Katram binārā meklēšanas koka mezglam ir jābūt maksimāli diviem bērniem; citiem vārdiem sakot, mēs varam teikt, ka binārais meklēšanas koks ir binārā koka variants.
Binārās meklēšanas koks arī seko binārās meklēšanas īpašībām. Binārajā meklēšanā visiem masīva elementiem jābūt sakārtotiem. Mēs aprēķinām vidējo elementu binārajā meklēšanā, kurā vidējā elementa kreisajā daļā ir vērtība, kas ir mazāka par vidējo vērtību, un vidējā elementa labajā daļā ir vērtības, kas ir lielākas par vidējo vērtību.
Binārajā meklēšanas kokā vidējais elements kļūst par saknes mezglu, labā daļa kļūst par labo apakškoku, bet kreisā daļa kļūst par kreiso apakškoku. Tāpēc mēs varam teikt, ka binārais meklēšanas koks ir a kombinācija binārais koks un binārā meklēšana .
Piezīme. Bināro meklēšanas koku var definēt kā bināro koku, kurā visi kreisā apakškoka elementi ir mazāki par saknes mezglu un visi labā apakškoka elementi ir lielāki par saknes mezglu.
Laika sarežģītība binārajā meklēšanas kokā
Ja binārais meklēšanas koks ir gandrīz līdzsvarots koks, tad visām operācijām būs laika sarežģītība O(pieteikties) jo meklēšana ir sadalīta vai nu pa kreisi vai pa labi apakškoku.
kā pārvērst char par virkni java
Ja binārais meklēšanas koks ir šķībs pa kreisi vai pa labi, tad visām operācijām būs laika sarežģītība O(n) jo mums jāšķērso n elementi.
Kas ir AVL koks?
An AVL koks ir pašbalansējošs binārais meklēšanas koks, kurā kreisā un labā apakškoku augstumu starpība nevar būt lielāka par vienu. Šī atšķirība ir pazīstama kā līdzsvara faktors. AVL kokā bilances koeficienta vērtības var būt -1, 0 vai 1.
Kā notiek binārā meklēšanas koka pašbalansēšana?
Kā zināms, AVL koks ir pašbalansējošs binārais meklēšanas koks. Ja binārais meklēšanas koks nav līdzsvarots, to var līdzsvarot ar dažiem pārkārtojumiem. Šos pārkārtojumus var veikt, izmantojot dažas rotācijas.
Sapratīsim pašbalansēšanu, izmantojot piemēru.
Pieņemsim, ka mēs vēlamies ievietot 10, 20, 30 AVL kokā.
drukāšanas paziņojums java
Tālāk ir norādīti veidi, kā AVL kokā ievietot 10, 20, 30:
1. darbība: Pirmkārt, mēs izveidojam bināro meklēšanas koku, kā parādīts zemāk:
2. darbība: Augšējā attēlā redzams, ka koks ir nelīdzsvarots, jo mezgla 30 līdzsvara koeficients ir 2. Lai to padarītu par AVL koku, mums ir jāveic dažas rotācijas. Ja mēs veicam pareizo rotāciju mezglā 20, tad mezgls 30 pārvietosies uz leju, bet mezgls 20 pārvietosies uz augšu, kā parādīts zemāk:
Kā mēs varam novērot, pēdējais koks seko Binārā meklēšanas koka un līdzsvarota koka īpašībai; tāpēc tas ir AVL koks.
Gadījumā koks bija atstāts nelīdzsvarots koks, tāpēc mēs veicam pareizo rotāciju mezglā.
1. darbība: Vispirms mēs izveidojam bināro meklēšanas koku, kā parādīts zemāk:
2. darbība: Iepriekš redzamajā attēlā var novērot, ka koks ir nelīdzsvarots, jo mezgla 10 līdzsvara koeficients ir -2. Lai padarītu to par AVL koku, mums ir jāveic dažas rotācijas. Tas ir labais nelīdzsvarots koks, tāpēc mēs veiksim rotāciju pa kreisi. Ja mēs veicam 20. mezgla rotāciju pa kreisi, tad mezgls 20 pārvietosies uz augšu, bet 10. mezgls virzīsies uz leju, kā parādīts zemāk:
Kā mēs varam novērot, gala koks seko īpašumam Binārās meklēšanas koks un a līdzsvarots koks ; tāpēc tas ir AVL koks.
1. darbība: Vispirms mēs izveidojam binārās meklēšanas koku, kā parādīts zemāk:
2. darbība: Iepriekš redzamajā attēlā var novērot, ka koks ir nelīdzsvarots, jo saknes mezgla līdzsvara koeficients ir 2. Lai to padarītu par AVL koku, mums ir jāveic dažas rotācijas. Iepriekš minētais scenārijs ir nesabalansēts pa kreisi un pa labi, jo viens mezgls atrodas pa kreisi no tā vecākmezgla, bet otrs ir pa labi no tā vecākmezgla. Vispirms mēs veiksim pagriešanu pa kreisi, un rotācija notiek starp mezgliem 10 un 20. Pēc pagriešanas pa kreisi 20 pārvietosies uz augšu un 10 pārvietosies uz leju, kā parādīts tālāk:
Tomēr koks ir nelīdzsvarots, tāpēc kokam veicam pareizo rotāciju. Kad kokam ir veikta pareizā rotācija, koks vēlas, kā parādīts zemāk:
Kā mēs varam novērot iepriekš minētajā kokā, koks seko Binārās meklēšanas koka un līdzsvarota koka īpašībai; tāpēc tas ir AVL koks.
1. darbība: Vispirms mēs izveidojam binārās meklēšanas koku, kā parādīts zemāk:
2. darbība: Augšējā attēlā redzams, ka koks ir nelīdzsvarots, jo saknes mezgla līdzsvara koeficients ir 2. Lai to padarītu par AVL koku, mums ir jāveic dažas rotācijas. Iepriekš minētais scenārijs ir nelīdzsvarots ar labo un kreiso pusi, jo viens mezgls atrodas pa labi no tā vecākmezgla, bet cits mezgls atrodas pa kreisi no tā vecākmezgla. Vispirms mēs veiksim pareizo pagriešanu, kas notiek starp mezgliem 30 un 20. Pēc labās pagriešanas 20 pārvietosies uz augšu un 30 pārvietosies uz leju, kā parādīts tālāk:
Tomēr iepriekš minētais koks nav līdzsvarots, tāpēc mums ir jāveic mezgla pagriešana pa kreisi. Kad tiek veikta pagriešana pa kreisi, mezgls 20 pārvietosies uz augšu, bet mezgls 10 pārvietosies uz leju, kā parādīts zemāk:
virkne līdz rakstzīmei java
Kā mēs varam novērot iepriekš minētajā kokā, koks seko Binārās meklēšanas koka un līdzsvarota koka īpašībai; tāpēc tas ir AVL koks.
Atšķirības starp binārās meklēšanas koku un AVL koku
| Binārās meklēšanas koks | AVL koks |
|---|---|
| Katrs binārais meklēšanas koks ir binārs koks, jo abos kokos ir maksimāli divi bērni. | Katrs AVL koks ir arī binārs koks, jo AVL kokam ir arī maksimāli divi bērni. |
| BST nav termina, piemēram, līdzsvara faktors. | AVL kokā katrs mezgls satur līdzsvara koeficientu, un līdzsvara faktora vērtībai ir jābūt -1, 0 vai 1. |
| Katrs binārās meklēšanas koks nav AVL koks, jo BST var būt vai nu līdzsvarots, vai nelīdzsvarots koks. | Katrs AVL koks ir binārs meklēšanas koks, jo AVL koks seko BST rekvizītam. |
| Katrs binārās meklēšanas koka mezgls sastāv no trim laukiem, t.i., kreisā apakškoka, mezgla vērtības un labā apakškoka. | Katrs AVL koka mezgls sastāv no četriem laukiem, t.i., kreisā apakškoka, mezgla vērtības, labā apakškoka un līdzsvara faktora. |
| Binārās meklēšanas koka gadījumā, ja vēlamies kokā ievietot jebkuru mezglu, tad mēs salīdzinām mezgla vērtību ar saknes vērtību; ja mezgla vērtība ir lielāka par saknes mezgla vērtību, tad mezgls tiek ievietots labajā apakškokā, pretējā gadījumā mezgls tiek ievietots kreisajā apakškokā. Kad mezgls ir ievietots, nav nepieciešams pārbaudīt augstuma līdzsvara koeficientu, lai ievietošana tiktu pabeigta. | AVL koka gadījumā vispirms mēs atradīsim piemērotu vietu mezgla ievietošanai. Kad mezgls ir ievietots, mēs aprēķināsim katra mezgla līdzsvara koeficientu. Ja katra mezgla līdzsvara koeficients ir izpildīts, ievietošana ir pabeigta. Ja līdzsvara koeficients ir lielāks par 1, mums ir jāveic dažas rotācijas, lai līdzsvarotu koku. |
| Binārās meklēšanas kokā koka augstums vai dziļums ir O(n), kur n ir mezglu skaits binārās meklēšanas kokā. | AVL kokā koka augstums vai dziļums ir O(logn). |
| To ir vienkārši ieviest, jo mums ir jāievēro binārās meklēšanas rekvizīti, lai ievietotu mezglu. | To ir sarežģīti ieviest, jo AVL kokā mums vispirms ir jākonstruē AVL koks, un tad mums ir jāpārbauda augstuma līdzsvars. Ja augstums ir nelīdzsvarots, mums ir jāveic dažas rotācijas, lai līdzsvarotu koku. |
| BST nav līdzsvarots koks, jo tas neatbilst līdzsvara faktora jēdzienam. | AVL koks ir augstuma līdzsvarots koks, jo tas atbilst līdzsvara faktora koncepcijai. |
| Meklēšana BST ir neefektīva, ja kokā ir pieejams liels skaits mezglu, jo augstums nav līdzsvarots. | Meklēšana ir efektīva AVL kokā pat tad, ja kokā ir liels mezglu skaits, jo augstums ir līdzsvarots. |