[เล่นเพลง] 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