[Powered by Google Translate] [Binary Search] [Patrick Schmid - Harvard University] [Dit is CS50. - CS50.TV] 

Als ik u een lijst met Disney-karakter namen in alfabetische volgorde en vroeg je om Mickey Mouse te vinden, hoe zou je dat doen? Een voor de hand liggende manier zou zijn om de lijst vanaf het begin te scannen en controleer elke naam om te zien of het is Mickey. Maar als je leest Aladdin, Alice, Ariel, enzovoort, je zult snel beseffen dat vanaf de voorzijde van de lijst niet een goed idee was. Oke, misschien moet je beginnen met werk hierbij vanaf het einde van de lijst. Nu lees je Tarzan, Stitch, Sneeuwwitje, enzovoort. Toch lijkt dit niet als de beste manier om te gaan over. 

Nou, nog een manier waarop je zou kunnen gaan over het doen van dit is om te proberen om een ​​beperking van de lijst met namen die je moet kijken. Omdat je weet dat ze in alfabetische volgorde, kon je gewoon kijkt naar de namen in het midden van de lijst en controleer of Mickey Mouse is voor of na deze naam. Kijkend naar de laatste naam in de tweede kolom je zou beseffen dat M voor Mickey komt na J voor Jasmine, dus je zou gewoon negeren de eerste helft van de lijst. Dan zou je waarschijnlijk kijken naar de top van de laatste kolom en zie dat het begint met Rapunzel. Mickey komt voor Rapunzel, lijkt erop dat we kunnen de laatste kolom negeren ook. Voortzetting van de zoekstrategie, zul je snel zien dat Mickey in de eerste helft van de resterende namenlijst en eindelijk Mickey verstopt tussen Merlijn en Minnie. 

Wat je net deed was eigenlijk binaire zoekopdracht. Zoals deze naam al impliceert, zij haar zoeken strategie in een binaire kwestie. Wat betekent dit? Nou, gegeven een lijst met gesorteerde items, de binaire zoekalgoritme maakt een binaire beslissing - links of rechts, groter of kleiner dan, alfabetisch voor of na - op elk punt. Nu we een naam die gepaard gaat met deze zoekalgoritme te hebben, Laten we eens kijken naar een ander voorbeeld, maar dit keer met een lijst met gesorteerde nummers. Stel dat we op zoek zijn naar het nummer 144 in deze lijst van gesorteerd nummers. Net als vroeger, vinden we het getal dat is in het midden - in dit geval is 13 - 144 om te zien of groter of minder dan 13. Omdat het duidelijk groter dan 13, kunnen we negeren alles wat is 13 of minder en gewoon concentreren op de andere helft. Omdat we nu een even aantal items achtergelaten, we gewoon een nummer kiezen die dicht bij het midden. In dit geval kiezen we 55. We konden net zo goed hebben gekozen 89. Oke. Nogmaals, 144 groter is dan 55, dus we gaan naar rechts. Gelukkig voor ons, de volgende middelste getal is 144, degene die we zoeken. Dus om 144 vinden met behulp van een binair zoeken, zijn we in staat om het te vinden in slechts 3 stappen. Als we gebruik hebben gemaakt van lineair zoeken hier, zou het hebben genomen ons 12 stappen. In feite, aangezien deze zoekmethode halveert het aantal items het moet kijken bij elke stap zal vinden het produkt dat zoekt in ongeveer de log van het aantal items in de lijst. Nu we 2 voorbeelden gezien, laten we eens een kijkje op wat pseudocode voor een recursieve functie die binaire zoekopdracht implementeert. Begin bij de bovenkant, zien we dat we een functie die 4 argumenten neemt te vinden: sleutel, array, min en max. De sleutel is het nummer dat we op zoek zijn naar, dus 144 in het vorige voorbeeld. Matrix is ​​de lijst met nummers die we zoeken. Min en max zijn de indices van de minimale en maximale posities dat we momenteel op zoek naar. Dus als we beginnen, zullen min nul en max is de maximale index van de array. Als we de zoekopdracht naar beneden, zullen we een update van min en max om alleen het assortiment dat we nog steeds op zoek zijn naar binnen worden 

Laten we eerst naar het interessante deel. Het eerste wat we doen is het vinden het middelpunt, de index die is halverwege tussen de min en max van de array dat we nog overwegen. Vervolgens kijken we naar de waarde van de array op dat punt locatie en kijk of het nummer dat we op zoek zijn naar minder dan die toets. Als het aantal op die positie minder, dan betekent de sleutel groter is dan alle getallen links van die positie. Dus we kunnen noemen binaire zoekfunctie weer, maar deze keer het bijwerken van de min. en max. parameters om enkel de helft gelezen die groter dan of gelijk aan de waarde die we keek. Anderzijds, als de sleutel dan het aantal in de huidige midden van de array, we willen gaan naar links en alle nummers die groter zijn negeren. Nogmaals, we noemen binair zoeken, maar dit keer met het bereik van de min en max updated alleen de onderste helft omvat. Als de waarde op de huidige midden in de array noch groter dan of kleiner dan de sleutel, dan moet gelijk zijn aan de sleutel. Zo kunnen we gewoon terug de huidige midden-index, en we zijn klaar. Tenslotte, deze controle is hier voor het geval dat het aantal is eigenlijk niet in de array van getallen zijn we op zoek. Als de maximale index van het bereik dat we op zoek zijn naar is altijd minder dan het minimum, dat betekent dat we zijn te ver gegaan. Omdat het aantal was niet in de input array, we -1 terug dat niets dan gevonden. 

Je hebt misschien gemerkt dat het voor dit algoritme te laten werken, de lijst met nummers moet worden gesorteerd. Met andere woorden, kunnen we alleen maar vinden 144 met behulp van binaire zoekopdracht Als alle nummers zijn gerangschikt van laag naar hoog. Als dit niet het geval is, zouden we niet in staat zijn om de helft van de nummers te sluiten bij elke stap. Dus we hebben 2 opties. Of we kunnen een ongesorteerde lijst en sorteren voordat u binary search, of we kunnen ervoor zorgen dat de lijst met nummers wordt gesorteerd als we nummers aan toe te voegen. Dus in plaats van sorteren net toen we moeten zoeken, waarom niet houden van de lijst gesorteerd op elk moment? 

Een manier om een ​​lijst met nummers houden gesorteerd en tegelijkertijd toestaan een toe te voegen of nummers te verplaatsen van de lijst is met behulp van een zogenaamde binaire zoekboom. Een binaire zoekboom is een datastructuur die 3 eigenschappen heeft. Enerzijds de linker deelboom van elke node alleen waarden die kleiner zijn dan of gelijk is aan de waarde van de node. Ten tweede, de rechter deelboom van een knooppunt bevat alleen waarden die groter zijn dan of gelijk is aan de waarde van de node. En tenslotte de linker en rechter subbomen van alle knooppunten zijn ook binaire zoekbomen. Laten we eens kijken naar een voorbeeld met dezelfde nummers die we eerder gebruikt. Voor degenen onder u die nog nooit een computer science boom eerder gezien, laat ik beginnen met te vertellen dat een computer science boom naar beneden groeit. Ja, in tegenstelling tot bomen u gewend bent, de wortel van een informatica boom bovenaan en de bladeren staan ​​onderaan. Elk doosje wordt een knooppunt en de knooppunten met elkaar verbonden door randen. Dus de wortel van deze boom is een knooppunt waarde met de waarde 13, die heeft 2 kinderen nodes met de waarden 5 en 34. Een substructuur is de boom die wordt gevormd door gewoon te kijken naar een onderafdeling van de gehele boom. 

Bijvoorbeeld de linker deelboom van het knooppunt 3 is de boom die door de knooppunten 0, 1 en 2. Dus, als we terug gaan naar de eigenschappen van een binaire zoekboom, we zien dat elke knoop in de boom voldoet aan alle drie eigenschappen, namelijk de linker deelboom bevat alleen waarden die minder dan of gelijk aan de waarde van het knooppunt; de rechter deelboom van alle knooppunten Alleen bevat waarden die groter dan of gelijk aan de waarde van het knooppunt, en zowel links als rechts substructuren van alle knooppunten zijn ook binaire zoekbomen. Hoewel deze boom er anders, dit een geldig binaire zoekboom voor dezelfde reeks getallen. In feite zijn er vele mogelijke manieren waarop u kunt een geldige binaire zoekboom van deze nummers. Nou, laten we terug gaan naar de eerste die we gemaakt. Dus wat kunnen we doen met deze bomen? Nou, we kunnen heel gewoon vinden de minimale en maximale waarden. De minimumwaarden kan worden gevonden door altijd naar links totdat er geen meer knooppunten te bezoeken. Omgekeerd, het vinden van de maximum een ​​simpelweg naar beneden gaat naar rechts op elk tijdstip. 

Het vinden van een ander nummer dat niet het minimale of de maximale is net zo gemakkelijk. Zeggen dat we op zoek naar het nummer 89. We hebben gewoon controleren van de waarde van elk knooppunt en ga naar links of rechts, naargelang het knooppunt waarde kleiner is dan of groter dan degene die we zoeken. Dus vanaf de wortel van 13 zien we dat 89 groter is, en dus gaan we naar rechts. Dan zien we het knooppunt voor 34, en weer gaan we naar rechts. 89 nog steeds groter is dan 55, dus we blijven gaan naar rechts. Vervolgens komen met een knooppunt met de waarde van 144 en naar links. Lo en zie, 89 is daar. 

Een ander ding dat we kunnen doen is uit te printen alle nummers door het uitvoeren van een inorder traversal. Een inorder traversal betekent om alles af te drukken in de linker deelboom gevolgd door de knoop zelf drukken en dan gevolgd door bedrukken alles in de rechter deelboom. Bijvoorbeeld, laten we onze favoriete binaire zoekboom en print de nummers in gesorteerde volgorde. We beginnen bij de wortel van 13, maar voordat u gaat afdrukken 13 moeten we uit te printen alles in de linker deelboom. Dus gaan we naar 5. We moeten nog dieper naar beneden gaan in de boom totdat we de meest linkse knooppunt, dat nul is. Na het afdrukken nul, gaan we terug naar de 1 en af ​​te drukken dat uit. Dan gaan we naar de rechter deelboom, dat is 2, en af ​​te drukken dat uit. Nu we klaar zijn met die substructuur, kunnen we terug te gaan naar de 3 en print het uit. Voortzetting van een back-up is een afdruk van de 5 en dan de 8. Nu we de hele afgerond linker deelboom, Wij kunnen de 13 en gaan werken aan de rechter deelboom. We springen naar 34, maar voordat u gaat afdrukken 34 moeten we uit te printen zijn linker deelboom. Dus we afdrukken 21; dan krijgen we te printen 34 en de rechter deelboom te bezoeken. Omdat 55 heeft geen linker deelboom, drukken we het uit en verder naar de rechter deelboom. 144 heeft een linker deelboom, en dus de 89 afdrukken, gevolgd door 144, en tenslotte de meest rechtse node 233. Daar heb je het, alle nummers zijn afgedrukt in de volgorde van laag naar hoog. 

Het toevoegen van iets aan de boom is relatief pijnloos ook. Het enige wat we hoeven te doen is ervoor te zorgen dat we 3 binaire zoekboom eigenschappen te volgen en steek vervolgens de waarde waar ruimte is. Laten we zeggen dat we de waarde van 7 in te voegen. Sinds 7 is minder dan 13, gaan we naar links. Maar het is groter dan 5, dus beweeg naar rechts. Omdat het minder dan 8 en 8 een eindknooppunt voegen wij 7 naar links kind van 8. Voila! We hebben een aantal van onze binaire zoekboom. 

Als we kunnen toevoegen dingen, we beter in staat zijn om dingen te verwijderen ook. Helaas voor ons, het verwijderen is een beetje ingewikkelder - niet veel, maar slechts een klein beetje. Er zijn 3 verschillende scenario's die we moeten overwegen bij het verwijderen van elementen uit binaire zoekbomen. Eerste, het eenvoudigste geval is dat het element een eindknooppunt. In dit geval hebben we gewoon verwijderen en verder gaan met ons bedrijf. Stel dat we willen de 7 die we net toegevoegd te verwijderen. Nou ja, gewoon wij het vinden, neem hem uit en dat is het. De volgende zaak is wanneer de node heeft slechts 1 kind. Hier kunnen we verwijderen van het knooppunt, maar moeten we eerst zorgen dat om de substructuur die nu ouderloos overblijft aansluiten aan de ouder van het knooppunt we gewoon verwijderd. Stel dat we willen 3 verwijderen uit onze boom. We nemen de onderliggend element van die knoop en voeg het bij de ouder van het knooppunt. In dit geval worden momenteel bevestigen van de een naar de 5. Dit werkt zonder problemen omdat we weten volgens het binaire zoekboom bezit, dat alles in de linker deelboom van 3 minder dan 5. Nu 3's substructuur wordt verzorgd, kunnen we verwijderen. De derde en laatste geval is het meest complex. Dit is het geval wanneer het knooppunt we willen verwijderen heeft 2 kinderen. Om dit te doen, moeten we eerst het knooppunt dat de volgende grootste waarde te vinden, swap de twee en verwijder het knooppunt in kwestie. Let op het knooppunt dat is de volgende grootste waarde kan geen 2 kinderen zelf sinds de linker kind zou een betere kandidaat voor de op een na grootste is. Daarom verwijderen van een knooppunt 2 kinderen bedraagt ​​wisselen van twee knooppunten, en dan te verwijderen wordt afgehandeld door 1 van de 2 voornoemde regels. Bijvoorbeeld, laten we zeggen dat we willen de root node, 13 verwijderen. Het eerste wat we doen is vinden we de volgende grootste waarde in de boom die in dit geval is 21. Vervolgens hebben we ruilen de 2 knopen, het maken van 13 een blad en 21 van de centrale groep knooppunt. Nu kunnen we gewoon verwijderen 13. 

Zoals eerder gezinspeeld, zijn er vele manieren om een ​​geldige binaire zoekboom maken. Helaas voor ons, sommige zijn erger dan anderen. Bijvoorbeeld, wat er gebeurt als we een binaire zoekboom uit een gesorteerde lijst van nummers? Alle nummers zijn gewoon toegevoegd aan de juiste bij elke stap. Wanneer we willen zoeken naar een aantal, We hebben geen andere keuze dan alleen aan op de juiste kijken bij elke stap. Dit is niet beter dan lineair zoeken op alle. Hoewel we hier niet bedek ze, zijn er andere, meer complexe, datastructuren die ervoor zorgen dat dit niet gebeurt. Echter, een simpel ding dat kan worden gedaan om dit te voorkomen is om gewoon willekeurig shuffle de ingevoerde waarden. Het is zeer onwaarschijnlijk dat bij toeval een geschud lijst met nummers gesorteerd. Als dit het geval is, zou casino's niet blijven in het bedrijfsleven voor lang. 

Daar heb je het. Je weet nu over binair zoeken en binaire zoekbomen. Ik ben Patrick Schmid, en dit is CS50. [CS50.TV] Een voor de hand liggende manier zou zijn om de lijst te scannen van ... [piep] ... Het aantal items ... yep [Lacht] ... Na knooppunt van 234 ... augh. >> Yay! Dat was -