[Powered by Google Translate] რა წარმოადგენს ყველა თქვენი ოჯახის წევრების კომპიუტერი? ჩვენ უბრალოდ გამოიყენოთ სია, მაგრამ წმინდა იერარქია აქ. 

ვთქვათ ჩვენ დაწყებული თქვენი დიდი ბებია, Alice. მას 2 ვაჟი, ბობ და თქვენი ბაბუა, ჩარლი. ჩარლი ჰყავს 3 შვილი, თქვენი ბიძა, Dave, თქვენი დეიდა, ევა, და თქვენი მამა, ფრედ. თქვენ ხართ Fred ერთადერთი შვილი. 

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

ჩვენ ვერ ვისარგებლებთ, რომ აქ, მაგრამ ჩვენ დავინახავთ მაგალითია მალე. თითოეულმა ადამიანმა წარმოდგენილია კვანძის on ხე. კვანძების შეიძლება ჰქონდეს ბავშვის კვანძების ისევე როგორც მშობელი კვანძი. ეს არის ტექნიკური თვალსაზრისით, მაშინაც კი, როდესაც გამოყენებით ხეების რამ გარდა ოჯახებს. Alice-ის კვანძის აქვს 2 შვილი და არ მშობლები, ხოლო ჩარლი მისი კვანძის ჰყავს 3 შვილი და 1 მშობელი. 

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

ორობითი ხე არის კონკრეტული ტიპის ხე, რომელშიც თითოეული კვანძის აქვს, უმეტეს, 2 შვილი. აქ არის struct of node of ორობითი ხე C. ყველა კვანძის აქვს გარკვეული მონაცემები ასოცირდება იგი და 2 მითითებას სხვა კვანძების. 

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

ორობითი ძებნა tree არის სპეციალური დავალებით ტიპის ორობითი ხე რომ საშუალებას გვაძლევს შევხედოთ ფასეულობების სწრაფად. თქვენ შეიძლება არ შეამჩნია რომ ყველა კვანძის ქვემოთ ფესვი ხე არის root სხვა ხე, რომელსაც ეწოდება "subtree. ' აქ ფესვი ხე 6, და მისი შვილი, 2, არის ფესვი subtree. 

In ორობითი ძებნა tree ყველა ღირებულებებს კვანძის უფლება subtree მეტი კვანძის ღირებულების. აქ: 6. ისე, ღირებულებების კვანძის მარცხენა subtree ნაკლებია კვანძის ღირებულების. თუ ჩვენ გვჭირდება გაუმკლავდეს დუბლიკატი ღირებულებების, ჩვენ შეგვიძლია შევცვალოთ ან იმ to loose უთანასწორობა, რაც იმას ნიშნავს, იდენტური ღირებულებებს შეიძლება დაეცემა ან მარცხენა ან მარჯვენა, სანამ ჩვენ თანმიმდევრული ამის შესახებ მასშტაბით. ეს ხე არის ორობითი ძებნა tree რადგან ეს შემდეგნაირად ამ წესებს. 

ეს არის, თუ როგორ გამოიყურება თუ გადავედით ყველა კვანძების შევიდა C structs. გაითვალისწინეთ, რომ თუ ბავშვი არის დაკარგული, კურსორი არის null. როგორ შეამოწმეთ, რომ 7 არის ხე? ჩვენ იწყება root. შვიდი მეტია 6 ასე რომ, თუ ეს წელს ხე, ეს უნდა იყოს სწორი. მაშინ იგი ნაკლებია, ვიდრე 8, ასე რომ უნდა დაუტოვებიათ. აქ, ჩვენ მოვნახეთ 7. ახლა, ჩვენ შევამოწმოთ 5. ხუთი ნაკლებია, ვიდრე 6, ასე რომ უნდა იყოს მარცხნივ. ხუთი მეტია 2, ასე რომ უნდა იყოს უფლება, და ისიც აღემატება 4, ასე რომ უნდა იყოს უფლება კვლავ. თუმცა, არ არსებობს ბავშვი აქ. კურსორი არის null. ეს ნიშნავს, რომ 5 არ არის ჩვენი ხე. 

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

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

როგორ სწრაფად ხართ ოპერაციების ორობითი ძებნა ხე? გახსოვდეთ, რომ Bigohnotation ცდილობს უზრუნველყოს ზედა შეკრული. ყველაზე ცუდ შემთხვევაში, ჩვენი ხე უბრალოდ იყოს დაკავშირებული სია რაც იმას ნიშნავს, რომ Insertion, წაშლის, და ძებნა შეეძლო დროის პროპორციული რაოდენობის კვანძების ხე. ეს არის O (N). 

მაგალითად, შემდეგ არის სწორი ორობითი ძებნა ხე. თუმცა, თუ ჩვენ ვცდილობთ ვიპოვოთ 9, ჩვენ უნდა traverse ყველა კვანძში. არავისთვის არ არის უკეთესი, ვიდრე უკავშირდება სიაში. იდეალურ შემთხვევაში, ჩვენ გვინდა ყველა კვანძის ჩვენი ორობითი ძებნა ხე აქვს 2 შვილი. ეს გზა, Insertion, წაშლა და ძებნა მიიღებს, ზე უარესი, O (შესვლა n) დრო. ხე საწყისი ადრე შეიძლება უფრო დაბალანსებული, მოსწონს ეს. ახლა, ეძებს up ნებისმიერი მნიშვნელობა იღებს, უმეტეს, 3 ნაბიჯები. ეს ხე არის დაბალანსებული, მნიშვნელობა, რომელიც აქვს მინიმალური სიღრმე შედარებით ხმების კვანძების. 

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

ჩემი სახელი არის Bannus ვან დერ Kloot. ეს არის CS50.