Čo je to binárny vyhľadávací strom?
Binárny vyhľadávací strom je pokročilý algoritmus používaný na analýzu uzla, jeho ľavej a pravej vetvy, ktoré sú modelované v stromovej štruktúre a vracajú hodnotu. BST je navrhnutý na architektúre základného algoritmu binárneho vyhľadávania; teda umožňuje rýchlejšie vyhľadanie, vloženie a odstránenie uzlov. Vďaka tomu je program skutočne rýchly a presný.
V tomto výučbe dátovej štruktúry sa dozviete:
- Čo je to binárny vyhľadávací strom?
- Atribúty binárneho vyhľadávacieho stromu
- Prečo potrebujeme binárny vyhľadávací strom?
- Typy binárnych stromov
- Ako funguje binárny vyhľadávací strom?
- Dôležité podmienky
Atribúty binárneho vyhľadávacieho stromu
BST sa skladá z viacerých uzlov a skladá sa z nasledujúcich atribútov:
- Uzly stromu sú znázornené vo vzťahu rodič - dieťa
- Každý nadradený uzol môže mať nulové podradené uzly alebo maximálne dva poduzly alebo podstromy na ľavej a pravej strane.
- Každý podstrom, tiež známy ako binárny vyhľadávací strom, má čiastkové vetvy vpravo a vľavo od seba.
- Všetky uzly sú prepojené s pármi kľúč - hodnota.
- Kľúče uzlov nachádzajúcich sa v ľavom podstrome sú menšie ako kľúče ich nadradeného uzla
- Podobne majú kľúče uzlov ľavého podstromu menšie hodnoty ako kľúče ich nadradených uzlov.
- Nachádza sa tu hlavný uzol alebo nadradená úroveň 11. Pod ním sa nachádzajú ľavý a pravý uzol / vetva s vlastnými kľúčovými hodnotami
- Pravý podstrom má kľúčové hodnoty väčšie ako nadradený uzol
- Ľavý podstrom má hodnoty ako nadradený uzol
Prečo potrebujeme binárny vyhľadávací strom?
- Dva hlavné faktory, ktoré robia z binárneho vyhľadávacieho stromu optimálne riešenie akýchkoľvek problémov v reálnom svete, sú rýchlosť a presnosť.
- Vzhľadom na to, že binárne vyhľadávanie je vo formáte podobnom vetve so vzťahmi rodič - dieťa, algoritmus vie, v ktorom umiestnení stromu je potrebné prvky prehľadávať. Tým sa zníži počet porovnaní kľúč - hodnota, ktoré musí program vykonať, aby našiel požadovaný prvok.
- Ďalej v prípade, že má byť prvok prehľadávaný väčší alebo menší ako nadradený uzol, uzol vie, na ktorej strane stromu sa má vyhľadávať. Dôvod je ten, že ľavý podstrom je vždy menší ako nadradený uzol a pravý podstrom má hodnoty vždy rovnaké alebo väčšie ako nadradený uzol.
- BST sa bežne používa na implementáciu komplexných vyhľadávaní, robustnej logiky hier, aktivít automatického dokončovania a grafiky.
- Algoritmus efektívne podporuje operácie ako vyhľadávanie, vkladanie a mazanie.
Typy binárnych stromov
Tri druhy binárnych stromov sú:
- Kompletný binárny strom: Všetky úrovne na stromoch sú plné možných výnimiek z poslednej úrovne. Podobne sú všetky uzly plné a smerujú úplne doľava.
- Plný binárny strom: Všetky uzly majú okrem koreňového listu 2 podradené uzly.
- Vyvážený alebo dokonalý binárny strom: Na strome majú všetky uzly dve deti. Okrem toho existuje rovnaká úroveň každého poduzlu.
Ako funguje binárny vyhľadávací strom?
Strom má vždy koreňový uzol a ďalšie podradené uzly, či už vľavo alebo vpravo. Algoritmus vykonáva všetky operácie porovnaním hodnôt s koreňom a jeho ďalšími podradenými uzlami v ľavom alebo pravom pod strome.
Závisí od prvku, ktorý sa má vložiť, vyhľadať alebo vymazať, po porovnaní môže algoritmus ľahko odhodiť ľavý alebo pravý podstrom koreňového uzla.
Program BST ponúka pre vaše použitie predovšetkým tieto tri typy operácií:
- Hľadať: vyhľadá prvok z binárneho stromu
- Vložiť: pridá prvok do binárneho stromu
- Odstrániť: odstránenie prvku z binárneho stromu
Každá operácia má svoju vlastnú štruktúru a spôsob vykonania / analýzy, ale najkomplexnejšia zo všetkých je operácia Odstrániť.
Vyhľadávacia operácia
Vždy inicializujte analytický strom v koreňovom uzle a potom sa posuňte ďalej buď do pravého, alebo ľavého podstromu koreňového uzla v závislosti od toho, či je element, ktorý sa má umiestniť, menší alebo väčší ako koreň.
- Element, ktorý sa má prehľadať, je 10
- Porovnajte prvok s koreňovým uzlom 12, 10 <12, preto sa presuňte do ľavého podstromu. Nie je potrebné analyzovať pravý podstrom
- Teraz porovnajte 10 s uzlom 7, 10> 7, takže prejdite na pravý podstrom
- Potom porovnajte 10 s ďalším uzlom, ktorý je 9, 10> 9, pozrite sa do pravého podradeného stromu
- 10 zhoduje sa s hodnotou v uzle, 10 = 10, vráti hodnotu používateľovi.
Vložiť operáciu
Toto je veľmi jednoduchá operácia. Najskôr sa vloží koreňový uzol, potom sa porovnáva ďalšia hodnota s koreňovým uzlom. Ak je hodnota väčšia ako root, pridá sa do pravého podstromu a ak je menšia ako root, pridá sa do ľavého podstromu.
- Existuje zoznam 6 prvkov, ktoré je potrebné vložiť do kódu BST zľava doprava
- Vložte 12 ako koreňový uzol a porovnajte ďalšie hodnoty 7 a 9 pre príslušné vloženie do pravého a ľavého podstromu
- Porovnajte zostávajúce hodnoty 19, 5 a 10 s koreňovým uzlom 12 a podľa toho ich umiestnite. 19> 12 ho umiestni ako pravé dieťa 12, 5 <12 & 5 <7, a preto ho umiestni ako ľavé dieťa 7 rokov.
- Teraz porovnajte 10, 10 je <12 a 10 je> 7 a 10 je> 9, miesto 10 ako pravý podstrom 9.
Vymazať operácie
Odstrániť je najpokročilejší a najkomplexnejší spomedzi všetkých ostatných operácií. V BST je riešených niekoľko prípadov na odstránenie.
- Prípad 1 - Uzol s nulovými deťmi: toto je najjednoduchšia situácia, stačí vymazať uzol, ktorý nemá ďalšie deti vpravo alebo vľavo.
- Prípad 2 - Uzol s jedným potomkom: po odstránení uzla jednoducho pripojte jeho podradený uzol s nadradeným uzlom odstránenej hodnoty.
- Prípad 3 Uzol s dvoma deťmi: toto je najťažšia situácia a funguje podľa nasledujúcich dvoch pravidiel
- 3a - V Predchodcovi objednávky: musíte odstrániť uzol s dvoma potomkami a nahradiť ho najväčšou hodnotou v ľavom podstrome odstráneného uzla.
- 3b - V nasledujúcom poradí: musíte odstrániť uzol s dvoma potomkami a nahradiť ho najväčšou hodnotou v pravom podstrome odstráneného uzla.
- Toto je prvý prípad odstránenia, v ktorom odstránite uzol, ktorý nemá potomkov. Ako je zrejmé z diagramu, 19, 10 a 5 nemajú žiadne deti. Ale 19 vypustíme.
- Odstráňte hodnotu 19 a odstráňte odkaz z uzla.
- Prezrite si novú štruktúru BST bez 19
- Toto je druhý prípad odstránenia, pri ktorom odstránite uzol, ktorý má 1 dieťa, ako vidíte na diagrame, keď 9 má jedno dieťa.
- Vymažte uzol 9 a nahraďte ho jeho dieťaťom 10 a pridajte odkaz od 7 do 10
- Prezrite si novú štruktúru BST bez verzie 9
- Tu budete mazať uzol 12, ktorý má dve deti
- Vymazanie uzla sa uskutoční na základe pravidla predchodcu v poradí, čo znamená, že ho nahradí najväčší prvok v ľavom podstrome z 12.
- Vymažte uzol 12 a nahraďte ho 10, pretože to je najväčšia hodnota v ľavom podstrome
- Po odstránení 12 si pozrite novú štruktúru BST
- 1 Vymažte uzol 12, ktorý má dve deti
- 2 Vymazanie uzla sa uskutoční na základe pravidla In Order Successor, čo znamená, že ho nahradí najväčší prvok v pravom podstrome z 12
- 3 Vymažte uzol 12 a nahraďte ho 19, pretože to je najväčšia hodnota v pravom podstrome
- 4 Po odstránení 12 zobrazte novú štruktúru BST
Dôležité podmienky
- Vložiť - Vloží prvok do stromu / vytvorí strom.
- Hľadať - Vyhľadá prvok na strome.
- Predobjednať Traversal - Traverzuje strom predobjednávkovým spôsobom.
- Inorder Traversal - Traverzuje strom v poradí.
- Postorder Traversal - Traverzuje strom v režime poobjednávky.
Zhrnutie
- BST je pokročilý algoritmus úrovne, ktorý vykonáva rôzne operácie na základe porovnania hodnôt uzlov s koreňovým uzlom.
- Ktorýkoľvek z bodov v hierarchii rodič - dieťa predstavuje uzol. Aspoň jeden nadradený alebo koreňový uzol zostáva stále prítomný.
- Existuje ľavý podstrom a pravý podstrom. Ľavý podstrom obsahuje hodnoty, ktoré sú menšie ako koreňový uzol. Pravý podstrom však obsahuje hodnotu, ktorá je väčšia ako koreňový uzol.
- Každý uzol môže mať buď nulu, jedno alebo dve deti.
- Binárny vyhľadávací strom umožňuje primárne operácie, ako je vyhľadávanie, vkladanie a mazanie.
- Vymazanie, ktoré je najkomplexnejšie, má viac prípadov, napríklad uzol bez potomka, uzol s jedným dieťaťom a uzol s dvoma deťmi.
- Algoritmus sa používa v riešeniach z reálneho sveta, ako sú hry, údaje z automatického dopĺňania a grafika.