Kas yra dvejetainis paieškos medis?
Dvejetainis paieškos medis yra pažangus algoritmas, naudojamas analizuoti mazgą, jo kairę ir dešinę šakas, kurios yra modeliuojamos medžio struktūroje ir grąžina vertę. BST yra sukurtas dėl pagrindinio dvejetainio paieškos algoritmo architektūros; taigi tai leidžia greičiau ieškoti, įterpti ir pašalinti mazgus. Tai daro programą tikrai greitą ir tikslią.
Šioje duomenų struktūros pamokoje sužinosite:
- Kas yra dvejetainis paieškos medis?
- Dvejetainio paieškos medžio atributai
- Kodėl mums reikia dvejetainio paieškos medžio?
- Dvejetainių medžių rūšys
- Kaip veikia dvejetainis paieškos medis?
- Svarbios sąlygos
Dvejetainio paieškos medžio atributai
BST yra sudarytas iš kelių mazgų ir susideda iš šių atributų:
- Medžio mazgai yra atstovaujami tėvų ir vaikų santykiuose
- Kiekviename pirminiame mazge gali būti nulis antrinių mazgų arba daugiausia du potemiai arba potemiai kairėje ir dešinėje pusėse.
- Kiekvienas medis, dar vadinamas dvejetainiu paieškos medžiu, turi poskyrius dešinėje ir kairėje.
- Visi mazgai susieti su raktų ir verčių poromis.
- Kairiajame potemyje esančių mazgų raktai yra mažesni nei jų pagrindinio mazgo raktai
- Panašiai kairiųjų porūšių mazgų raktų reikšmės yra mažesnės nei jų pagrindinio mazgo raktų.
- Yra pagrindinis mazgas arba tėvų 11 lygis. Po juo yra kairieji ir dešinieji mazgai / šakos su savo pagrindinėmis reikšmėmis
- Dešiniojo submedžio raktinės vertės yra didesnės nei pirminio mazgo
- Kairiajame medyje yra reikšmės nei pagrindiniame mazge
Kodėl mums reikia dvejetainio paieškos medžio?
- Du pagrindiniai veiksniai, dėl kurių dvejetainis paieškos medis tampa optimaliu bet kokių realių problemų sprendimu, yra greitis ir tikslumas.
- Atsižvelgiant į tai, kad dvejetainė paieška yra filialo formos su tėvų ir vaikų santykiais, algoritmas žino, kurioje medžio vietoje reikia ieškoti elementų. Tai sumažina pagrindinių verčių, kurias programa turi atlikti norimam elementui rasti, skaičių.
- Be to, jei ieškomas elementas yra didesnis ar mažesnis už pirminį mazgą, mazgas žino, kurios medžio pusės ieškoti. Priežastis ta, kad kairiojo medžio medis visada yra mažesnis nei pirminio mazgo, o dešiniojo medžio reikšmės visada yra lygios arba didesnės už pirminį mazgą.
- BST dažniausiai naudojamas sudėtingoms paieškoms, patikimai žaidimo logikai, automatinio užbaigimo veiklai ir grafikai įgyvendinti.
- Algoritmas efektyviai palaiko tokias operacijas kaip paieška, įterpimas ir ištrynimas.
Dvejetainių medžių rūšys
Trijų rūšių dvejetainiai medžiai yra:
- Pilnas dvejetainis medis: visi medžių lygiai yra pilni paskutinio lygio galimų išimčių. Panašiai visi mazgai yra pilni, nukreipiantys į kairę.
- Pilnas dvejetainis medis: Visuose mazguose yra 2 antriniai mazgai, išskyrus lapą.
- Subalansuotas arba tobulas dvejetainis medis: medyje visi mazgai turi du vaikus. Be to, kiekvieno subnode yra tas pats lygis.
Kaip veikia dvejetainis paieškos medis?
Medis visada turi šaknies mazgą ir kitus vaiko mazgus, tiek kairėje, tiek dešinėje. Algoritmas atlieka visas operacijas, atitinkamai lygindamas reikšmes su šaknimi ir tolesniais jos vaikais, esančiais kairiajame arba dešiniajame medyje.
Priklauso nuo elemento, kurį reikia įterpti, ieškoti ar ištrinti. Po palyginimo algoritmas gali lengvai numesti kairįjį arba dešinįjį šaknies mazgo porą.
„BST“ pirmiausia siūlo šias tris operacijų rūšis:
- Paieška: ieško elemento iš dvejetainio medžio
- Įterpti: prideda elementą prie dvejetainio medžio
- Ištrinti: ištrinti elementą iš dvejetainio medžio
Kiekviena operacija turi savo struktūrą ir atlikimo / analizės metodą, tačiau pati sudėtingiausia yra „Delete“ operacija.
Paieškos operacija
Visada pradėkite analizuoti medį šaknies mazge ir tada eikite toliau į šaknies mazgo dešinįjį arba kairįjį potemį, priklausomai nuo to, ar elementas, kuris bus, yra mažesnis arba didesnis už šaknį.
- Ieškomas elementas yra 10
- Palyginkite elementą su šaknies mazgu 12, 10 <12, taigi jūs einate į kairįjį potemį. Nereikia analizuoti dešiniojo potemio
- Dabar palyginkite 10 su 7 mazgu, 10> 7, taigi pereikite prie dešinio potemio
- Tada palyginkite 10 su kitu mazgu, kuris yra 9, 10> 9, ieškokite dešiniojo porūšio vaiko
- 10 sutampa su mazgo verte, 10 = 10, grąžina vertę vartotojui.
Įterpti operaciją
Tai labai tiesi operacija. Pirmiausia įterpiamas šaknies mazgas, tada kita reikšmė palyginama su šaknies mazgu. Jei vertė yra didesnė už šaknį, ji pridedama prie dešiniojo potemio, o jei ji yra mažesnė už šaknį, ji pridedama prie kairiojo potemio.
- Yra 6 elementų, kuriuos reikia įterpti į BST, sąrašas iš kairės į dešinę
- Įterpkite 12 kaip šakninį mazgą ir palyginkite kitas 7 ir 9 reikšmes, kad įterptumėte juos atitinkamai į dešinį ir kairį potemį
- Palyginkite likusias 19, 5 ir 10 reikšmes su šaknies mazgu 12 ir atitinkamai padėkite jas. 19> 12 padėkite jį kaip dešinįjį 12 metų vaiką, 5 <12 ir 5 <7, taigi padėkite jį kaip kairįjį 7 vaikų vaiką.
- Dabar palyginkite 10, 10 yra <12 ir 10 yra> 7 ir 10 yra> 9, padėkite 10 kaip dešinį 9 pogrindį.
Ištrinti operacijas
Ištrinti yra pažangiausia ir sudėtingiausia tarp visų kitų operacijų. Yra keli atvejai, kuriuos BST nagrinėja ištrinti.
- 1 atvejis - mazgas, kuriame nėra vaikų: tai lengviausia situacija, jums tiesiog reikia ištrinti mazgą, kuriame nėra daugiau vaikų dešinėje ar kairėje.
- 2 atvejis - mazgas su vienu vaiku: kai ištrinsite mazgą, tiesiog prijunkite jo antrinį mazgą su ištrintos vertės pagrindiniu mazgu.
- 3 atvejis Mazgas su dviem vaikais: tai sunkiausia situacija ir ji veikia pagal šias dvi taisykles
- 3a - Užsakymo pirmtake: turite ištrinti mazgą su dviem vaikais ir pakeisti jį didžiausia verte ištrinto mazgo kairiajame potemyje.
- 3b - užsakymo perėmėju: turite ištrinti mazgą su dviem vaikais ir pakeisti jį didžiausia verte ištrinto mazgo dešiniame poskyryje
- Tai yra pirmasis ištrinimo atvejis, kai ištrinate mazgą, kuriame nėra vaikų. Kaip matote diagramoje, 19, 10 ir 5 neturi vaikų. Bet mes ištrinsime 19.
- Ištrinkite vertę 19 ir pašalinkite nuorodą iš mazgo.
- Peržiūrėkite naują BST struktūrą be 19
- Tai yra antrasis ištrinimo atvejis, kai ištrinate mazgą, kuriame yra 1 vaikas, kaip matote diagramoje, kad 9 turi vieną vaiką.
- Ištrinkite mazgą 9 ir pakeiskite jį antriniu 10 ir pridėkite nuorodą nuo 7 iki 10
- Peržiūrėkite naują BST struktūrą be 9
- Čia jūs ištrinsite mazgą 12, kuriame yra du vaikai
- Mazgas bus ištrintas remiantis tvarka pagal pirmtaką, o tai reiškia, kad jį pakeis didžiausias kairiajame 12 medyje esantis elementas.
- Ištrinkite mazgą 12 ir pakeiskite jį 10, nes tai yra didžiausia vertė kairiajame potemyje
- Peržiūrėkite naują BST struktūrą ištrynę 12
- 1 Ištrinkite mazgą 12, kuriame yra du vaikai
- 2 Mazgas bus ištrintas remiantis taisykle „Tvarkos perėmėjas“, o tai reiškia, kad didžiausias dešiniojo 12 medžio 12 elementas jį pakeis
- 3 Ištrinkite mazgą 12 ir pakeiskite jį 19, nes tai didžiausia vertė dešiniajame medyje
- 4 Ištrynę 12 peržiūrėkite naują BST struktūrą
Svarbios sąlygos
- Įterpti - įterpia elementą į medį / sukuria medį.
- Paieška - ieško elemento medyje.
- Išankstinis perėjimas - iš anksto užsisakydamas važiuoja medį.
- „Inorder Traversal“ - tvarkingai kerta medį.
- Postorder Traversal - važiuoja medžiu pagal užsakymą.
Santrauka
- BST yra pažangaus lygio algoritmas, atliekantis įvairias operacijas, pagrįstas mazgo reikšmių palyginimu su šakniniu mazgu.
- Bet kuris iš tėvų ir vaikų hierarchijos taškų reiškia mazgą. Bent vienas pagrindinis arba šakninis mazgas lieka nuolat.
- Yra kairysis ir dešinysis potisiai. Kairiajame potemyje yra reikšmės, kurios yra mažesnės už šakninį mazgą. Tačiau dešiniajame potemyje yra reikšmė, didesnė už šakninį mazgą.
- Kiekvienas mazgas gali turėti nulį, vieną arba du vaikus.
- Dvejetainis paieškos medis palengvina pagrindines operacijas, tokias kaip paieška, įterpimas ir ištrynimas.
- Ištrynimas yra sudėtingiausias atvejis, pvz., Mazgas be vaiko, mazgas su vienu vaiku ir su dviem vaikais.
- Algoritmas naudojamas realaus pasaulio sprendimuose, tokiuose kaip žaidimai, automatinio užbaigimo duomenys ir grafika.