>> [เล่นเพลง]
DOUG LLOYD: ดังนั้นเราได้รับอีกนิดใกล้ชิด และใกล้ชิดที่ศักดิ์สิทธิ์ grail ของข้อมูล
โครงสร้างหนึ่งที่เราสามารถแทรก เข้าไปลบจากและเงยหน้าขึ้นมอง
ในเวลาคง
ขวา
นั่นคือการจัดเรียงของเป้าหมาย
เราต้องการที่จะสามารถที่จะทำ สิ่งมากอย่างรวดเร็ว
>> เราได้พบได้ที่นี่เมื่อ เรากำลังพูดถึงพยายาม?
ดีให้มาดู
ดังนั้นเราจึงได้เห็นหลาย ๆ โครงสร้างข้อมูลที่แตกต่างกัน
ที่จัดการการทำแผนที่ของ ที่เรียกว่าคู่ค่าคีย์,
การทำแผนที่ชิ้นส่วนของข้อมูลบางส่วน บางส่วนชิ้นส่วนอื่น ๆ ของข้อมูล
ดังนั้นเราจึงทราบว่าจะหา ข้อมูลในโครงสร้าง
>> ดังนั้นสำหรับอาร์เรย์เช่น ที่สำคัญคือดัชนีองค์ประกอบหรืออาร์เรย์
สถานที่ 0 หรืออาร์เรย์ 1 และอื่น ๆ
และมีค่าเป็นข้อมูล ที่มีอยู่ในสถานที่นั้น
ดังนั้นสิ่งที่จะถูกเก็บไว้ในอาร์เรย์ 0?
สิ่งที่ถูกเก็บไว้ในอาร์เรย์ 1 เมื่อเทียบกับเพียง 0 และ 1 ซึ่งจะเป็นกุญแจ
>> ด้วยตารางแฮชมัน การเรียงลำดับของความคิดเดียวกัน
ด้วยตารางแฮชเรามีกัญชานี้ ฟังก์ชั่นที่สร้างรหัสกัญชา
ดังนั้นที่สำคัญคือรหัสกัญชาของข้อมูล
และความคุ้มค่าโดยเฉพาะอย่างยิ่ง เราได้พูดคุยเกี่ยวกับการผูกมัด
ในวิดีโอบนตารางแฮช, คือรายการที่เชื่อมโยงข้อมูล
ที่ hashes เพื่อ hashcode ที่
ขวา
สิ่งที่เกี่ยวกับวิธีการอื่น วิธีการนี​​้ว่า?
สิ่งที่เกี่ยวกับวิธีการที่เป็น สำคัญคือการรับประกันว่าจะไม่ซ้ำกัน
ซึ่งแตกต่างจากตารางแฮชที่เราจะทำได้ จบลงด้วยสองชิ้นของข้อมูล
มี hashcode เดียวกัน
และจากนั้นเราต้องจัดการกับ ว่าด้วยการอย่างใดอย่างหนึ่งหรือมากกว่าละเอียด
โดยเฉพาะอย่างยิ่งผูกมัดในการแก้ไขปัญหาที่
>> ดังนั้นตอนนี้เราสามารถรับประกันได้ ที่สำคัญของเราจะไม่ซ้ำกัน
และสิ่งที่ถ้าค่าของเราคือ บางสิ่งบางอย่างเพียงเป็นเรื่องง่าย
เป็นความจริงและเท็จที่บอกเราว่า หรือไม่ได้ชิ้นส่วนของข้อมูลที่
ที่มีอยู่ในโครงสร้างหรือไม่
แบบบูลอาจจะเป็นง่ายๆเป็นบิต
แนบเนียนก็อาจจะเป็น ไบต์จะมีโอกาสมากกว่าเล็กน้อย
แต่ที่มากมีขนาดเล็กกว่า การจัดเก็บอาจจะเป็นสตริง 50 ตัวอักษร
ตัวอย่างเช่น.
>> ดังนั้นพยายามคล้ายกับกัญชาตาราง ซึ่งรวมอาร์เรย์และรายการที่เชื่อมโยง
พยายามรวมอาร์เรย์ โครงสร้างและตัวชี้
ร่วมกันเพื่อเก็บข้อมูลใน วิธีที่น่าสนใจว่า
สวยที่แตกต่างจาก สิ่งที่เราได้เห็นเพื่อให้ห่างไกล
ตอนนี้เราจะใช้ข้อมูลตามแผนงาน เพื่อนำทางโครงสร้างข้อมูลนี้
และถ้าเราสามารถทำตาม แผนงานถ้าเราสามารถทำได้
ตามข้อมูลจาก ต้นจนจบเราจะ
ทราบว่าข้อมูลที่ ที่มีอยู่ในของ Trie
>> และถ้าเราไม่สามารถทำตามแผนที่ จากความหมายที่จะจบที่ทุกคน
ข้อมูลที่ไม่สามารถมีชีวิตอยู่
อีกครั้งกุญแจที่นี่ รับประกันว่าจะไม่ซ้ำกัน
และจึงไม่เหมือนตารางแฮชเราจะไม่เคย มีการจัดการกับการชนกันที่นี่
และไม่มีสองชิ้นของข้อมูล ได้ว่าแผนงานเดียวกัน
ยกเว้นในกรณีที่ข้อมูลที่เหมือนกัน
>> ถ้าเราใส่จอห์นแล้ว เราค้นหาสำหรับจอห์น
นั่นเป็นสองชิ้นที่เหมือนกันของ ข้อมูลที่ถูกต้องเรากำลังมองหาผ่าน
แต่อย่างอื่นใด สองชิ้นของข้อมูล
รับประกันว่าจะมีแผนการพัฒนาที่ไม่ซ้ำกัน ผ่านโครงสร้างข้อมูลนี้
และเรากำลังจะไปดูที่ ภาพนี้ในรอสักครู่
>> เราจะทำเช่นนี้โดยพยายามที่จะ สร้างโครงสร้างข้อมูลใหม่
การทำแผนที่คู่ค่าที่สำคัญดังต่อไปนี้
ในกรณีนี้เราจะไม่ใช้ บางสิ่งบางอย่างที่เป็นง่ายๆเป็นบูลีน
เราจริงจะเก็บสตริง
และสตริงที่เป็นไปได้ เป็นชื่อของมหาวิทยาลัยที่
>> และที่สำคัญเป็นไปได้ทั้งปี เมื่อมหาวิทยาลัยที่ก่อตั้งขึ้น
ทุกปีสำหรับมหาวิทยาลัย กำลังจะเป็นตัวเลขสี่หลัก
และเพื่อให้เราจะใช้บรรดาสี่ตัวเลขไป นำทางผ่านโครงสร้างข้อมูลนี้
และเราจะเห็นอีกครั้งว่า เราทำอย่างนั้นในเวลาเพียงสอง
>> ในตอนท้ายของเส้นทาง เราจะเห็นชื่อ
ของมหาวิทยาลัยที่สอดคล้อง การที่สำคัญที่ผู้ที่ตัวเลขสี่หลัก
ความคิดพื้นฐานหลัง Trie คือเรามีเส้นทางภาคกลาง
ดังนั้นคิดเกี่ยวกับมันเหมือนต้นไม้
และนี่คือที่คล้ายกันในการสะกดคำ และแนวความคิดกับต้นไม้
โดยทั่วไปเมื่อเราคิดเกี่ยวกับ ต้นไม้ในโลกแห่งความจริง
พวกเขามีรากที่อยู่ในที่ และพื้นดินที่พวกเขาเติบโตขึ้น
และพวกเขามีสาขา และพวกเขามีใบ
และโดยทั่วไปความคิดของ Trie คือตรงเดียวกัน
ยกเว้นรากที่ทอดส​​มอ ที่ไหนสักแห่งในท้องฟ้า
และใบอยู่ที่ด้านล่าง
>> ดังนั้นมันจึงเป็นชนิดเช่นการต้นไม้ และเพียงแค่พลิกคว่ำ
แต่ยังมีสาขา
และผู้ที่จะเป็นทางเดินของเรา ผู้ที่จะได้รับการเชื่อมต่อของเรา
จากรากจรดใบ
ในกรณีนี้ผู้ที่ เส้นทางสาขาเหล่านั้น
มีความโดดเด่นด้วยตัวเลขที่บอกเรา ซึ่งวิธีที่จะไปจากที่เรามี
>> ถ้าเราเห็น 0 เราลงไปสาขานี้ ถ้าเราเห็น 1 เราลงไปสาขานี้
และอื่น ๆ และอื่น ๆ
ดีสิ่งนี้หมายความว่าอย่างไร
ดีที่หมายความว่า ที่จุดทางแยกทุก
และโหนดในทุก กลางและทุกสาขา,
มี 10 ที่เป็นไปได้ สถานที่ที่เราสามารถไป
ดังนั้นมี 10 ตัวชี้ จากทุกสถานที่
>> และนี่คือที่พยายามจะได้รับ นิด ๆ หน่อย ๆ ที่น่ากลัวสำหรับคน
ผู้ที่ไม่ได้มีจำนวนมาก มีประสบการณ์ในด้านวิทยาศาสตร์คอมพิวเตอร์ก่อน
แต่พยายามเป็นจริงที่น่ากลัวสวย
และถ้าคุณมี โอกาสที่จะทำงานกับพวกเขา
และคุณยินดีที่จะขุดใน และการทดสอบกับพวกเขา
พวกเขากำลังจริงๆค่อนข้างน่าสนใจ โครงสร้างข้อมูลที่จะทำงานกับ
ถ้าเราต้องการที่จะแทรกองค์ประกอบ เข้า Trie ทั้งหมดที่เราต้องทำ
มีการสร้างเส้นทางที่ถูกต้อง จากรากใบ
นี่คือสิ่งที่ทุกขั้นตอนพร้อม วิธีที่อาจมีลักษณะเช่น
เรากำลังจะไปกำหนดข้อมูลใหม่ โครงสร้างโหนดใหม่ที่เรียกว่า Trie
>> และภายในของข้อมูลที่ โครงสร้างมีสองชิ้น
เรากำลังจะไปเก็บ ชื่อของมหาวิทยาลัย
และเรากำลังจะจัดเก็บ อาร์เรย์ของตัวชี้
ไปยังโหนดอื่น ๆ ของประเภทเดียวกัน
ดังนั้นครั้งนี้เป็นประเภทที่ แนวคิดของทุก
เราเป็นเราที่ 10 เป็นไปได้ สถานที่ที่เราจะไป
ถ้าเราเห็น 0 เราลงไปสาขานี้
ถ้าเราเห็น 1 สาขานี้ และอื่น ๆ และอื่น ๆ และอื่น ๆ
ถ้าเราบอก 9 เราลงไปสาขานี้
ดังนั้นที่จุดทางแยกทุก เราสามารถไปสถานที่ที่เป็นไปได้ 10
ดังนั้นทุกคนมีโหนดจะมี 10 ตัวชี้ ไปยังโหนดอื่น ๆ ถึง 10 โหนดอื่น ๆ
>> และข้อมูลที่เรากำลังจัดเก็บคือ เพียงแค่ชื่อของมหาวิทยาลัย
ดังนั้นขอสร้าง Trie
ลองใส่คู่ ของรายการลงใน Trie ของเรา
ดังนั้นที่ด้านบนมาก นี้เป็นโหนดรากของเรา
นี้อาจจะเป็นสิ่งที่ คุณกำลังจะไปทั่วโลกประกาศ
และคุณกำลังจะไปรักษาทั่วโลก ตัวชี้ไปยังโหนดนี้เสมอ
>> คุณกำลังจะบอกว่า เท่ากับรากและคุณ
จะ malloc ตัวเองโหนด Trie
และคุณไม่เคยไป สัมผัสรากอีกครั้ง
เวลาที่คุณต้องการทุก เริ่มต้นการนำทางผ่าน
คุณตั้งค่าตัวชี้อีก เท่ากับรากเช่น Trav,
ซึ่งเป็นตัวอย่างที่ผม ใช้ในหลายวิดีโอของฉัน
ที่นี่ในกองและการรอคิว และรายการการเชื่อมโยงและอื่น ๆ
>> คุณตั้งค่าตัวชี้อีก เรียกว่า Trav สำหรับการสำรวจเส้นทาง
และคุณใช้ Trav เพื่อนำทาง ผ่านโครงสร้างข้อมูล
ดังนั้นเรามาดูวิธีนี้อาจมีลักษณะ
ดังนั้นตอนนี้สิ่งที่ ไม่โหนดมีลักษณะอย่างไร
ดีเช่นเดียวกับข้อมูลของเรา ประกาศโครงสร้างระบุ
เรามีสตริงที่ ในกรณีนี้เป็นที่ว่างเปล่า
ไม่มีอะไรที่นี่
>> และอาเรย์ 10 ตัวชี้
และตอนนี้เรามีเพียง มี 1 โหนดใน Trie นี้
มีอะไรอย่างอื่นในมัน
ดังนั้นสิ่งที่ 10 ของคนเหล่านั้น ตัวชี้ชี้ไป null
นั่นคือสิ่งที่แสดงให้เห็นสีแดง
>> ลองใส่สตริงฮาร์วาร์
ลองใส่มหาวิทยาลัย ฮาร์วาร์เข้า Trie นี้ซึ่ง
ก่อตั้งขึ้นในปี 1636
เราต้องการที่จะใช้ที่สำคัญ 1636 เพื่อที่จะบอกเราว่าเรา
จะเก็บในฮาร์วาร์ของ Trie
ตอนนี้วิธีที่เราอาจทำเช่นนั้น?
>> มันอาจจะมีลักษณะบางอย่างเช่นนี้
เราเริ่มต้นที่ราก
และเรามี 10 สถานที่ที่เราจะไป
รากก็เหมือนกับการใด ๆ โหนดอื่น ๆ ของ Trie
มี 10 สถานที่ที่เราสามารถไปจากที่นี่
>> เราอาจต้องการอยู่ที่ไหน ที่จะไปหากที่สำคัญคือ 1636?
มีจริงๆสองตัวเลือก
ขวา
เราสามารถสร้างที่สำคัญจาก ขวาไปซ้ายและเริ่มต้นด้วย 6
หรือเราสามารถสร้างที่สำคัญจาก จากซ้ายไปขวาและเริ่มต้นด้วย 1
>> มันอาจจะมากขึ้น ที่ใช้งานง่ายเป็นมนุษย์
ที่จะเข้าใจเราจะ เพียงแค่ไปซ้ายไปขวา
ดังนั้นถ้าผมต้องการที่จะแทรก ฮาร์วาร์เข้า Trie นี้
ฉันอาจต้องการเริ่มต้น โดยเริ่มต้นที่ราก
มองไปที่ตัวเลือกของฉัน 10 ในด้านหน้าของฉันและพูดว่า
ฉันต้องการที่จะลงไป 1 เส้นทาง
ตกลง.
>> ตอนนี้ 1 เส้นทางขณะนี้เป็นโมฆะ
ดังนั้นถ้าผมต้องการที่จะดำเนินการต่อไปตามเส้นทางที่ ที่จะแทรกเข้าไปในองค์ประกอบนี้ Trie ที่
ฉันต้อง malloc โหนดใหม่มี 1 ชี้มีแล้วฉันดีไป
>> ดังนั้นผมจึงรู้สึกโดยทั่วไปที่ จุดที่ฉันยืนอยู่
ที่รากของต้นไม้หรือที่ Trie และมี 10 สาขา
แต่สาขาที่แต่ละคนมี ประตูด้านหน้าของมัน
ขวา
เพราะมีอะไรอย่างอื่นที่มี
ไม่มีความปลอดภัย
นั่นหมายความว่ามีอะไร ลงทุกสาขาเหล่านั้น
ถ้าผมต้องการที่จะเริ่มต้นสร้าง สิ่งที่ผมต้องการที่จะเอาประตู
ฉันต้องการที่จะเอาประตู ในด้านหน้าของหมายเลข 1
และผมต้องการที่จะเดินลง
และผมต้องการที่จะสร้าง สถานที่อื่นสำหรับผมที่จะไป
>> และนั่นคือสิ่งที่ผมเคยทำที่นี่
ดังนั้น 1 ไม่ได้ชี้ให้เป็นโมฆะ
ฉันได้กล่าวว่ามันปลอดภัยที่จะลงไปที่นี่ตอนนี้
ฉันสร้างโหนดอื่น
และเมื่อฉันได้รับไปยังโหนดนั้นผม มีการตัดสินใจที่จะทำให้คนอื่น
ฉันกำลังจะไปไหนจะไปจากที่นี่?
>> ดีฉันได้ลงไปแล้ว 1
ดังนั้นตอนนี้ฉันอาจต้องการที่จะไปลง 6
ขวา
อีกครั้งผมมี 10 สถานที่ที่ผมสามารถเลือก
ดังนั้นตอนนี้ขอไปลง 6 จำนวน
ดังนั้นผมจึงล้างประตู ในด้านหน้าของหมายเลข 6
และผมก็เดินลงไปที่นั่น
และฉันสร้างโหนดอื่น
และฉันได้มาถึงจุดทางแยกอีก
>> อีกครั้งผมมี 10 ตัวเลือก สำหรับที่ที่ฉันสามารถไป
ฉันได้ย้าย 1-6
ดังนั้นตอนนี้ฉันอาจจะต้องการที่จะไป 3
3 มีไม่มีที่ไหนเลยที่ฉันจะไป
ดังนั้นผมจึงต้องล้างทาง และสร้างตัวเองพื้นที่ใหม่
และจาก 3 ที่ฉันต้องการที่จะไป?
ฉันต้องการที่จะลงไป 6
>> และอีกครั้งที่ผมต้อง ล้างทางที่จะทำมัน
ดังนั้นตอนนี้ผมเคยใช้ที่สำคัญของฉันที่จะแทรกสร้าง โหนดและเริ่มสร้าง Trie นี้
ผมได้เริ่มต้นที่ราก
ฉันได้ไปลง 1636
และตอนนี้ฉันที่ด้านล่าง มีบนโหนดที่
และคุณอาจจะสามารถ เห็นมันบนหน้าจอของคุณ
>> มันเน้นสีเหลือง
นั่นคือสิ่งที่ฉันกำลัง am
ที่สำคัญที่ฉันจะทำ
ฉันได้หมดทุกตำแหน่งในคีย์ของฉัน
ดังนั้นผมจึงไม่สามารถไปเพิ่มเติมใด ๆ
เพื่อที่จุดนี้ทั้งหมดที่ฉัน จริงๆต้องทำคือการพูดว่าตกลง
มันเป็นชนิดของชอบมอง ลงที่พื้นดิน
ถ้าคุณกำลังวาดภาพ ตัวเองเป็นจัดเรียงของเส้นทางนี้
ด้วยการเชื่อมต่อที่แตกต่างกัน
เรียงจากมองลงมาและการจัดเรียงของ สเปรย์ภาพวาดฮาร์วาร์บนพื้นดิน
นั่นเป็นชื่อนี้
รู้ว่าสิ่งที่อยู่ในตำแหน่งนี้
ถ้าเราเริ่มต้นที่รากและเราลงไป 1 แล้ว 6 แล้ว 3 แล้ว 6
เราอยู่ที่ไหน
ดีถ้าเรามองลงมา และเราจะเห็นฮาร์วาร์แล้ว
เรารู้ว่าฮาร์วาร์เป็น ก่อตั้งขึ้นในปี 1636 ขึ้นอยู่กับวิธีการที่
เรากำลังดำเนินการโครงสร้างข้อมูลนี้
เพื่อให้เป็นที่หวังว่าตรงไปตรงมา
เรากำลังจะทำสองแทรกเพิ่มเติม
และหวังว่ามันจะช่วยในการ เห็นนี้ทำอีกครั้ง
>> ตอนนี้ขอแทรกมหาวิทยาลัยอื่น
ลองใส่เยลเข้า Trie นี้
เยลก่อตั้งขึ้นในปี 1701
ดังนั้นเราจะเริ่มต้นที่ รากที่เราเคยทำ
และเราจะกำหนดตัวชี้สำรวจเส้นทาง
เรากำลังจะใช้ว่าจะเคลื่อนตัวผ่าน
สิ่งแรกที่เราต้องการ ทำคือการลงไป 1 เส้นทาง
นั่นคือหลักแรกของสำคัญของเรา
โชคดีที่ว่าเราทำไม่ได้ ต้องทำงานใด ๆ ในเวลานี้
1 เส้นทางที่ได้รับการล้างแล้ว
ผมเคลียร์ก่อนหน้านี้เมื่อฉัน ถูกใส่ฮาร์วาร์ที่ 1636
ดังนั้นผมจึงสามารถย้ายได้อย่างปลอดภัย ลดลง 1 และเพียงแค่ไปที่นั่น
หากสามารถย้ายลง 1
>> แต่ในเวลานี้ผมอยากจะไปถึง 7
ผมเคลียร์ทางที่ 6
ฉันรู้ว่าฉันสามารถได้อย่างปลอดภัย ดำเนินการต่อไปตามเส้นทางที่ 6
แต่ฉันต้องการที่จะดำเนินการต่อไปบนเส้นทางที่ 7
ดังนั้นสิ่งที่ฉันจะต้องทำอย่างไร
ดีเช่นเดียวกับก่อนหน้านี้ผมก็ต้อง เพื่อล้างประตูได้รับการออกจากทาง
และสร้างโหนดใหม่จากเส้นทาง 7
เพียงเช่นนี้
>> ดังนั้นตอนนี้ฉันได้ย้ายที่ 1 และ 7 แล้ว
และตอนนี้สังเกตเห็นผมจัดเรียง บน subbranch ใหม่นี้
ขวา
ทุกสิ่งทุกอย่างตั้งแต่วันที่ 16 ที่ฉันไม่สนใจเกี่ยวกับ
ฉันไม่ได้ทำอะไรที่ 16
ฉันทำสิ่งที่ 17
>> ดังนั้นในขณะนี้จาก 17 ผมต้อง การเรียงลำดับของลุกโชนเส้นทางใหม่ที่นี่
หลักที่สำคัญต่อไปของฉันคือ 0
ฉันชัดเจนไม่สามารถไปได้ทุกที่
ฉันเพิ่งสร้างโหนดนี้
ดังนั้นผมจึงรู้ว่าไม่มี เส้นทางข้างหน้าจากที่นี่
ดังนั้นผมจึงต้องทำหนึ่งตัวเอง
>> ดังนั้นผมจึง malloc โหนดใหม่ และมี 0 จุดมี
และจากนั้นอีกครั้งหนึ่งผม malloc โหนดใหม่และมีจุดหนึ่งที่มี
อีกครั้งที่ฉันได้หมดที่สำคัญของฉัน 1701
ดังนั้นผมจึงมองลงมาและผมสเปรย์สีเยล
นั่นคือชื่อของโหนดนี้
>> และดังนั้นตอนนี้ถ้าผมจำเป็นต้องดูว่าเยล ที่อยู่ใน Trie นี้ผมเริ่มต้นที่ราก
ผมลงไป 1,701 และมองลงมา
และถ้าผมเห็นสเปรย์เยล วาดลงบนพื้นดินแล้ว
ฉันรู้ว่ามีอยู่ในเยล Trie นี้
ขอทำอีกครั้งหนึ่ง
ลองใส่ดาร์ทเมาท์ในนี้ Trie ซึ่งก่อตั้งขึ้นในปี 1769
>> เริ่มต้นที่รากอีกครั้ง
หลักแรกของฉันที่สำคัญของฉันคือ 1
ผมสามารถย้ายลงเส้นทางที่
ที่มีอยู่แล้ว
หลักที่สำคัญต่อไปของฉันคือ 7
ผมสามารถย้ายลงเส้นทางที่
มันมีอยู่เช่นกัน
>> ต่อไปของฉันคือ 6
จากที่นี่จากที่ฉันกำลัง am สีเหลืองที่มีในโหนดกลาง
6 ขณะนี้ถูกล็อคออก
ถ้าผมต้องการที่จะไปลงเส้นทางที่ ฉันต้องสร้างมันเอง
ดังนั้นฉันจะ malloc โหนดใหม่ และมี 6 จุดมี
และจากนั้นอีกครั้งฉัน ที่เห็นได้ชัดเส้นทางใหม่ที่นี่
>> ดังนั้นผมจึง malloc โหนดใหม่เพื่อให้จาก ว่าจำนวนเส้นทาง node-- 9-- แล้วในขณะนี้
ถ้าผมเดินทาง 1769 และผมมองลงมา
ไม่มีอะไรในขณะนี้ สเปรย์ที่มีสี
ฉันจะเขียนดาร์ทเมาท์
และฉันได้ใส่ ดาร์ทเมาท์เข้าของ Trie
>> ดังนั้นที่ใส่ สิ่งที่เป็นของ Trie
ตอนนี้เราต้องการที่จะค้นหาสิ่งที่
เราจะค้นหาวิธีสำหรับสิ่งที่อยู่ใน Trie หรือไม่
ดีก็สวยมากความคิดเดียวกัน
ตอนนี้เราใช้เพียงตัวเลขของคีย์ เพื่อดูว่าเราสามารถนำทางจากราก
การที่เราต้องการที่จะไปในของ Trie
>> ถ้าเราตีปลายตายที่จุดใด ๆ แล้ว เรารู้ว่าองค์ประกอบที่ไม่สามารถที่มีอยู่
หรืออื่น ๆ ที่จะเส้นทางที่ ได้รับการล้างแล้ว
ถ้าเราทำให้ทุกอย่างเพื่อ ท้ายที่สุดสิ่งที่เราต้องทำ
คือมองลงมาและดูว่าที่ องค์ประกอบที่เรากำลังมองหา
ถ้ามันเป็นความสำเร็จ
หากยังไม่ได้ล้มเหลว
>> ถ้าอย่างนั้นเราค้นหา ฮาร์วาร์ใน Trie นี้
เราเริ่มต้นที่ราก
และอีกครั้งที่เรากำลังจะ สร้างตัวชี้สำรวจเส้นทาง
ที่จะทำการเคลื่อนไหวของเราสำหรับเรา
จากรากที่เรารู้ว่า สถานที่แรกที่เราต้องไปคือ 1,
เราสามารถทำเช่นนั้น?
ใช่เราสามารถ.
ถ้ามีอยู่ได้อย่างปลอดภัย
เราสามารถไปที่นั่น
>> ตอนนี้สถานที่ต่อไปที่เราต้องไปคือ 6
ไม่เส้นทางที่ 6 มีอยู่จากที่นี่?
ใช่มันไม่
เราสามารถไปลงเส้นทางที่ 6
และเราจะจบลงที่นี่
>> เราสามารถไปลงเส้นทางที่ 3 จากที่นี่?
ดีที่มันจะเปิดออก ใช่ที่มีอยู่มากเกินไป
และเราจะได้รับบนเส้นทางที่ 6 จากที่นี่?
ใช่เราสามารถ.
>> เรายังไม่ได้ตอบเลยทีเดียว คำถามที่ยัง
ยังคงมีอีกหนึ่ง ขั้นตอนซึ่งขณะนี้
เราต้องดูและลง ดูว่าที่ actually--
ถ้าเรากำลังมองหาฮาร์วาร์เป็นที่ สิ่งที่เราพบว่าหลังจากที่เราหมดที่สำคัญ?
ในตัวอย่างที่เรากำลังใช้ที่นี่ ปีที่ผ่านมามักจะมีตัวเลขสี่หลัก
แต่คุณอาจจะใช้ตัวอย่างที่ คุณเก็บพจนานุกรมของคำ
>> ดังนั้นแทนที่จะมี 10 ตัวชี้ สำหรับสถานที่ตั้งของฉันคุณอาจจะมี 26
หนึ่งสำหรับแต่ละตัวอักษร
และมีบางคำเช่นค้างคาว ซึ่งเป็นส่วนหนึ่งของชุดตัวอย่างเช่น
และดังนั้นแม้ว่าคุณจะได้รับการ ในตอนท้ายของที่สำคัญและคุณมองลง
คุณอาจไม่เห็นสิ่งที่ คุณกำลังมองหา
>> ดังนั้นคุณจึงมักจะมีการสำรวจ เส้นทางทั้งหมดแล้ว
ถ้าคุณมีความสามารถที่ประสบความสำเร็จ เพื่อสำรวจเส้นทางทั้งหมด
มองลงมาและทำหนึ่งยืนยันขั้นสุดท้าย
คือสิ่งที่ฉันกำลังมองหา?
ดีฉันมองลงมาหลังจากที่เริ่มต้น ที่ด้านบนและไป 1636
ฉันมองลงมา
ผมเห็นฮาร์วาร์
ดังนั้นใช่ฉันประสบความสำเร็จ
เกิดอะไรขึ้นถ้าสิ่งที่ฉันกำลังมองหา ไม่ได้อยู่ใน Trie แม้ว่า
เกิดอะไรขึ้นถ้าฉันกำลังมองหาพรินซ์ตัน ซึ่งก่อตั้งขึ้นใน 1746
และเพื่อ 1746 จะกลายเป็นกุญแจสำคัญของฉัน เพื่อนำทางผ่านของ Trie
ดีฉันเริ่มต้นที่ราก
และครั้งแรกที่ฉันต้องการ ที่จะลงไป 1 เส้นทาง
ฉันสามารถทำมันได้หรือไม่
ใช่, ฉันทำได้.
>> ฉันสามารถไปลงเส้นทางที่ 7 จากที่นั่น?
ใช่ฉันสามารถ.
ที่มีอยู่มากเกินไป
แต่ผมสามารถไปลงเส้นทางที่ 4 จากที่นี่?
ที่ชอบถามคำถามสามารถ ผมดำเนินการต่อไปลงที่ตารางเล็ก ๆ น้อย ๆ
ที่ฉันได้เน้นสีเหลือง?
มีอะไรที่มี
ขวา
>> ไม่มีทางข้างหน้าลงเส้นทางที่ 4
หากพรินซ์ตันอยู่ใน Trie นี้ว่า 4 จะได้รับการล้างสำหรับเราแล้ว
และเพื่อที่จุดนี้ เราได้มาถึงปลายตาย
เราไม่สามารถไปเพิ่มเติมใด ๆ
และเพื่อให้เราสามารถพูดได้อย่างแน่นอนไม่
พรินซ์ตันไม่อยู่ใน Trie นี้
>> ดังนั้นสิ่งที่จะทั้งหมดนี้หมายความว่าอย่างไร
ขวา
มีจำนวนมากที่เกิดขึ้นที่นี่
มีตัวชี้เป็นทั่วทุกสถานที่
และอย่างที่คุณเห็น เพียง แต่จากแผนภาพ
มีจำนวนมากของโหนดที่ กำลังชนิดของการบินไปรอบ ๆ
แต่แจ้งให้ทราบทุกครั้งที่เราอยากจะทุกคน ตรวจสอบว่าสิ่งที่อยู่ใน Trie ที่
เราจะต้องทำให้การเคลื่อนไหว 4
>> เวลาที่เราทุกคนต้องการที่จะ ใส่อะไรบางอย่างใน Trie ที่
เราจะต้องทำให้การเคลื่อนไหว 4 อาจจะเป็น mallocing สิ่งบางอย่างไปพร้อมกัน
แต่ที่เราเห็นเมื่อเราใส่ ดาร์ทเมาท์เข้า Trie ที่
บางครั้งบางส่วนของเส้นทาง แล้วอาจจะมีการเคลียร์สำหรับเรา
และเพื่อให้เป็น Trie ของเราได้รับที่ใหญ่กว่าและ ใหญ่กว่าที่เรามีจะทำงานน้อยลงทุกครั้ง
แทรกสิ่งใหม่ ๆ เพราะเราได้อยู่แล้ว
สร้างจำนวนมากของกลางที่ สาขาไปพร้อมกัน
ถ้าเราเท่านั้นที่เคยต้องมองไปที่ 4 สิ่งที่ 4 เป็นเพียงคงที่
จริงๆเรากำลังใกล้เข้ามาชนิดของ แทรกเวลาคง
และการค้นหาเวลาคง
ถ่วงดุลอำนาจของหลักสูตรการที่ Trie นี้ที่คุณอาจจะสามารถบอกได้
มีขนาดใหญ่มาก
แต่ละคนโหนดเหล่านี้ จะขึ้นมากของพื้นที่
>> แต่ที่ถ่วงดุลอำนาจ
ถ้าเราต้องการได้อย่างรวดเร็วจริงๆ แทรกลบอย่างรวดเร็วจริงๆ
และค้นหาได้อย่างรวดเร็วจริงๆเราจะต้อง มีข้อมูลจำนวนมากบินไปรอบ ๆ
เรามีการตั้งสำรองพื้นที่มาก และหน่วยความจำสำหรับโครงสร้างข้อมูลว่า
จะมีชีวิตอยู่
>> และเพื่อให้เป็นถ่วงดุลอำนาจ
แต่มันดูเหมือนว่าเรา อาจได้พบมัน
เราอาจจะได้พบว่า จอกศักดิ์สิทธิ์ของโครงสร้างข้อมูล
ที่มีการแทรกอย่างรวดเร็ว การลบและการค้นหา
และอาจจะนี้จะเป็น โครงสร้างข้อมูลที่เหมาะสม
ที่จะใช้สำหรับข้อมูลอะไรก็ตาม เรากำลังพยายามที่จะเก็บ
ฉันลอยด์ดั๊กนี้เป็น CS50