Kas ir binārais meklēšanas koks?

Binārais meklēšanas koks ir viena no dažādajām datu struktūrām, kas palīdz mums sakārtot un kārtot datus. Tas ir efektīvs veids, kā uzglabāt datus hierarhijā, un ir ļoti elastīgs.

Šajā rakstā mēs sīkāk aplūkosim, kā tas darbojas, kā arī tās īpašības un lietojumus.

Kas ir binārais meklēšanas koks?

Binārais meklēšanas koks ir datu struktūra, kas sastāv no mezgliem — līdzīgi kā saistītajiem sarakstiem. Var būt divu veidu mezgli: vecāks un bērns. Saknes mezgls ir struktūras sākuma punkts, kas sazarojas divos pakārtotos mezglos, ko sauc par kreiso mezglu un labo mezglu.

Uz katru mezglu var atsaukties tikai tā vecāks, un mēs varam šķērsot koka mezglus atkarībā no virziena. Binārajam meklēšanas kokam ir trīs galvenie rekvizīti:

1. Kreisais mezgls ir mazāks par tā vecāku.
2. Labais mezgls ir lielāks par tā vecāku.
3. Kreisajam un labajam apakškokam jābūt Binary Search Trees.

Perfekts binārās meklēšanas koks tiek sasniegts, ja ir aizpildīti visi līmeņi, un katram mezglam ir kreisais un labais pakārtots mezgls.

Saistīts: Datu zinātnes bibliotēkas Python, kas būtu jāizmanto ikvienam datu zinātniekam

Binārā meklēšanas koka pamatoperācijas

Tagad jums ir labāks priekšstats par to, kas ir binārās meklēšanas koks. Tālāk mēs varam apskatīt tā pamatdarbības.

1. Meklēšanas operācija

Meklēšana ļauj mums atrast konkrētu kokā esošo vērtību. Mēs varam izmantot divu veidu meklēšanu: meklēšanu pēc platuma (BFS) un dziļuma meklēšanu (DFS). Meklēšana pēc platuma ir meklēšanas algoritms, kas sākas saknes mezglā un šķērso horizontāli, no vienas puses uz otru, līdz tiek atrasts mērķis. Katrs mezgls šīs meklēšanas laikā tiek apmeklēts vienu reizi.

No otras puses, meklēšana pēc dziļuma šķērso koku vertikāli — sākot no saknes mezgla un virzoties lejup pa vienu zaru. Ja mērķis ir atrasts, darbība beidzas. Bet, ja nē, tas pārmeklē citus mezglus.

2. Ievietošanas darbība

Ievietošanas darbība izmanto meklēšanas darbību, lai noteiktu vietu, kur jāievieto jaunais mezgls. Process sākas no saknes mezgla, un meklēšana sākas, līdz tiek sasniegts galamērķis. Ir trīs gadījumi, kas jāņem vērā, ievietojot.

• 1. gadījums: ja mezgla nav. Ievietojamais mezgls kļūs par saknes mezglu.

• 2. gadījums: bērnu nav. Šajā gadījumā mezgls tiks salīdzināts ar saknes mezglu. Ja tas ir lielāks, tas kļūs par pareizo bērnu; pretējā gadījumā tas kļūs par kreiso bērnu.

• 3. gadījums: kad ir klāt sakne un tās bērni. Jaunais mezgls tiks salīdzināts ar katru mezglu tā ceļā, lai noteiktu, kuru mezglu tas apmeklēs nākamais. Ja mezgls ir lielāks par saknes mezglu, tas šķērsos pa labo apakškoku vai pa kreisi. Līdzīgi tiek veikti salīdzinājumi katrā līmenī, lai noteiktu, vai tas virzīsies pa labi vai pa kreisi, līdz tas nonāks galamērķī.

3. Dzēšanas darbība

Dzēšanas darbība tiek izmantota, lai noņemtu noteiktu mezglu kokā. Dzēšana tiek uzskatīta par sarežģītu, jo pēc mezgla noņemšanas koks ir attiecīgi jāpārkārto. Ir trīs galvenie gadījumi, kas jāņem vērā:

• 1. gadījums: lapas mezgla dzēšana. Lapu mezgls ir mezgls bez bērniem. To ir visvieglāk noņemt, jo tas neietekmē nevienu citu mezglu; mēs vienkārši šķērsojam koku, līdz sasniedzam to, un izdzēšam to.

• 2. gadījums: mezgla dzēšana ar vienu bērnu. Dzēšot vecāku ar vienu mezglu, bērns ieņems savu pozīciju, un visi nākamie mezgli tiks pārvietoti uz augšu. Apakškoku struktūrā izmaiņas nebūs.

• 3. gadījums: mezgla dzēšana ar diviem bērniem. Kad mums ir jānoņem mezgls ar diviem bērniem, vispirms jāatrod nākamais mezgls, kas var ieņemt savu pozīciju. Divi mezgli var aizstāt noņemto mezglu, secīgo pēcteci vai priekšteci. Kārtas kārtas pēctecis ir labā apakškoka vistālāk pa kreisi esošais bērns, un kārtas priekštecis ir kreisā apakškoka galējais labējais bērns. Mēs kopējam mezglā pēcteča/priekšgājēja saturu un izdzēšam secīgo pēcteci/priekšgājēju.

Saistīts: Kā izveidot datu struktūras, izmantojot JavaScript ES6 klases

Kā šķērsot bināro meklēšanas koku

Pāreja ir process, kurā mēs pārvietojamies binārajā meklēšanas kokā. Tas tiek darīts, lai atrastu konkrētu objektu vai izdrukātu koka kontūru. Mēs vienmēr sākam no saknes mezgla un ir jāseko malām, lai nokļūtu citos mezglos. Katrs mezgls ir jāuzskata par apakškoku, un process tiek atkārtots, līdz tiek apmeklēti visi mezgli.

• Pasūtījuma šķērsošana: Pārvietojoties secībā, karte tiks izveidota augošā secībā. Ar šo metodi mēs sākam no kreisā apakškoka un turpinām uz sakni un labo apakškoku.

• Iepriekšēja pasūtījuma apceļošana: Šajā metodē vispirms tiek apmeklēts saknes mezgls, pēc tam kreisais apakškoks un labais apakškoks.

• Apmeklēšana pēc pasūtījuma: Šī šķērsošana ietver saknes mezgla apmeklējumu pēdējo. Mēs sākam no kreisā apakškoka, tad labā apakškoka un tad saknes mezgla.

Reālās pasaules lietojumprogrammas

Tātad, kā mēs izmantojam bināros meklēšanas koka algoritmus? Kā var nojaust, tie ir ārkārtīgi efektīvi meklēšanā un šķirošanā. Bināro koku lielākā stiprā puse ir to organizētā struktūra. Tas ļauj veikt meklēšanu ar ievērojamu ātrumu, samazinot analizējamo datu apjomu uz pusi vienā piegājienā.

Binārie meklēšanas koki ļauj mums efektīvi uzturēt dinamiski mainīgu datu kopu organizētā formā. Lietojumprogrammām, kurās dati tiek bieži ievietoti un izņemti, tie ir ļoti noderīgi. Videospēļu dzinēji izmanto algoritmu, kas balstīts uz kokiem, kas pazīstams kā binārais telpas nodalījums, lai palīdzētu sakārtot objektus. Microsoft Excel un lielākā daļa izklājlapu programmatūras izmanto bināros kokus kā pamata datu struktūru.

Jūs varētu būt pārsteigts, uzzinot, ka Morzes kods datu kodēšanai izmanto bināro meklēšanas koku. Vēl viens ievērojams iemesls, kāpēc binārās meklēšanas koki ir tik noderīgi, ir to daudzās variācijas. To elastība ir radījusi daudzus variantus, lai atrisinātu visu veidu problēmas. Pareizi lietojot, binārās meklēšanas koki ir lieliska vērtība.

Binārie meklēšanas koki: ideāls sākumpunkts

Viens no galvenajiem veidiem, kā novērtēt inženiera zināšanas, ir viņu zināšanas un datu struktūru izmantošana. Datu struktūras ir noderīgas un var palīdzēt izveidot efektīvāku sistēmu. Binārās meklēšanas koki ir lielisks ievads datu struktūrām jebkuram izstrādātājam, kas sāk darbu.

15 JavaScript masīva metodes, kuras jums vajadzētu apgūt jau šodien

Vai vēlaties izprast JavaScript masīvus, bet nevarat ar tiem tikt galā? Lai iegūtu norādījumus, skatiet mūsu JavaScript masīvu piemērus.

Lasiet Tālāk

Par autoru