Vēl viena atšķirība starp B-koku un bināro koku ir tā, ka B-kokam jābūt visiem tās bērnu mezgliem vienā līmenī, bet bināram kokam nav šāda ierobežojuma. Bināram kokam var būt ne vairāk kā 2 subtrees vai mezgli, bet B-kokā var būt M apakšgrupu vai mezglu skaits, kur M ir B-koka kārtība.
Salīdzinājuma diagramma
| Salīdzināšanas pamats | B-koks | Binārais koks |
|---|---|---|
| Būtisks ierobežojums | Mezglā var būt pie maksimālā M bērnu mezglu skaita (kur M ir koka kārtība). | Mezglā var būt ne vairāk kā 2 apakšstundu skaits. |
| Lietots | To izmanto, ja dati tiek glabāti diskā. | To izmanto, ja ieraksti un dati tiek saglabāti RAM. |
| Koka augstums | log M N (kur m ir M-ceļa koka secība) | log 2 N |
| Pieteikums | Kodu indeksēšanas datu struktūra daudzās DBVS. | Kodu optimizācija, Huffman kodēšana utt. |
B-koka definīcija
B-koks ir līdzsvarots M-ceļš, kas pazīstams arī kā līdzsvarots šķirnes koks. Tas ir līdzīgs binārā meklēšanas kokam, kur mezgli ir sakārtoti, balstoties uz iekšējo šķērsošanu. B-koka telpu sarežģītība ir O (n). Ievietošanas un dzēšanas laika sarežģītība ir O (log n).
Ir daži nosacījumi, kas attiecas uz B koku:
- Koka augstumam jābūt pēc iespējas mazākam.
- Virs koka lapām nevajadzētu būt tukšiem apakšstilbiem.
- Koka lapām jānāk vienā līmenī.
- Visiem mezgliem jābūt vismazākam bērnu skaitam, izņemot atvaļinājuma mezglus.
B kārtas M īpašības
- Katram mezglam var būt maksimālais M bērnu skaits un minimālais M / 2 bērnu skaits vai jebkurš skaitlis no 2 līdz maksimāli.
- Katram mezglam ir viena atslēga mazāk nekā bērni ar maksimālo M-1 taustiņu.
- Taustiņu izvietojums ir konkrētā secībā mezglos. Visas atslēgas apakšējā daļā esošās atslēgas ir atslēgas priekšgājēji, un to, 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 mātes mezglā.
- Apvienošanās notiek tad, kad mezgli ir izdzēsti.
Binārā koka definīcija
Binārais koks ir koka struktūra, kurai var būt ne vairāk kā divas norādes tās bērnu mezgliem. Tas nozīmē, ka augstākais pakāpes mezgls var būt 2, un var būt arī nulle vai viena grāda mezgls.
Ir daži binārā koka varianti, piemēram, stingri binārs koks, pilnīgs binārs koks, paplašināts binārs koks, utt.
- Stingri binārais koks ir koks, kuram katram ne-terminālajam mezglam jābūt kreisajai daļai un labajai daļai.
- Koks tiek saukts par pilnīgu bināro koku, ja tas atbilst 2 i mezglu stāvoklim katrā līmenī, kur i ir līmenis.
- Vītņots binārs ir binārs koks, kas sastāv no 0 mezglu vai 2 mezglu skaita.
Brauciena metodes
Koku pārvietošanās ir viena no biežākajām operācijām, ko veic ar koku datu struktūru, kurā katrs mezgls sistemātiski apmeklēja tieši vienu reizi.
- Inorder- Šajā kokā pārvietojas kreisā apakšgrupa recursīvi, pēc tam tiek apmeklēts saknes mezgls, un pēdējā apmeklējuma laikā tiek apmeklēts subtree.
- Priekšnieks- Šajā koku šķērsošanā saknes mezgls tiek apmeklēts pirmajā, tad kreisajā apakšgrupā un beidzot labajā apakšgrupā.
- Postorder- Šī metode apmeklē kreisās subtree, tad labo subtree un pēdējā saknes mezglu.
Galvenās atšķirības starp B-koku un bināro koku
- B-kokā maksimālais bērnu mezglu skaits, kas nav gala mezgls, var būt M, kur M ir B-koka kārtība. No otras puses, bināram kokam var būt ne vairāk kā divi apakšstili vai bērnu mezgli.
- B-koks tiek izmantots, ja dati tiek saglabāti diskā, bet bināro koku izmanto, ja dati tiek saglabāti ātrās atmiņas, piemēram, RAM, atmiņā.
- Vēl viena B-piemērošanas joma ir kodu indeksēšanas datu struktūra DBVS, savukārt binārais koks tiek izmantots koda optimizācijā, kodolā kodēšanai utt.
- B-koka maksimālais augstums ir log M N (M ir koku secība). Pretstatā binārajam kokam maksimālais augstums ir log 2 N (N ir mezglu skaits un bāze ir 2, jo tā ir binārajiem).
Secinājums
B-koku izmanto binārajā un binārajā meklēšanas kokā. Galvenais iemesls tam ir atmiņas hierarhija, kurā CPU ir savienots ar kešatmiņu ar lieliem joslas platuma kanāliem, bet CPU ir savienots ar disku, izmantojot mazu joslas platuma kanālu. Bināro koku izmanto, kad ieraksti tiek saglabāti RAM (mazs un ātrs) un B-koks tiek izmantots, ja ieraksti tiek glabāti diskā (liels un lēns). Tātad B-koka izmantošana binārā koka vietā ievērojami samazina piekļuves laiku, jo ir augsts sazarojuma faktors un samazināts koka augstums.
