Kas ir binārs meklēšanas koks?
Binārais meklēšanas koks ir uzlabots algoritms, ko izmanto, lai analizētu mezglu, tā kreiso un labo zaru, kas tiek modelēti koka struktūrā un atgriež vērtību. BST ir izstrādāts par pamata binārā meklēšanas algoritma arhitektūru; tādējādi tas ļauj ātrāk meklēt, ievietot un noņemt mezglus. Tas padara programmu patiešām ātru un precīzu.
Šajā apmācības datu struktūrā jūs uzzināsiet:
- Kas ir binārs meklēšanas koks?
- Binārā meklēšanas koka atribūti
- Kāpēc mums vajadzīgs binārs meklēšanas koks?
- Bināro koku veidi
- Kā darbojas binārais meklēšanas koks?
- Svarīgi noteikumi
Binārā meklēšanas koka atribūti
BST sastāv no vairākiem mezgliem un sastāv no šādiem atribūtiem:
- Koka mezgli ir attēloti vecāku un bērnu attiecībās
- Katrā vecāka mezglā var būt nulle pakārtoto mezglu vai maksimums divi apakšmezgli vai apakškoki kreisajā un labajā pusē.
- Katram apakškokam, ko dēvē arī par bināro meklēšanas koku, pa labi un pa kreisi ir apakšzari.
- Visi mezgli ir saistīti ar atslēgu un vērtību pāriem.
- Kreisajā apakškokā esošo mezglu atslēgas ir mazākas nekā viņu vecāku mezgla atslēgas
- Līdzīgi kreisā apakškoka mezglu atslēgām ir mazākas vērtības nekā vecāku mezgla atslēgām.
- Ir galvenais mezgls vai vecāku līmenis 11. Zem tā ir kreisie un labie mezgli / zari ar savām galvenajām vērtībām
- Labajā apakškokā atslēgas vērtības ir lielākas nekā vecāka mezglā
- Kreisajā apakškokā ir vērtības nekā vecāka mezglā
Kāpēc mums vajadzīgs binārs meklēšanas koks?
- Divi galvenie faktori, kas padara bināro meklēšanas koku par optimālu risinājumu jebkurām reālās pasaules problēmām, ir Ātrums un precizitāte.
- Sakarā ar to, ka binārā meklēšana ir filiālei līdzīgā formātā ar vecāku un bērnu attiecībām, algoritms zina, kurā koka vietā elementi ir jāmeklē. Tas samazina galveno vērtību salīdzinājumu skaitu, kas programmai jāveic, lai atrastu vēlamo elementu.
- Turklāt, ja meklējamais elements ir lielāks vai mazāks par vecāku mezglu, mezgls zina, kuru koka pusi meklēt. Iemesls ir tāds, ka kreisais apakškoks vienmēr ir mazāks par vecāku mezglu, un labajā apakškokā vērtības vienmēr ir vienādas vai lielākas par vecāku mezglu.
- BST parasti izmanto, lai ieviestu sarežģītus meklējumus, stabilu spēļu loģiku, automātiskās pabeigšanas darbības un grafiku.
- Algoritms efektīvi atbalsta tādas darbības kā meklēšana, ievietošana un dzēšana.
Bināro koku veidi
Trīs veidu binārie koki ir:
- Pilnīgs binārs koks: visi līmeņi kokos ir pilni ar pēdējā līmeņa iespējamiem izņēmumiem. Līdzīgi visi mezgli ir pilni, virzot galēji kreiso pusi.
- Pilns binārs koks: visiem mezgliem ir 2 bērnu mezgli, izņemot lapu.
- Līdzsvarots vai ideāls binārs koks: kokā visiem mezgliem ir divi bērni. Turklāt katram apakšmezglam ir vienāds līmenis.
Kā darbojas binārais meklēšanas koks?
Kokam vienmēr ir saknes mezgls un citi bērnu mezgli, neatkarīgi no tā, vai tie atrodas pa kreisi vai pa labi. Algoritms veic visas darbības, attiecīgi salīdzinot vērtības ar sakni un tās nākamajiem pakārtotajiem mezgliem kreisajā vai labajā apakškokā.
Atkarībā no elementa, kas jāievieto, jāmeklē vai jāizdzēš, pēc salīdzināšanas algoritms var viegli nomest saknes mezgla kreiso vai labo apakškoku.
BST galvenokārt piedāvā trīs veidu darbības jūsu lietošanai:
- Meklēt: meklē elementu no binārā koka
- Ievietot: bināram kokam pievieno elementu
- Dzēst: dzēš elementu no binārā koka
Katrai operācijai ir sava izpildes / analīzes struktūra un metode, taču vissarežģītākā ir operācija Dzēst.
Meklēšanas darbība
Vienmēr sāciet analizēt koku saknes mezglā un pēc tam virzieties tālāk uz saknes mezgla labo vai kreiso apakškoku atkarībā no tā, vai atrodamais elements ir mazāks vai lielāks par sakni.
- Meklējamais elements ir 10
- Salīdziniet elementu ar saknes mezglu 12, 10 <12, tādējādi jūs pārvietojaties uz kreiso apakškoku. Nav nepieciešams analizēt labo apakškoku
- Tagad salīdziniet 10 ar mezglu 7, 10> 7, tāpēc pārejiet uz labo apakškoku
- Pēc tam salīdziniet 10 ar nākamo mezglu, kas ir 9, 10> 9, meklējiet labo apakškoku bērnu
- 10 sakrīt ar vērtību mezglā, 10 = 10, atgrieziet vērtību lietotājam.
Ievietot darbību
Šī ir ļoti tieša darbība. Pirmkārt, tiek ievietots saknes mezgls, pēc tam nākamo vērtību salīdzina ar saknes mezglu. Ja vērtība ir lielāka par sakni, tā tiek pievienota labajam apakškokam un, ja tā ir mazāka par sakni, tā tiek pievienota kreisajam apakškokam.
- Ir saraksts ar 6 elementiem, kas jāievieto BST secībā no kreisās uz labo
- Ievietojiet 12 kā saknes mezglu un salīdziniet nākamās 7 un 9 vērtības, lai attiecīgi ievietotu labajā un kreisajā apakškokā
- Salīdziniet atlikušās vērtības 19, 5 un 10 ar saknes mezglu 12 un attiecīgi ievietojiet tās. 19> 12 novietojiet to kā pareizo bērnu no 12, 5 <12 un 5 <7, tātad - kā kreiso 7 bērnu bērnu.
- Tagad salīdziniet 10, 10 ir <12 un 10 ir> 7 un 10 ir> 9, novietojiet 10 kā 9. labo apakškoku.
Dzēst darbības
Dzēšana ir vismodernākā un sarežģītākā starp visām citām darbībām. BST tiek izdzēsti vairāki gadījumi.
- 1. gadījums - mezgls ar nulli bērnu: šī ir visvieglākā situācija, jums vienkārši jāizdzēš mezgls, kurā labajā vai kreisajā pusē vairs nav bērnu.
- 2. gadījums - mezgls ar vienu bērnu: pēc mezgla dzēšanas vienkārši savienojiet tā pakārtoto mezglu ar izdzēstās vērtības vecāku mezglu.
- 3. gadījums Mezgls ar diviem bērniem: šī ir visgrūtākā situācija, un tā darbojas saskaņā ar šādiem diviem noteikumiem
- 3.a - Pasūtījuma priekšgājējā: jums ir jāizdzēš mezgls ar diviem bērniem un jāaizstāj ar lielāko vērtību izdzēstā mezgla kreisajā apakškokā
- 3.b - Pasūtījuma pēctecī: jums jāizdzēš mezgls ar diviem bērniem un jāaizstāj ar lielāko vērtību izdzēstā mezgla labajā apakškokā
- Šis ir pirmais dzēšanas gadījums, kad izdzēšat mezglu, kurā nav bērnu. Kā redzat diagrammā, 19, 10 un 5 nav bērnu. Bet mēs izdzēsīsim 19.
- Dzēsiet vērtību 19 un noņemiet saiti no mezgla.
- Apskatiet jauno BST struktūru bez 19
- Šis ir otrais dzēšanas gadījums, kad izdzēšat mezglu, kurā ir 1 bērns, kā redzat diagrammā, ka 9 ir viens bērns.
- Izdzēsiet mezglu 9 un nomainiet to ar bērnu 10 un pievienojiet saiti no 7 līdz 10
- Apskatiet jauno BST struktūru bez 9
- Šeit jūs izdzēsīsit mezglu 12, kurā ir divi bērni
- Mezgls tiks izdzēsts, pamatojoties uz kārtību priekšgājēja kārtulu, kas nozīmē, ka lielākais elements kreisajā 12 apakškokā 12 to aizstās.
- Izdzēsiet mezglu 12 un aizstājiet to ar 10, jo tā ir lielākā vērtība kreisajā apakškokā
- Pēc 12 dzēšanas skatiet jauno BST struktūru
- 1 Izdzēsiet mezglu 12, kurā ir divi bērni
- 2 Mezgls tiks izdzēsts, pamatojoties uz kārtulu secībā pēctecis, kas nozīmē, ka lielākais elements labajā 12 apakšgrupā to aizstās
- 3 Izdzēsiet mezglu 12 un nomainiet to ar 19, jo tā ir lielākā vērtība labajā apakškokā
- 4 Pēc 12 dzēšanas skatiet jauno BST struktūru
Svarīgi noteikumi
- Ievietot - ievieto kokā elementu / izveido koku.
- Meklēt - meklē elementu kokā.
- Priekšpasūtīšana - iepriekšēja pasūtījuma šķērso koku.
- Inorder Traversal - kārtīgi šķērso koku.
- Postorder Traversal - pēc pasūtījuma šķērso koku.
Kopsavilkums
- BST ir uzlabota līmeņa algoritms, kas veic dažādas darbības, pamatojoties uz mezglu vērtību salīdzināšanu ar saknes mezglu.
- Jebkurš no vecāku un bērnu hierarhijas punktiem apzīmē mezglu. Vismaz viens vecāku vai sakņu mezgls paliek pastāvīgi.
- Ir kreisā un labā apakškoks. Kreisajā apakškokā ir vērtības, kas ir mazākas par saknes mezglu. Tomēr labajā apakškokā ir vērtība, kas ir lielāka par saknes mezglu.
- Katrā mezglā var būt nulle, viens vai divi bērni.
- Binārais meklēšanas koks atvieglo primārās darbības, piemēram, meklēšanu, ievietošanu un dzēšanu.
- Dzēšana ir vissarežģītākā gadījumā ir vairāki gadījumi, piemēram, mezgls bez bērna, mezgls ar vienu bērnu un mezgls ar diviem bērniem.
- Algoritms tiek izmantots reālos risinājumos, piemēram, spēlēs, automātiskās pabeigšanas datos un grafikā.