Kompleksā datu struktūra koks / tree

Iepriekšējos rakstos jūs uzzinājāt par datu struktūrām, piemēram,

• Lists, 
• Stacks
• un Queues

. Vēl viena datu struktūra, par kuru es neesmu rakstijis, ir koki, jeb trees.

Kas īsti ir koks, jeb Tree datu struktūras kontekstā?

Koki ir spēcīga datu struktūra, kas sniedz lielu elastību vērtību pievienošanā un meklēšanā. Kokam raksturīgā struktūra var ļaut jums daudz saprast par attiecībām starp saglabātajiem datiem, kas var ietaupīt daudz laika un koda, iegūstot informāciju no datiem.

Šajā rakstā jūs izpētīsiet koku vispārējo struktūru un raksturīgās iezīmes. Jūs arī uzzināsiet par dažādiem koku veidiem un koku datu struktūras izmantošanas priekšrocībām.

Koks ir ļoti sarežģīta datu struktūra, kas arī pēc sava dizaina atgādina koku.

Tas sastāv no mezgliem, kas ir saistīti viens ar otru. Mezgls var būt vecākmezgls (Parent node) vai tam pakārtots (bērna) mezgls (Child node).

Vecākmezglam var būt savienota pakārtoto mezglu kopa. Mezgli, kuriem nav bērnu, tiek saukti par lapu mezgliem (Leaf node).

Tāpat kā kokā, mezgli var atzaroties dažādos virzienos, nodrošinot jaudīgas meklēšanas un uzglabāšanas funkcijas. Parasti mēs varam aplūkot koku kā diagrammai līdzīgu struktūru, kurā ir mezgli, kas satur datus, un malas, kas modelē katra mezgla savstarpējo saistību. Apspriežot kokus, ir svarīgi zināt dažus terminus.

• Augstākā līmeņa mezgls tiek saukts par sakni (Root).
• Katrs nākamais mezgls uz leju, kas ir savienots ar šo mezglu, tiek saukts par bērnu mezglu (Child).
• Mezgli, kuriem ir viens un tas pats vecāks, tiek saukti par brāļiem un māsām (Siblings) un tiek uzskatīti par vienā līmenī esošajiem.

Var attēlot grāmatas nodaļu, kurā apakšsadaļas ir saistītas ar savienotajiem mezgliem. Šo mezglu tēma būs ļoti līdzīga. Citas nodaļas būtu citas nodaļas, kas joprojām ietilpst vispārīgajā tēmā, bet par dažādām tēmām. Ceļš attiecas uz savienotu mezglu sēriju (Connection). Varat pieņemt savienojumu (Connection) starp diviem mezgliem, nosakot īsāko ceļu.

Tas ir ātrākais veids, kā pārvietoties no viena mezgla uz otru. Intuitīvi, mezgliem ar īsākiem ceļiem būs vairāk kopīga. Mezgla dziļums attiecas uz to, cik malu ir no vecāka līdz saknei vai garākajam ceļam. Koka augstums (Height) attiecas uz malu skaitu starp augšējo mezglu (Topmost) līdz dziļākajam mezglam (Deepest) struktūrā.

Visbeidzot, koka izmērs attiecas uz kopējo mezglu skaitu kokā. Ir daudz koku variantu un realizācijas, piemēram,

• binārie koki, – Binārais koks ir datu struktūra, kas sastāv no mezgliem, kas savienoti ar saitēm. Katram mezglam var būt ne vairāk kā divi bērni. Binārā koka galvenais mērķis ir ātra meklēšana, ievietošana un izdzēšana. Binārais meklēšanas koks ir binārs koks ar papildu īpašībām. Tā atslēgas sakārto un tādējādi ļauj ātri meklēt, ievietot un izdzēst vienumus ¹².
• B koki – B koks ir datu struktūra, kas sastāv no mezgliem, kas savienoti ar saitēm. Katram mezglam var būt ne vairāk kā B bērni. B koka galvenais mērķis ir ātra meklēšana, ievietošana un izdzēšana ¹.
• B-plus koki – B-plus koks ir datu struktūra, kas sastāv no mezgliem, kas savienoti ar saitēm. Katram mezglam var būt ne vairāk kā B bērni. B-plus koka galvenais mērķis ir ātra meklēšana, ievietošana un izdzēšana ¹.
• Quad koki – Quad koks ir datu struktūra, kas sastāv no mezgliem, kas savienoti ar saitēm. Katram mezglam var būt ne vairāk kā 4 bērni. Quad koka galvenais mērķis ir ātra meklēšana, ievietošana un izdzēšana ¹.
• AVL koki – AVL koks ir datu struktūra, kas sastāv no mezgliem, kas savienoti ar saitēm. AVL koka galvenais mērķis ir līdzsvara saglabāšana un tajā pašlaik tiek izmantots daudz programmēšanas valodu biblioteku ¹.

Lai gan visos tajos būs ietverta vispārīgā izklāstītā tēma, to izmantošana un ieviešana nedaudz atšķiras atkarībā no izmantotā koka veida. Datu glabāšanai kokam līdzīgā struktūrā ir daudz priekšrocību. Savienojumi starp mezgliem norāda uz attiecībām (Relationship), kas ir raksturīgas jūsu datiem. Tie var glabāt informāciju hierarhiskā veidā, kur augstākais saturs (Topmost content) tiek glabāts augšējos mezglos, un padziļinātāku informāciju (In-depth information) var izgūt, šķērsojot noteiktu zaru uz koku.

Tie ir arī ļoti efektīvi datu ievietošanai un dzēšanai, jo tie ir elastīgi ieviesti. Koka nelineārais raksturs nozīmē, ka ir daudz veidu, kā šķērsot datus. Binārajos kokos šī funkcija var būt ļoti noderīga, saglabājot datus. Kreisajam mezglam ir mazāka vērtība, bet labais mezgls norāda, ka ir lielāka vērtība. Pierādīsim to ar dažām datu vērtībām.

Pirmie dati satur vērtību 23, pēc tam tiek pievienots 4. Tā kā tas ir mazāks par 23, tas iet pa kreisi.

Tālāk ir 1, kas arī mazāks par 23, bet arī mazāks par 4. Tas arī iet pa kreisi.

Nākamais skaitlis ir 30. Tā kā tagad tas ir lielāks par 23, tas iet pa labi.

Tiek pievienots 24, un, tā kā tas ir mazāks par 30, tas iet pa kreisi.

Bet pievienotais 56 atkal iet pa labi no 30. Koku var šķērsot pēc dziļuma vai platuma metodes.

Pirmā dziļuma metode (Depth-first) ietver katra mezgla apmeklēšanu no augšas uz leju. Platuma pirmā metode (Breadth-first) ietver katra mezgla meklēšanu tajā pašā līmenī, pirms pāriet uz nākamo līmeni, un atkārtošanu, līdz ir sasniegts saknes mezgls.

Vairāk koku priekšrocību ir tas, ka tos var izmantot, lai modelētu failu sistēmas jūsu klēpjdatorā, klašu hierarhijas, piemēram, Java, vai hierarhiju modelēšanai organizācijās. Šajā raksta daļā jūs izpētījāt koku vispārējo struktūru un raksturīgās iezīmes. Jūs arī uzzinājāt par dažiem dažādiem koku veidiem un koku datu struktūras ieviešanas priekšrocībām.

Koki dažādās programmēšanas valodās

Šajā raksta turpinājumā jūs uzzināsiet par dažām atšķirībām koku ieviešanā dažādās programmēšanas valodās.

Tree ir abstrakts datu tips (ADT), kas ir pieejams daudzās valodās. Kā minēts citos rakstos, ADT ir datu struktūras izpausmes projekts. Tas attiecas uz ierobežojumiem un prasībām, kas noteiktas datu struktūrai, lai nodrošinātu, ka tā vienmēr darbosies vienādi. Tas var būt ļoti noderīgi programmētājiem, kuri pārslēdzas starp vairākām programmēšanas valodām, jo ​​tas sniedz skaidras cerības par datu struktūras darbību un to, ko no tās sagaidīt.

Koka galvenie pamatprincipi ir, ka tajā ir vairāki mezgli, saknes mezgls un lapu mezglu atlase. Lapu mezgli ir nesaistīti mezgli koka pamatnē. Saknes mezgls vienmēr atrodas augšpusē, un katra vērtība nāk no šī mezgla. Koks vienmēr tiks sakārtots kādā hierarhijas formā.

Koka ieviešana

Ir daudz veidu koku; iespējams, visvienkāršākais un visizplatītākais ir binārais koks. Binārajam kokam ir šādas īpašības:

• Katram mezglam ir ne vairāk kā divi pakārtotie mezgli.
• Katram mezglam ir jābūt atslēgai, lai to varētu viegli identificēt.
• Vērtības, kas ir mazākas par mezglu, tiek ievietotas kreisajā pakārtotajā mezglā, un vērtības, kas ir lielākas, tiek ievietotas labajā pakārtotajā mezglā.

Lai izveidotu koku, ir jānodrošina, ka ir sakne (sākuma mezgls / starting node) un metode turpmāko mezglu noteikšanai. Katrā mezglā ir jābūt atsaucei uz kreiso un labo mezglu, lai koku varētu šķērsot. To var panākt, izveidojot klasi ar šiem trim atribūtiem (atslēga, kreisā mezgla atrašanās vieta, labā mezgla atrašanās vieta / key, location of left node, location of right node). Šai klasei būs nepieciešamas trīs papildu metodes, lai tā varētu darboties kā koks. Tie ietver:

• Uzmeklēšanas metode lookup method: ir svarīgi, lai kokā varētu noskaidrot informācijas esamību vai neesamību.
• Ievietošanas metode Insertion method: kā jau minēts, mezgla ievietošana kokā ir saistīta ar to, ka ir jānoskaidro, kur tam vajadzētu virzīties, un tas jānovieto tuvākās lielākās vērtības kreisajā pusē.
• Noņemšanas metode Removal method: izmantojot šo metodi, vienums ir jānoņem no koka. Šī darbība rada papildu izaicinājumus, ja to piemēro kokam koka savienojuma dēļ. Apsveriet, ka koks sastāv no savienotu mezglu sērijas. Tātad, neuzmanīgi noņemot vienu, var tikt iznīcināti savienojumi kokā. Tāpēc, ieviešot šo metodi, papildus mezgla noņemšanai ir jāpārbauda visi pakārtotie mezgli un jāpārliecinās, ka tiek izveidots jauns savienojums ar nākamās augstākās vērtības mezglu.

Meklē kokos

Iepriekš aprakstītā koka kodēšanas pieeja ir piemērojama visām šajā kursā apskatītajām valodām. Nav konkrētu koku implementāciju, kas nozīmē, ka, lai tos izmantotu, jums pašiem ir jāievieš kods. Vēl viena iezīme, ko ir vērts paturēt prātā, ir tas, kā tiek veikta meklēšana kokā. Var kodēt risinājumu, kas izmanto meklēšanu pēc dziļuma vai meklēšanu pēc plašuma. Lai labāk izprastu šo jēdzienu, apsveriet, kā koks ir organizēts. Katram līmenim ir vecāku mezgls, kas savienojas ar diviem pakārtotajiem mezgliem. Šiem bērnu mezgliem savukārt ir divi savi bērnu mezgli. Meklēšana pēc plašuma ir tāda, kas pārbaudīs katru mezglu tajā pašā līmenī, pirms pāriet uz dziļāku līmeni. To var attēlot kā visu mezglu skenēšanu horizontāli pirms nākamā līmeņa pārbaudes. Pirmā dziļuma meklēšana pārbaudīs katru atzara mezglu, līdz tiks sasniegts gala mezgls, pirms tiek pārbaudīts blakus esošais zars. To var attēlot kā koka vertikālu skenēšanu.

Secinājums
Šis raksts aptvēra tēmu par kokiem un to, kā tie parādās dažādās programmēšanas valodās. Tā kā koki ir abstrakts datu tips, šajā kursā izmantotajām valodām nav iebūvētas metodes. Lai ieviestu koku, ir svarīgi paturēt prātā svarīgās koka īpašības, lai tās varētu pareizi ieviest.