Iesācēju ceļvedis bināriem kokiem

Ja esat apguvis datorzinātņu grādu datu struktūru kursā vai esat pašmācīts programmētājs, iespējams, esat saskāries ar terminu “binārie koki”. Lai gan tie var izklausīties nedaudz satriecoši un sarežģīti, binārā koka jēdziens ir pavisam vienkāršs.

Lasiet tālāk, kad mēs sadalām bināros kokus, un kāpēc tie ir nepieciešama programmētāju pamatkoncepcija.

Kas ir binārie koki?

Binārie koki ir viena no pirmajām datu struktūrām, kuras studentiem māca datu struktūru kursā. Bināro koku veido daudzi mezgli, un katrā binārā koka mezglā ir divi rādītāji, kas norāda kreiso un labo bērnu datu mezglu.

Pirmo mezglu binārajā kokā sauc par “sakni”. Pēdējā līmeņa mezglus kokā sauc par lapām.

Katrā mezglā ir datu vienums un divi mezgla rādītāji. Tukšu bināro koku attēlo nulles rādītājs. Kā jūs, iespējams, jau sapratāt, binārajiem kokiem var būt tikai divi bērni (līdz ar to arī nosaukums).

Bināro koku struktūru veidi

Atkarībā no mezglu izvietojuma ir vairākas dažādas bināro koku struktūras. Bināro koku sauc par pilnu bināro koku, ja katram koka mezglam ir nulle vai divi bērni. Perfektā binārā kokā visiem mezgliem ir divi bērni, un lapas atrodas vienā dziļumā.

Saistīts: Labākie veidi, kā iemācīties bez maksas kodēt

Pilnīgam binārajam kokam ir mezgli, kas aizpildīti katrā līmenī, izņemot pēdējo līmeni. Pilnīgos bināros kokos mezgli koncentrējas saknes kreisajā pusē. Vēl viena izplatīta struktūra ir līdzsvarots binārs koks; šajā struktūrā labās un kreisās apakškoku augstumam ir jāatšķiras ne vairāk kā par vienu. Ir arī nepieciešams, lai kreisās un labās apakškokiem būtu jābūt līdzsvarotiem.

Ir svarīgi atzīmēt, ka līdzsvarotā binārā koka augstums ir O (logn), kur n ir mezglu skaits kokā.

Dažos gadījumos, ja katram mezglam ir tikai viens kreisais vai labais bērns, binārais koks var kļūt par šķību bināro koku. Pēc tam tas uzvedīsies kā saistīts saraksts, šādus kokus sauc arī par deģenerētu koku.

Kas ir binārie meklēšanas koki?

Binārā meklēšanas koks (BST) būtībā ir sakārtots binārs koks ar īpašu īpašību, kas pazīstams kā "bināro meklēšanas koka" īpašums. BST rekvizīts nozīmē, ka mezgli, kuru atslēgas vērtība ir mazāka par sakni, tiek ievietoti kreisajā apakškokā, un mezgli, kuru atslēgas vērtība ir lielāka par sakni, ir daļa no labās apakškokiem.

BST rekvizītam ir jābūt patiesam katram nākamajam koka meistaram.

Binārās meklēšanas koki piedāvā ātru ievietošanu un meklēšanu. Ievietošanas, dzēšanas un meklēšanas operācijām ir sliktākā laika sarežģītība O (n), kas ir līdzīga saistītajam sarakstam.

Bināro koku priekšrocības

Binārie koki piedāvā daudzas priekšrocības, tāpēc tie joprojām ir ļoti noderīga datu struktūra. Tos var izmantot, lai parādītu strukturālās attiecības un hierarhijas datu kopā. Vēl svarīgāk ir tas, ka binārie koki ļauj efektīvi meklēt, dzēst un ievietot.

Tas ir arī ļoti viegli ieviest un uzturēt bināro koku. Binārais koks programmētājiem piedāvā sakārtota masīva un saistītā saraksta priekšrocības; meklēšana binārā kokā ir tikpat ātra kā sakārtotā masīvā, un ievietošanas vai dzēšanas darbības ir tikpat efektīvas kā saistītajos sarakstos.

Binārie koki ir svarīgas datu struktūras

Binārie koki ir ļoti svarīga datu struktūra, un ir svarīgi, lai programmētājiem būtu ērti tos pielietot savās programmās. Bieži intervētāji uzdod vienkāršas bināro koku problēmas, piemēram, šķērsošanu, maksimālo dziļumu, spoguļošanu utt.

Mēs ļoti iesakām izprast bināro koku koncepciju un iepazīties ar tipiskām intervijas problēmām.

TreeViz: vienkāršs veids, kā vizualizēt datu struktūras

Lasīt Tālāk

Par autoru