TechCodeview

Pirmkārt, mēs sapratīsim binārais koks un binārā meklēšanas koks atsevišķi, un tad mēs aplūkosim atšķirības starp bināro koku un bināro meklēšanas koku.

Kas ir binārais koks?

A Binārais koks irRādītājs uz kreiso bērnu:Tajā tiek saglabāta kreisā pakārtota mezgla atsauce.Rādītājs uz pareizo bērnu:Tajā tiek saglabāta labā pakārtotā mezgla atsauce.Datu elements:Datu elements ir mezglā saglabāto datu vērtība.

Bināro koku var attēlot šādi:

Iepriekš redzamajā attēlā var novērot, ka katrā mezglā ir maksimāli 2 bērni. Ja nevienā mezglā nav kreisās vai labās puses atvasinājuma, rādītāja vērtība attiecībā uz šo bērnu būtu NULL.

Binārajā kokā izmantotās pamata terminoloģijas ir:

Saknes mezgls:Saknes mezgls ir pirmais vai augstākais mezgls binārajā kokā.Vecuma mezgls:Ja mezgls ir savienots ar citu mezglu caur malām, šo mezglu sauc par vecākmezglu. Binārajā kokā vecākajam mezglam var būt ne vairāk kā 2 bērni.Bērnu mezgls:Ja mezglam ir priekštecis, tad šis mezgls ir pazīstams kā a bērnu mezgls .Lapu mezgls:Mezgls, kurā nav neviena bērna, kas pazīstams kā a lapas mezgls .Iekšējais mezgls:Mezgls, kuram ir vismaz 2 bērni, kas pazīstams kā an iekšējais mezgls .Mezgla dziļums:Attālums no saknes mezgla līdz dotajam mezglam ir zināms kā a mezgla dziļums . Mēs nodrošinām etiķetes visiem mezgliem, piemēram, saknes mezgls ir apzīmēts ar 0, jo tam nav dziļuma, saknes mezglu bērni ir apzīmēti ar 1, saknes bērna bērni ir apzīmēti ar 2.Augstums:Garākais attālums no saknes mezgla līdz lapas mezglam ir mezgla augstums .

Binārajā kokā ir viens koks, kas pazīstams kā a ideāls binārais koks . Tas ir koks, kurā visos iekšējos mezglos ir jābūt diviem mezgliem, un visiem lapu mezgliem jābūt vienādā dziļumā. Perfekta binārā koka gadījumā kopējo binārajā kokā esošo mezglu skaitu var aprēķināt, izmantojot šādu vienādojumu:

n = 2^m+1-1

kur n ir mezglu skaits, m ir mezgla dziļums.

Kas ir binārās meklēšanas koks?

A Binārais meklēšanas koks ir koks, kas seko noteiktai secībai, lai sakārtotu elementus, savukārt binārais koks neseko nevienai secībai. Binārajā meklēšanas kokā kreisā mezgla vērtībai ir jābūt mazākai par vecākmezglu, bet labā mezgla vērtībai ir jābūt lielākai par vecākmezglu.

Izpratīsim binārā meklēšanas koka jēdzienu, izmantojot piemērus.

Iepriekš redzamajā attēlā var novērot, ka saknes mezgla vērtība ir 15, kas ir lielāka par visu kreisā apakškoka mezglu vērtību. Saknes mezgla vērtība ir mazāka par visu labās puses apakškoka mezglu vērtībām. Tagad mēs pārejam uz saknes mezgla kreiso bērnu. 10 ir lielāks par 8 un mazāks par 12; tas apmierina arī binārā meklēšanas koka īpašību. Tagad mēs pārejam uz saknes mezgla labo bērnu; vērtība 20 ir lielāka par 17 un mazāka par 25; tas atbilst arī binārā meklēšanas koka īpašībai. Tāpēc mēs varam teikt, ka iepriekš parādītais koks ir binārais meklēšanas koks.

Tagad, ja mēs mainām vērtību 12 uz 16 iepriekš minētajā binārajā kokā, mums ir jāatrod, vai tas joprojām ir binārais meklēšanas koks.

Saknes mezgla vērtība ir 15, kas ir lielāka par 10, bet mazāka par 16, tāpēc tā neatbilst binārā meklēšanas koka īpašībai. Tāpēc tas nav binārs meklēšanas koks.

Operācijas binārajā meklēšanas kokā

Mēs varam veikt ievietošanas, dzēšanas un meklēšanas darbības binārajā meklēšanas kokā. Sapratīsim, kā tiek veikta meklēšana binārajā meklēšanā. Tālāk ir parādīts binārais koks, kurā mums jāveic meklēšanas darbība:

Pieņemsim, ka mums ir jāmeklē 10 iepriekš minētajā binārajā kokā. Lai veiktu bināro meklēšanu, mēs ņemsim vērā visus veselos skaitļus sakārtotā masīvā. Pirmkārt, mēs izveidojam pilnu sarakstu meklēšanas laukā, un visi skaitļi būs meklēšanas laukā. Meklēšanas vieta ir atzīmēta ar diviem rādītājiem, t.i., sākumu un beigas. Iepriekš minētā binārā koka masīvu var attēlot kā

Vispirms mēs aprēķināsim vidējo elementu un salīdzināsim vidējo elementu ar meklējamo elementu. Vidējais elements tiek aprēķināts, izmantojot n/2. n vērtība ir 7; tāpēc vidējais elements ir 15. Vidējais elements nav vienāds ar meklēto elementu, t.i., 10.

Piezīme: Ja meklējamais elements ir mazāks par vidējo elementu, tad meklēšana tiks veikta kreisajā pusē; pretējā gadījumā meklēšana tiks veikta labajā pusē. Vienlīdzības gadījumā elements tiek atrasts.

Tā kā meklējamais elements ir mazāks par vidējo elementu, meklēšana tiks veikta kreisajā masīvā. Tagad meklēšana ir samazināta uz pusi, kā parādīts zemāk:

Vidējais elements kreisajā masīvā ir 10, kas ir vienāds ar meklēto elementu.

Laika sarežģītība

Binārajā meklēšanā ir n elementi. Ja vidējais elements nav vienāds ar meklēto elementu, tad meklēšanas telpa tiek samazināta līdz n/2, un mēs turpināsim samazināt meklēšanas telpu par n/2, līdz elementu atradīsim. Visā samazināšanā, ja mēs pārietam no n uz n/2 uz n/4 un tā tālāk, tad tas aizņems log₂n soļi.

Atšķirības starp bināro koku un bināro meklēšanas koku