Šajā apmācībā jūs uzzināsit par koku datu struktūru. Jūs arī uzzināsiet par dažādiem koku veidiem un kokā lietotajām terminoloģijām.
Koks ir nelineāra hierarhiska datu struktūra, kas sastāv no mezgliem, kurus savieno malas.
Koks
Kāpēc koka datu struktūra?
Citas datu struktūras, piemēram, masīvi, saistīts saraksts, kaudze un rinda, ir lineāras datu struktūras, kas datus glabā secīgi. Lai veiktu jebkuru darbību lineārā datu struktūrā, laika sarežģītība palielinās, palielinoties datu lielumam. Bet tas nav pieņemams mūsdienu skaitļošanas pasaulē.
Dažādas koku datu struktūras ļauj ātrāk un vieglāk piekļūt datiem, jo tā ir nelineāra datu struktūra.
Koku terminoloģijas
Mezgls
Mezgls ir entītija, kas satur atslēgu vai vērtību un norādes uz tā pakārtotajiem mezgliem.
Katra ceļa pēdējos mezglus sauc par lapu mezgliem vai ārējiem mezgliem, kas nesatur saiti / rādītāju uz bērnu mezgliem.
Mezglu, kuram ir vismaz bērnu mezgls, sauc par iekšējo mezglu .
Mala
Tā ir saite starp jebkuriem diviem mezgliem.
Koka mezgli un malas
Sakne
Tas ir koka augšējais mezgls.
Mezgla augstums
Mezgla augstums ir malu skaits no mezgla līdz dziļākajai lapai (ti, garākais ceļš no mezgla līdz lapu mezglam).
Mezgla dziļums
Mezgla dziļums ir malu skaits no saknes līdz mezglam.
Koka augstums
Koka augstums ir saknes mezgla augstums vai dziļākā mezgla dziļums.
Katra koka mezgla augstums un dziļums
Mezgla pakāpe
Mezgla pakāpe ir kopējais šī mezgla zaru skaits.
Mežs
Nesadalīto koku kolekciju sauc par mežu.
Meža veidošana no koka
Mežu var izveidot, griežot koka sakni.
Koku veidi
- Binārais koks
- Binārais meklēšanas koks
- AVL koks
- B-koks
Koku šķērsošana
Lai kokā veiktu jebkādas darbības, jums jāsasniedz konkrētais mezgls. Koka šķērsošanas algoritms palīdz apmeklēt nepieciešamo koka mezglu.
Lai uzzinātu vairāk, lūdzu, apmeklējiet koku šķērsošanu.
Koka lietojumi
- Binārie meklēšanas koki (BST) tiek izmantoti, lai ātri pārbaudītu, vai elements atrodas komplektā.
- Kaudze ir sava veida koks, ko izmanto kaudzes šķirošanai.
- Modificēta koka versija ar nosaukumu Tries tiek izmantota mūsdienu maršrutētājos, lai saglabātu maršruta informāciju.
- Vispopulārākajās datu bāzēs tiek izmantoti B-Trees un T-Trees, kas ir koku struktūras varianti, kurus mēs iepriekš iemācījāmies, lai saglabātu savus datus
- Sastādītāji izmanto sintakses koku, lai pārbaudītu katras rakstītās programmas sintaksi.
