Binārā meklēšanas koka ieviešana

2024 Autors: Angel Austin | [email protected]. Pēdējoreiz modificēts: 2023-12-17 05:35

Binārais meklēšanas koks - strukturēta datu bāze, kurā ir mezgli, divas saites uz citiem mezgliem, pa labi un pa kreisi. Mezgli ir klases objekts, kurā ir dati, un NULL ir zīme, kas iezīmē koka beigas.

To bieži dēvē par BST, kam ir īpaša īpašība: mezgli, kas ir lielāki par sakni, atrodas pa labi no tā, bet mazāki - pa kreisi.

Vispārīga teorija un terminoloģija

Binārā meklēšanas kokā katrs mezgls, izņemot sakni, ir savienots ar virzītu malu no viena mezgla uz otru, ko sauc par vecāku. Katru no tiem var savienot ar patvaļīgu skaitu mezglu, ko sauc par bērniem. Mezgli bez "bērniem" sauc par lapām (ārējiem mezgliem). Elementus, kas nav lapas, sauc par iekšējiem. Mezgli ar vienu un to pašu vecāku ir brāļi un māsas. Augšējo mezglu sauc par sakni. Programmā BST katram mezglam piešķiriet elementu un pārliecinieties, vai tiem ir iestatīts īpašs rekvizīts.

Koku terminoloģija:

Mezgla dziļums ir malu skaits, kas noteikts no saknes līdz tam.
Mezgla augstums ir malu skaits, kas noteikts no tā līdz dziļākajai lapai.
Koka augstumu nosaka saknes augstums.
Binārās meklēšanas koks ir īpašs dizains, tas nodrošina vislabāko augstuma un mezglu skaita attiecību.
Augstums h ar N mezgliem, ne vairāk kā O (log N).

To var viegli pierādīt, saskaitot mezglus katrā līmenī, sākot no saknes, pieņemot, ka tajā ir vislielākais to skaits: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Atrisinot šo vērtību h, iegūst h=O (log n).

Koksnes priekšrocības:

Atspoguļojiet datu strukturālās attiecības.
Izmanto, lai attēlotu hierarhijas.
Nodrošiniet efektīvu instalēšanu un meklēšanu.
Koki ir ļoti elastīgi dati, kas ļauj pārvietot apakškokus ar minimālu piepūli.

Meklēšanas metode

Kopumā, lai noteiktu, vai vērtība atrodas BST, sāciet bināro meklēšanas koku tās saknē un nosakiet, vai tas atbilst prasībām:

būt pašā saknē;
būt saknes kreisajā apakškokā;
saknes labajā apakškokā.

Ja neviens bāzes reģistrs nav apmierināts, tiek veikta rekursīva meklēšana attiecīgajā apakškokā. Faktiski ir divas pamata iespējas:

Koks ir tukšs - atgriezt nepatiesu.
Vērtība atrodas saknes mezglā - atgriezt patiesu.

Jāatzīmē, ka binārais meklēšanas koks ar izstrādātu shēmu vienmēr sāk meklēšanu pa ceļu no saknes līdz lapai. Sliktākajā gadījumā tas iet līdz pat lapai. Tāpēc sliktākais laiks ir proporcionāls garākā ceļa garumam no saknes līdz lapai, kas ir koka augstums. Kopumā šajā gadījumā jums ir jāzina, cik ilgs laiks nepieciešams, lai meklētu kokā saglabāto vērtību skaita funkciju.

Citiem vārdiem sakot, pastāv saistība starp mezglu skaitu BST un koka augstumu atkarībā no tā "formas". Sliktākajā gadījumā mezgliem ir tikai viens bērns, un līdzsvarots binārais meklēšanas koks būtībā ir saistīts saraksts. Piemēram:

Šim kokam ir 5 mezgli un augstums=5. Lai atrastu vērtības diapazonā no 16-19 un 21-29, būs nepieciešams šāds ceļš no saknes līdz lapai (mezgls, kurā ir vērtība 20), t.i., tas prasīs laiku proporcionāli mezglu skaitam. Labākajā gadījumā viņiem visiem ir 2 bērni, un lapas atrodas vienādā dziļumā.

Šim binārajam meklēšanas kokam ir 7 mezgli un augstums=3. Parasti šāda koka (pilna koka) augstums būs aptuveni log 2 (N), kur N ir mezglu skaits kokā.. Log 2 (N) vērtība ir reižu skaits (2), kad N var dalīt, pirms tiek sasniegta nulle.

Apkopojot: sliktākais laiks, kas nepieciešams, lai meklētu BST, ir O (koka augstums). Sliktākais "lineārais" koks ir O(N), kur N ir mezglu skaits kokā. Labākajā gadījumā "pilnīgs" koks ir O(log N).

BST binārais ievietojums

Jautāju, kur vajadzētu būtjaunais mezgls atrodas BST, jums ir jāsaprot loģika, tas ir jānovieto tur, kur lietotājs to atrod. Turklāt jums ir jāatceras noteikumi:

Dublikāti nav atļauti. Mēģinot ievietot dublikātu, tiks radīts izņēmums.
Publiskās ievietošanas metode faktiskai ievietošanai izmanto rekursīvo palīgmetodi.
Mezgls ar jaunu vērtību vienmēr tiek ievietots kā lapa BST.
Publiskās ievietošanas metode atgriež spēkā neesošu, bet palīgmetode atgriež BSTnode. Tas tiek darīts, lai apstrādātu gadījumu, kad tam nodotais mezgls ir nulle.

Kopumā palīgmetode norāda, ka, ja sākotnējais binārais meklēšanas koks ir tukšs, rezultāts ir koks ar vienu mezglu. Pretējā gadījumā rezultāts būs rādītājs uz to pašu mezglu, kas tika nodots kā arguments.

Dzēšana binārajā algoritmā

Kā jūs varētu gaidīt, elementa dzēšana ietver mezgla atrašanu, kurā ir noņemamā vērtība. Šajā kodā ir vairākas lietas:

BST izmanto palīgu, pārslogotu dzēšanas metodi. Ja meklējamais elements nav kokā, palīga metode galu galā tiks izsaukta ar n==null. To neuzskata par kļūdu, koks šajā gadījumā vienkārši nemainās. Dzēšanas palīga metode atgriež vērtību - rādītāju uz atjaunināto koku.
Kad lapa tiek noņemta, noņemšana no binārā meklēšanas koka iestata atbilstošo tās vecākbērnu rādītāju uz nulli vai sakni uz nulli, ja tiek noņemta.mezgls ir sakne, un tam nav bērnu.
Ņemiet vērā, ka dzēšanas izsaukumam ir jābūt vienam no šiem: root=delete (root, key), n.setLeft (delete (n.getLeft (), taustiņš)), n.setRight (delete(n. getRight(), atslēga)). Tādējādi visos trīs gadījumos ir pareizi, ka dzēšanas metode vienkārši atgriež nulli.
Kad izdodas meklēt mezglu, kurā ir dzēšamā vērtība, ir trīs iespējas: dzēšamais mezgls ir lapa (nav bērnu), dzēšamajam mezglam ir viens bērns, tam ir divi bērni.
Ja mezglam, kas tiek noņemts, ir viens bērns, varat to vienkārši aizstāt ar bērnu, atgriežot rādītāju bērnam.
Ja dzēšamajam mezglam ir nulle vai 1 pakārtots, tad dzēšanas metode "sekos ceļu" no saknes uz šo mezglu. Tāpēc sliktākais laiks ir proporcionāls koka augstumam gan meklēšanai, gan ievietošanai.

Ja noņemamajam mezglam ir divi bērni, tiek veiktas šādas darbības:

Atrodiet dzēšamo mezglu, ievērojot ceļu no saknes uz to.
Atrodiet mazāko v vērtību labajā apakškokā, turpinot ceļu uz lapu.
Rekursīvi noņemiet v vērtību, izpildiet to pašu ceļu kā 2. darbībā.
Tādējādi sliktākajā gadījumā ceļš no saknes līdz lapai tiek veikts divas reizes.

Gājienu secība

Izbraukšana ir process, kas apmeklē visus koka mezglus. Tā kā C binārais meklēšanas koks ir nelineāra datu struktūra, nav unikālas šķērsošanas. Piemēram, dažreiz vairāki šķērsošanas algoritmisagrupēti šādos divos veidos:

šķērsošanas dziļums;
pirmā caurlaide.

Ir tikai viens platuma šķērsošanas veids - līmeņa apiešana. Šī šķērsošana apmeklē mezglus vienā līmenī uz leju un pa kreisi, augšā un pa labi.

Ir trīs dažādi dziļuma krustojumu veidi:

Priekšpasūtījuma nodošana - vispirms apmeklējiet vecāku un pēc tam kreiso un labo bērnu.
Kārtības nodošana - apciemot kreiso bērnu, pēc tam vecāku un labo bērnu.
Pagājuši pēc pasūtījuma - apciemo kreiso bērnu, tad labo bērnu, tad vecāku.

Piemērs četriem binārā meklēšanas koka šķērsojumiem:

Iepriekšpasūtījums - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
Pasūtījums - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
Pasūtījums - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
Līmeņa pasūtījums - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Attēlā parādīta secība, kādā mezgli tiek apmeklēti. Skaitlis 1 ir pirmais mezgls noteiktā šķērsošanā, bet 7 ir pēdējais mezgls.

Šos vispārīgos šķērsojumus var attēlot kā vienu algoritmu, pieņemot, ka katrs mezgls tiek apmeklēts trīs reizes. Eilera tūre ir pastaiga ap bināro koku, kur katra mala tiek uzskatīta par sienu, kuru lietotājs nevar šķērsot. Šajā gājienā katrs mezgls tiks apmeklēts vai nu kreisajā, vai zemāk, vai labajā pusē. Eilera tūre, kas apmeklē mezglus kreisajā pusē, liek apiet prievārdu. Kad tiek apmeklēti tālāk norādītie mezgli, tie tiek šķērsoti secībā. Un, kad tiek apmeklēti labajā pusē esošie mezgli - iegūstietsoli pa solim apiet.

Navigācija un atkļūdošana

Lai atvieglotu navigāciju kokā, izveidojiet funkcijas, kas vispirms pārbauda, vai tie ir kreisais vai labais bērns. Lai mainītu mezgla pozīciju, ir jābūt ērtai piekļuvei rādītājam vecākmezglā. Pareizi ieviest koku ir ļoti grūti, tāpēc jums ir jāzina un jāpiemēro atkļūdošanas procesi. Binārā meklēšanas kokam ar ieviešanu bieži ir norādes, kas faktiski nenorāda braukšanas virzienu.

Lai to visu noskaidrotu, tiek izmantota funkcija, kas pārbauda, vai koks var būt pareizs, un palīdz atrast daudzas kļūdas. Piemēram, tas pārbauda, vai vecākais mezgls ir pakārtots mezgls. Izmantojot assert(is_wellformed(root)), daudzas kļūdas var tikt uztvertas priekšlaicīgi. Izmantojot pāris dotos pārtraukuma punktus šajā funkcijā, varat arī precīzi noteikt, kurš rādītājs ir nepareizs.

Funkcija Konsolenausgabe

Šī funkcija izskalo visu koku konsolē un tāpēc ir ļoti noderīga. Koka izvades mērķa izpildes secība ir šāda:

Lai to izdarītu, vispirms ir jānosaka, kāda informācija tiks izvadīta caur mezglu.
Un jums arī jāzina, cik plats un garš ir koks, lai ņemtu vērā, cik daudz vietas atstāt.
Tālāk norādītās funkcijas aprēķina šo informāciju kokam un katram apakškokam. Tā kā konsolē varat rakstīt tikai rindiņu pa rindiņai, jums būs jādrukā arī koks pa rindiņai.
Tagad mums ir nepieciešams cits veids, kā izstātiesvisu koku, nevis tikai rindiņu pa rindiņai.
Ar dump funkcijas palīdzību jūs varat nolasīt koku un būtiski uzlabot izvades algoritmu, ciktāl tas attiecas uz ātrumu.

Tomēr šo funkciju būs grūti izmantot lieliem kokiem.

Kopēt konstruktoru un iznīcinātāju

Tā kā koks nav triviāla datu struktūra, labāk ir ieviest kopēšanas konstruktoru, destruktoru un piešķiršanas operatoru. Destruktoru ir viegli ieviest rekursīvi. Ļoti lieliem kokiem tas var izturēt "kaudzes pārplūdi". Šajā gadījumā tas tiek formulēts iteratīvi. Ideja ir noņemt lapu, kas ir mazākā vērtība no visām lapām, tāpēc tā atrodas koka kreisajā pusē. Nogriežot pirmās lapas, veidojas jaunas, un koks saraujas, līdz beidzot beidz pastāvēt.

Kopēšanas konstruktoru var ieviest arī rekursīvi, taču esiet piesardzīgs, ja tiek izmests izņēmums. Pretējā gadījumā koks ātri kļūst mulsinošs un pakļauts kļūdām. Tāpēc priekšroka tiek dota iteratīvajai versijai. Ideja ir iziet cauri vecajam kokam un jaunajam kokam, tāpat kā to darītu destruktorā, klonējot visus mezglus, kas atrodas vecajā kokā, bet ne jaunos.

Izmantojot šo metodi, binārā meklēšanas koka ieviešana vienmēr ir labā stāvoklī, un iznīcinātājs to var noņemt pat nepilnīgā stāvoklī. Ja notiek izņēmums, viss, kas jums jādara, ir jādod destruktoram dzēst pusfabrikātu. norīkojuma operatorsvar viegli ieviest, izmantojot Kopēt un apmainīt.

Binārā meklēšanas koka izveide

Optimālie binārie meklēšanas koki ir neticami efektīvi, ja tie tiek pareizi pārvaldīti. Daži noteikumi binārajiem meklēšanas kokiem:

Vecākmezglam ir ne vairāk kā 2 pakārtotie mezgli.
Kreisais pakārtots mezgls vienmēr ir mazāks par vecākmezglu.
Derīgs pakārtots mezgls vienmēr ir lielāks par vecāku mezglu vai vienāds ar to.

Masīvs, kas tiks izmantots, lai izveidotu bināro meklēšanas koku:

Pamats veselu skaitļu masīvs ar septiņām vērtībām nešķirotā secībā.
Pirmā vērtība masīvā ir 10, tāpēc pirmais solis koka veidošanā ir izveidot 10 saknes mezglu, kā parādīts šeit.
Ar saknes mezglu kopu visas pārējās vērtības būs šī mezgla atvasinājumi. Atsaucoties uz noteikumiem, pirmais solis, kas jāveic, lai kokam pievienotu 7, ir salīdzināt to ar saknes mezglu.
Ja vērtība 7 ir mazāka par 10, tā kļūs par kreiso pakārtoto mezglu.
Ja vērtība 7 ir lielāka vai vienāda ar 10, tā tiks pārvietota pa labi. Tā kā ir zināms, ka 7 ir mazāks par 10, tas tiek apzīmēts kā kreisais pakārtotais mezgls.
Rekursīvi veiciet katra elementa salīdzināšanu.
Sekojot tam pašam modelim, veiciet to pašu salīdzinājumu ar masīva 14. vērtību.
Salīdzinot vērtību 14 ar saknes mezglu 10, zinot, ka 14 ir pareizais bērns.
Ejot pa masīvu,nāc uz 20.
Sāciet, salīdzinot masīvu ar 10 - atkarībā no tā, kurš no tiem ir lielāks. Tāpēc pārejiet pa labi un salīdziniet to ar 14 gadiem, viņam ir vairāk nekā 14 gadu, un viņam nav bērnu labajā pusē.
Tagad ir vērtība 1. Ievērojot to pašu modeli kā citām vērtībām, salīdziniet 1 ar 10, pārejot pa kreisi un salīdzinot ar 7 un visbeidzot ar 1 kreiso 7. mezgla atvasinājumu.
Ja vērtība ir 5, salīdziniet to ar 10. Tā kā 5 ir mazāks par 10, pārejiet pa kreisi un salīdziniet to ar 7.
Zinot, ka 5 ir mazāks par 7, turpiniet lejup pa koku un salīdziniet 5 ar 1 vērtību.
Ja 1 nav bērnu un 5 ir lielāks par 1, tad 5 ir derīgs 1 mezgla pakārtots.
Visbeidzot kokā ievietojiet vērtību 8.
Kad 8 ir mazāks par 10, pārvietojiet to pa kreisi un salīdziniet ar 7, bet 8 ir lielāks par 7, tāpēc pārvietojiet to pa labi un pabeidziet koku, padarot 8 par pareizu bērnu no 7.

Optimālo bināro meklēšanas koku vienkāršās elegances iegūšana un novērtēšana. Tāpat kā daudzas programmēšanas tēmas, bināro meklēšanas koku spēks izriet no to spējas sadalīt datus mazos, saistītos komponentos. No šī brīža varat strādāt ar pilnu datu kopu organizētā veidā.

Iespējamas binārās meklēšanas problēmas

Binārās meklēšanas koki ir lieliski, taču ir jāņem vērā daži brīdinājumi. Tie parasti ir efektīvi tikai tad, ja tie ir līdzsvaroti. Līdzsvarots koks ir koks, kurāstarpība starp jebkura koka mezgla apakškoku augstumiem ir ne vairāk kā viens. Apskatīsim piemēru, kas varētu palīdzēt precizēt noteikumus. Iedomāsimies, ka masīvs sākas kā kārtojams.

Ja šajā kokā mēģināt palaist binārā meklēšanas koka algoritmu, tas darbosies tieši tā, it kā tas tikai iterētu masīvā, līdz tiks atrasta vēlamā vērtība. Binārās meklēšanas spēks slēpjas spējā ātri filtrēt nevēlamās vērtības. Ja koks nav līdzsvarots, tas nesniegs tādas pašas priekšrocības kā līdzsvarots koks.

Veidojot bināro meklēšanas koku, ir ļoti svarīgi pārbaudīt datus, ar kuriem lietotājs strādā. Pirms veselu skaitļu binārā meklēšanas koka ieviešanas varat integrēt tādas rutīnas kā masīvu nejaušināšana, lai to līdzsvarotu.

Binārās meklēšanas aprēķinu piemēri

Mums ir jānosaka, kāda veida koks tiks iegūts, ja 25 tiks ievietots šādā binārajā meklēšanas kokā:

5 15

/ /

2 12 20

Ievietojot x kokā T, kas vēl nesatur x, atslēga x vienmēr tiek ievietota jaunā lapā. Saistībā ar to jaunais koks izskatīsies šādi:

5 15

/ /

2 12 20

Kādu koku jūs iegūtu, ja šādā binārajā meklēšanas kokā ievietotu 7?

5 15

/ /

2 12 20

Atbilde:

5 15

/ / /

2 7 12 20

Bināro meklēšanas koku var izmantot, lai saglabātu jebkuru objektu. Bināra meklēšanas koka izmantošanas priekšrocība saistītā saraksta vietā ir tāda, ka, ja koks ir pietiekami līdzsvarots un vairāk līdzinās "pilnam", nevis "lineāram", ievietošanas, meklēšanas un visas dzēšanas darbības var tikt realizētas O(log N) laiks.