Starpība starp B-koku un bināro koku
Saturs
- Salīdzināšanas tabula
- B-koka definīcija
- M-kārtas B-koka īpašības
- Binārā koka definīcija
- Šķēršļu paņēmieni
- Secinājums
B-koks un binārais koks ir nelineāras datu struktūras veidi. Lai arī termini šķiet līdzīgi, taču visos aspektos ir atšķirīgi. Binārais koks tiek izmantots, kad ieraksti vai dati tiek glabāti RAM, nevis diskā, jo RAM piekļuves ātrums ir daudz lielāks nekā diskam. No otras puses, B-koks tiek izmantots, kad dati tiek glabāti diskā, tas samazina piekļuves laiku, samazinot koka augstumu un palielinot filiāles mezglā.
Vēl viena atšķirība starp B koku un bināro koku ir tāda, ka B kokam visiem tā mezgla mezgliem jābūt vienā līmenī, turpretī binārajam kokam nav šādu ierobežojumu. Binārā kokā var būt ne vairāk kā 2 apakštīri vai mezgli, turpretī B kokā nedrīkst būt M apakšgrupu vai mezglu, kur M ir B koka secība.
- Salīdzināšanas tabula
- Definīcija
- Galvenās atšķirības
- Secinājums
Salīdzināšanas tabula
| Salīdzināšanas pamats | B-koks | Binārs koks |
|---|---|---|
| Būtisks ierobežojums | Mezglā var būt maksimāli M bērnu mezglu skaits (kur M ir koka secība). | Mezglā var būt ne vairāk kā 2 apakšzaru skaits. |
| Lietots | To izmanto, kad dati tiek glabāti diskā. | To izmanto, ja ieraksti un dati tiek glabāti RAM. |
| Koka augstums | žurnālsM N (kur m ir M virziena koka secība) | žurnāls2 N |
| Pieteikums | Koda indeksēšanas datu struktūra daudzās DBVS. | Kodu optimizācija, Huffmana kodēšana utt. |
B-koka definīcija
B koks ir līdzsvarots M-veida koks, kas pazīstams arī kā līdzsvarots kārtošanas koks. Tas ir līdzīgs binārajam meklēšanas kokam, kurā mezgli ir sakārtoti, pamatojoties uz ievadītāja šķērsošanu. B-koka telpas sarežģītība ir O (n). Ievietošanas un dzēšanas laika sarežģītība ir O (log n).
Ir daži nosacījumi, kuriem jāatbilst B kokam:
- Koka augstumam jābūt pēc iespējas mazākam.
- Virs koka lapām nedrīkst būt tukšas apakškrāsas.
- Koka lapām jābūt vienā līmenī.
- Visos mezglos jābūt vismazākajam bērnu skaitam, izņemot atstāšanas mezglus.
M-kārtas B-koka īpašības
- Katrā mezglā var būt maksimālais M bērnu skaits un minimālais M / 2 bērnu skaits vai jebkurš skaits no 2 līdz maksimālajam.
- Katrā mezglā ir par vienu taustiņu mazāk nekā bērniem ar maksimālo M-1 taustiņu.
- Taustiņu izvietojums mezglos atrodas noteiktā secībā. Visas apakškrāsas atslēgas, kas atrodas atslēgas kreisajā pusē, ir atslēgas priekšteces, un tās, kas atrodas atslēgas labajā pusē, sauc par pēctecēm.
- Pilna mezgla ievietošanas laikā koks sadalās divās daļās, un atslēga ar vidējo vērtību tiek ievietota vecāku mezglā.
- Apvienošanas darbība notiek, kad mezgli tiek izdzēsti.
Binārā koka definīcija
Binārais koks ir koka struktūra, kurai var būt ne vairāk kā divi rādītāji tā bērna mezgliem. Tas nozīmē, ka mezgla augstākā pakāpe var būt 2 un tur varētu būt arī nulle vai vienas pakāpes mezgls.
Ir daži binārā koka varianti, piemēram, stingri binārs koks, pilnīgs binārs koks, pagarināts binārs koks utt.
- Stingri binārs koks ir koks, kurā katram termināla mezglam ir jābūt pa kreisi apakšējai un labajai apakškrāsai.
- Koku sauc par pilnīgu bināro koku, ja tas atbilst nosacījumam, ka tam ir 2 i mezgli katrā līmenī, kur i ir līmenis.
- Vītņots binārs ir binārs koks, kas sastāv vai nu no 0 mezglu skaita, vai no 2 mezglu skaita.
Šķēršļu paņēmieni
Koku šķērsošana ir viena no biežākajām darbībām ar koku datu struktūru, kurā katrs mezgls sistemātiski apmeklēja precīzi vienu reizi.
- Inorder - šajā kokā šķērsojot kreiso subtree tiek apmeklēta rekursīvi, tad tiek apmeklēts saknes mezgls un pēdējā labajā subcreeree.
- Priekšgājējs - šajā koka šķērsojumā saknes mezgls tiek apmeklēts sākumā, pēc tam kreisajā apakštēvā un pēdējā labajā apakštēvā.
- Pēcpasūtīšana - šī metode apmeklē apakšējo apakšdaļu, tad labo apakškrāsu un pēdējā saknes mezglu.
- B kokā maksimālais bērnu mezglu skaits, kas var būt bez termināla, ir M, kur M ir B koka secība. No otras puses, binārajam kokam var būt ne vairāk kā divi apakšturi vai bērnu mezgli.
- B koku izmanto, ja dati tiek glabāti diskā, savukārt bināro koku izmanto, ja dati tiek glabāti ātrajā atmiņā, piemēram, RAM.
- Vēl viena B-koka piemērošanas joma ir datu indeksēšanas datu struktūra datu bāzēs DBVS, turpretī Binārais koks tiek izmantots koda optimizācijā, huffman kodēšanā utt.
- B-koka maksimālais augstums ir apaļkokuMN (M ir koka secība). Binārā koka maksimālais augstums ir log2N (N ir mezglu skaits, un bāze ir 2, jo tā ir binārā).
Secinājums
B-koks tiek izmantots binārā un binārā meklēšanas kokā, galvenais iemesls tam ir atmiņas hierarhija, kurā centrālais procesors ir savienots ar kešatmiņu ar liela joslas platuma kanāliem, bet centrālais procesors ir savienots ar disku caur zema joslas platuma kanālu. Binārs koks tiek izmantots, ja ieraksti tiek glabāti RAM (mazs un ātrs), un B-koks tiek izmantots, ja ieraksti tiek glabāti diskā (lieli un lēni). Tātad, B-koka izmantošana binārā koka vietā ievērojami samazina piekļuves laiku augsta sazarojuma faktora un samazināta koka augstuma dēļ.
