Mēs lasām lineārās datu struktūras, piemēram, masīvu, saistīto sarakstu, steku un rindu, kurā visi elementi ir sakārtoti secīgi. Dažādiem datu veidiem tiek izmantotas dažādas datu struktūras.

Izvēloties datu struktūru, jāņem vērā daži faktori:

Kāda veida dati ir jāuzglabā?: Iespējams, ka noteikta datu struktūra var būt vislabāk piemērota kāda veida datiem.Operāciju izmaksas:Ja vēlamies maksimāli samazināt operāciju izmaksas par biežāk veiktajām operācijām. Piemēram, mums ir vienkāršs saraksts, kurā mums ir jāveic meklēšanas darbība; tad mēs varam izveidot masīvu, kurā elementi tiek glabāti sakārtotā secībā, lai veiktu binārā meklēšana . Binārā meklēšana vienkāršajā sarakstā darbojas ļoti ātri, jo tā sadala meklēšanas vietu uz pusēm.Atmiņas lietojums:Dažreiz mēs vēlamies datu struktūru, kas izmanto mazāk atmiņas.

Koks ir arī viena no datu struktūrām, kas attēlo hierarhiskus datus. Pieņemsim, ka mēs vēlamies parādīt darbiniekus un viņu pozīcijas hierarhiskā formā, tad to var attēlot, kā parādīts zemāk:

Iepriekš redzamais koks parāda organizācijas hierarhija kāda uzņēmuma. Iepriekš minētajā struktūrā Džons ir izpilddirektors no uzņēmuma, un Džonam ir divi tiešie ziņojumi, kas nosaukti kā Stīvs un Rohans . Stīvs ir nosaucis trīs tiešos ziņojumus Lī, Bobs, Ella kur Stīvs ir menedžeris. Bobam ir divi tiešie ziņojumi Jā un Emma . Emma ir nosaukti divi tiešie ziņojumi Toms un Raj . Tomam ir viens tiešs ziņojums Bils . Šī konkrētā loģiskā struktūra ir pazīstama kā a Koks . Tā struktūra ir līdzīga īstajam kokam, tāpēc to nosauc par a Koks . Šajā struktūrā sakne atrodas augšpusē, un tā zari virzās lejup. Līdz ar to varam teikt, ka Tree datu struktūra ir efektīvs veids, kā hierarhiskā veidā uzglabāt datus.

Izpratīsim dažus galvenos Tree datu struktūras punktus.

• Koka datu struktūra ir definēta kā objektu vai entītiju kopums, kas pazīstams kā mezgli, kas ir saistīti kopā, lai attēlotu vai simulētu hierarhiju.
• Koka datu struktūra ir nelineāra datu struktūra, jo tā netiek saglabāta secīgi. Tā ir hierarhiska struktūra, jo elementi kokā ir sakārtoti vairākos līmeņos.
• Koka datu struktūrā augšējais mezgls ir pazīstams kā saknes mezgls. Katrs mezgls satur dažus datus, un dati var būt jebkura veida. Iepriekš minētajā koka struktūrā mezgls satur darbinieka vārdu, tāpēc datu veids būtu virkne.
• Katrs mezgls satur dažus datus un saites vai atsauces uz citiem mezgliem, kurus var saukt par bērniem.

Daži pamata termini, kas tiek izmantoti koka datu struktūrā.

Apskatīsim koka struktūru, kas parādīta zemāk:

Iepriekš minētajā struktūrā katrs mezgls ir apzīmēts ar kādu numuru. Katra bultiņa, kas parādīta iepriekš attēlā, ir pazīstama kā a saite starp diviem mezgliem.

Sakne:Saknes mezgls ir koka hierarhijas augstākais mezgls. Citiem vārdiem sakot, saknes mezgls ir tas, kuram nav neviena vecāka. Iepriekš minētajā struktūrā mezgls ar numuru 1 ir koka sakņu mezgls. Ja mezgls ir tieši saistīts ar kādu citu mezglu, to sauc par vecāku un bērnu attiecībām.Bērnu mezgls:Ja mezgls ir jebkura mezgla pēcnācējs, tad mezglu sauc par bērnu mezglu.Vecāks:Ja mezglā ir kāds apakšmezgls, tad tiek uzskatīts, ka šis mezgls ir šī apakšmezgla vecāks.Brālis un māsa:Mezglus, kuriem ir viens un tas pats vecāks, sauc par brāļiem un māsām.Lapu mezgls: -Koka mezglu, kuram nav neviena bērna mezgla, sauc par lapas mezglu. Lapas mezgls ir koka zemākais mezgls. Vispārīgā kokā var būt jebkurš lapu mezglu skaits. Lapu mezglus var saukt arī par ārējiem mezgliem.Iekšējie mezgli:Mezglam ir vismaz viens pakārtots mezgls, kas pazīstams kā an iekšējais Senču mezgls: -Mezgla priekštecis ir jebkurš priekštecis, kas atrodas ceļā no saknes uz šo mezglu. Saknes mezglam nav priekšteču. Augšējā attēlā redzamajā kokā 1., 2. un 5. mezgli ir 10. mezgla priekšteči.Pēcnācējs:Dotā mezgla tiešais pēctecis ir zināms kā mezgla pēctecis. Iepriekš redzamajā attēlā 10 ir mezgla 5 pēcnācējs.

Koka datu struktūras īpašības

Rekursīvā datu struktūra:Koks ir pazīstams arī kā a rekursīvā datu struktūra . Koku var definēt kā rekursīvi, jo koka datu struktūrā noteiktais mezgls ir pazīstams kā a saknes mezgls . Koka saknes mezglā ir saite uz visām tā apakškoku saknēm. Kreisais apakškoks ir parādīts dzeltenā krāsā zemāk esošajā attēlā, bet labais apakškoks ir parādīts sarkanā krāsā. Kreiso apakškoku var sadalīt apakškokos, kas parādīti trīs dažādās krāsās. Rekursija nozīmē kaut ko samazināt sev līdzīgā veidā. Tātad šī koka datu struktūras rekursīvā īpašība tiek realizēta dažādās lietojumprogrammās.
Malu skaits:Ja ir n mezgli, tad būtu n-1 malas. Katra struktūras bultiņa apzīmē saiti vai ceļu. Katram mezglam, izņemot saknes mezglu, būs vismaz viena ienākošā saite, kas pazīstama kā mala. Vecāku un bērnu attiecībām būtu viena saite.Mezgla x dziļums:Mezgla x dziļumu var definēt kā ceļa garumu no saknes līdz mezglam x. Viena mala veido vienu garuma vienību ceļā. Tātad mezgla x dziļumu var definēt arī kā malu skaitu starp saknes mezglu un mezglu x. Saknes mezglam ir 0 dziļums.Mezgla x augstums:Mezgla x augstumu var definēt kā garāko ceļu no mezgla x līdz lapas mezglam.

Pamatojoties uz Tree datu struktūras īpašībām, koki tiek klasificēti dažādās kategorijās.

Koka ieviešana

Koka datu struktūru var izveidot, dinamiski izveidojot mezglus ar rādītāju palīdzību. Atmiņā esošo koku var attēlot, kā parādīts zemāk:

Augšējā attēlā parādīts koka datu struktūras attēlojums atmiņā. Iepriekš minētajā struktūrā mezglā ir trīs lauki. Otrais lauks saglabā datus; pirmajā laukā tiek saglabāta kreisā bērna adrese, bet trešajā laukā tiek saglabāta labā bērna adrese.

Programmēšanā mezgla struktūru var definēt šādi:

 struct node { int data; struct node *left; struct node *right; } 

Iepriekš minēto struktūru var definēt tikai binārajiem kokiem, jo ​​binārajam kokam var būt ne vairāk kā divi bērni, bet vispārīgajiem kokiem var būt vairāk nekā divi bērni. Vispārīgo koku mezgla struktūra atšķiras no binārā koka.

Koku pielietojumi

Tālāk ir norādīti koku pielietojumi:

Dabiski hierarhisku datu glabāšana:Koki tiek izmantoti datu glabāšanai hierarhiskā struktūrā. Piemēram, failu sistēma. Diska diskdzinī saglabātā failu sistēma, fails un mape ir dabiski hierarhisku datu veidā un tiek glabāti koku veidā.Sakārtot datus:To izmanto, lai sakārtotu datus efektīvai ievietošanai, dzēšanai un meklēšanai. Piemēram, bināram kokam ir logN laiks elementa meklēšanai.Izmēģiniet:Tas ir īpašs koku veids, ko izmanto vārdnīcas glabāšanai. Tas ir ātrs un efektīvs dinamiskas pareizrakstības pārbaudes veids.Kaudze:Tā ir arī koka datu struktūra, kas ieviesta, izmantojot masīvus. To izmanto prioritāro rindu ieviešanai.B koks un B + koks:B-Tree un B+Tree ir koka datu struktūras, ko izmanto indeksēšanas ieviešanai datu bāzēs.Maršrutēšanas tabula:Koka datu struktūra tiek izmantota arī datu glabāšanai maršrutēšanas tabulās maršrutētājos.

Koka datu struktūras veidi

Tālāk ir norādīti koka datu struktūras veidi.

Vispārējs koks:Vispārējais koks ir viens no koka datu struktūras veidiem. Vispārējā kokā mezglam var būt 0 vai maksimālais n mezglu skaits. Mezgla pakāpei (mezglu skaitam, ko mezgls var saturēt) nav noteikti nekādi ierobežojumi. Vispārīgā koka augšējais mezgls ir pazīstams kā saknes mezgls. Vecāku mezgla bērni ir pazīstami kā apakškoki .

Var būt n apakškoku skaits vispārējā kokā. Vispārējā kokā apakškoki nav sakārtoti, jo apakškoka mezglus nevar sakārtot.
Katram kokam, kas nav tukšs, ir lejupvērsta mala, un šīs malas ir savienotas ar mezgliem, kas pazīstami kā bērnu mezgli . Saknes mezgls ir apzīmēts ar 0. līmeni. Mezgli, kuriem ir viens un tas pats vecākais, ir zināmi kā brāļi un māsas . Binārais koks :Šeit pats binārais nosaukums norāda uz diviem skaitļiem, t.i., 0 un 1. Binārajā kokā katram koka mezglam var būt maksimāli divi pakārtotie mezgli. Šeit vislielākais nozīmē, vai mezglam ir 0 mezgli, 1 mezgls vai 2 mezgli.

Lai uzzinātu vairāk par bināro koku, noklikšķiniet uz tālāk norādītās saites:
https://www.javatpoint.com/binary-tree Binārās meklēšanas koks :Binārais meklēšanas koks ir nelineāra datu struktūra, kurā ir savienots viens mezgls n mezglu skaits. Tā ir uz mezgliem balstīta datu struktūra. Mezglu var attēlot binārā meklēšanas kokā ar trim laukiem, t.i., datu daļa, kreisais pabērns un labais pabērns. Mezglu var savienot ar diviem galējiem pakārtotajiem mezgliem binārā meklēšanas kokā, tāpēc mezglā ir divas norādes (kreisais pakārtotais un labais pakārtotais rādītājs).
Katram kreisā apakškoka mezglam ir jābūt vērtībai, kas ir mazāka par saknes mezgla vērtību, un katra labā apakškoka mezgla vērtībai ir jābūt lielākai par saknes mezgla vērtību.

Mezglu var izveidot, izmantojot lietotāja definētu datu tipu, kas pazīstams kā struktūra, kā parādīts zemāk:

 struct node { int data; struct node *left; struct node *right; } 

Iepriekš minētā ir mezgla struktūra ar trim laukiem: datu lauks, otrais lauks ir mezgla tipa kreisais rādītājs un trešais lauks ir mezgla tipa labais rādītājs.

Lai uzzinātu vairāk par bināro meklēšanas koku, noklikšķiniet uz tālāk norādītās saites:

https://www.javatpoint.com/binary-search-tree

AVL koks

Tas ir viens no binārā koka veidiem, vai mēs varam teikt, ka tas ir binārā meklēšanas koka variants. AVL koks atbilst īpašumam binārais koks kā arī no binārā meklēšanas koks . Tas ir pašbalansējošs binārais meklēšanas koks, ko izgudroja Adelsons Veļskis Lindas . Šeit pašbalansēšana nozīmē kreisā apakškoka un labā apakškoka augstuma līdzsvarošanu. Šo līdzsvarošanu mēra ar līdzsvarošanas faktors .

Mēs varam uzskatīt koku par AVL koku, ja koks pakļaujas binārajam meklēšanas kokam, kā arī līdzsvarojošajam faktoram. Līdzsvarošanas koeficientu var definēt kā starpība starp kreisā apakškoka augstumu un labā apakškoka augstumu . Līdzsvarošanas faktora vērtībai jābūt 0, -1 vai 1; tāpēc katram AVL koka mezglam balansēšanas koeficienta vērtībai jābūt 0, -1 vai 1.

c# vārdnīca

Lai uzzinātu vairāk par AVL koku, noklikšķiniet uz tālāk norādītās saites:

https://www.javatpoint.com/avl-tree

Sarkanmelns koks

Sarkanmelnais koks ir binārais meklēšanas koks. Red-Black koka priekšnoteikums ir tas, ka mums jāzina par bināro meklēšanas koku. Binārajā meklēšanas kokā kreisā apakškoka vērtībai jābūt mazākai par šī mezgla vērtību, bet labā apakškoka vērtībai jābūt lielākai par šī mezgla vērtību. Kā zināms, binārās meklēšanas laika sarežģītība vidējā gadījumā ir log₂n, labākais gadījums ir O(1), bet sliktākais ir O(n).

Veicot jebkuru darbību ar koku, mēs vēlamies, lai koks būtu līdzsvarots tā, lai visas darbības, piemēram, meklēšana, ievietošana, dzēšana utt., aizņemtu mazāk laika, un visām šīm darbībām būtu laika sarežģītība: žurnāls₂n.

Sarkanmelnais koks ir pašbalansējošs binārais meklēšanas koks. AVL koks ir arī augstuma balansēšanas binārās meklēšanas koks kāpēc mums vajadzīgs sarkanmelns koks . AVL kokā mēs nezinām, cik apgriezienu būtu nepieciešams, lai koku līdzsvarotu, bet sarkanmelnajā kokā ir nepieciešami maksimāli 2 apgriezieni, lai koku līdzsvarotu. Tajā ir viens papildu bits, kas attēlo mezgla sarkano vai melno krāsu, lai nodrošinātu koka līdzsvarošanu.

Spēļu koks

Izklāšanas koka datu struktūra ir arī binārais meklēšanas koks, kurā nesen piekļūtais elements tiek novietots koka saknes pozīcijā, veicot dažas rotācijas darbības. Šeit, izspēle nozīmē nesen piekļūtu mezglu. Tas ir pašbalansēšana binārais meklēšanas koks, kam nav skaidru līdzsvara nosacījumu, piemēram, AVL koks.

Var būt iespēja, ka izplešanās koka augstums nav līdzsvarots, t.i., gan kreisā, gan labā apakškoka augstums var atšķirties, taču darbības izvēršanas kokā notiek secībā mierīgs laiks kur n ir mezglu skaits.

Splay koks ir līdzsvarots koks, taču to nevar uzskatīt par augstuma sabalansētu koku, jo pēc katras darbības tiek veikta rotācija, kas noved pie līdzsvarota koka.

Treap

Treap datu struktūra nāk no Tree un Heap datu struktūras. Tātad tas ietver gan koka, gan kaudzes datu struktūru īpašības. Binārajā meklēšanas kokā katram kreisā apakškoka mezglam ir jābūt vienādam vai mazākam par saknes mezgla vērtību, un katram labā apakškoka mezglam ir jābūt vienādam vai lielākam par saknes mezgla vērtību. Kaudzes datu struktūrā gan labais, gan kreisais apakškoks satur lielākas atslēgas nekā sakne; tāpēc mēs varam teikt, ka saknes mezglā ir viszemākā vērtība.

Slēpšanas datu struktūrā katram mezglam ir abi taustiņu un prioritāte kur atslēga ir iegūta no binārās meklēšanas koka un prioritāte ir iegūta no kaudzes datu struktūras.

The Treap datu struktūra atbilst diviem rekvizītiem, kas norādīti tālāk:

• Mezgla labais bērns>=pašreizējais mezgls un kreisais mezgla bērns<=current node (binary tree)< li>
• Jebkura apakškoka atvasinājumiem ir jābūt lielākiem par mezglu (kaudzi)

B-koks

B-koks ir līdzsvarots m-way koks kur m nosaka koka secību. Līdz šim mēs lasījām, ka mezglā ir tikai viena atslēga, bet b-kokam var būt vairāk nekā viena atslēga un vairāk nekā 2 bērni. Tas vienmēr uztur sakārtotos datus. Binārajā kokā ir iespējams, ka lapu mezgli var būt dažādos līmeņos, bet b-kokā visiem lapu mezgliem jābūt vienā līmenī.

Ja secība ir m, tad mezglam ir šādas īpašības:

• Katram mezglam b-kokā var būt maksimums m bērniem
• Minimālajiem bērniem lapas mezglā ir 0 bērnu, saknes mezglā ir vismaz 2 bērni, un iekšējā mezgla minimālie griesti ir m/2 bērni. Piemēram, m vērtība ir 5, kas nozīmē, ka mezglā var būt 5 bērni un iekšējos mezglos var būt ne vairāk kā 3 bērni.
• Katram mezglam ir maksimālās (m-1) atslēgas.

Saknes mezglā ir jābūt vismaz 1 atslēgai, un visos pārējos mezglos ir jābūt vismaz griesti m/2 mīnus 1 atslēgas.