Koks (datu struktūra)

Koks ir datu struktūra - mezglpunktu (mezglu) kopa (var būt tukša), kas satur sakni, kurai ir nulle vai vairāk apakškoku. Katrs apakškoks atbilst koka definīcijai. Tātad koka definīcija ietver rekursiju, kur katrā zarā ir stingras norādes. Ja objekts vai jebkāda informācija var tikt sadalīta sīkākās daļās, un daļas, attiecīgi, vēl sīkākās, var tikt izmantota koku datu struktūra dalījuma attēlošanai. Galvenā koka priekšrocība pār citām datu struktūrām ir veiksmīgā hierarhijas attēlošana. Tā kā ar šo struktūru var viegli organizēt informācijas apstrādi un glabāšanu, tad koku datu struktūra ir viena no svarīgākajām datorzinātnē.

Zari, mezgli un lapas

Koka piemērs. Saknes mezgls - 50, lapu mezgli - 9, 14, 19, 64, 76.

Šī tipa struktūru var labi paskaidrot ar Windows Explorer piemēru, kas parāda mapju, direktoriju un failu struktūru, kas atrodas šajās mapēs.

Koks satur tādus objektus kā mezgli un lapas. Tiem jāatbilst šādiem noteikumiem:

Mezgli var atrasties jebkurā līmenī datu struktūrā, kur 1. līmenis ir augšpuse un n līmenis ir apakša.
Mezgls, kas atrodas 1. līmenī, tiek saukts par saknes mezglu.
Viens mezgls, kuram nav šķautņu (zaru), arī tiek saukts par koku.
Apakšējam zaram (bērnam) ir jābūt saistītam ar to vecāku, kas ir tieši 1 līmeni augstāk par viņu.
Vienam vecākam var būt bezgalīgi daudz bērnu, bet bērnam var būt tikai viens vecāks.
Tie mezgli (bērni) vienā līmenī, kuriem ir viens kopīgs vecāks, tiek saukti par kaimiņiem.
Tāds mezgls, kuram nav bērnu, tiek saukts par lapu.
Kokam ir divi lielumi – augstums un dziļums.
Augstums ir līmeņu skaits no saknes mezgla līdz pēdējai lapai.
Dziļums ir zaru skaits līdz pēdējam bērnam (lapai). Dziļums = Augstums – 1;

Windows pārlūkā kā zari tiek reprezentētas mapes (direktoriji), kuru sakne var būt diski C vai D, kas neietilpst nevienā citā direktorijā – nav bērns nevienam mezglam. Lapas ir faili, jo tajos neietilpst citi lielumi (citi faili vai mapes) – tie ir koka mazākie elementi.

Koku veidi

Kokus var iedalīt kā sakārtotus un nesakārtotus.
Sakārtots koks ir tāds, kurš ir veidots pēc noteikta algoritma – vecāks ir pēc kāda noteikta kritērija lielāks nekā bērns un var noteikt, kurš no bērniem ir pirmais (primārais) un kuri nākamie.
Koks vēl var būt binārs – nosaukums jau norāda, ka struktūras pamatā ir skaitlis ‘2’. Tas nozīmē, ka katram vecākam var būt augstākais divi bērni. Papildu nosacījums – kreisajam bērnam vienmēr jābūt lielākam nekā labajam.
Ja binārs koks ir sakārtots, tad tas atbilst iepriekšējiem nosacījumiem un pilns sakārtots binārs koks ir tāds, kur katram mezglam ir tieši divi bērni.
Ja bināram kokam nav neviena mezgla, to sauc par tukšu koku un to mēdz apzīmēt ar NIL.
Ja visām koka lapām ir vienāds dziļums, to sauc par perfektu bināru koku.

Koku operācijas

Create (sakne) – Izveido koku, kas raksturojas ar sakni.
Empty (sakne) – loģiskā funkcija, kura pārbauda, vai saknē ir vērtība.
Find (sakne, pozīcija, zīme) – izvēlētajai saknei atgriež pozīciju (atrašanās vietu). Ja nevar atrast tā vietu kokā, tad atgriež jauno piešķirto zīmi.
Add (sakne, mezgls) – Pievieno datus kokam (ar izvēlēto sakni, noteiktajā mezglā).
Delete (sakne, mezgls) – Izmet datus no izvēlētās pozīcijas (skat. Add operāciju).
Traverse (sakne) – Kokam ar izvēlēto sakni iziet visus mezglus atbilstoši hierarhijai.
Parent (m) – Izvēlētajam mezglam atgriež tā vecāku vai NIL, ja vecāks nav atrasts.
Children (m) – Tiek atgriezta bērnu kopa izvēlētajam mezglam. Tomēr tiek atgriezta nulle, ja izvēlētā ir lapa (bez bērniem).
FirstChild (m) – Atgriež izvēlētā mezgla pirmo (mazāko/”vis-kreisāko”) bērnu vai, ja ‘m’ ir lapa, atgriež NIL.
RightSibling (m) un LeftSibling(m) – Atgriež izvēlētā mezgla attiecīgi labo vai kreiso kaimiņu vai NIL, ja tāda nav. (Tikai bināram kokam).
RightChild (m) un LeftChild(m) – Atgriež bērnus vai NIL (skat. iepriekš. operāciju).
IsLeaf (m) – loģiska operācija, kas pārbauda, vai izvēlētajam mezglam nav bērnu vai ir tie(vai tā ir lapa vai nav). Tiek atgriezta viena no būla vērtībām – true vai false.
Depth (m) – Kokam atgriež mezgla m dziļumu.
Height (m) – Kokam atgriež mezgla m augstumu.