სიღრმე-პირველი vs სიგანე – პირველი ძიება

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

რა არის ხე?

ხე არის კოდებისგან შემდგარი მონაცემთა სტრუქტურა, რომელიც შეიცავს სხვა კვანძებამდე მითითებულ წერტილებს. რეალურ ცხოვრებაში ხეებისგან განსხვავებით (ან იქნებ ისინი სადმე არსებობდნენ), მონაცემთა ხე თავდაყირაა. არსებითად, ფესვი ზედა ნაწილშია, ხოლო ფოთლები ბოლოში.

მოდით განვსაზღვროთ დიაგრამა.

ყველა ხეს აქვს ერთი ფესვის კვანძი, რომელიც ზედა დონეზეა (ამ შემთხვევაში, დონე 0). შემდეგ ჩვენ ვხედავთ, რომ შემდეგ ეტაპზე, root კვანძს A აქვს წერტილები კვანძებამდე B და C. ანალოგიურად, კვანძებს B და C აქვთ წერტილები კვანძთან A. ამ სიტუაციაში, კვანძი A არის მშობლის კვანძი, ხოლო კვანძები B და C არიან. მისი შვილები. გარდა ამისა, კვანძები B და C ითვლება ძმა.

თქვენ შეიძლება გაინტერესოთ, შესაძლებელია თუ არა კვანძს 2-ზე მეტი შვილი ჰყავდეს. პასუხი დიახ! ეს სპეციფიკური გამოსახულება არის ორობითი ხე, რომელიც შეიძლება განისაზღვროს მაქსიმუმ ორი ბავშვის კვანძით თითოეული მშობლისთვის.

ხის კოდი

უარი პასუხისმგებლობა: მე Javascript- ს ვიყენებ მარტივი ხის შესაქმნელად!

პირველ რიგში, ჩვენ უნდა შევქმნათ კვანძის კლასი:

როდესაც ჩვენ ვქმნით კვანძის კლასს, ჩვენ გადავცემთ მას მნიშვნელობას, ანუ მონაცემებს, რომელიც ხდება კვანძის მონაცემთა საკუთრება. ჩვენ ასევე გვაქვს მშობლებისა და შვილების თვისებები, რომლებიც null და ცარიელი მასივია, შესაბამისად, ამჟამად. საბოლოოდ, მშობლის საკუთრება მიუთითებს კონკრეტული კვანძის მშობელზე და შვილების საკუთრება მიუთითებს კვანძის შვილებზე.

შემდეგ, ჩვენ ვქმნით ხის კლასს:

ხის კლასი შეიცავს ერთ ქონებას, ფესვს, რომელიც თავდაპირველად ნულიანია. ხეები მოიცავს პროტოტიპის მეთოდებს, როგორიცაა (()), ჩასმა () და ამოღება (), მაგრამ ჩვენ მათ გადავარჩენთ წვიმიანი დღისთვის!

ეძებს!

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

სიღრმე-პირველი მიდგომა

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

ძებნა დავალება: [10, 4, 1, 9, 17, 12, 18]

კოდი

სიღრმისეული ძებნის მნიშვნელობას წარმოადგენს არგუმენტი, რომელიც წარმოადგენს მნიშვნელობას, რომელსაც ხეში ვეძებთ. მას შემდეგ, რაც გვსურს კვანძების გადალახვა მარცხნიდან მარჯვნივ, ჩვენ ვაყენებთ ძირს, როგორც დასტას, რადგან გვინდა, რომ უკანასკნელად მივიღოთ პირველი. შემდეგ ჩვენ ვასრულებთ ხანგძლივ მარყუჟს, რომელიც გრძელდება მანამ, სანამ დასტის შემადგენელი ელემენტებია. ხოლო მარყუჟის შიგნით, ჩვენ ამოიღეთ დასტის პირველი ელემენტი, ან ვეძახით shift () მასივის მეთოდს და ვადგენთ მას კვანძის ტოლფასი. ჩვენ ვადარებთ ამ კვანძის მონაცემებს არგუმენტის მნიშვნელობას და თუ ისინი შეესაბამება, ფუნქცია ბრუნდება ნამდვილ. თუ ეს ასე არ არის, ის დასძენს კვანძის შვილებს დასტის წინა მხარეს, ან უწოდებს არათანაბარი () მასივის მეთოდით და აგრძელებს ძიებას ახალი მონაცემების საშუალებით. თუ კონკრეტული მნიშვნელობა არ არსებობს ხეში, ფუნქცია ყალბდება.

სიგანე-პირველი მიდგომა

სიგანის პირველი მიდგომა იწყება ძირის კვანძში და გადის თითოეულ თანმიმდევრულ დონეზე, სასურველი კვანძის მოსაძებნად. სიღრმე-პირველი მიდგომის მსგავსად, კვანძები იკითხება თითოეულ დონეზე მარცხნიდან მარჯვნივ.

ძებნა დავალება: [10, 4, 17, 1, 9, 12, 18]

კოდი

სიგანის პირველი ძებნა მსგავსია კოდის სიღრმისეული ძებნისათვის. იგი იღებს მნიშვნელობას, როგორც არგუმენტი. აქ განსხვავება ისაა, რომ დასტის გამოყენების ნაცვლად, გვსურს, რომ რიგს გამოვიყენოთ, რომ შევძლოთ პირველი და პირველი მიდგომის გაკეთება. ხოლო მარყუჟში, სიღრმისეული ძებნის ანალოგიურად, გვსურს გამოვიყენოთ ცვლა () მასივის მეთოდი, რიგის პირველი ელემენტის კვანძის ამოღების მიზნით. ამასთან, თუ კვანძის მონაცემები არ არის იგივე, რაც სასურველია, კვანძის შვილების შეცვლის ნაცვლად, ჩვენ გამოვიყენებთ push () მასივის მეთოდით, რომ ბავშვებს დავამატოთ რიგში. ეს საშუალებას გვაძლევს გადავამოწმოთ ყველა კვანძი ერთ დონეზე, სანამ კვანძების გავლა შემდეგ ეტაპზე. დაბოლოს, ისევე, როგორც პირველი სიღრმისეული ძებნა, თუ ღირებულება ვერ მოიძებნა, ფუნქცია ცრუ დაბრუნდება.

რომელი გამოვიყენო?

მიუხედავად იმისა, რომ ორივე სიღრმისეულის (DFS) და სიგანის პირველი (BFS) ჩხრეკა ლეგიტიმური მიდგომებია და ერთსა და იმავე დასკვნამდე მიდის, თითოეული მათგანი გარკვეულ ვითარებაში ემხრობა. თუმცა, ხშირად აშკარა არაა, რომელია ამ ორიდან უფრო ეფექტური.

უარი პასუხისმგებლობაზე: ეს ზოგადი სახელმძღვანელო მითითებებია! ნამდვილად არა ყოველთვის ყველაზე ოპტიმალური მიდგომები.

DFS: ზოგადად სასურველია, როდესაც ხე ძალიან ღრმაა და სასურველი მნიშვნელობები ან მონაცემები იშვიათად ხდება.

BFS: ზოგადად უპირატესობას ანიჭებენ არაღრმა ხეებს, რომლებიც არც თუ ისე ფართოა. ასევე გამოიყენება, თუ ცნობილია, რომ სასურველი კვანძი უფრო ახლოს არის ფესვის დონეზე.

მიუხედავად იმისა, რომ არსებობს ზოგადი პრეფერენციები, თუ გადაწყვეტთ რომელი მეთოდის გამოყენებას, თუ არ ხართ დარწმუნებული, ალბათ უკეთესია სცადოთ ორივე მეთოდი და ნახოთ რომელი მათგანი უფრო ეფექტურია.

მაგალითად, ვთქვათ, რომ თქვენ იყენებთ ხეზე ზემოთ და ეძებთ კვანძს, რომელსაც შეიცავს 8. ხე არ არის ისეთი ღრმა, ასე რომ თქვენ ფიქრობთ, რომ უკეთესი იქნება გამოიყენოს BFS. ამასთან, სინამდვილეში უფრო ეფექტური იქნებოდა DFS– ის გამოყენება.

მოდით შევადაროთ ორი მეთოდი და რომელი კვანძები გაიარა:

DFS: 1, 2, 4, 8

BFS: 1, 2, 3, 4, 5, 6, 7, 8

უკვე ვხედავთ, რომ პირველი სიგანის ძებნა უფრო მეტ კვანძზე გადადის და ამიტომ საჭიროა მეტი მეხსიერების დაშვება.

გარდა ამისა, მას შემდეგ, რაც კვანძს 8 დავაფიქსირებთ, DFS დასაშვები იქნება [8, 9, 5, 3], ხოლო BFS რიგში იქნება [8, 9, 10, 11, 13, 14]. BFS რიგში მოცემულია კიდევ 2 კვანძი, რომელიც, როგორც ჩანს, ამ მაგალითში ტოლი არ არის, მაგრამ მეხსიერების თვალსაზრისით, იგი კვლავ მეტ რაოდენობას იყენებს. ამრიგად, ამ კონკრეტულ სიტუაციაში, DFS უფრო ეფექტური იქნება ვიდრე BFS.

მიუხედავად იმისა, რომ ეს მაგალითი მარტივი და პირდაპირია, სიტუაციებში, როდესაც ხეები უფრო ღრმა და ფართოა, ნამდვილად გაცილებით რთულია იმის დადგენა, რომელია უფრო ოპტიმალური. უკეთესი მეთოდის კარნახის საუკეთესო გზა ორივე სცადე.

სირთულე

დრო და სივრცე სირთულეებს როგორც DFS- ს, ასევე BFS- სთვის საკმაოდ მარტივია. ვინაიდან ჩვენ ვსაუბრობთ ხეზე გადასასვლელად, იმის დასადგენად, არსებობს თუ არა რაიმე მნიშვნელობა ან მონაცემი ხის შიგნით, უნდა მოვინახულოთ ყველა კვანძს. ყველა კვანძზე ერთჯერადი მონახულება ნიშნავს, რომ დროის სირთულე ორივე DFS და BFS არის O (n), ან წრფივი. თუ დავფიქრდებით ხეებზე, როგორც დალაგებულ მასივებზე, მხოლოდ ერთი დრო უნდა მოვთხოვოთ იმის დასადგენად, შეესაბამება თუ არა მნიშვნელობა ღირებულებას, რომელსაც ვეძებთ. ანალოგიურად, სივრცის სირთულის თვალსაზრისით, DFS არის O (თ) და BFS არის O (w). DFS- სთვის, ის სიმაღლეა, რადგან რამდენი ადგილი დაიკავებს ფუნქციას, დამოკიდებულია იმაზე, თუ რამდენ კვანძს წარმოადგენს ხე. ანალოგიურად, BFS- სთვის, "სიგანეა", რადგან სივრცე დამოკიდებულია იმაზე, თუ რამდენად ფართოა ხე. რა თქმა უნდა, ეს დიდი O ნოტაციები იცვლება მონაცემთა სტრუქტურის მიხედვით, მაგრამ ხეების გულისთვის, დრო და სივრცე სირთულეები იგივე იქნება.

გმადლობთ, რომ დრო დაუთმეთ ამ სტატიის წასაკითხად! თუ თქვენ გაქვთ რაიმე კავშირი ან შეკითხვა, ნება მიბოძეთ! იმედი მაქვს, რომ მშვენიერი დღე გისურვებთ!