[Powered by Google Translate] [Binary Keresés] [Patrick Schmid - Harvard University] [Ez CS50. - CS50.TV] 

Ha én adtam neked egy listát a Disney karakter nevek betűrendben és arra kérte, hogy megtalálja Mickey Mouse, hogyan megy a csinálod ezt? Az egyik kézenfekvő módja az lenne, hogy megvizsgálja a lista elején és ellenőrizze, minden nevet, hogy ha ez a Mickey. De ahogy olvasol Aladdin, Alice, Ariel, és így tovább, akkor hamar rájön, hogy az indítást elején a lista nem volt jó ötlet. Oké, lehet, hogy meg kell kezdeni visszafelé haladva az a lista végére. Most olvas Tarzan, Stitch, Hófehérke, és így tovább. Mégis, ez nem tűnik a legjobb módja, hogy menjen vele. 

Nos, egy másik módja, hogy meg tudná járni ezt az, hogy megpróbálja leszűkítheti a neveket, hogy meg kell nézni. Mivel tudja, hogy ABC sorrendben, akkor csak nézd meg a nevét a közepén a lista és ellenőrizze, hogy Mickey egér előtt vagy után ezt a nevet. Keresi az utolsó név a második oszlopban azt észre, hogy M Mickey után jön J Jasmine, így azt egyszerűen figyelmen kívül hagyja az első felében a listán. Akkor lenne talán nézd meg a tetején az utolsó oszlop és nézd meg, hogy kezdődik Rapunzel. Mickey előbb Rapunzel, úgy néz ki, mint tudjuk figyelmen kívül hagyni az utolsó oszlop is. Folytatva a keresési stratégiát, akkor gyorsan látni, hogy Mickey az első felében a fennmaradó nevek listáját és végül megtalálni Mickey bujkál között Merlin és Minnie. 

Amit most tett, az tulajdonképpen a bináris keresés. Mivel ez a neve is mutatja, ez végzi keresés stratégiáját bináris kérdésben. Mit jelent ez? Nos, adott egy listát rendezett tárgyakat, a bináris keresés algoritmus teszi a bináris döntés - balra vagy jobbra, nagyobb vagy kisebb, mint betűrendben előtt vagy után - minden ponton. Most, hogy van egy név, amely együtt jár a keresést algoritmus, nézzük egy másik példát, de ezúttal egy listát a számok sorrendje. Mondja keresünk számát 144-ben ezt a listát a rendezett számok. Csakúgy, mint korábban, azt látjuk, hogy ez a szám a középső - amely ebben az esetben 13 -, és ha 144-nél nagyobb vagy kisebb mint 13. Mivel ez nyilvánvalóan nagyobb, mint 13, akkor figyelmen kívül mindent, ami 13 vagy kevesebb és csak koncentrálni a másik felét. Mivel most már páros számú tétel maradt, egyszerűen válassza ki a számot, amely közel áll a közepén. Ebben az esetben válassza a 55. Mi volna éppen olyan könnyen választott 89. Oké. Ismét, 144 nagyobb, mint 55, így megy a jobbra. Szerencsénkre, a következő középső szám 144, az, amit keresünk. Így annak érdekében, hogy megtalálják 144 egy bináris keresés, képesek vagyunk megtalálni mindössze 3 lépésben. Ha használta volna a lineáris keresést itt, akkor volna minket 12 lépésben. Ami azt illeti, mivel ez a keresési mód felezi a tételek száma azt, hogy nézd meg minden lépésben, akkor megtalálja a tételt, hogy keres körülbelül a naplót a tételek számát a listában. Most, hogy láttuk 2 példa, vessünk egy pillantást Néhány pszeudokód egy rekurzív függvény, amely megvalósítja a bináris keresés. Kezdve a tetején, azt látjuk, hogy meg kell találni egy függvényt, amely úgy 4 érvek: gombot, tömb, min és max. A legfontosabb az a szám, amelyet keresünk, ezért 144-ben az előző példában. Array a lista a számokat keresünk. Min és max a mutatók minimális és maximális pozíciók hogy jelenleg nézi. Szóval mikor kezdünk, min nulla lesz és max lesz a legnagyobb index a tömb. Ahogy szűkíteni a keresést, akkor frissíteni min és max hogy csak a tartomány, hogy mi még mindig keresi be 

Nézzük ugrás az érdekes rész első. Az első dolog, amit tennie, hogy megtalálja a középpont, az index, amely félúton a min és max értéke a tömb, hogy mi továbbra is vizsgálja. Akkor nézzük az érték a tömb az adott középponti helyen és nézd meg azt a számot, keresünk kisebb, mint hogy a kulcsot. Ha a szám ebben a pozícióban a kisebb, akkor ez azt jelenti, a legfontosabb az, nagyobb, mint az összes számot a bal oldalon ez az álláspont. Így tudjuk hívni a bináris keresési funkció újra, de ezúttal frissítésével min és max paraméterek olvasni, csak a felét amely nagyobb vagy egyenlő, mint az értéket adunk csak nézett. Másrészről, ha a kulcs kisebb, mint a szám az aktuális felezőpontja a tömb, akarunk menni a balra és figyelmen kívül hagyja az összes számot, amely nagyobb. Ismét hívjuk bináris keresés, de ezúttal tartomány min és max updated fel, csak az alsó felét. Ha az érték az aktuális felezőpontjában a tömbben sem nagyobb, sem kisebb, mint a kulcs, akkor meg kell egyeznie a kulcsot. Így, akkor egyszerűen vissza a jelenlegi felezőpontja index, és készen vagyunk. Végül, ez a csekk itt Az a helyzet, hogy a szám valójában nem a tömbben lévő számok keresünk. Ha a legnagyobb index a tartomány, hogy keresünk örökké kisebb, mint a minimum, ami azt jelenti, hogy már túl messzire ment. Mivel a szám nem volt az input tömb, akkor vissza -1 annak jelzésére, hogy semmit sem találtak. 

Lehet, hogy észrevette, hogy ezen algoritmus működik, A számok listája kell válogatni. Más szóval, csak akkor tudjuk találni 144 bináris keresés ha minden a számokat a megrendelt legalacsonyabbtól a legmagasabb. Ha ez nem így lenne, akkor nem lenne képes kizárni felét a számok az egyes lépésekben. Tehát van 2 lehetőség. Vagy vehetjük a szétválogatott listát, és rendezheti előtt bináris keresés, vagy mi lehet benne, hogy a lista a számok sorrendje, ahogy hozzá számokat is. Így ahelyett, hogy válogatás csak amikor meg kell keresni, miért nem tartja a lista sorrendje minden alkalommal? 

Az egyik módja annak, hogy egy listát a számok sorrendje miközben lehetővé 1 hozzáadásához vagy áthelyezni a telefonszámokat a listából a segítségével egy úgynevezett bináris kereső fa. A bináris kereső fa olyan adatszerkezet, amely 3 tulajdonságait. Először is, a bal részfájának bármely csomópont tartalmaz, csak olyan értékekre, amelyek kevesebb, mint vagy egyenlő a csomópont értékét. Másodszor, a jobb részfájának egy csomópont csak értékeket tartalmaz, amelyek-nél nagyobb vagy egyenlő a csomópont értékét. És végül, a bal és jobb részfákat az összes csomópont szintén bináris keresés fák. Nézzünk egy példát az azonos számokat használtunk korábban. Azok számára, akik még soha nem látott a számítógép-tudomány fa előtt, Hadd kezdjem azzal, amely jelzi, hogy a számítógép-tudomány fa nő lefelé. Igen, ellentétben a fák akkor szokott, gyökere a számítógép-tudomány fa van a tetején, és a levelek alján. Minden egyes kis doboz hívják csomópont, és a csomópontok kapcsolódnak egymáshoz élek. Tehát a gyökere ennek a fának van egy csomópont érték az érték 13, amely 2 gyermek csomópontok az értékek 5 és 34. A részfa az a fa, van kialakítva ránézésre egy alfejezetet az egész fa. 

Így például, a bal részfájának a 3 csomópont a fa által létrehozott csomópontok 0, 1, és 2. Tehát, ha visszamegyünk a tulajdonságait egy bináris keresési fa, azt látjuk, hogy minden csomópont a fában megfelel mind a 3 tulajdonságok, nevezetesen, a bal oldali részfa egyetlen értékeket tartalmaz, amelyek kisebb vagy egyenlő, mint a csomópont értékét; a jobb részfa összes csomópont csak azokat, amelyek értéke nagyobb, vagy egyenlő, mint a csomópont értékét, és mind a bal és jobb oldali részfa összes csomópont is vannak bináris keresési fák. Bár ez a fa másképp néz ki, ez egy érvényes bináris keresési fa számára ugyanazokat a számokat. Ami azt illeti, sok lehetséges módon lehet létrehozni érvényes bináris keresési fa ezeket a számokat. Nos, menjünk vissza az első hoztunk létre. Szóval mit tehetünk ezekkel a fák? Nos, akkor nagyon egyszerűen megtalálja a minimum és maximum értékek. A minimum értékek is talált mindig megy a bal amíg nincs több csomópont meglátogatni. Ezzel, hogy megtalálják a legnagyobb ember egyszerűen csak megy lefelé a jogot minden alkalommal. 

Finding bármely másik szám, amely nem a legkisebb, illetve a maximális éppen olyan egyszerű. Mondja keresünk a szám 89. Egyszerűen ellenőrizze értékét minden egyes csomópont és menj a balra vagy jobbra, attól függően, hogy a csomópont értéke kisebb vagy nagyobb, mint az, amit keresünk. Szóval, a gyökértől kiindulva 13, azt látjuk, hogy 89 nagyobb, és így megy a jobbra. Aztán látjuk a csomópont 34, és újra megyünk jobbra. 89 még mindig nagyobb, mint 55, így továbbra is megy a jobb oldalon. Ezután jön egy csomópont értékét 144 és menj balra. Lo és íme, a 89 ott van. 

A másik dolog, amit tehetünk, nyomtassa ki az összes számok végző inorder bejárás. Egy inorder bejárás jelent nyomtatni mindent a bal oldali részfa nyomás követi a csomópont maga majd nyomás követi mindent a jobb részfa. Például vegyük a kedvenc bináris keresési fa és nyomtassa ki a számokat rendezetten. Kezdjük a gyökere a 13, de a nyomtatás előtt 13 van, hogy nyomtassa ki mindent a bal oldali részfa. Akkor megyünk 5-re. Meg kell még mélyebben le a fán, amíg meg nem találja a bal szélső csomópont, amely nulla. Nyomtatás után nulla, megyünk vissza az 1-es és nyomtassa azt ki. Aztán menj jobbra részfa, amely 2, és nyomtassa ki, hogy ki. Most, hogy mi történik, hogy a részfa, mehetünk vissza a 3 és nyomtassa ki. Folytatva vissza, kiírjuk az 5, majd a 8. Most, hogy elkészült az egész bal részfa, akkor nyomtassa ki a 13 és elkezd dolgozni a jobb részfa. Mi hop le a 34, de a nyomtatás előtt 34 van, hogy nyomtassa ki a bal oldali részfa. Tehát ki kell nyomtatni, 21, akkor megkapjuk, hogy nyomtassa ki 34 és látogasson el a jobb részfa. Mivel a 55 nincs bal részfa, akkor nyomtassa ki, és továbbra is a tőle jobbra részfa. 144 egy balra részfa, és így ki kiírjuk a 89, majd a 144, és végül a jobb szélső csomópont, 233. Ott van ez, minden a számok kinyomtatható sorrendben a legalacsonyabbtól a legmagasabb. 

Hozzáadása valamit a fa viszonylag fájdalommentes is. Mindössze annyit kell tennie, hogy megbizonyosodjon arról, hogy követjük 3 bináris keresési fa tulajdonságai majd helyezze be az értéket, ahol van hely. Tegyük fel, hogy szeretnénk beszúrni értékének 7. 7-től kevesebb, mint 13, akkor menj a bal oldalon. De ez 5-nél nagyobb, így keresztezik jobbra. Mivel ez kevesebb, mint 8 és 8 a levél csomópont, adjuk 7 balra gyermek 8. Voila! Már ki egy számot a bináris keresési fa. 

Ha sikerül hozzá dolgokat, mi jobban tudja törölni a dolgokat is. Sajnos nekünk, törlésére egy kicsit bonyolultabb - Nem sok, de csak egy kicsit. Jelenleg 3 különböző forgatókönyvek, hogy meg kell vizsgálni törlésekor elemek bináris keresési fák. Először is, a legegyszerűbb eset az, hogy az elem egy levél csomópont. Ebben az esetben, egyszerűen törölje le, és folytassa a mi dolgunk. Mondja el akarjuk törölni a 7, hogy csak hozzá. Nos, egyszerűen keresse meg, távolítsa el, és ennyi. A következő eset az, ha a csomópont csak 1 gyerek. Itt törölheti a csomópont, de először meg kell győződjön meg róla, csatlakoztassa a részfa, hogy most marad árva a szülő a csomópont már csak el kell hagyni. Mondja el akarjuk törölni a mi 3 fa. Vesszük a gyermek eleme, hogy a csomópont és csatolja a szülő a csomópont. Ebben az esetben, most azon kapcsolódó az 1-től az 5. Ez úgy működik, anélkül, hogy a probléma, mert tudjuk, hogy szerint a bináris keresési fa ingatlanok, hogy mindent a bal részfa a 3 volt, kevesebb, mint 5. Most, hogy a 3-as részfa van intézve, akkor törölheti azt. A harmadik és egyben utolsó eset a legbonyolultabb. Ez az az eset, amikor a csomópont akarunk törölni területén 2 gyermek. Annak érdekében, hogy ezt, akkor először meg kell találnunk a csomópont, amely a következő legnagyobb érték, csere a két, majd törölje a csomópontot a kérdést. Figyeljük meg a csomópont, amely a következő legnagyobb érték nem lehet 2 gyermek maga mivel a bal gyerek lenne a jobb jelölt a következő legnagyobb. Ezért törlése csomópont 2 gyermek összege cseréje 2-csomópont, majd törli kezeli 1 a 2 említett szabályokat. Például, tegyük fel, szeretnénk törölni a gyökér csomópont, 13. Az első dolog, amit tennie, hogy megtalálja a következő legnagyobb érték a fában amely ebben az esetben, 21 év. Ezután cserélni a 2 csomópont, így 13 a levél és 21 a központi csoportban csomópontot. Most egyszerűen törölheti 13. 

Mint utalt korábban, sok lehetséges módja, hogy egy érvényes bináris keresési fa. Sajnos nekünk, néhány rosszabb, mint mások. Például, mi történik, ha építünk egy bináris keresési fa egy rendezett lista számok? Minden szám is csak hozzá a jogot minden lépést. Ha azt akarjuk, hogy keres egy számot, nincs más választásunk, csak hogy nézd meg a jogot minden lépést. Ez nem jobb, mint a lineáris keresés egyáltalán. Bár mi nem terjed ki őket ide, vannak más, bonyolultabb, adatszerkezeteket, hogy győződjön meg arról, hogy ez nem történhet meg. Azonban egy egyszerű dolog, amit tehetünk, hogy elkerüljék ezt hogy csak véletlenszerűen shuffle a bemeneti értékeket. Ez nagyon valószínűtlen, hogy a véletlen esélye a csoszogott számlista van rendezve. Ha ez lenne a helyzet, kaszinók nem marad az üzleti életben sokáig. 

Ott van ez. Most már tudni bináris keresést és bináris keresési fák. Vagyok Patrick Schmid, és ez CS50. [CS50.TV] Az egyik kézenfekvő módja az lenne, hogy végig a lista ... [BEEP] ... A tételek számát ... yep [Nevet] ... Elhelyezhet csomópontja 234 ... augh. >> Yay! Ez volt -