>> [მუსიკის დაკვრა]
DOUG LLOYD: ასე რომ, ჩვენ უკვე უახლოვდებიან და უფრო ახლოს, რომ წმინდა გრაალი მონაცემები
სტრუქტურები, ერთი, რომ ჩვენ შეგვიძლია ჩადეთ შევიდა, წაშლა, და გამოიყურება
მუდმივი დროს.
უფლება.
სწორედ ერთგვარი მიზანი.
ჩვენ გვინდა, რომ იყოს ვერ გააკეთებს რამ ძალიან, ძალიან სწრაფად.
>> გვაქვს ნაპოვნია აქ, როდესაც ჩვენ ვსაუბრობთ ლელო?
ისე, მოდით შევხედოთ.
ასე რომ, ჩვენ ვნახეთ რამდენიმე სხვადასხვა მონაცემთა სტრუქტურები
რომ გაუმკლავდეს რუკების ე.წ. ძირითადი ღირებულების წყვილი,
ობიექტების გარკვეული ნაჭერი მონაცემები ზოგიერთი სხვა ნაჭერი მონაცემები
ასე რომ, ჩვენ, სად ინფორმაციის სტრუქტურა.
>> ასე მასივი, მაგალითად, გასაღები არის ელემენტს ინდექსი ან მასივი
განთავსების 0 ან მასივი 1 და ასე შემდეგ.
და მნიშვნელობა მონაცემები რომ არსებობს იმ ადგილას.
ასე რომ, რა ინახება მასივი 0?
რა ინახება მასივი 1 ჯინაზე 0 და 1, რომელიც იქნება გასაღებები.
>> ერთად hash მაგიდა ის ერთგვარი იგივე იდეა.
ერთად hash მაგიდა, ჩვენ გვაქვს ეს hash ფუნქცია, რომელიც წარმოშობს hash კოდები.
ასე რომ, გასაღები არის hash კოდი მონაცემებს.
და ღირებულება, განსაკუთრებით ჩვენ ვისაუბრეთ მიჯაჭვის
ამ ვიდეო hash მაგიდები, ის არის, რომ უკავშირდება სიაში მონაცემები
რომ ჰეშები რომ hashcode.
უფლება.
რაც შეეხება მეორე მიდგომა ეს მეთოდი, თუმცა?
რაც შეეხება მეთოდს, სადაც გასაღები არის გარანტირებული იყოს უნიკალური,
განსხვავებით hash მაგიდა, სადაც შეგვეძლო დასრულდება up ერთად ორი ცალი მონაცემები
რომელსაც იგივე hashcode.
და მაშინ ჩვენ უნდა გაუმკლავდეთ რომ არც საცდელი ან მეტი
სასურველია მიჯაჭვის დაფიქსირება, რომ პრობლემა.
>> ასე რომ, ახლა ჩვენ შეგვიძლია გაგაცნოთ ჩვენი მთავარი იქნება უნიკალური.
და რა, თუ ჩვენი ღირებულება უბრალოდ რაღაც როგორც მარტივი
როგორც ჭეშმარიტი და ცრუ რომელიც გვეუბნება, თუ არა თუ არა, რომ ინფორმაცია
არსებობს სტრუქტურა?
ლოგიკური შეიძლება იყოს როგორც მარტივი, როგორც ცოტა.
რეალურად ეს, ალბათ, byte უფრო მეტია, ვიდრე ცოტა.
მაგრამ რომ ბევრი პატარა, ვიდრე შენახვის იქნებ 50-ხასიათის ტექსტი,
მაგალითად.
>> ასე რომ, ლელო, მსგავსი hash მაგიდები, რომელიც აერთიანებს კოლექტორები და უკავშირდება სია,
ლელო გაერთიანდება მასივები, სტრუქტურები, და მითითებას
ერთად ჩაწეროთ მონაცემები საინტერესო ისე, რომ
საკმაოდ განსხვავდება არაფერი ჩვენ ვნახეთ ჯერჯერობით.
ახლა ჩვენ ვიყენებთ მონაცემების საგზაო რუკა ნავიგაცია ამ მონაცემების სტრუქტურას.
და თუ ჩვენ შეგვიძლია დაიცვას საგზაო რუკა, შევძლებთ თუ არა
დაიცვას მონაცემები თავიდან ბოლომდე, ჩვენ გამოგიგზავნით
იცით თუ არა, რომ მონაცემები არსებობს trie.
>> და თუ ჩვენ არ შეუძლია დაიცვას რუკა ეხლა იმას ნიშნავს, რომ დასრულდეს ყველა,
მონაცემები არ არსებობს.
ისევ და ისევ, გასაღებები აქ გარანტირებული უნდა იყოს უნიკალური.
ასე რომ, განსხვავებით hash მაგიდა, ჩვენ არასდროს უნდა გაუმკლავდეთ collisions აქ.
და არა ორი ცალი მონაცემები ზუსტად იგივე საგზაო რუკა
თუ ეს მონაცემები იდენტურია.
>> თუ ჩვენ ჩადეთ ჯონ, მაშინ ჩვენ მოძებნოთ იოანე.
ეს არის ორი ერთნაირი ცალი მონაცემები, უფლება, ჩვენ ვეძებთ მეშვეობით.
მაგრამ სხვა შემთხვევაში, ორი ცალი მონაცემები
გარანტირებული აქვს უნიკალური სამოქმედო გეგმა მეშვეობით ამ მონაცემების სტრუქტურას.
და ჩვენ ვაპირებთ შევხედოთ ვიზუალური ეს მხოლოდ ერთი წუთით.
>> ჩვენ ყველაფერს გავაკეთებთ ამ ცდილობს შექმნა ახალი მონაცემების სტრუქტურას,
რუკების შემდეგ გასაღები ღირებულება წყვილი.
ამ შემთხვევაში, ჩვენ არ ვაპირებთ, გამოიყენოს რაღაც მარტივია, როგორც ლოგიკური.
ჩვენ რეალურად შესანახად სიმებიანი.
და რომ სიმებიანი აპირებს იყოს სახელი უნივერსიტეტში.
>> და გასაღები იქნება წელს როდესაც, რომელიც დაარსდა.
ყველა წლის უნივერსიტეტებში ვაპირებთ, რომ ოთხი ციფრი.
ასე რომ, ჩვენ ვიყენებთ იმ ოთხი ციფრები ნავიგაცია მეშვეობით ამ მონაცემების სტრუქტურას.
და ჩვენ დავინახავთ, კიდევ ერთხელ, თუ როგორ ჩვენ გავაკეთებთ, რომ მხოლოდ მეორე.
>> ბოლოს გზა, ჩვენ დავინახავთ სახელი
უნივერსიტეტის, რომელიც შეესაბამება რომ გასაღები, იმ ოთხი ციფრი.
ძირითადი იდეა უკან trie ჩვენ გვაქვს ცენტრალური მარშრუტის.
ასე რომ, ვფიქრობ, რომ, როგორც ხე.
და ეს არის მსგავსი მართლწერა და კონცეფცია ხე.
საერთოდ, როდესაც ჩვენ ვიფიქროთ ხეები რეალურ სამყაროში,
მათ აქვთ ფესვი, რომელიც არის ადგილზე და მოყავთ ზევით
და მათ აქვთ ფილიალები და მათ აქვთ ფოთლები.
და ძირითადად იდეა trie არის ზუსტად იგივე,
გარდა იმისა, რომ root უძღვება სადღაც ცაში.
და ფოთლები ბოლოში.
>> ასე რომ, ეს სახის როგორც აღების ხე და უბრალოდ flipping ეს თავდაყირა.
მაგრამ ჯერ კიდევ არსებობს ფილიალში.
და იმ იქნება ჩვენი გზა, ეს იქნება ჩვენი კავშირები
ძირი ფოთლები.
ამ შემთხვევაში, იმ ბილიკები, იმ ფილიალი
იარლიყით ერთად ციფრები, რომ გვითხრათ რომელი გზით წახვიდე, სადაც ჩვენ ვართ.
>> თუ ჩვენ ვხედავთ 0 ვეშვებით ამ ფილიალი, თუ ჩვენ ვხედავთ 1 ვეშვებით ამ ფილიალი,
და ასე და ასე შემდეგ.
ისე, რას ნიშნავს ეს?
ისე, ეს ნიშნავს, რომ ყოველ გადაკვეთაზე წერტილი
და ყველა კვანძის შუა და ყველა ფილიალში,
არსებობს 10 შესაძლო ადგილებში, რომ ჩვენ შეგვიძლია წავიდეთ.
ასე რომ, არსებობს 10 მითითებას ყველა ადგილმდებარეობა.
>> ეს არის სადაც ლელო შეგიძლიათ მიიღოთ ცოტა დაშინებას ვინმეს
ვინ არის ამჯამად არ აქვს ბევრი გამოცდილება კომპიუტერულ მეცნიერებათა ადრე.
მაგრამ ლელო მართლაც საკმაოდ გასაოცარია.
და თუ თქვენ გაქვთ შანსი, რომ მათთან მუშაობა
და თქვენ მზად იჭრება-in და ექსპერიმენტი მათ,
ისინი მართლაც საკმაოდ საინტერესო მონაცემთა სტრუქტურების მუშაობა.
თუ გვინდა, რომ ჩადეთ ელემენტს შევიდა trie, ყველა ჩვენ უნდა გავაკეთოთ
აშენება სწორი გზა ძირი ფოთოლი.
აი რა ყველა ნაბიჯი გასწვრივ გზა შეიძლება გამოიყურებოდეს.
ჩვენ ვაპირებთ, რომ განსაზღვროს ახალი მონაცემების სტრუქტურა ახალი კვანძის მოუწოდა trie.
>> და შიგნით რომ მონაცემები სტრუქტურა არსებობს ორი ცალი.
ჩვენ ვაპირებთ, რომ შესანახად სახელი უნივერსიტეტში.
და ჩვენ ვაპირებთ შესანახად მასივი პოინტერები
სხვა კვანძების იმავე ტიპის.
ასე რომ, კიდევ ერთხელ, ეს არის, რომ ერთგვარი კონცეფციის ყველგან
ჩვენ ვართ, ჩვენ 10 შესაძლო ადგილებში ჩვენ შეგვიძლია წავიდეთ.
თუ ჩვენ ვხედავთ 0 ვეშვებით ამ ფილიალში.
თუ ჩვენ ვხედავთ 1, ამ დარგის, და ასე შემდეგ და ასე შემდეგ და ასე შემდეგ.
თუ ვიტყვით, 9, ვეშვებით ამ ფილიალში.
ასე რომ, ყოველ გადაკვეთაზე წერტილი, ჩვენ შეგვიძლია წავიდეთ 10 შესაძლო ადგილებში.
ასე რომ, ყველა კვანძის უნდა შეიცავდეს 10 მითითებას სხვა კვანძების, 10 სხვა კვანძების.
>> და მონაცემები ჩვენ შენახვის არის მხოლოდ სახელწოდება უნივერსიტეტში.
მოდით ავაშენოთ trie.
მოდით ჩადეთ ორი ნივთები ჩვენს trie.
ასე რომ, ძალიან ზევით, ეს არის ჩვენი ძირეული კვანძის.
ეს არის ალბათ იქნება რაღაც თქვენ აპირებს გლობალურად აცხადებენ.
და თქვენ ვაპირებთ გლობალურად შენარჩუნება მომცეთ ამ კვანძის ყოველთვის.
>> თქვენ ვაპირებთ ამბობენ, root უდრის, და თქვენ
ვაპირებ malloc თავს trie კვანძი.
და თქვენ არასდროს შეეხოთ root ერთხელ.
ყოველ ჯერზე გსურთ დაიწყოს სანავიგაციო საშუალებით,
თქვენ მითითებული ერთი მაჩვენებელი უდრის ფესვი, როგორიცაა trav,
რომელიც არის მაგალითად მე გამოყენება ბევრ ჩემს ვიდეოები
აქ stacks და რიგები და ბმული სიები და ასე შემდეგ.
>> თქვენ შეიქმნა კიდევ ერთი მაჩვენებელი მოუწოდა trav for გასვლის.
და თქვენ იყენებთ trav ნავიგაცია მეშვეობით მონაცემთა სტრუქტურას.
ასე რომ, ვნახოთ, როგორ შეიძლება გამოიყურებოდეს.
ასე რომ, ახლა, რა ამჯამად კვანძის ჰგავს?
ისევე, როგორც ჩვენი მონაცემებით სტრუქტურა დეკლარაციაში მითითებულია,
ჩვენ სიმებიანი, რომელიც ამ შემთხვევაში არის ცარიელი.
არაფერია აქ.
>> და მასივი 10 მითითებას.
და ახლა, ჩვენ მხოლოდ 1 კვანძში ამ trie.
იქ სხვა არაფერი იყო.
ასე რომ, ყველა 10 იმ პოინტერები აღვნიშნო, რომ null.
ეს არის ის, რაც წითელი მიუთითებს.
>> მოდით ჩადეთ სიმებიანი ჰარვარდის.
მოდით ჩადეთ უნივერსიტეტის ჰარვარდის ამ trie, რომელიც
დაარსდა წელი 1636.
ჩვენ გვინდა, რომ გამოიყენოთ გასაღები, 1636, გვითხრათ, სადაც ჩვენ ვართ
აპირებს შესანახად ჰარვარდის trie.
ახლა, როგორ შეიძლება ამის გაკეთება?
>> ეს შეიძლება რაღაც მსგავსი.
ჩვენ იწყება root.
და ჩვენ ამ 10 ადგილებში ჩვენ შეგვიძლია წავიდეთ.
ძირეული ისევე, როგორც ნებისმიერი სხვა კვანძის trie.
არსებობს 10 ადგილებში ჩვენ შეგვიძლია წავიდეთ აქედან.
>> სად ჩვენ ალბათ სურთ წასვლა თუ გასაღები 1636?
იქ ნამდვილად ორი ვარიანტი.
უფლება.
ჩვენ შეგვიძლია ავაშენოთ გასაღები მარჯვნიდან მარცხნივ და იწყება 6.
ან ჩვენ შეგვიძლია ავაშენოთ გასაღები მარცხნიდან მარჯვნივ და იწყება 1.
>> ეს, ალბათ, უფრო ინტუიციური, როგორც ადამიანის
უნდა გვესმოდეს, რომ ჩვენ უბრალოდ დაუტოვებიათ მარჯვნივ.
ასე რომ, თუ მინდა ჩადეთ ჰარვარდის ამ trie,
მე, ალბათ, მინდა, რომ დაიწყოს დაწყებული root,
შევხედავთ ჩემი 10 ვარიანტი ჩემს წინ, და განაცხადა,
მე მინდა, რომ დაცემას 1 გზას.
OK.
>> ახლა, 1 გზა არის გაკეთებული null.
ასე რომ, თუ გსურთ გაგრძელება ქვემოთ რომ გზა ჩადეთ ამ ელემენტის trie,
მე უნდა malloc ახალი კვანძის, 1 აღვნიშნო, და მაშინ მე კარგი წასვლა.
>> ამიტომ, მე ძირითადად ვარ საათზე სადაც მე ვდგავარ
ერთი ძირი ხე ან trie და არსებობს 10 ფილიალში.
მაგრამ თითოეული ფილიალი აქვს კარების წინ.
უფლება.
იმის გამო, რომ იქ სხვა არაფერი არსებობს.
არარის უსაფრთხო გადასასვლელი.
ეს იმას ნიშნავს, რომ არაფერი ქვემოთ ნებისმიერი იმ ფილიალში.
თუ მინდა, რომ დაიწყოს შენობა რაღაც, მინდა ამოიღონ კარიბჭე.
მინდა ამოიღონ კარიბჭე თვალწინ ნომერი 1.
და მე მინდა ფეხით ქვემოთ რომ.
და მინდა აშენება სხვა ადგილი მე წასვლა.
>> და რომ ის, რასაც მე ვაკეთებ აქ.
ასე რომ 1 აღარ მიუთითებს null.
მე განაცხადა, რომ ეს უსაფრთხო დაცემას აქ არის.
მე აგებული სხვა კვანძის.
და როდესაც მე, რომ კვანძის, მე გვაქვს კიდევ ერთი გადაწყვეტილება.
სად ვარ მე ვაპირებ წავიდეთ აქედან?
>> ისე, მე უკვე წავიდა ქვემოთ 1.
ასე რომ, ახლა მე ალბათ მინდა ქვევით 6.
უფლება.
ისევ და ისევ, მე მაქვს 10 ადგილას შემიძლია აირჩიოს.
მოდით ახლა დაცემას 6.
ასე რომ, მე გარკვევა კარიბჭე თვალწინ 6.
მე ფეხით ქვემოთ.
და მე აშენება სხვა კვანძის.
და მე მიაღწია მეორე გადაკვეთაზე წერტილი.
>> ერთხელ, მაქვს 10 არჩევანი სად შემიძლია წასვლა.
მე გადავიდა 1-დან 6.
ასე რომ, ახლა მე, ალბათ, მინდა წასვლა 3.
3, იქ არსად შემიძლია წასვლა.
ასე რომ, მე უნდა გარკვევა გზა და ავაშენოთ თავს ახალ სივრცეში.
და მაშინ 3, სადაც არ მინდა წასვლა?
მე მინდა ქვევით 6.
>> და, კიდევ ერთხელ, მე მქონდა გარკვევა გზა ამის გაკეთება.
ასე რომ, ახლა მე გამოიყენება ჩემი გასაღები ჩადეთ შექმნა კვანძების და დაიწყოს აშენება ამ trie.
მე დაიწყო ძირეული.
მე წავიდა ქვემოთ 1636.
და ახლა მე ბოლოში იქ რომ კვანძის.
და თქვენ შეძლებთ ვხედავ, რომ თქვენს ეკრანზე.
>> ეს მონიშნულია ყვითელი.
სწორედ იქ, სადაც მე გაკეთებული ვარ.
ჩემი გასაღები კეთდება.
მე ამოწურა ყველა პოზიცია ჩემი გასაღები.
ასე რომ, მე არ შემიძლია რაიმე.
ასე რომ, ამ ეტაპზე, ყველა მე ნამდვილად უნდა გავაკეთოთ ამბობენ, OK.
ეს არის სახის მოსწონს ეძებს ქვემოთ ადგილზე,
თუ თქვენ ითვალისწინებდა თავს, როგორც ეს ერთგვარი გზა
სხვადასხვა კავშირები.
დალაგება ეძებს ქვემოთ და სახის spray ფერწერა ჰარვარდის ადგილზე.
ეს არის ის, სახელი ამ.
ვიცი, რომ ის, რაც ამ ადგილას.
თუ ჩვენ იწყება root და ვეშვებით 1 და შემდეგ 6 და შემდეგ 3 და შემდეგ 6,
სად ვართ ჩვენ?
კარგად თუ დავაკვირდებით, ქვემოთ და ჩვენ ვხედავთ, ჰარვარდის, მაშინ
ჩვენ ვიცით, რომ ჰარვარდის დაარსდა 1636 წელს საფუძველზე გზა
ჩვენ ახორციელებს ამ მონაცემების სტრუქტურას.
ასე რომ, იმედია პირდაპირი.
ჩვენ ვაპირებთ, რომ კიდევ ორი ​​ჩანართები.
და იმედია ეს დაეხმარება იხილეთ ამ გაკეთდეს ორჯერ მეტი.
>> ახლა, მოდით ჩადეთ სხვა უნივერსიტეტში.
მოდით ჩადეთ Yale ამ trie.
იელის დაარსდა 1701.
ასე რომ, ჩვენ იწყება root, როგორც ყოველთვის.
და ჩვენ დავსახეთ გასვლის მაჩვენებელი.
ჩვენ ვაპირებთ, რომ გამოიყენოთ, რომ გადაადგილება მეშვეობით.
პირველი, რაც ჩვენ გვინდა წავიდეს ქვემოთ 1 გზას.
ეს არის პირველი ციფრი ჩვენი გასაღები.
საბედნიეროდ, მიუხედავად იმისა, რომ ჩვენ არ აქვს რაიმე სამუშაოს ამ დროს.
1 გზა უკვე გაწმინდეს.
მე განბაჟებული ეს ადრე, როცა იყო ჩასმა ჰარვარდის at 1636.
ასე რომ, შემიძლია უსაფრთხოდ გადავიდეს down 1 და მხოლოდ იქ.
თუ შეიძლება ქვევით 1.
>> ახლა, თუმცა, მე მინდა წასვლა 7.
მე გაწმინდეს გზა at 6.
მე ვიცი, რომ შემიძლია უსაფრთხოდ გაგრძელება ქვემოთ 6 გზას.
მაგრამ მე უნდა გააგრძელონ 7 გზას.
ასე რომ, რა უნდა გავაკეთოთ?
ისე, ისევე, როგორც ადრე, მე უბრალოდ უნდა გარკვევა კარიბჭე, გავიდნენ გზაზე,
და ავაშენოთ ახალი კვანძის 7 გზას.
როგორც ეს.
>> ასე რომ, ახლა მე გადავიდა 1 და შემდეგ 7.
და ახლა შეამჩნია, მე ერთგვარი საქართველოს ამ ახალი subbranch.
უფლება.
ყველაფერი დანარჩენი 16 , მე არ აინტერესებს.
მე არ აკეთებს 16 არაფერი.
მე ვაკეთებ 17 პერსონალი.
>> ასე რომ, ახლა 17 წლის, მაქვს ერთგვარი Blaze ახალი მარშრუტები აქ.
შემდეგი ციფრი ჩემი გასაღები არის 0.
მე აშკარად ვერ მიიღოს სადმე.
მე უბრალოდ აგებული ეს კვანძი.
ასე რომ მე ვიცი, რომ არ არსებობს ბილიკები წინ აქ.
ასე რომ, მე უნდა მიიღოს ერთ თავს.
>> ასე რომ, მე malloc ახალი კვანძის და 0 ეტაპზე.
და მაშინ კიდევ ერთხელ, მე malloc ახალი კვანძის და ერთ მომენტში არ არსებობს.
ისევ და ისევ, მე ამოწურა ჩემი გასაღები, 1701.
ასე რომ, მე გამოიყურება ქვემოთ და მე spray საღებავი Yale.
ეს არის ის, სახელი ამ კვანძში.
>> ასე რომ, ახლა თუ მე ოდესმე უნდა დაინახოს, თუ Yale არის ამ trie, მე იწყება root,
მე ქვევით 1701, და გამოიყურება ქვემოთ.
და თუ მე ვერ ვხედავ Yale spray მოხატული გადატანა ადგილზე, მაშინ
მე ვიცი, Yale არსებობს ამ trie.
მოდით გავაკეთოთ კიდევ ერთი.
მოდით ჩადეთ Dartmouth ამ trie, რომელიც დაარსდა 1769 წელს.
>> იწყება root ერთხელ.
ჩემი პირველი ციფრი ჩემი გასაღები არის 1.
თამამად შემიძლია ქვევით, რომ გზა.
რომელიც უკვე არსებობს.
შემდეგი ციფრი ჩემი გასაღები 7.
თამამად შემიძლია ქვევით, რომ გზა.
ის არსებობს, ისევე.
>> ჩემი მომავალი 6.
აქ, სადაც მე გაკეთებული ვარ ყვითელი იქ რომ შუა კვანძის,
6 ამჟამად დახურული off.
თუ მინდა წასვლა ქვემოთ რომ გზა, მე უნდა ავაშენოთ თავს.
ასე რომ, მე malloc ახალი კვანძის და 6-პუნქტიანი არსებობს.
შემდეგ, კიდევ ერთხელ, მე სროლით ახალი ბილიკების აქ.
>> ასე რომ, მე malloc ახალი კვანძის ისე, რომ რომ კვანძის გზას ნომერი 9- და მაშინ ახლა
თუ მე გამგზავრება 1769, და მე ქვემოთ.
არაფერია გაკეთებული spray მოხატული არსებობს.
შემიძლია წერა Dartmouth.
და მე ჩასმული DARTMOUTH შევიდა trie.
>> ასე რომ, ჩასმა რამ შევიდა trie.
ახლა ჩვენ გვინდა მოძებნოთ ნივთები.
როგორ უნდა მოძებნოთ რამ trie?
ისე, ეს საკმაოდ ბევრი იგივე იდეა.
ახლა ჩვენ უბრალოდ გამოიყენოთ ციფრები, რომ გასაღები თუ ჩვენ შეგვიძლია ნავიგაცია ძირი
სადაც ჩვენ გვინდა, რომ წავიდეს trie.
>> თუ ჩვენ მოხვდა ჩიხი ნებისმიერ წერტილში, მაშინ ჩვენ ვიცით, რომ ელემენტს არ არსებობს
ანდა, რომ გზიდან უკვე გაწმინდეს.
თუ ჩვენ, რათა ის ყველა გზა და ბოლოს, ყველა ჩვენ უნდა გავაკეთოთ
არის გამოიყურება ქვემოთ და ვნახოთ, თუ ეს ელემენტს ჩვენ ვეძებთ.
თუ ეს არის, წარმატება.
თუ ეს ასე არ არის, ვერ.
>> მოდით ძიება ჰარვარდის ამ trie.
ჩვენ იწყება root.
და კიდევ ერთხელ, ჩვენ ვაპირებთ შექმნა გასვლის მაჩვენებელი
გავაკეთოთ ჩვენი ნაბიჯები ჩვენთვის.
ძირი ჩვენ ვიცით, რომ პირველ რიგში, ჩვენ უნდა წავიდეთ, 1
შეგვიძლია ამის გაკეთება?
დიახ, ჩვენ შეგვიძლია.
თუ უსაფრთხოდ არსებობს.
ჩვენ შეგვიძლია წავიდეთ იქ.
>> ახლა, მომდევნო რიგში, ჩვენ უნდა წავიდეთ 6.
თუ არა 6 გზა არსებობს აქ?
ჰო, ეს ასეა.
ჩვენ შეგვიძლია დაცემას 6 გზას.
ჩვენ დასრულდება მდე აქ.
>> ვერ ვეშვებით 3 გზა აქ?
ისე, როგორც ირკვევა, დიახ, არსებობს ძალიან.
და მივიღებთ 6 გზა აქ?
დიახ, ჩვენ შეგვიძლია.
>> ჩვენ არ საკმაოდ უპასუხა კითხვა ამჟამად.
არსებობს კიდევ ერთი ნაბიჯი, რომელიც ახლა
ჩვენ უნდა შევხედოთ ქვემოთ და ვნახოთ, თუ რომ სინამდვილეში
თუ ჩვენ ვეძებთ ჰარვარდის, ის არის, რომ რა ჩვენ მას შემდეგ, რაც ჩვენ გამონაბოლქვი გასაღები?
მაგალითში ჩვენ გამოყენებით აქ, განმავლობაში ყოველთვის ოთხი ციფრი.
მაგრამ თქვენ შეიძლება გამოყენებით, მაგალითად, სადაც თქვენ შენახვის ლექსიკონი სიტყვა.
>> ასე რომ, ნაცვლად, რომელმაც 10 მითითებას ჩემი ადგილმდებარეობა, ალბათ 26.
ერთი თითოეული წერილი ანბანი.
და არსებობს სიტყვები, როგორიცაა წინ, რომელიც არის subset სურათების, მაგალითად.
ასე რომ, მაშინაც კი, თუ თქვენ მიიღებთ ბოლოს გასაღები და თქვენ გამოიყურება ქვემოთ,
თქვენ არ ხედავთ რა თქვენ ეძებთ.
>> ასე, რომ თქვენ ყოველთვის უნდა კვეთენ მთელი გზა და მაშინ
თუ იყო წარმატებით შეუძლიათ traverse მთელი გზა,
შეხედეთ ქვემოთ და ამის ერთ-ერთი საბოლოო დადასტურება.
ის არის, რომ ის, რაც მე ვეძებ?
ისე, მე გამოიყურება ქვემოთ დაწყების შემდეგ ზედა და აპირებს 1636.
მე გამოიყურება ქვემოთ.
მე ვხედავ ჰარვარდის.
ასე რომ, დიახ, მე შეძლო.
რა მოხდება, თუ ის, რაც მე ვეძებ არ არის trie, თუმცა.
რა მოხდება, თუ ვეძებ Princeton, რომელიც დაარსდა 1746 წელს.
ასე რომ, 1746 ხდება ჩემი გასაღები ნავიგაცია მეშვეობით trie.
ისე, მე იწყება root.
და, პირველ რიგში, მინდა, რომ მიდის ქვემოთ 1 გზას.
შემიძლია ამის გაკეთება?
დიახ, მე არ შემიძლია.
>> შემიძლია ქვევით 7 გზა არსებობს?
ჰო, მე არ შემიძლია.
რომ არსებობს ძალიან.
მაგრამ შემიძლია ქვევით 4 გზა აქ?
ეს იგივეა სვამს კითხვას, შეუძლია მე გაგრძელება ქვემოთ რომ პატარა მოედანზე
რომ მე მონიშნულია ყვითელი?
იქ არაფერია.
უფლება.
>> არ არსებობს გზა, წინ ქვემოთ 4 გზას.
თუ Princeton იყო ამ trie, რომ 4 არ გაიწმინდა ჩვენთვის უკვე.
ასე რომ, ამ ეტაპზე ჩვენ ჩიხში.
ჩვენ არ შეგვიძლია რაიმე.
ასე რომ, შეიძლება ითქვას, საბოლოოდ, არ.
პრინსტონის არ არსებობს ამ trie.
>> ასე რომ, რას ნიშნავს?
უფლება.
არსებობს ბევრი ხდება აქ.
არსებობს მითითებას მთელი ადგილი.
და, როგორც ხედავთ მხოლოდ გრაფიკაზე,
არსებობს ბევრი კვანძების რომ რომლებიც სახის საფრენი გარშემო.
მაგრამ შეამჩნია, ყოველ დროს, ჩვენ გვინდოდა, რომ შეამოწმეთ არის თუ არა რაღაც trie,
ჩვენ მხოლოდ უნდა გაეკეთებინათ 4 გადადის.
>> ყოველ დროს, ჩვენ გვინდოდა, რომ ჩადეთ რამე trie,
ჩვენ უნდა მიიღოს 4 გადადის, შესაძლოა, mallocing რაღაცები გზაზე.
მაგრამ, როგორც ვნახეთ, როდესაც ჩვენ ჩასმული DARTMOUTH შევიდა trie,
ზოგჯერ გზას შეიძლება უკვე განუბაჟებელი ჩვენთვის.
ასე რომ, ჩვენი trie იღებს უფრო დიდი და დიდი, ჩვენ ნაკლებად მუშაობს ყოველ ჯერზე
ჩადეთ ახალი რამ იმიტომ, რომ ჩვენ უკვე
აშენდა ბევრი შუალედური ფილიალები გზაზე.
თუ ჩვენ მხოლოდ ოდესმე უნდა შევხედოთ 4 რამ, 4 არის მუდმივი.
ჩვენ ნამდვილად სახის ახლოვდება მუდმივი დრო ჩასმა
და მუდმივი დრო საძიებელი.
იდგა, რა თქმა უნდა, ის არის, რომ ამ trie, როგორც თქვენ ალბათ გითხრათ,
დიდია.
თითოეული ამ კვანძების იკავებს ბევრი სივრცეში.
>> მაგრამ ეს tradeoff.
თუ გვინდა, მართლაც სწრაფი ჩასმა, მართლაც სწრაფი წაშლის,
და მართლაც სწრაფი ძიება, ჩვენ უნდა აქვს ბევრი მონაცემები საფრენი გარშემო.
ჩვენ უნდა გათვალისწინებულია ბევრი სივრცე და მეხსიერების, რომ მონაცემები სტრუქტურა
არსებობა.
>> და ისე, რომ tradeoff.
მაგრამ როგორც ჩანს, ჩვენ შეიძლება იპოვეს იგი.
ჩვენ შეიძლება არ აღმოაჩინა, რომ წმინდა გრაალი მონაცემთა სტრუქტურები
სწრაფი ჩანართი, წაშლა, და საძიებელი.
და, შესაძლოა, ეს იქნება შესაბამისი მონაცემები სტრუქტურა
გამოყენება ნებისმიერი ინფორმაცია ჩვენ ვცდილობთ, რომ მაღაზია.
მე Doug Lloyd, ეს არის CS50.