[Powered by Google Translate] [Binární vyhledávání]
[Patrick Schmid - Harvard University]
[To je CS50. - CS50.TV]
>> Kdybych vám dal seznam jmen postav Disney v abecedním pořadí
a zeptal se tě najít Mickey Mouse,
jak byste jít asi dělá?
Jeden zřejmý způsob, jak by bylo skenovat seznam od začátku
a zkontrolujte, každé jméno aby zjistil, jestli je to Mickey.
Ale jak budete číst Aladdin, Alice, Ariel, a tak dále,
budete rychle uvědomit, že začíná v přední části seznamu nebyl dobrý nápad.
Dobře, možná byste měli začít pracovat pozpátku od konce seznamu.
Nyní budete číst Tarzana, steh, Sněhurka, a tak dále.
Přesto, to nevypadá jako nejlepší způsob, jak jít na to.
>> No, další způsob, jak byste mohli jít asi dělá, je pokusit zúžit
seznam jmen, které budete muset podívat.
Vzhledem k tomu, víte, že jsou v abecedním pořadí,
vy jste mohli jen dívat na jména v polovině seznamu
a zkontrolujte, zda Mickey Mouse je před nebo po tomto názvu.
Při pohledu na poslední jméno v druhém sloupci
byste si uvědomit, že M pro Mickey přichází poté, co J pro Jasmine,
takže bys prostě ignorovat první polovinu seznamu.
Pak jste nejspíš podíváte na horní části posledního sloupce
a uvidíte, že to začne Rapunzel.
Mickey je před Rapunzel, vypadá to, že může ignorovat poslední sloupec stejně.
Pokračování vyhledávací strategie, budete rychle vidět, že Mickey
je v první polovině zbývající seznamu jmen
a konečně najít Mickey skrývá mezi Merlin a Minnie.
>> Co jste právě udělal, bylo v podstatě binární vyhledávání.
Jak toto jméno napovídá, provede svoji Hledám strategii v binárním věci.
Co to znamená?
No, vzhledem seznam seřazena položek, binární vyhledávací algoritmus je binární rozhodnutí -
doleva nebo doprava, větší nebo menší než, abecedně před nebo po - v každém bodě.
Nyní, když máme název, který jde spolu s tímto vyhledávací algoritmus,
Pojďme se podívat na další příklad, ale tentokrát se seznamem tříděných čísel.
Řekněme, že hledáme číslo 144 v tomto seznamu seřazených čísel.
Stejně jako předtím, najdeme číslo, které je ve středu -
který je v tomto případě je 13 - a zjistit, zda 144 je větší nebo menší než 13 let.
Vzhledem k tomu, že je to jasně větší než 13, můžeme ignorovat vše, co je 13 nebo méně
a jen se soustředit na zbývající poloviny.
Vzhledem k tomu, nyní máme dokonce počet položek vlevo,
jsme prostě vybrat číslo, které je v blízkosti středu.
V tomto případě jsme se rozhodli 55.
Mohli jsme stejně snadno zvolit 89.
Dobře. Opět, 144 je větší než 55, tak jdeme na pravé straně.
Naštěstí pro nás, další střední číslo je 144,
ten, kterého hledáme.
Takže s cílem nalézt 144 pomocí binárního vyhledávání, jsme schopni najít jen ve 3 krocích.
Pokud bychom použili lineární hledat zde, zabralo by mi to nám 12 kroků.
Jako ve skutečnosti, protože tato metoda hledání poloviční počet položek
má se podívat na na každém kroku, bude to najít položku je hledali
asi v protokolu o počtu položek v seznamu.
Teď, když jsme viděli 2 příklady, pojďme se podívat na
některé pseudokód pro rekurzivní funkce, která implementuje binární vyhledávání.
Od vrcholu, vidíme, že musíme najít funkci, která vezme 4 argumenty:
klíč, pole, min, max a.
Klíčem k úspěchu je číslo, které hledáme, tak 144 v předchozím příkladu.
Pole je seznam čísel, která hledáme.
Min a max jsou indexy minimální a maximální pozice
že se v současné době hledá na.
Takže, když se začne, bude min nulové a maximální bude maximální index pole.
Jak jsme zúžit hledání dolů, budeme aktualizovat min a max
být právě rozsah, který stále hledáme palců
>> Pojďme přeskočit na zajímavé části první.
První věc, kterou musíme udělat, je najít střed,
index, který je na půli cesty mezi min a max na pole, které jsme stále zvažuje.
Pak se podíváme na hodnotě pole v tomto místě středu dráhy
a uvidíme, jestli číslo, které hledáme, je menší než daný klíč.
Pokud je číslo v této pozici je méně,
pak to znamená, že klíč je větší než všech čísel na levé straně této poloze.
Takže můžeme volat binární vyhledávací funkce znovu,
ale tentokrát aktualizaci min a max parametry číst pouze polovinu
, který je větší než nebo rovna hodnotě jsme se podíval na.
Na druhé straně, je-li klíč je menší, než je číslo v aktuálním středu pole,
chceme jít doleva a ignorovat všechny čísla, která jsou větší.
Opět, nazýváme binární vyhledávání, ale tentokrát s rozsahem min a max Aktualizováno
zahrnout jen spodní polovina.
Pokud je hodnota v aktuálním středu v poli není ani
větší než ani menší než klíč, pak to musí být roven klíči.
Tak, můžeme jednoduše vrátit aktuální midpoint index, a jsme hotovi.
A konečně, tato kontrola je zde pro případ, že se počet
není vlastně v poli čísel jsme hledají.
Pokud je maximální index rozsahu, že se díváme na
je stále nižší než minimum, to znamená, že jsme zašli příliš daleko.
Vzhledem k tomu, počet není ve vstupním poli, jsme vrátí -1
o tom, že nebylo nalezeno nic.
>> Možná jste si všimli, že pro tento algoritmus pracovat,
seznam čísel musí být seřazeny.
Jinými slovy, můžeme najít pouze 144 pomocí binárního vyhledávání
pokud jsou všechny čísla jsou seřazeny od nejnižší po nejvyšší.
Pokud by tomu tak nebylo, nebyli bychom schopni vyloučit polovinu čísel na každém kroku.
Takže máme 2 možnosti.
Buď můžeme vzít netříděného seznamu a seřadit je před použitím binárního vyhledávání,
nebo můžeme ujistit, že seznam čísel je řazen jak jsme přidat čísla k němu.
Tak, místo toho třídění, právě když budeme muset hledat,
proč ne držet seznam seřazen za všech okolností?
>> Jeden způsob, jak udržet seznam čísel jsou seřazena současně umožňuje
kdo přidat nebo přesunout čísla z tohoto seznamu
je pomocí tzv. binární vyhledávací strom.
Binární vyhledávací strom je datová struktura, která má 3 vlastnosti.
Za prvé, levého podstromu každého uzlu obsahuje pouze hodnoty, které jsou menší než
nebo se rovná uzlu hodnoty.
Za druhé, právo podstrom uzlu obsahuje pouze hodnoty, které jsou větší než
nebo rovná uzlu hodnoty.
A konečně, jak levé a pravé podstromy všech uzlů
jsou také binární vyhledávací stromy.
Pojďme se podívat na příklad se stejnými čísly jsme používali dříve.
Pro ty z vás, kteří ještě nikdy neviděl počítačové vědy strom před,
dovolte mi začít tím, že řekne, že počítačová věda strom roste směrem dolů.
Ano, na rozdíl od stromů, na kterou jste zvyklí,
kořen stromu počítačové vědy je na vrcholu,
a listy jsou na dně.
Každý malý box se nazývá uzel, a uzly jsou navzájem spojeny hranami.
Takže Kořen tohoto stromu je hodnota uzlu s hodnotou 13,
která má 2 děti uzly s hodnotami 5 a 34.
Podstrom je strom, který je tvořen jen tím, že při pohledu na odstavce celého stromu.
>> Například, levý podstrom uzlu 3 je strom vytvořený uzly 0, 1, 2 a.
Takže, pokud se vrátíme k vlastnostem stromu binární vyhledávání,
vidíme, že každý uzel ve stromu odpovídá všem 3 vlastnosti, a to,
vlevo subtree obsahuje pouze hodnoty, které jsou menší nebo rovna uzlu hodnoty;
pravého podstromu všech uzlů
obsahuje pouze hodnoty, které jsou větší než nebo rovno uzlu hodnoty, a
jak levé a pravé podstromy všech uzlů jsou také stromy binární vyhledávání.
Ačkoli tento strom vypadá jinak, je to platný binární vyhledávací strom
pro stejnou sadu čísel.
Jako ve skutečnosti, existuje mnoho možných způsobů, které můžete vytvořit
platný binární vyhledávací strom z těchto čísel.
No, vraťme se k první jsme vytvořili.
Co tedy můžeme dělat s těmito stromy?
No, můžeme velmi jednoduše najít minimální a maximální hodnoty.
Minimální hodnoty lze nalézt vždycky vlevo
dokud nejsou k dispozici žádné další uzly se můžete vydat.
Naopak, najít maximální je prostě jen klesá doprava na každém čase.
>> Hledání jiné číslo, které není minimální nebo maximální
je stejně snadné.
Řekněme, že hledáte pro číslo 89.
Prostě jsme zkontrolovat hodnotu každého uzlu a jít doleva nebo doprava,
v závislosti na tom, zda je uzel je hodnota menší nebo větší, než
ten, kterého hledáme.
Takže, počínaje u kořene 13, vidíme, že 89 je větší,
a tak jdeme na pravé straně.
Pak vidíme uzel pro 34, a znovu jsme se jít doprava.
89 je ještě vyšší než 55, takže se i nadále bude na pravé straně.
Pak jsme přišli s uzlem s hodnotou 144 a jít doleva.
A ejhle, 89 je tady.
>> Další věc, co můžeme udělat, je vytisknout všechna čísla provedením nezbytného traversal.
Nezbytného traversal znamená tisknout vše v levém podstromu
po němž následuje potisk na uzel sám
a pak po němž následuje potisk všechno ven v pravého podstromu.
Například, pojďme se náš oblíbený strom binárního vyhledávání
a vytisknout čísla v seřazeném pořadí.
Začneme u kořene 13, ale před tiskem 13 budeme muset vytisknout
vše v levém podstromu.
Takže jdeme na 5. Máme ještě jít hlouběji ve stromu, dokud nenajdeme nejvíce vlevo uzel,
který je nula.
Po tisku nulové, jdeme zpátky do 1 a tisk, že ven.
Pak jdeme na pravého podstromu, což je o 2, a vytiskněte, že ven.
Teď, když už jsme to udělali s tím podstromu,
se můžeme vrátit do 3 a vytisknout.
Pokračování zálohovat, jsme vytisknout 5 a pak 8.
Teď, když jsme dokončili celý levého podstromu,
můžeme vytisknout 13 a začít pracovat na pravý podstrom.
My hop až 34, ale před tiskem 34 budeme muset vytisknout jeho levého podstromu.
Tak jsme vytisknout 21, pak jsme si vytisknout 34 a navštívit jeho pravého podstromu.
Vzhledem k tomu, 55 nemá levého podstromu, jsme vytisknout a pokračovat na své právo podstromu.
144 má levého podstromu, a tak jsme vytisknout 89, následuje 144,
a nakonec nejvíce vpravo uzel z 233.
Tady to máte, všechna čísla jsou vytištěny v pořadí od nejnižší po nejvyšší.
>> Přidání něco stromu je relativně bezbolestná stejně.
Vše, co musíme udělat, je ujistit, že budeme následovat 3 binární vlastnosti vyhledávacího stromu
a pak vložit hodnotu tam, kde je prostor.
Řekněme, že chcete vložit hodnotu 7.
Vzhledem k tomu, 7 je menší než 13, jdeme vlevo.
Ale to je větší než 5, takže traverz doprava.
Vzhledem k tomu, že je to méně než 8 a 8 je koncový uzel, přidáme 7 do levého dítě 8.
Voila! Přidali jsme několik našich stromu binární vyhledávání.
>> Pokud se nám podaří přidat věci, budeme lépe schopni odstranit věci stejně.
Bohužel pro nás, mazání je trochu složitější -
nic moc, ale jen trochu.
K dispozici jsou 3 různé scénáře, které máme, aby zvážila
při mazání prvků z binárních vyhledávacích stromů.
Za prvé, Nejjednodušší případ je, že prvek je koncový uzel.
V tomto případě, jsme jednoduše odstranit a pokračovat s naší obchodní činnosti.
Řekněme, že chceme odstranit 7, které jsme právě přidali.
No, prostě najít, odstranit, a to je vše.
Další případ je v případě, že uzel má pouze 1 dítě.
Zde můžeme smazat uzel, ale musíme nejprve ujistit,
připojit podstromu, který je nyní ponecháno bez rodičů
na rodiče uzlu jsme právě smazal.
Řekněme, že chceme odstranit 3 z našeho stromu.
Bereme podřízený prvek tohoto uzlu a připojit ji k nadřazené uzlu.
V tomto případě, jsme nyní upevnění 1 do 5.
Tato funkce je bez problémů, protože je známo, v závislosti na binární vyhledávací strom majetku,
že všechno v levém podstromu 3 bylo méně než 5.
Nyní, když je 3 je podstrom postaráno, můžeme jej odstranit.
Třetí a poslední případ je nejsložitější.
To je případ, kdy je uzel chceme odstranit má 2 děti.
Aby k tomu, musíme nejprve najít uzel, který má příští největší hodnotu,
swap dva, a potom odstraňte uzel v otázce.
Všimněte si uzel, který má příští největší hodnota nemůže mít 2 děti sama
protože jeho levý dítě bude lepší kandidát na příští největší.
Proto odstranění uzlu s 2 dětmi činí prohození 2 uzly,
a odstraněním je řešen 1 ze 2 uvedených pravidel.
Například, řekněme, že chcete vymazat kořenový uzel, 13.
První věc, kterou musíme udělat, je najdeme další největší hodnotu ve stromu
která je v tomto případě, je 21.
Pak jsme prohodit 2 uzly, takže 13 listů a 21 CENTRAL GROUP uzlu.
Nyní můžeme jednoduše odstranit 13.
>> Jak zmínil dříve, existuje mnoho možných způsobů, jak platný binární vyhledávací strom.
Bohužel pro nás, některé jsou horší než ostatní.
Například, co se stane, když budujeme binární vyhledávací strom
z tříděného seznamu čísel?
Všechna čísla a přidány doprava na každém kroku.
Když chceme hledat číslo,
nemáme jinou možnost, ale jen podívat na pravé straně na každém kroku.
To není lepší než lineární hledání vůbec.
I když nebudeme jejich pokrytí, je zde další, složitější,
datové struktury, které se ujistili, že se tak nestane.
Nicméně, jedna jednoduchá věc, že ​​by bylo možné vyhnout se
jen na náhodně zamíchat vstupních hodnot.
Je velmi nepravděpodobné, že by náhody je seřazena zamíchány seznam čísel.
Pokud by tomu tak bylo, by kasina nezůstal v podnikání dlouho.
>> Tady to máte.
Nyní víte, o binární vyhledávání a stromy binární vyhledávání.
Jsem Patrick Schmid, a to je CS50.
[CS50.TV]
Jeden zřejmý způsob, jak by bylo skenovat seznamu od ... [píp]
... Počet kusů ... yep
[Smích]
... Přidat uzel 234 ... augh.
>> Yay! To bylo -