[Powered by Google Translate] [ორობითი ძებნა] [პატრიკ შმიდი - ჰარვარდის უნივერსიტეტი] [ეს არის CS50. - CS50.TV] 

თუ მივეცი თქვენ სიაში Disney ხასიათი სახელები ანბანის მიხედვით და გთხოვეთ მოძიების Mickey Mouse, როგორ წავიდეთ შესახებ ამით? ერთი აშკარა გზა იქნებოდა სკანირებას სიის დასაწყისში და შეამოწმოს ყველა სახელზე თუ მიკი. მაგრამ, როგორც წაიკითხოთ Aladdin, Alice, Ariel, და ა.შ., თქვენ სწრაფად გააცნობიეროს, რომ დაწყებული წინაშე სიაში არ იყო კარგი იდეა. Okay, იქნებ თქვენ უნდა დაიწყოს მუშაობა უკან ბოლოდან სიაში. თქვენ ახლა Tarzan, Stitch, თოვლი თეთრი და სხვ. და მაინც, ეს არ ჩანს როგორც საუკეთესო გზაა გასავლელი შესახებ. 

ისე, სხვა გზა, რომ თქვენ შეიძლება წავიდეთ შესახებ აკეთებს ეს ცდილობენ ვიწრო ქვემოთ სიაში სახელები, რომ თქვენ უნდა შევხედოთ. მას შემდეგ, რაც თქვენ იცით, რომ ისინი ანბანის მიხედვით, თქვენ შეიძლება შევჩერდეთ სახელები შუა სია და შემოწმება თუ Mickey Mouse მანამდე ან მის შემდეგ ამ სახელით. ეძებს გვარი მეორე სვეტი ნეტავ გააცნობიეროს, რომ მ მიკი უძღოდა J ამისთვის Jasmine, ასე რომ თქვენ მინდა უბრალოდ იგნორირება პირველ ნახევარში სიაში. მაშინ მინდა ალბათ შეხედეთ ზევით ბოლო სვეტი და ვხედავთ, რომ იგი იწყება Rapunzel. მიკი მოდის ადრე Rapunzel; ჰგავს შეგვიძლია იგნორირება ბოლო სვეტი ისევე. გრძელდება ძებნა სტრატეგია, თქვენ სწრაფად ვხედავთ, რომ მიკი არის პირველ ნახევარში დარჩენილი სიაში სახელები და ბოლოს იპოვის მიკი იმალებოდა შორის Merlin და Minnie. 

რა უბრალოდ გააკეთა, ძირითადად ორობითი ძებნა. როგორც ამ სახელი გულისხმობს, ეს თავის ძებნას სტრატეგია ორობითი საკითხზე. რას ნიშნავს ეს? კარგად, მოცემულ სიაში დახარისხებული ნივთები, ბინარული ძებნის ალგორითმი ხდის ორობითი გადაწყვეტილება - მარცხნივ ან მარჯვნივ, მეტია ან ნაკლები, ალფავიტის წინ ან შემდეგ - ყოველ წერტილს. არის, რომ ჩვენ გვყავს სახელი რომ მიდის ერთად ამ ძებნის ალგორითმი, მოდით შევხედოთ კიდევ ერთი მაგალითია, მაგრამ ამ დროს სიაში დახარისხებული ნომრები. Say ვეძებთ ნომერი 144 ამ სიაში დახარისხებული ნომრები. ისევე ადრე, ჩვენ ხმების რომ ახლო - რაც ამ შემთხვევაში არის 13 - და თუ 144 მეტია ან ნაკლები 13. რადგან ნათლად აღემატება 13, შეგვიძლია იგნორირება ყველაფერი, რაც არის 13 ან ნაკლები და მხოლოდ კონცენტრაციას დარჩენილი ნახევარი. ვინაიდან ჩვენ ახლა კი ელემენტთა რაოდენობა დაუტოვებიათ, ჩვენ უბრალოდ აირჩიეთ ნომერი, რომელიც ახლოს არის ახლო. ამ შემთხვევაში ვირჩევთ 55. ჩვენ შეგვეძლო ასევე ადვილად არჩეული 89. Okay. ერთხელ, 144 მეტია 55, ამიტომ ჩვენ წასვლა უფლება. საბედნიეროდ ჩვენთვის, შემდეგი შუა რიცხვი 144, ერთი ჩვენ ვეძებთ. ამიტომ, რათა 144 გამოყენებით ორობითი ძებნა, ჩვენ მიაგნეს მხოლოდ 3 ნაბიჯებს. თუ ჩვენ არ გამოიყენება წრფივი ძებნა აქ, ეს იქნებოდა მიღებული us 12 ნაბიჯები. როგორც ფაქტობრივად, რადგან ამ ძებნის მეთოდი halves ელემენტთა რაოდენობა მას შევხედოთ თითოეული ნაბიჯი, იგი იპოვის პუნქტში იგი ეძებს დაახლოებით შესვლა რაოდენობის ელემენტი სიაში. ახლა, ჩვენ ვნახეთ 2 მაგალითები, მოდით შევხედოთ ზოგიერთი pseudocode ამისთვის რეკურსიული ფუნქცია, რომელიც ახორციელებს ორობითი ძებნა. დასაწყისი დაბრუნება, ჩვენ ვხედავთ, რომ ჩვენ უნდა მოვძებნოთ ფუნქცია, რომელიც იღებს 4 არგუმენტები: გასაღები, array, მინ და მაქს. გასაღები არის ნომერი, რომელიც ჩვენ ვეძებთ, ასე რომ 144 წელს წინა მაგალითი. Array არის სიაში ნომრები, რომ ჩვენ ძებნას. მინ და მაქს are მაჩვენებლების მინიმალური და მაქსიმალური პოზიციები რომ ჩვენ გაკეთებული ეძებს. ასე რომ, როდესაც ჩვენ ვიწყებთ, მინ იქნება ნულოვანი და max იქნება მაქსიმალური მაჩვენებელი მასივი. როგორც ჩვენ ვიწრო ძებნა down, ჩვენ განაახლებს min და max უნდა იყოს მხოლოდ დიაპაზონი, რომ ჩვენ ჯერ კიდევ ეძებს შემოსული 

მოდით გაფართოებული საინტერესო ნაწილი პირველი. პირველი, რასაც ვაკეთებთ არის იპოვოს შუაში, ინდექსი, რომ არის შუა ნაწილამდე იყვნენ შორის min და max of მასივი, რომ ჩვენ ჯერ კიდევ გათვალისწინებით. მაშინ შევხედავთ ღირებულება array იმ შუაში საიდან და თუ ნომერი, რომ ჩვენ ვეძებთ ნაკლებია გასაღები. თუ ნომერი რომ თანამდებობა ნაკლებია, მაშინ ეს ნიშნავს გასაღები აღემატება ყველა ნომრები მარცხნივ რომ პოზიცია. ასე რომ ჩვენ შეგვიძლია მოვუწოდებთ ბინარული ძებნის ფუნქცია ისევ, მაგრამ ამ დროს განახლებაზე min და max პარამეტრების წაკითხვის მხოლოდ ნახევარი რომ მეტია ან ტოლია ღირებულების ჩვენ უბრალოდ შევხედე. მეორეს მხრივ, თუ გასაღები ნაკლებია, ვიდრე ნომერი მიმდინარე შუაში მასივი, ჩვენ გვინდა წასვლა და მარცხენა იგნორირება ყველა ციფრები, რომლებიც უფრო დიდი. ერთხელ, ჩვენ მოვუწოდებთ ორობითი ძებნა მაგრამ ამ დროს სპექტრს min და max განახლება უნდა შეიცავდეს მხოლოდ ქვედა ნახევარში. თუ ღირებულება მიმდინარე შუაში მასივში არც აღემატება და არც ნაკლები გასაღები, მაშინ იგი უნდა იყოს ტოლი გასაღები. ამდენად, ჩვენ შეგვიძლია უბრალოდ დააბრუნოს მიმდინარე შუაში ინდექსი, და ჩვენ გავაკეთეთ. საბოლოოდ, ამ გამშვები აქ არის საქმე, რომ ნომერი არ არის რეალურად მასივი ნომრები ჩვენ ძებნას. თუ მაქსიმალური მაჩვენებელი დიაპაზონი, რომ ჩვენ ვეძებთ ოდესმე ნაკლები მინიმალური, რაც იმას ნიშნავს, რომ ჩვენ ძალიან შორს წავიდა. წლიდან ნომერი არ იყო შეყვანის მასივი, ვბრუნდებით -1 მიუთითოს, რომ არაფერი იქნა ნაპოვნი. 

თქვენ შეიძლება არ შეამჩნია, რომ ამ ალგორითმის მუშაობის, სიაში ნომრები უნდა იყოს დახარისხებული. სხვა სიტყვებით, ჩვენ შეგვიძლია მხოლოდ იპოვოს 144 გამოყენებით ორობითი ძებნა თუ ყველა ციფრები დავალება ყველაზე დაბალი უმაღლესი. თუ ეს არ იყო შემთხვევაში, ჩვენ ვერ გამორიცხავს ნახევარში ციფრები ყოველ ნაბიჯს. ამიტომ ჩვენ გვაქვს 2 ვარიანტი. ან ჩვენ შეუძლია არასორტირებული სიაში და დასალაგებლად ეს ადრე გამოყენებით ორობითი ძებნა, ან შეგვიძლია დავრწმუნდეთ, რომ სიაში ნომრები დალაგებულია როგორც ჩვენ დაამატოთ ნომრები მას. ამდენად, ნაცვლად დახარისხება უბრალოდ, როცა ჩვენ უნდა მოძებნოს, რატომ არ შეინახოთ სია დალაგებულია ნებისმიერ დროს? 

ერთი გზა შენარჩუნება სიაში ნომრები დახარისხებული და ამავდროულად რომელიც საშუალებას ერთი დამატება ან გადაადგილება ციფრები ამ სიაში არის გამოყენებით რაღაც მოუწოდა ორობითი ძებნა ხე. ორობითი ძებნა ხე მონაცემები სტრუქტურა, რომელსაც აქვს 3 თვისებები. პირველი, მარცხენა subtree ნებისმიერი კვანძის შეიცავს მხოლოდ ღირებულებები, რომლებიც ნაკლები ან ტოლია კვანძის ღირებულების. მეორე, მარჯვენა subtree of node შეიცავს მხოლოდ ღირებულებები რომ მეტი ან ტოლია კვანძის ღირებულების. და ბოლოს, ორივე მარცხენა და მარჯვენა subtrees ყველა კვანძების ასევე ორობითი ძებნა ხეები. მოდით შევხედოთ მაგალითად იგივე ციფრები ჩვენ გამოყენებული ადრე. მათთვის, ვინც არ მინახავს კომპიუტერულ მეცნიერებათა ხე ადრე, ნება მომეცით მიერ გეუბნებოდით, რომ კომპიუტერულ მეცნიერებათა ხე იზრდება ქვემოთ ჩასატანად. დიახ, განსხვავებით ხეები თქვენ მიჩვეული, ფესვი კომპიუტერულ მეცნიერებათა ხე ზედა, და ფოთლები ბოლოში. თითოეული პატარა ყუთი ეწოდება კვანძის და კვანძების უკავშირდება ერთმანეთს კიდეები. ასე root ამ ხე კვანძის ღირებულების ღირებულების 13, რომელსაც 2 შვილი კვანძების ღირებულებების დაცვითა 5 და 34. Subtree არის ხე, რომ იქმნება მხოლოდ ეძებს ქვეპუნქტის მთელი ხე. 

მაგალითად, მარცხენა subtree of კვანძის 3 არის ხის მიერ შექმნილი კვანძების 0, 1, და 2. ასე რომ, თუ ჩვენ დავუბრუნდებით თვისებები ორობითი ძებნა ხე, ჩვენ ვხედავთ, რომ თითოეული კვანძის in ხე შეესაბამება ყველა 3 თვისებები, კერძოდ, მარცხენა subtree მხოლოდ შეიცავს ღირებულებებს რომ ნაკლებია ან ტოლი კვანძის მისი ღირებულება; უფლება subtree ყველა კვანძების შეიცავს მხოლოდ ღირებულებები, რომლებიც მეტია ან ტოლია კვანძის ღირებულების და ორივე მარცხენა და მარჯვენა subtrees ყველა კვანძების ასევე ორობითი ძებნა ხეები. მიუხედავად იმისა, რომ ამ ხის გამოიყურება სხვადასხვა, ეს არის სწორი ორობითი ძებნა tree იმავე კომპლექტი ნომრები. როგორც ფაქტობრივად, არსებობს მრავალი შესაძლო გზები, რომ თქვენ შეგიძლიათ შექმნათ მოქმედებს ორობითი ძებნა ხე ამ ნომრებზე. კარგად, მოდით დავუბრუნდეთ პირველი შევქმენით. მერე რა ვქნათ ამ ხეები? ისე, ჩვენ შეგვიძლია ძალიან მარტივად იპოვოს მინიმალური და მაქსიმალური ღირებულებებს. მინიმალური ღირებულებების შეიძლება მოიძებნოს მიერ ყოველთვის აპირებს მარცხენა სანამ არ არსებობს უფრო კვანძების ეწვევა. პირიქით, იპოვოს მაქსიმუმ ერთ უბრალოდ უბრალოდ მიდის ქვემოთ უფლება ყოველ ჯერზე. 

Finding ნებისმიერი სხვა ნომრით, რომელიც არ არის მინიმალური და მაქსიმალური ისეთივე ადვილი. Say ჩვენ ვეძებთ ნომერი 89. ჩვენ უბრალოდ შეამოწმოს ღირებულება თითოეული კვანძის, გადადით მარცხნივ ან მარჯვნივ, დამოკიდებულია თუ არა კვანძში ს მნიშვნელობა ნაკლებია ან მეტი ერთი ჩვენ ვეძებთ. ასე რომ, დაწყებული ფესვი 13, ჩვენ ვხედავთ, რომ 89 მეტია, და ამიტომ ჩვენ წასვლა უფლება. მაშინ ჩვენ ვხედავთ კვანძის ამისთვის 34, და ისევ ჩვენ წასვლა უფლება. 89 ჯერ კიდევ აღემატება 55, ჩვენ გავაგრძელებთ აპირებს უფლება. ჩვენ მაშინ ამუშავება კვანძის ერთად ღირებულება 144, გადადით მარცხნივ. Lo და აჰა, 89 არის უფლება არსებობს. 

სხვა საქმეა, რომ ჩვენ შეგვიძლია გავაკეთოთ არის ბეჭდვის ყველა ნომრები მიერ საშემსრულებლო inorder გასვლის. Inorder გასვლის საშუალება ბეჭდვა ყველაფერი გარეთ მარცხენა subtree მოჰყვა ბეჭდვა კვანძის თავად და მოყვა ბეჭდვის ყველაფერს სწორი subtree. მაგალითად, ავიღოთ ჩვენი საყვარელი ორობითი ძებნა tree და ამობეჭდოთ ნომრები დახარისხებული მიზნით. ჩვენ იწყება ფესვი 13, მაგრამ სანამ ბეჭდვა 13 ჩვენ უნდა ამობეჭდოთ ყველაფერი მარცხენა subtree. ამიტომ, ჩვენ წასვლა 5. ჩვენ კვლავ უნდა წავიდეს უფრო ღრმა ქვემოთ ხე სანამ ჩვენ მარცხენა საუკეთესო კვანძის, რაც ნულოვანი. შემდეგ ბეჭდვა ნულოვანი, ჩვენ დავბრუნდებით მდე 1 და ბეჭდვა, რომ. მაშინ ჩვენ წასვლა უფლება subtree, რომელიც 2, და ბეჭდვა, რომ. არის, რომ ჩვენ გაკეთდეს, რომ subtree, ჩვენ შეგვიძლია დავუბრუნდეთ მდე 3 და ამობეჭდოთ. გრძელდება უკან, ჩვენი ბეჭდვა 5 და შემდეგ 8. არის, რომ ჩვენ დასრულდება მთელი დაუტოვებიათ subtree, ჩვენ შეგვიძლია ამობეჭდოთ 13 და დაიწყოს მუშაობა უფლება subtree. ჩვენ hop ქვემოთ 34, მაგრამ სანამ ბეჭდვა 34 ჩვენ უნდა ამობეჭდოთ მისი მარცხენა subtree. ამიტომ, ჩვენ ამობეჭდოთ 21; მაშინ მივიღებთ რომ ამობეჭდოთ 34 და მოინახულოს თავისი უფლება subtree. მას შემდეგ, რაც 55 ვიზიტორების მარცხენა subtree, ჩვენ ამობეჭდოთ და გაგრძელდება მისი უფლება subtree. 144 აქვს მარცხენა subtree, და ამიტომ ჩვენ ამობეჭდოთ 89, რასაც მოჰყვა 144, და ბოლოს მარჯვენა საუკეთესო კვანძის of 233. არსებობს მოგეცათ, ყველა ნომრები იბეჭდება წელს ბრძანება ყველაზე დაბალი უმაღლესი. 

დამატება რაიმე ხე შედარებით უმტკივნეულო ისევე. ყველა ჩვენ უნდა გააკეთოთ დარწმუნდით, რომ მივყვებით 3 ორობითი ძებნა ხე თვისებები და შემდეგ ჩადეთ ღირებულება სადაც სივრცეში. ვთქვათ გვინდა ჩადეთ ღირებულება 7. მას შემდეგ, რაც 7 ნაკლებია, ვიდრე 13, ჩვენ გადადით მარცხნივ. მაგრამ მეტი 5, ამიტომ ჩვენ traverse მარჯვნივ. რადგან არანაკლებ 8 და 8 არის ფოთოლი კვანძში, დავუმატებთ 7 მარცხნივ ბავშვი 8. Voila! ჩვენ დასძინა ხმების ჩვენი ორობითი ძებნა ხე. 

თუ ჩვენ შეგიძლიათ დაამატოთ რამ, ჩვენ უკეთესი შეძლებთ წაშალოთ რამ ისევე. სამწუხაროდ ჩვენთვის, წაშლის არის ცოტა უფრო რთული - არ ბევრად, მაგრამ ცოტა. არსებობს 3 სხვადასხვა სცენარი, რომ ჩვენ უნდა განიხილოს წაშლის ელემენტების ბინარული ძებნის ხეები. პირველი, უმარტივეს შემთხვევაში ის არის, რომ ელემენტი ფოთოლი კვანძში. ამ შემთხვევაში, ჩვენ უბრალოდ წაშლის მას და წასულიყვნენ ჩვენს ბიზნესში. Say გვინდა წაშლა 7 რომ ჩვენ უბრალოდ დასძინა მან. ასევე, ჩვენ უბრალოდ ის, ამოიღონ, და ამით ყველაფერი მთავრდება. შემდეგი შემთხვევაში არის თუ კვანძის აქვს მხოლოდ 1 ბავშვი. აქ შეგიძლიათ წაშალოთ კვანძში, მაგრამ ჩვენ პირველი უნდა დავრწმუნდეთ, დაკავშირება subtree რომ არის დაუტოვებიათ უპატრონო to მშობელი კვანძი ჩვენ უბრალოდ მკვდარია. Say გვინდა წაშლა 3 ჩვენი ხე. ჩვენ ვიღებთ ბავშვის ელემენტს, რომ კვანძის და დაურთოს მშობელი კვანძი. ამ შემთხვევაში, ჩვენ ახლა ვამაგრებ 1 დან 5. ეს მუშაობს უპრობლემოდ, რადგან ჩვენ ვიცით, შესაბამისად ორობითი ძებნა ხე ქონება, რომ ყველაფერი მარცხენა subtree 3 ნაკლები იყო 5. ახლა, 3 ს subtree არის აღებული ზრუნვა, ჩვენ შეგვიძლია წაშლა. მესამე და საბოლოო საქმე ყველაზე რთული. ეს ის შემთხვევაა, როცა კვანძის გვინდა წაშლა ჰყავს 2 შვილი. იმისათვის, რომ გააკეთებს, ჩვენ პირველი უნდა მოვძებნოთ კვანძში, რომელსაც აქვს შემდეგი უმსხვილესი ღირებულება, სვოპ ორი და შემდეგ წაშლა კვანძის კითხვა. გაითვალისწინეთ კვანძში, რომელსაც აქვს შემდეგი უმსხვილესი ღირებულება არ შეიძლება 2 შვილი თავად რადგან მისი მარცხენა ბავშვი იქნებოდა უკეთესი კანდიდატი შემდეგი უმსხვილეს. ამიტომ, წაშლის კვანძის ერთად 2 შვილი შეადგენს შევცვალე 2 კვანძების, და მერე წაშლის არის სიფრთხილით მიერ 1 of 2 აღნიშნული წესები. მაგალითად, ვთქვათ გვინდა წაშლა ძირეული კვანძის, 13. პირველი, რასაც ვაკეთებთ არის ჩვენ მომავალი უდიდესი მნიშვნელობა ხე რაც, ამ შემთხვევაში, არის 21. ჩვენ მაშინ სვოპ 2 კვანძების, რაც 13 ფოთოლი და 21 ცენტრალური ჯგუფი კვანძში. ახლა ჩვენ უბრალოდ წაშლა 13. 

როგორც გააკეთა მინიშნება ადრე, არსებობს მრავალი შესაძლო გზები, რათა სწორი ორობითი ძებნა ხე. სამწუხაროდ ჩვენთვის, ზოგი უარესი, ვიდრე სხვები. მაგალითად, რა ხდება, როდესაც ჩვენ ვაშენებთ ორობითი ძებნა tree საწყისი დახარისხებული სიის ნომრების? ყველა ციფრები უბრალოდ დაემატა უფლება თითოეულ ნაბიჯს. როდესაც ჩვენ გვინდა მოძებნოთ ნომერი, ჩვენ არ გვაქვს არჩევანი, მაგრამ მხოლოდ შევხედოთ უფლება თითოეულ ნაბიჯს. ეს არ არის უკეთესი, ვიდრე სწორხაზოვანი ძებნა ყველა. მიუხედავად იმისა, რომ ჩვენ არ დაფარავს მათ აქ, არსებობს სხვა, უფრო რთული, მონაცემები სტრუქტურები, რომ დავრწმუნდეთ, რომ ეს არ მოხდეს. თუმცა, ერთი მარტივი რამ, რომ შეიძლება გაკეთდეს, რათა თავიდან ავიცილოთ ეს უბრალოდ შემთხვევით shuffle შეყვანის ღირებულებები. ეს ძალზედ ნაკლებად სავარაუდოა, რომ შემთხვევითი შანსი აჩეხვა სიაში ნომრები დალაგებულია. თუ ეს იყო შემთხვევაში, სამორინედან არ დარჩება ბიზნეს ხანგრძლივი. 

არსებობს მოგეცათ. თქვენ ახლა უკვე იცის დაახლოებით ორობითი ძიება და ბინარული ძებნის ხეები. მე პატრიკ შმიდი, და ეს არის CS50. [CS50.TV] ერთი აშკარა გზა იქნებოდა სკანირებას სიის ... [beep] ... ელემენტთა რაოდენობა ... yep [იცინის] პოსტი ... კვანძის of 234 ... augh. >> YAY! ეს იყო -