[Powered by Google Translate] [Binárne vyhľadávanie] [Patrick Schmid - Harvard University] [To je CS50. - CS50.TV] 

Keby som vám dal zoznam mien postáv Disney v abecednom poradí a spýtal sa ťa nájsť Mickey Mouse, ako by ste ísť asi robí? Jeden zrejmý spôsob, ako by bolo skenovať zoznam od začiatku a skontrolujte, každé meno aby zistil, či je to Mickey. Ale ako budete čítať Aladdin, Alice, Ariel, a tak ďalej, budete rýchlo uvedomiť, že začína v prednej časti zoznamu nebol dobrý nápad. Dobre, možno by ste mali začať pracovať pospiatky od konca zoznamu. Teraz budete čítať Tarzana, steh, Snehulienka, a tak ďalej. Napriek tomu, to nevyzerá ako najlepší spôsob, ako ísť na to. 

No, ďalší spôsob, ako by ste mohli ísť asi robí, je pokúsiť zúžiť zoznam mien, ktoré budete musieť pozrieť. Vzhľadom k tomu, viete, že sú v abecednom poradí, vy ste mohli len pozerať na mená v polovici zoznamu a skontrolujte, či Mickey Mouse je pred alebo po tomto názve. Pri pohľade na posledné meno v druhom stĺpci by ste si uvedomiť, že M pre Mickey prichádza potom, čo J pre Jasmine, takže by si jednoducho ignorovať prvú polovicu zoznamu. Potom ste asi pozriete na hornej časti posledného stĺpca a uvidíte, že to začne Rapunzel. Mickey je pred Rapunzel, vyzerá to, že môže ignorovať posledný stĺpec rovnako. Pokračovanie vyhľadávacie stratégie, budete rýchlo vidieť, že Mickey je v prvej polovici zostávajúce zoznamu mien a konečne nájsť Mickey skrýva medzi Merlin a Minnie. 

Čo ste práve urobil, bolo v podstate binárne vyhľadávanie. Ako toto meno napovedá, vykoná svoju Hľadám stratégiu v binárnom veci. Čo to znamená? No, vzhľadom zoznam zoradené položiek, binárny vyhľadávací algoritmus je binárne rozhodnutie - doľava alebo doprava, väčšie alebo menšie ako, abecedne pred alebo po - v každom bode. Teraz, keď máme názov, ktorý ide spolu s týmto vyhľadávací algoritmus, Poďme sa pozrieť na ďalší príklad, ale tentoraz so zoznamom triedených čísel. Povedzme, že hľadáme číslo 144 v tomto zozname zoradených čísel. Rovnako ako predtým, nájdeme číslo, ktoré je v strede - ktorý je v tomto prípade je 13 - a zistiť, či 144 je väčší alebo menší ako 13 rokov. Vzhľadom k tomu, že je to jasne väčší ako 13, môžeme ignorovať všetko, čo je 13 alebo menej a len sa sústrediť na zostávajúce polovice. Vzhľadom k tomu, teraz máme dokonca počet položiek vľavo, sme jednoducho vybrať číslo, ktoré je v blízkosti stredu. V tomto prípade sme sa rozhodli 55. Mohli sme rovnako ľahko zvoliť 89. Dobre. Opäť, 144 je väčší ako 55, takže choďte doprava. Našťastie pre nás, ďalšie stredné číslo je 144, ten, ktorého hľadáme. Takže s cieľom nájsť 144 pomocou binárneho vyhľadávania, sme schopní nájsť len v 3 krokoch. Ak by sme použili lineárne hľadať tu, zabralo by mi to nám 12 krokov. Ako v skutočnosti, pretože táto metóda hľadania polovičná počet položiek má sa pozrieť na na každom kroku, bude to nájsť položku je hľadali asi v protokole o počte položiek v zozname. Teraz, keď sme videli 2 príklady, poďme sa pozrieť na niektoré pseudokód pre rekurzívne funkcie, ktorá implementuje binárne vyhľadávanie. Od vrcholu, vidíme, že musíme nájsť funkciu, ktorá vezme 4 argumenty: kľúč, pole, min, max a Kľúčom je číslo, ktoré hľadáme, tak 144 v predchádzajúcom príklade. Pole je zoznam čísel, ktoré hľadáme. Min a max sú indexy minimálne a maximálne pozície že sa v súčasnej dobe hľadá na. Takže, keď sa začne, bude min nulové a maximálnu bude maximálny index poľa. Ako sme zúžiť hľadanie dole, budeme aktualizovať min a max byť práve rozsah, ktorý stále hľadáme palcov 

Poďme preskočiť na zaujímavé časti prvej. Prvá vec, ktorú musíme urobiť, je nájsť stred, index, ktorý je na polceste medzi min a max na pole, ktoré sme stále zvažuje. Potom sa pozrieme na hodnote poľa v tomto mieste strede dráhy a zistiť, či číslo, ktoré hľadáme, je menšia ako daný kľúč. Ak je číslo v tejto pozícii je menej, potom to znamená, že kľúč je väčšia než všetkých čísel naľavo tejto polohe. Takže môžeme volať binárne vyhľadávacie funkcie znovu, ale tentoraz aktualizáciu min a max parametre čítať iba polovicu , Ktorý je väčší alebo rovná hodnote sme sa pozrel na. Na druhej strane, ak je kľúč je menší, než je číslo v aktuálnom stredu poľa, chceme ísť doľava a ignorovať všetky čísla, ktoré sú väčšie. Opäť, nazývame binárne vyhľadávanie, ale tentoraz s rozsahom min a max Aktualizované zahrnúť len spodná polovica. Ak je hodnota v aktuálnom stredu v poli nie je ani väčší ako ani menšie ako kľúč, potom to musí byť rovný kľúčmi. Tak, môžeme jednoducho vrátiť aktuálne midpoint index, a sme hotoví. A konečne, táto kontrola je tu pre prípad, že sa počet nie je vlastne v poli čísel sme hľadajú. Ak je maximálny index rozsahu, že sa pozeráme na je stále nižšia než minimum, to znamená, že sme zašli príliš ďaleko. Vzhľadom k tomu, počet nie je vo vstupnom poli, sme vráti -1 o tom, že sa nenašlo nič. 

Možno ste si všimli, že pre tento algoritmus pracovať, zoznam čísel musí byť zoradené. Inými slovami, môžeme nájsť iba 144 pomocou binárneho vyhľadávania ak sú všetky čísla sú zoradené od najnižšej po najvyššiu. Ak by tomu tak nebolo, neboli by sme schopní vylúčiť polovicu čísel na každom kroku. Takže máme 2 možnosti. Buď môžeme vziať netriedeného zoznamu a zoradiť ich pred použitím binárneho vyhľadávania, alebo môžeme uistiť, že zoznam čísel je radený ako sme pridať čísla k nemu. Tak, namiesto toho triedenie, práve keď budeme musieť hľadať, prečo nie držať zoznam zoradený za všetkých okolností? 

Jeden spôsob, ako udržať zoznam čísel sú zoradené súčasne umožňuje kto pridať alebo presunúť čísla z tohto zoznamu je pomocou tzv binárny vyhľadávací strom. Binárne vyhľadávacie strom je dátová štruktúra, ktorá má 3 vlastnosti. Po prvé, ľavého podstromu každého uzla obsahuje iba hodnoty, ktoré sú menšie ako alebo sa rovná uzla hodnoty. Po druhé, právo podstrom uzla obsahuje iba hodnoty, ktoré sú väčšie ako alebo rovná uzla hodnoty. A konečne, ako ľavej a pravej podstromy všetkých uzlov sú tiež binárne vyhľadávacie stromy. Poďme sa pozrieť na príklad s rovnakými číslami sme používali predtým. Pre tých z vás, ktorí ešte nikdy nevidel počítačovej vedy strom pred, dovoľte mi začať tým, že povie, že počítačová veda strom rastie smerom dole. Áno, na rozdiel od stromov, na ktorú ste zvyknutí, koreň stromu počítačovej vedy je na vrchole, a listy sú na dne. Každý malý box sa nazýva uzol, a uzly sú navzájom spojené hranami. Takže Koreň tohto stromu je hodnota uzla s hodnotou 13, ktorá má 2 deti uzly s hodnotami 5 a 34. Podstrom je strom, ktorý je tvorený len tým, že pri pohľade na odseky celého stromu. 

Napríklad, ľavý podstrom uzla 3 je strom vytvorený uzly 0, 1, 2 a Takže, ak sa vrátime k vlastnostiam stromu binárne vyhľadávanie, vidíme, že každý uzol v strome zodpovedá všetkým 3 vlastnosti, a to, ľavého podstromu obsahuje iba hodnoty, ktoré sú menšie alebo rovná uzla hodnoty; právo podstromu všetkých uzlov obsahuje iba hodnoty, ktoré sú väčšie alebo rovné uzla hodnoty, a ako ľavej a pravej podstromy všetkých uzlov sú tiež stromy binárne vyhľadávanie. Hoci tento strom vyzerá inak, je to platný binárny vyhľadávací strom pre rovnakú sadu čísel. Ako v skutočnosti, existuje mnoho možných spôsobov, ktoré môžete vytvoriť platný binárny vyhľadávací strom z týchto čísel. No, vráťme sa k prvej sme vytvorili. Čo teda môžeme robiť s týmito stromami? No, môžeme veľmi jednoducho nájsť minimálne a maximálne hodnoty. Minimálne hodnoty možno nájsť vždy vľavo kým nie sú k dispozícii žiadne ďalšie uzly sa môžete vydať. Naopak, nájsť maximálnu je jednoducho len klesá doprava v každom okamihu. 

Nájdenie iné množstvo, že nie je minimálna alebo maximálna je rovnako jednoduché. Povedzme, že hľadáte pre číslo 89. Proste sme skontrolovať hodnotu každého uzla a ísť doľava alebo doprava, v závislosti na tom, či je uzol je hodnota menšia alebo väčšia, ako ten, ktorého hľadáme. Takže, počnúc pri koreni 13, vidíme, že 89 je väčšia, a tak ideme na pravej strane. Potom vidíme uzol pre 34, a znovu sme sa ísť doprava. 89 je ešte vyššia ako 55, takže sa aj naďalej bude na pravej strane. Potom sme prišli s uzlom s hodnotou 144 a ísť doľava. A ajhľa, 89 je tu. 

Ďalšia vec, čo môžeme urobiť, je vytlačiť všetky čísla prevedením nevyhnutného traversal. Nevyhnutného traversal znamená tlačiť všetko v ľavom podstromu po ktorom nasleduje potlač na uzol sám a potom po ktorom nasleduje potlač všetko von v pravého podstrome. Napríklad, poďme sa náš obľúbený strom binárneho vyhľadávania a vytlačiť čísla v zoradené poradí. Začneme pri koreni 13, ale pred tlačou 13 budeme musieť vytlačiť všetko v ľavom podstrome. Takže ideme na 5. Máme ešte ísť hlbšie v strome, kým nenájdeme najviac vľavo uzol, ktorý je nula. Po tlače nulové, ideme späť do 1 a tlač, že von. Potom ideme na pravého podstromu, čo je o 2, a vytlačte, že von. Teraz, keď už sme to urobili s tým podstromu, sa môžeme vrátiť do 3 a vytlačiť. Pokračovanie zálohovať, sme vytlačiť 5 a potom 8. Teraz, keď sme dokončili celý ľavého podstromu, môžeme vytlačiť 13 a začať pracovať na pravý podstrom. My hop až 34, ale pred tlačou 34 budeme musieť vytlačiť jeho ľavého podstrome. Tak sme vytlačiť 21, potom sme si vytlačiť 34 a navštíviť jeho pravého podstromu. Vzhľadom k tomu, 55 nemá ľavého podstromu, sme vytlačiť a pokračovať na svoje právo podstrome. 144 má ľavého podstromu, a tak sme vytlačiť 89, nasleduje 144, a nakoniec najviac vpravo uzol z 233. Tu to máte, všetky čísla sú vytlačené v poradí od najnižšej po najvyššiu. 

Pridanie niečo stromu je relatívne bezbolestná rovnako. Všetko, čo musíme urobiť, je uistiť, že budeme nasledovať 3 binárne vlastnosti vyhľadávacieho stromu a potom vložiť hodnotu tam, kde je priestor. Povedzme, že chcete vložiť hodnotu 7. Vzhľadom k tomu, 7 je menší ako 13, ideme vľavo. Ale to je väčšia ako 5, takže traverz doprava. Vzhľadom k tomu, že je to menej ako 8 a 8 je koncový uzol, pridáme 7 do ľavého dieťa 8. Voila! Pridali sme niekoľko našich stromu binárne vyhľadávanie. 

Ak sa nám podarí pridať veci, budeme lepšie schopní odstrániť veci rovnako. Bohužiaľ pre nás, mazanie je trochu zložitejšie - nič moc, ale len trochu. K dispozícii sú 3 rôzne scenáre, ktoré máme, aby zvážila pri mazaní prvkov z binárnych vyhľadávacích stromov. Po prvé, najjednoduchšie prípad je, že prvok je koncový uzol. V tomto prípade, sme jednoducho odstrániť a pokračovať s našej obchodnej činnosti. Povedzme, že chceme odstrániť 7, ktoré sme práve pridali. No, jednoducho nájsť, odstrániť, a to je všetko. Ďalší prípad je v prípade, že uzol má len 1 dieťa. Tu môžeme zmazať uzol, ale musíme najprv uistiť, pripojiť podstrome, ktorý je teraz ponechané bez rodičov na rodičov uzla sme práve zmazal. Povedzme, že chceme odstrániť 3 z nášho stromu. Berieme podriadený prvok tohto uzla a pripojiť ju k nadradenej uzla. V tomto prípade, sme teraz upevnenie 1 do 5. Táto funkcia je bez problémov, pretože je známe, v závislosti na binárne vyhľadávacie strom majetku, že všetko v ľavom podstrome 3 bolo menej ako 5. Teraz, keď je 3 je podstrom postarané, môžeme ho odstrániť. Tretí a posledný prípad je najzložitejšie. To je prípad, keď je uzol chceme odstrániť má 2 deti. Aby k tomu, musíme najprv nájsť uzol, ktorý má budúci najväčšiu hodnotu, swap dva, a potom odstráňte uzol v otázke. Všimnite si uzol, ktorý má budúci najväčšiu hodnotu nemožno mať 2 deti sama pretože jeho ľavej dieťa bude lepší kandidát na budúci najväčší. Preto odstránenie uzla s 2 deťmi robí prehodenie 2 uzly, a odstránením je riešený 1 z 2 uvedených pravidiel. Napríklad, povedzme, že chcete vymazať koreňový uzol, 13. Prvá vec, ktorú musíme urobiť, je nájdeme ďalšie najväčšiu hodnotu vo stromu ktorá je v tomto prípade, je 21. Potom sme prehodiť 2 uzly, takže 13 listov a 21 CENTRAL GROUP uzla. Teraz môžeme jednoducho odstrániť 13. 

Ako spomenul skôr, existuje mnoho možných spôsobov, ako platný binárny vyhľadávací strom. Bohužiaľ pre nás, niektoré sú horšie ako ostatné. Napríklad, čo sa stane, keď budujeme binárny vyhľadávací strom z triedeného zoznamu čísel? Všetky čísla a pridané doprava na každom kroku. Keď chceme hľadať číslo, nemáme inú možnosť, ale len pozrieť na pravej strane na každom kroku. To nie je lepšie ako lineárny hľadanie vôbec. Aj keď nebudeme ich pokrytie, je tu ďalšie, zložitejšie, dátové štruktúry, ktoré sa uistili, že sa tak nestane. Avšak, jedna jednoduchá vec, že ​​by bolo možné vyhnúť sa len na náhodne zamiešať vstupných hodnôt. Je veľmi nepravdepodobné, že by náhody je zoradená zamiešané zoznam čísel. Ak by tomu tak bolo, by kasína nezostal v podnikaní dlho. 

Tu to máte. Teraz viete, o binárne vyhľadávanie a stromy binárne vyhľadávanie. Som Patrick Schmid, a to je CS50. [CS50.TV] Jeden zrejmý spôsob, ako by bolo skenovať zoznamu od ... [píp] ... Počet kusov ... yep [Smiech] ... Pridať uzol 234 ... augh. >> Yay! To bolo -