Galvenā atšķirība - binārais koks pret bināro meklēšanas koku
Datu struktūra ir sistemātisks veids, kā sakārtot datus, lai tos efektīvi izmantotu. Sakārtojot datus, izmantojot datu struktūru, jāsamazina darbības laiks vai izpildes laiks. Arī datu struktūrai ir nepieciešams minimāls atmiņas apjoms. Dažreiz datus var sakārtot koka struktūrā. Koks apzīmē mezglu, kas savienots ar malām. Augšējais mezgls ir sakne. Katrā mezglā var būt ne vairāk kā divi mezgli. Tie ir pazīstami kā bērnu mezgli. Mezgls pa kreisi no vecākmezgla ir kreisais bērnmezgls, bet mezgls pa labi no vecākmezgla ir labais mezgls. Binārais koks un binārais meklēšanas koks ir divas koku datu struktūras. Binārais koks ir datu struktūras veids, kurā katram vecākmezglam var būt ne vairāk kā divi pakārtotie mezgli. Binārais meklēšanas koks ir binārais koks, kurā kreisajā pakārtotajā ir tikai mezgli ar vērtībām, kas ir mazākas vai vienādas ar vecākmezglu, un labajā pakārtotajā ir tikai mezgli, kuru vērtības ir lielākas par vecākmezgla vērtībām. Tā ir galvenā atšķirība. Atšķirībā no datu struktūrām, piemēram, masīviem, binārajam kokam un binārajam meklēšanas kokam nav datu glabāšanas augšējā ierobežojuma.
Kas ir binārais koks?
Sakārtojot datus koka struktūrā, koka augšdaļā esošo mezglu sauc par saknes mezglu. Visam kokam var būt tikai viena sakne. Jebkuram mezglam, izņemot saknes mezglu, ir viena mala uz augšu uz mezglu. To sauc par vecāku mezglu. Mezgls zem vecākkoda tiek saukts par tā atvasināto mezglu. Katram vecākmezglam var būt ne vairāk kā divi pakārtotie mezgli. Tie tiek saukti par kreiso bērnmezglu un labo bērna mezglu. Mezgls bez bērna mezgla tiek saukts par lapas mezglu. Nav īpaša veida, kā sakārtot datus binārajā kokā. No saknes mezgla uz katru mezglu ir ceļš.
Attēls 01: Binārā koka piemērs
Augšpusē ir binārā koka piemērs. Elements 2, kas atrodas koka augšdaļā, ir sakne. Katram mezglam ir ne vairāk kā divi mezgli. Ja kokā ir cilpas vai ja vienā mezglā ir vairāk nekā divi mezgli, to nevar klasificēt kā bināro koku. Lai pārietu no viena mezgla uz otru, vienmēr ir viens ceļš. 2. saknes mezgla pakārtotie mezgli ir 7 un 5. Ir arī iespējams, ka mezglam nav mezglu. Bet jebkuram mezglam nevar būt vairāk par diviem mezgliem. Saknes labais elements ir 5. Šis elements 5 ir 9. pakārtotā mezgla vecākmezgls. Mezglā 4 un 11 nav pakārtotu elementu. Tāpēc tie ir lapu mezgli.
Binārais koks tiek izmantots datu glabāšanai hierarhiskā secībā. Tā ir līdzīga datora failu struktūrai. Datu struktūra, piemēram, masīvs, var uzglabāt noteiktu datu apjomu. Bet binārajā kokā mezglu skaitam nav augšējā ierobežojuma.
Kas ir binārās meklēšanas koks?
Binārais meklēšanas koks ir bināra koka datu struktūra. Līdzīgi kā binārajam kokam, arī binārajam meklēšanas kokam var būt divi mezgli. Jebkuram mezglam, izņemot saknes mezglu, ir viena mala uz augšu uz mezglu. To sauc par vecāku mezglu. Mezgls zem dotā, kas savienots ar malu uz leju, tiek saukts par bērna mezglu. Mezgls bez bērna mezgla tiek saukts par lapas mezglu. Katram vecākmezglam var būt ne vairāk kā divi mezgli. Ir pakārtotie mezgli, kas norāda uz kreiso pakārtoto mezglu un labo pakārtoto mezglu. Augšējo elementu sauc par saknes mezglu. Kreisajā pakārtotajā daļā ir tikai mezgli, kuru vērtības ir mazākas vai vienādas ar vecākmezglu. Pareizajā pakārtotajā vietā ir tikai mezgli, kuru vērtības ir lielākas vai vienādas ar vecākmezglu.
Attēls 02: Binārās meklēšanas koka piemērs
Elements 8 ir augstākais elements. Tāpēc tas ir saknes mezgls. Ja 3 ir vecāku mezgls, tad 1 un 6 ir bērnmezgli. 1 ir kreisais bērnmezgls, bet 6 ir labais bērnmezgls. Kreisajā pakārtotajā daļā ir vērtības, kas ir mazākas vai vienādas ar vecākmezglu. Ja 3 ir vecākmezgls, kreisajā pusē ir jābūt elementam, kas ir mazāks vai vienāds ar 3. Šajā piemērā tas ir 1. Labajā pakārtotajā vietā ir tikai mezgli, kuru vērtības ir lielākas par vecākmezglu. Ja 3 ir vecākais mezgls, labajam pakārtotajam mezglam ir jābūt lielākai vērtībai nekā 3. Šajā piemērā tā ir 6. Tāpat ir noteikta secība, lai katru datu elementu sakārtotu binārā meklēšanas kokā. Tā ir datu struktūra, kas nodrošina efektīvu veidu, kā veikt datu kārtošanu, izgūšanu un meklēšanu.
Kādas ir līdzības starp bināro koku un bināro meklēšanas koku?
- Gan binārais koks, gan binārais meklēšanas koks ir hierarhiskas datu struktūras.
- Gan binārajam kokam, gan binārajam meklēšanas kokam ir sakne.
- Gan binārajam kokam, gan binārajam meklēšanas kokam var būt ne vairāk kā divi pakārtotie mezgli.
Kāda ir atšķirība starp bināro koku un bināro meklēšanas koku?
Binārais koks pret bināro meklēšanas koku |
|
| Binārais koks ir datu struktūras veids, kurā katram vecākmezglam var būt ne vairāk kā divi pakārtotie mezgli. | Binārais meklēšanas koks ir binārs koks, kurā kreisajā pakārtotajā ir tikai mezgli, kuru vērtības ir mazākas vai vienādas ar vecākmezglu, un labajā pakārtotajā ir tikai mezgli, kuru vērtības ir lielākas par vecākmezglu. |
| Datu sakārtošanas secība | |
| Binārajam kokam nav noteikta datu elementu kārtošanas secība. | Binārā meklēšanas kokam ir noteikta datu elementu kārtošanas secība. |
| Lietošana | |
| Binārais koks tiek izmantots kā efektīva datu un informācijas meklēšana koka struktūrā. | Datu ievietošanai, dzēšanai un meklēšanai tiek izmantots binārais meklēšanas koks. |
Kopsavilkums - binārais koks pret bināro meklēšanas koku
Datu struktūra ir datu kārtošanas veids. Dažreiz datus var sakārtot koka struktūrā. Divi no tiem ir binārais koks un binārais meklēšanas koks. Šajā rakstā tika apspriesta atšķirība starp bināro koku un bināro meklēšanas koku. Binārais koks ir datu struktūras veids, kurā katram vecākmezglam var būt ne vairāk kā divi pakārtotie mezgli. Binārais meklēšanas koks ir binārais koks, kurā kreisajā pakārtotajā ir tikai mezgli, kuru vērtības ir mazākas vai vienādas ar vecākmezglu, un labajā pakārtotajā ir tikai mezgli, kuru vērtības ir lielākas par vecākmezglu.
Lejupielādēt PDF failu par bināro koku pret bināro meklēšanas koku
Varat lejupielādēt šī raksta PDF versiju un izmantot to bezsaistē saskaņā ar atsauces piezīmi. Lūdzu, lejupielādējiet PDF versiju šeit: Atšķirība starp bināro koku un bināro meklēšanas koku
