การคำนวณมีประโยชน์อย่างยิ่งเมื่อเราต้องจัดการกับข้อมูลปริมาณมากที่ไม่สามารถจัดการได้ด้วยขั้นตอนเพียงไม่กี่ครั้ง ในกรณีเช่นนี้ algorithm (อัลกอริทึม) ที่เหมาะสมจะช่วยให้ข้อมูลทั้งหมดถูกประมวลผลอย่างเป็นระบบ และในหลายกรณีก็ทำได้อย่างมีประสิทธิภาพ

สัญลักษณ์ที่กล่าวถึงใน chapter 3 แสดงให้เห็นว่า การแทนข้อมูลทำงานอย่างไรสำหรับชิ้นข้อมูลแต่ละชิ้น และการแทนนั้นเองก็กลายเป็นส่วนหนึ่งของการคำนวณ ตัวอย่างเช่น การที่ Hansel และ Gretel เดินจากก้อนกรวดไปยังก้อนกรวด หมายความว่าพวกเขายังอยู่ในอันตรายจนกว่าจะเดินจากก้อนกรวดสุดท้ายกลับบ้าน แต่แม้ว่าการรวมกันของสัญลักษณ์จะเป็นสัญลักษณ์ชิ้นหนึ่งเอง การคำนวณกับการรวมกันเช่นนั้นยังไม่ชัดเจน ในกรณีของ Hansel และ Gretel ก้อนกรวดแต่ละก้อนเป็นตัวแทนของตำแหน่งหนึ่ง และการรวมของก้อนกรวดทั้งหมดหมายถึงเส้นทางจากอันตรายไปสู่ความปลอดภัย แต่การรวมเช่นนี้สร้างขึ้นและถูกใช้เป็นระบบอย่างไร การดูแลรักษาคอลเลกชันของข้อมูลนำไปสู่คำถามสองประการ

อันดับแรก ข้อมูลจะถูกใส่ ค้นหา และลบออกจากคอลเลกชันในลำดับใด? คำตอบแน่นอนว่า ขึ้นกับงานคำนวณที่คอลเลกชันนั้นเกี่ยวข้อง แต่เราสามารถสังเกตได้ว่ารูปแบบการเข้าถึงองค์ประกอบบางรูปแบบเกิดขึ้นซ้ำ รูปแบบการเข้าถึงข้อมูลเช่นนี้เรียกว่า data type (ชนิดข้อมูล) ตัวอย่างเช่น ก้อนกรวดที่ Hansel และ Gretel ใช้ ถูกเข้าเยี่ยมชมในลำดับตรงกันข้ามกับที่วางไว้ รูปแบบการเข้าถึงเช่นนี้เรียกว่า stack

ประการที่สอง คอลเลกชันควรเก็บอย่างไรเพื่อให้รูปแบบการเข้าถึง หรือ data type ได้รับการสนับสนุนอย่างมีประสิทธิภาพที่สุด? คำตอบขึ้นกับปัจจัยหลากหลาย เช่น ต้องเก็บองค์ประกอบกี่ชิ้น จำนวนนี้ทราบล่วงหน้าหรือไม่ แต่ละองค์ประกอบต้องการพื้นที่เก็บเท่าใด และองค์ประกอบทั้งหมดมีขนาดเท่ากันหรือไม่ วิธีการเก็บคอลเลกชันใด ๆ เรียกว่า data structure (โครงสร้างข้อมูล) โครงสร้างข้อมูลทำให้คอลเลกชันพร้อมสำหรับการคำนวณ หนึ่ง data type สามารถถูกนำไปใช้ได้โดยโครงสร้างข้อมูลหลายแบบ ซึ่งหมายความว่ารูปแบบการเข้าถึงเดียวกันสามารถ implement ได้ผ่านวิธีการเก็บข้อมูลต่างกัน ความแตกต่างระหว่างโครงสร้างข้อมูลอยู่ที่ความมีประสิทธิภาพในการรองรับการปฏิบัติการเฉพาะบนคอลเลกชัน นอกจากนี้ โครงสร้างข้อมูลหนึ่งอาจ implement data types ต่าง ๆ ได้ด้วย

บทนี้จะกล่าวถึง data types หลายแบบ โครงสร้างข้อมูลที่ใช้ในการ implement พวกมัน และวิธีที่พวกมันถูกนำมาใช้เป็นส่วนหนึ่งของการคำนวณ

The Usual Suspects (ผู้ต้องสงสัยที่พบบ่อย)

เมื่อผู้กระทำผิดชัดเจน (เช่นมีพยานสายตาหรือการสารภาพ) เราไม่จำเป็นต้องใช้ทักษะของ Sherlock Holmes แต่เมื่อมีผู้ต้องสงสัยหลายคน เราจำเป็นต้องติดตามแรงจูงใจ อลิบิ และข้อมูลที่เกี่ยวข้องอื่น ๆ เพื่อตรวจสอบคดีอย่างละเอียด

ใน The Hound of the Baskervilles ผู้ต้องสงสัยได้แก่ Dr. Mortimer, Jack Stapleton และบุคคลที่คิดว่าเป็นน้องสาว Beryl (ซึ่งแท้จริงแล้วเป็นภรรยาของเขา), ผู้ร้ายที่หลบหนี Seiden, Mr. Frankland และคู่สามีภรรยา Barrymore ซึ่งเป็นคนรับใช้ของ Sir Charles Baskerville ที่ล่วงลับ ก่อนที่ Watson จะออกไปเยี่ยม Baskerville Hall Sherlock Holmes ให้คำสั่งกับ Watson ให้รายงานข้อเท็จจริงที่เกี่ยวข้องทั้งหมด แต่ให้ยกเว้น Mr. James Desmond ออกจากรายชื่อผู้ต้องสงสัย เมื่อ Watson แนะนำให้ Holmes ยกเว้นคู่ Barrymore ด้วย Sherlock Holmes ตอบว่า:

ไม่ ไม่ เราจะยังคงเก็บพวกเขาไว้ในรายชื่อผู้ต้องสงสัยของเรา.

การแลกเปลี่ยนสั้นๆ นี้แสดงให้เห็นสองประการ

อันดับแรก แม้ว่า Sherlock Holmes จะไม่รู้เรื่องโครงสร้างข้อมูลโดยละเอียด แต่เขาก็ใช้โครงสร้างข้อมูลแบบหนึ่งอยู่เพราะดูเหมือนว่าเขาเก็บรายชื่อผู้ต้องสงสัยไว้ list ซึ่งเป็นโครงสร้างข้อมูลง่าย ๆ ที่เก็บข้อมูลเป็นรายการโดยเชื่อมโยงกัน มันให้รูปแบบการเข้าถึงและการจัดการไอเท็มที่ชัดเจน ประการที่สอง รายชื่อผู้ต้องสงสัยไม่ใช่เอนทิตี้คงที่ มันเติบโตและหดเมื่อมีการเพิ่มผู้ต้องสงสัยใหม่หรือเมื่อผู้ต้องสงสัยถูกลบ การเพิ่ม การลบ หรือการเปลี่ยนแปลงไอเท็มในโครงสร้างข้อมูลมักต้องใช้อัลกอริทึมหลายขั้นตอน และเวลาในการรันของอัลกอริทึมเหล่านี้เป็นตัวกำหนดว่าโครงสร้างข้อมูลใดเหมาะกับงานใด

ด้วยความเรียบง่ายและความยืดหยุ่น รายการ (lists) น่าจะเป็นโครงสร้างข้อมูลที่ถูกใช้อย่างแพร่หลายที่สุดในวิทยาการคอมพิวเตอร์และที่อื่น ๆ เราทุกคนใช้รายการในรูปแบบต่าง ๆ ในชีวิตประจำวัน เช่น รายการสิ่งที่ต้องทำ รายการซื้อของ รายการอ่าน รายการที่อยากได้ และการจัดอันดับต่าง ๆ ลำดับขององค์ประกอบในรายการมีความสำคัญ และปกติเข้าถึงทีละองค์ประกอบ โดยเริ่มจากปลายด้านหนึ่งไปยังอีกด้านหนึ่ง นักคอมพิวเตอร์มักเขียนรายการแบบแนวนอน แสดงองค์ประกอบจากซ้ายไปขวา เชื่อมด้วยลูกศรเพื่อบอกลำดับ. ด้วยสัญกรณ์นี้ Sherlock Holmes สามารถจดรายชื่อผู้ต้องสงสัยของเขาได้ดังนี้:

Mortimer → Jack → Beryl → Seiden → …

ลูกศรเรียกว่า pointers และทำให้การเชื่อมต่อระหว่างองค์ประกอบในรายการชัดเจน ซึ่งมีความสำคัญเมื่อคิดถึงการอัปเดตรายการ สมมติว่ารายชื่อผู้ต้องสงสัยของ Sherlock Holmes เป็น Mortimer → Beryl และเขาต้องการเพิ่ม Jack ไว้ระหว่างทั้งสองคน

ถ้าเขียนองค์ประกอบเป็นรายการแนวตั้งโดยไม่มีช่องว่างระหว่างบรรทัด เขาจะต้องใช้สัญกรณ์พิเศษเพื่อระบุตำแหน่งขององค์ประกอบใหม่ ทางเลือกอีกทางคือเขียนสำเนาใหม่ของรายการทั้งหมด แต่นั่นจะเป็นการเสียเวลาทั้งหมดและเสียพื้นที่มาก ในกรณีที่เลวร้ายที่สุดจะต้องใช้เวลาและพื้นที่ที่เป็นสัดส่วนเชิงกำลังสองกับขนาดของรายการสุดท้าย

Pointers ให้ความยืดหยุ่นให้เราวางองค์ประกอบใหม่ที่ใดก็ได้และยังคงวางไว้ที่ตำแหน่งที่ถูกต้องในรายการโดยเชื่อมต่อกับองค์ประกอบข้างเคียง ตัวอย่างเช่น เราสามารถวาง Jack ที่ปลายรายการ เปลี่ยน pointer ออกจาก Mortimer ให้ชี้ไปที่ Jack แล้วเพิ่ม pointer จาก Jack ไปยัง Beryl

ในบริบทของเรื่อง การจัดลำดับผู้ต้องสงสัยในรายการนี้เป็นเรื่องเลือกได้และไม่มีความหมายพิเศษ แต่เราจะเห็นว่าการสร้างรายการบังคับให้เราต้องเลือกลำดับขององค์ประกอบ นี่เป็นลักษณะเฉพาะของรายการที่องค์ประกอบถูกเก็บไว้ในลำดับที่แน่นอน

การตรวจสอบองค์ประกอบของรายการเกิดขึ้นตามลำดับที่รายการกำหนด ดังนั้นเพื่อจะรู้ว่า Selden เป็นผู้ต้องสงสัยหรือไม่ เราต้องเริ่มจากจุดเริ่มต้นของรายการและตรวจสอบองค์ประกอบทีละตัวโดยตาม pointer ไป แม้ว่าเราจะสามารถเห็น Selden ในรายการได้สำหรับรายการขนาดเล็ก แต่สำหรับรายการยาวเราจะไม่สามารถจำแนกองค์ประกอบได้ทันที จึงต้องอาศัยการเดินผ่านรายการทีละองค์ประกอบ

คำอุปมาเชิงกายภาพสำหรับรายการคือแฟ้มวงแหวน (ring binder) ที่มีแผ่นกระดาษแต่ละแผ่นสำหรับแต่ละองค์ประกอบ การจะหาองค์ประกอบหนึ่งในแฟ้มวงแหวนต้องเปิดดูทีละหน้า และสามารถแทรกหน้าใหม่ได้ระหว่างหน้าอื่นๆ

คุณสมบัติเด่นของรายการคือ เวลาที่ใช้ในการค้นหาองค์ประกอบขึ้นกับตำแหน่งขององค์ประกอบนั้น ในตัวอย่างนี้ Selden จะถูกพบในขั้นตอนที่สี่ โดยทั่วไปการค้นหาองค์ประกอบอาจต้องเดินรายการทั้งรายการ เนื่องจากองค์ประกอบอาจเป็นตัวสุดท้าย ในการพูดถึงความซับซ้อนของเวลาใน chapter 2 อัลกอริทึมเช่นนี้ถูกเรียกว่า linear เพราะความซับซ้อนของเวลาเป็นสัดส่วนตรงกับจำนวนองค์ประกอบในรายการ

อย่างที่กล่าวมา ไม่แน่ว่ารายชื่อผู้ต้องสงสัยของ Sherlock Holmes จะอยู่ในลำดับที่แสดงจริงหรือไม่ และการที่ Selden มาอยู่หลัง Beryl ก็ไม่มีนัยพิเศษใด ๆ เพราะจุดประสงค์ของรายการเพียงแค่จดว่าใครเป็นผู้ต้องสงสัยเท่านั้น. นั่นหมายความว่ารายการไม่ใช่การแทนที่เหมาะสมสำหรับจดจำผู้ต้องสงสัยหรือ? ไม่เลย; มันแค่หมายความว่ารายการอาจประกอบด้วยข้อมูลบางอย่าง (เช่น การจัดลำดับขององค์ประกอบ) ที่ไม่จำเป็นสำหรับงานเฉพาะ ข้อสังเกตนี้ชี้ให้เห็นว่ารายการเป็นเพียงโครงสร้างข้อมูลหนึ่งสำหรับแทนข้อมูลผู้ต้องสงสัย และอาจมีตัวแทนอื่นที่สามารถใช้ในวัตถุประสงค์เดียวกันได้—ตราบเท่าที่ยังรองรับการปฏิบัติการเดียวกันในการเพิ่ม ลบ และค้นหาองค์ประกอบ การปฏิบัติการเหล่านี้แสดงความต้องการในสิ่งที่ต้องทำกับข้อมูล

ข้อกำหนดสำหรับข้อมูลที่แสดงผ่านชุดของการปฏิบัติการเรียกว่า data type (ชนิดข้อมูล) ในวิทยาการคอมพิวเตอร์ ข้อกำหนดสำหรับข้อมูลผู้ต้องสงสัยคือความสามารถในการเพิ่ม ลบ และค้นหาองค์ประกอบ data type นี้เรียกว่า set (เซต)

เซตมีการใช้งานอย่างกว้างขวาง เพราะมันสอดคล้องกับ predicate ที่เกี่ยวข้องกับปัญหาหรืออัลกอริทึม ตัวอย่างเช่น เซตของผู้ต้องสงสัยสอดคล้องกับนิพจน์ "is a suspect" ซึ่งใช้กับบุคคล และสามารถใช้ยืนยันหรือปฏิเสธประโยคเช่น "Selden is a suspect" ขึ้นกับว่าบุคคลนั้นเป็นสมาชิกของเซตหรือไม่ อัลกอริทึมการตามรอยก้อนกรวดของ Hansel และ Gretel ก็ใช้ predicate เมื่อมันสั่งว่า "Find a shining pebble that was not visited before." Predicate ในที่นี้คือ "not visited before" ซึ่งใช้กับก้อนกรวดและสามารถแทนได้ด้วยเซตที่เริ่มว่างและมีการเพิ่มก้อนกรวดหลังจากที่ถูกเยี่ยมชม

ในขณะที่ data type อธิบายสิ่งที่ต้องทำกับข้อมูล โครงสร้างข้อมูลจะให้การแทนที่เป็นรูปธรรมเพื่อรองรับข้อกำหนดเหล่านั้น คุณสามารถคิดว่า data type เป็นคำอธิบายของงานจัดการข้อมูล และโครงสร้างข้อมูลเป็นทางแก้ปัญหาสำหรับงานนั้น (เพื่อช่วยจำ: data type อธิบายงาน; data structure อธิบายทางแก้) data type เป็นคำอธิบายที่มีความเป็นนามธรรมมากกว่าโครงสร้างข้อมูลและมีข้อได้เปรียบที่สามารถเว้นรายละเอียดบางอย่างไว้ได้ ทำให้ได้คำอธิบายที่กระชับและทั่วไป ใน The Hound of the Baskervilles data type แบบ set สะท้อนงานของการคงรักษารายชื่อผู้ต้องสงสัยโดยไม่ต้องระบุรายละเอียดการ implement ในเชิงลึก ในเรื่องของ Hansel และ Gretel data type แบบ set เพื่อจดก้อนกรวดที่ถูกเยี่ยมชมก็เพียงพอสำหรับการอธิบายอัลกอริทึม อย่างไรก็ตาม เพื่อจะรันปฏิบัติการที่ data type ระบุได้จริง เครื่องคอมพิวเตอร์ต้องใช้โครงสร้างข้อมูลที่เป็นรูปธรรมซึ่งกำหนดว่าปฏิบัติการทำงานกับการแทนอย่างไร และเฉพาะเมื่อเลือกโครงสร้างข้อมูลที่เป็นรูปธรรมสำหรับอัลกอริทึม เราจึงสามารถกำหนดความซับซ้อนของเวลาในการรันของอัลกอริทึมได้

เนื่องจาก data type หนึ่งสามารถ implement ได้โดยโครงสร้างข้อมูลหลายแบบ คำถามคือควรเลือกโครงสร้างข้อมูลแบบใด เราต้องการโครงสร้างข้อมูลที่ทำให้การปฏิบัติการของ data type ทำงานด้วย runtime ที่ดีที่สุด เพื่อให้อัลกอริทึมที่ใช้โครงสร้างข้อมูลทำงานเร็วที่สุด อย่างไรก็ตาม การตัดสินใจนี้ไม่ง่ายเสมอไป เพราะโครงสร้างข้อมูลอาจรองรับบางปฏิบัติการได้ดีแต่ไม่ดีสำหรับปฏิบัติการอื่น ๆ นอกจากนี้โครงสร้างข้อมูลยังมีความต้องการพื้นที่จัดเก็บต่างกัน สถานการณ์นี้คล้ายกับการเลือกยานพาหนะสำหรับงานขนส่งเฉพาะ: จักรยานประหยัดพลังงานและให้ระยะทางคุ้มค่าต่อเชื้อเพลิง แต่ช้าและขนคนได้น้อย อาจต้องใช้ตู้หรือรถบัสสำหรับเดินทางกับคนจำนวนมาก คุณเลือกรถบรรทุกเพื่อขนของขนาดใหญ่ รถเก๋งสำหรับเดินทางสบาย และบางครั้งอาจเลือกสปอร์ตคาร์เมื่ออยากขับสนุก ๆ

เมื่อต้องพิจารณาการ implement data type แบบ set ทางเลือกยอดนิยมสองอย่างคือ array และ binary search tree โครงสร้างข้อมูลแบบ binary search tree ถูกพูดถึงโดยละเอียดใน chapter 5; ที่นี่ผมจะเน้นที่ arrays

ถ้ารายการเปรียบเหมือนแฟ้มวงแหวน array เปรียบเหมือนสมุดจดที่มีจำนวนหน้าคงที่ซึ่งแต่ละหน้ามีรหัสเฉพาะ ช่องข้อมูลแต่ละช่องในโครงสร้างข้อมูลแบบ array เรียกว่า cell และตัวระบุของ cell เรียกว่า index โดยปกติการระบุตำแหน่ง (indexing) ทำด้วยตัวเลข แต่เราสามารถใช้ตัวอักษรหรือนามได้ตราบเท่าที่เราสามารถเปิดหน้าเฉพาะด้วยตัวระบุได้ ความสำคัญของ array อยู่ที่การเข้าถึงที่รวดเร็วต่อแต่ละ cell ไม่ว่า array จะมีจำนวน cell เท่าใด ก็ใช้เพียงก้าวเดียวในการเข้าถึง cell ใด ๆ การปฏิบัติการที่ต้องการเพียงหนึ่งหรือไม่กี่ก้าว โดยไม่ขึ้นกับขนาดของโครงสร้างข้อมูล เรียกว่า constant time

เพื่อแทนเซตด้วยสมุดจด เราสมมติว่าทุกหน้ามีป้ายชื่อที่ระบุสมาชิกที่เป็นไปได้ของเซต ดังนั้นเพื่อแทนผู้ต้องสงสัยใน The Hound of the Baskervilles เราจะติดป้ายหน้าด้วยชื่อผู้ต้องสงสัยที่เป็นไปได้ทั้งหมด เช่น Mortimer, Jack เป็นต้น สมุดจดนี้ยังมีหน้าสำหรับ Desmond และคนอื่น ๆ ที่อาจเป็นผู้ต้องสงสัยด้วย ต่างจากแฟ้มวงแหวนซึ่งมีเฉพาะผู้ต้องสงสัยจริง ๆ เมื่อจะเพิ่ม Selden เป็นผู้ต้องสงสัย เราเปิดหน้าที่มีป้ายว่า “Selden” แล้วทำเครื่องหมายบางอย่าง (เช่น เขียน + หรือ "yes") เมื่อต้องการลบผู้ต้องสงสัย เราก็เปิดหน้าของคนนั้นแล้วลบเครื่องหมาย (หรือเขียน - หรือ "no") เมื่อต้องการตรวจสอบว่าใครเป็นผู้ต้องสงสัย เราเปิดหน้าของคนนั้นและดูเครื่องหมาย Array ทำงานในลักษณะเดียวกัน โดยเข้าถึง cell โดยตรงผ่าน index และอ่านหรือแก้ไขข้อมูลที่เก็บไว้

ความแตกต่างสำคัญระหว่าง arrays และ lists คือ เราสามารถระบุตำแหน่ง cell แต่ละตัวได้ทันทีใน array ขณะที่ต้องสแกนองค์ประกอบของ list ตั้งแต่ต้นเพื่อค้นหาองค์ประกอบ (หรือจนถึงจุดสิ้นสุดของรายการถ้าองค์ประกอบไม่อยู่)

เนื่องจากเราสามารถเปิดหน้าเฉพาะในสมุดจด (หรือเข้าถึง cell ใน array) ได้โดยตรง ทั้งสามปฏิบัติการ—การเพิ่ม การลบ และการค้นหาผู้ต้องสงสัย—สามารถทำได้ในเวลาแบบ constant time ซึ่งเป็นค่าที่ดีที่สุด: เราไม่สามารถทำให้เร็วกว่าได้อีก ในขณะที่โครงสร้างข้อมูลแบบ list ต้องใช้เวลาแบบ linear สำหรับการตรวจสอบและการลบผู้ต้องสงสัย โครงสร้างข้อมูลแบบ array ดูเหมือนจะชนะในด้านความเร็วทั้งหมด แล้วทำไมเรายังพูดถึง lists อยู่?

ปัญหาของ arrays คือขนาดคงที่ สมุดจดมีจำนวนหน้ากำหนดและไม่สามารถขยายได้เมื่อเวลาผ่านไป ซึ่งมีผลสำคัญสองประการ ประการแรก สมุดจดต้องถูกเลือกให้ใหญ่พอที่จะรองรับผู้ต้องสงสัยที่อาจเกิดขึ้นทั้งหมดตั้งแต่ต้น แม้กระทั่งถ้าหลายคนจะไม่เคยเป็นผู้ต้องสงสัยจริง ๆ นั่นอาจทำให้เราเสียพื้นที่มาก และเราอาจต้องพกสมุดเล่มใหญ่ที่มีหน้าสำหรับร้อยหรือพันผู้ต้องสงสัยที่เป็นไปได้ ทั้งที่ในความเป็นจริงชุดผู้ต้องสงสัยอาจมีจำนวนน้อย อาจมีน้อยกว่าสิบคนในเวลาใดเวลาหนึ่ง นี่ยังหมายความว่าการเตรียมดัชนีหน้าของสมุดในตอนเริ่มต้นอาจใช้เวลานานเพราะต้องเขียนชื่อผู้ต้องสงสัยที่เป็นไปได้แต่ละคนลงในหน้าต่าง ๆ ประการที่สอง—และนี่เป็นปัญหาที่ร้ายแรงกว่า—อาจไม่ชัดตั้งแต่ต้นว่าผู้ต้องสงสัยที่เป็นไปได้ทั้งหมดคือใคร โดยเฉพาะอย่างยิ่ง ผู้ต้องสงสัยใหม่อาจปรากฏขึ้นเมื่อเรื่องราวดำเนินไป ซึ่งเป็นกรณีของ The Hound of the Baskervilles การขาดข้อมูลเช่นนี้ทำให้ไม่สามารถใช้สมุดจดได้ เพราะการเริ่มต้นไม่สามารถทำได้

Figure 4.1 ชนิดข้อมูลหนึ่งสามารถนำไปใช้ได้โดยโครงสร้างข้อมูลที่ต่างกัน การแทรกองค์ประกอบในรายการสามารถทำได้โดยการเพิ่มไว้ที่หน้าหรือหัวรายการ แต่การลบต้องเดินผ่านรายการเพื่อค้นหา ในกรณีของ array การแทรกและการลบทำโดยการเข้าถึง cell ของ array ตาม index ขององค์ประกอบนั้นโดยตรงและเปลี่ยนเครื่องหมายตามที่ต้องการ Arrays ให้การ implement ที่เร็วกว่า แต่ lists ประหยัดพื้นที่กว่า.

จุดอ่อนของ array ที่มีขนาดใหญ่คือจุดแข็งของ list ที่คล่องตัว ซึ่งสามารถขยายและหดได้ตามต้องการและไม่เก็บองค์ประกอบมากเกินความจำเป็น เมื่อต้องเลือกโครงสร้างข้อมูลเพื่อ implement data type แบบ set เราต้องตระหนักถึงการแลกเปลี่ยนต่อไปนี้: array ให้การ implement ปฏิบัติการของ set อย่างรวดเร็วแต่มีแนวโน้มจะเสียพื้นที่และอาจใช้ไม่ได้ในทุกสถานการณ์ ในขณะที่ list ประหยัดพื้นที่กว่าและทำงานได้ในทุกสถานการณ์ แต่บางปฏิบัติการทำงานได้ด้อยกว่า สถานการณ์นี้สรุปไว้ใน figure 4.1

Information Gathering (การเก็บรวบรวมข้อมูล)

การระบุตัวผู้ต้องสงสัยเป็นเพียงก้าวหนึ่งในการไขปริศนาฆาตกรรมเท่านั้น เพื่อจำกัดชุดผู้ต้องสงสัย Sherlock Holmes และ Dr. Watson จำเป็นต้องรวบรวมข้อมูลเฉพาะเกี่ยวกับแต่ละคน เช่น แรงจูงใจหรือหลักฐานการอ้าง (alibi) ในกรณีของ Selden ข้อมูลนี้รวมถึงข้อเท็จจริงที่ว่าเขาเป็นผู้ต้องโทษที่หลบหนี ข้อมูลเพิ่มเติมทั้งหมดนี้ควรถูกเก็บรวมไว้กับผู้ต้องสงสัยแต่ละคน เมื่อใช้สมุดจด Sherlock Holmes จะเพิ่มข้อมูลเกี่ยวกับบุคคลลงในหน้าที่สงวนไว้สำหรับคนนั้น

การปฏิบัติการของ data type แบบ set ไม่สามารถทำเช่นนั้นได้โดยตรง แต่การปรับเปลี่ยนเล็กน้อยต่อการปฏิบัติการสำหรับการเพิ่มและการค้นหาก็เพียงพอที่จะทำให้เกิดฟีเจอร์นี้ ประการแรก การปฏิบัติการสำหรับการแทรกต้องรับข้อมูลสองชิ้น: key สำหรับระบุข้อมูลและข้อมูลเพิ่มเติมที่เกี่ยวข้องกับ key คีย์สำหรับข้อมูลเกี่ยวกับผู้ต้องสงสัยคือชื่อของเขาหรือเธอ ประการที่สอง การปฏิบัติการสำหรับการค้นหาและการลบจะรับเฉพาะ key เป็นอินพุต ในกรณีการลบ ชื่อและข้อมูลเพิ่มเติมทั้งหมดที่เก็บไว้กับชื่อนั้นจะถูกลบ ในกรณีการค้นหา ข้อมูลที่เก็บไว้สำหรับชื่อนั้นจะถูกคืนค่าเป็นผลลัพธ์

การขยายเล็ก ๆ แต่สำคัญนี้ของ data type แบบ set เรียกว่า dictionary เพราะเหมือนพจนานุกรมจริง มันอนุญาตให้เราค้นหาข้อมูลตามคีย์ เช่นเดียวกับที่ Sherlock Holmes ใช้คู่มือตรวจโรคเพื่อค้นหาประวัติการทำงานของ Dr. Mortimer ในตอนต้นของ The Hound of the Baskervilles พจนานุกรมมองได้ว่าเป็นคอลเลกชันของสัญลักษณ์ โดยแต่ละคีย์เป็นสัญลักษณ์สำหรับข้อมูลที่เก็บไว้กับคีย์นั้น พจนานุกรมแตกต่างจากพจนานุกรมแบบพิมพ์ในสองประการ ประการแรก เนื้อหาของพจนานุกรมแบบพิมพ์คงที่ ขณะที่ dictionary แบบข้อมูลสามารถเปลี่ยนแปลงได้—คำนิยามใหม่สามารถเพิ่ม คำนิยามล้าสมัยสามารถลบ และคำนิยามที่มีอยู่สามารถอัปเดตได้ ประการที่สอง รายการในพจนานุกรมแบบพิมพ์ถูกจัดเรียงตามลำดับตัวอักษรของคีย์ ในขณะที่พจนานุกรมข้อมูลไม่จำเป็นต้องเรียงลำดับ การจัดลำดับในพจนานุกรมแบบพิมพ์จำเป็นเพราะจำนวนรายการมากทำให้การเข้าถึงหน้าโดยตรงเป็นไปไม่ได้ เนื่องจากดัชนีที่เข้าถึงแต่ละหน้าจะต้องมีรายการมากเกินไปและมีขนาดเล็กเกินไป การเรียงคำกุญแจทำให้ผู้ใช้พจนานุกรมสามารถหา entry ได้ด้วยอัลกอริทึมการค้นหา (ดู chapter 5)

ทั้งสองข้อจำกัดของพจนานุกรมแบบกายภาพ—ความจำเป็นในการเรียงลำดับคีย์และขนาด/เนื้อหาที่คงที่—ไม่เป็นจริงสำหรับพจนานุกรมอิเล็กทรอนิกส์ พจนานุกรมแบบไดนามิกที่ใช้อย่างแพร่หลายคือ Wikipedia, ซึ่งไม่เพียงแต่ให้คุณใช้ มันยังให้คุณขยายและอัปเดตข้อมูลได้ ในความจริง เนื้อหาของ Wikipedia ถูกประกอบขึ้นโดยผู้ใช้ของมัน เป็นความสำเร็จอันโดดเด่นของ crowdsourcing และเป็นพยานแห่งพลังของการร่วมมือ ถ้า Sherlock Holmes และ Watson ทำงานคดี The Hound of the Baskervilles ในยุคปัจจุบัน พวกเขาอาจแทนที่จะส่งจดหมายไปมา ใช้ wiki ในการรักษาข้อมูลเกี่ยวกับผู้ต้องสงสัยและคดี

ลักษณะไดนามิกของพจนานุกรมไม่ได้จำกัดเพียงการแทรกและลบข้อมูลเกี่ยวกับผู้ต้องสงสัยเท่านั้น แต่มันยังอนุญาตให้ปรับปรุงข้อมูลเหล่านั้นด้วย ตัวอย่างเช่น ข้อเท็จจริงที่ว่า Selden เป็นพี่ชายของ Eliza Barrymore อาจไม่เป็นที่รู้เมื่อ Selden กลายเป็นผู้ต้องสงสัย จึงต้องเพิ่มเข้าไปใน entry ที่มีอยู่สำหรับเขาในภายหลัง แต่จะทำอย่างไร? เนื่องจากเรามีปฏิบัติการเพียงสามอย่างสำหรับการเพิ่ม การลบ และการค้นหา entry ใน dictionary เราจะอัปเดตข้อมูลที่เก็บกับคีย์ได้อย่างไร? เราทำได้โดยการรวมปฏิบัติการเข้าด้วยกัน: หา entry โดยใช้คีย์ นำข้อมูลที่คืนค่ามา แก้ไขตามที่ต้องการ ลบ entry ออกจากพจนานุกรม แล้วเพิ่มกลับพร้อมข้อมูลที่อัปเดต

เราสามารถเพิ่มปฏิบัติการใหม่ให้กับ data type แบบ set ในลักษณะเดียวกันได้ ตัวอย่างเช่น หาก Sherlock Holmes เก็บเซตของคนที่ได้รับผลประโยชน์จากการตายของ Sir Charles เขาอาจต้องการเพิ่มแรงจูงใจให้กับผู้ต้องสงสัยบางคน ในการทำเช่นนั้น เขาอาจคำนวณจุดร่วม (intersection) ของเซตผู้รับผลประโยชน์กับเซตผู้ต้องสงสัย หรืออาจต้องการระบุผู้ต้องสงสัยใหม่โดยหาผู้รับผลประโยชน์ที่ไม่อยู่ในเซตผู้ต้องสงสัย ในกรณีนี้เขาสามารถคำนวณความแตกต่างของเซต (set difference) ระหว่างสองเซตได้ โดยสมมติว่า data type แบบ set มีปฏิบัติการที่รายงานองค์ประกอบทั้งหมดในเซต อัลกอริทึมสำหรับคำนวณจุดร่วมหรือความแตกต่างของสองเซตนั้นสามารถทำได้โดยการเดินผ่านองค์ประกอบทั้งหมดของหนึ่งเซตและสำหรับแต่ละองค์ประกอบตรวจสอบว่ามันอยู่ในอีกเซตหรือไม่ ถ้าอยู่ มันจะรายงานองค์ประกอบเป็นผลลัพธ์ของการตัดกัน ถ้าไม่อยู่ มันจะรายงานองค์ประกอบเป็นผลลัพธ์ของความแตกต่างของเซต การคำนวณดังกล่าวค่อนข้างธรรมดาเพราะมันสอดคล้องกับการรวมกันของ predicate ตัวอย่างเช่น จุดร่วมของเซตผู้ต้องสงสัยและผู้รับผลประโยชน์สอดคล้องกับนิพจน์ "is a suspect and a beneficiary" และความแตกต่างระหว่างผู้รับผลประโยชน์และผู้ต้องสงสัยสอดคล้องกับนิพจน์ "is a beneficiary and not a suspect"

สุดท้าย เราต้องการโครงสร้างข้อมูลเพื่อ implement dictionaries เพื่อให้เราสามารถคำนวณกับมันได้จริง ๆ เนื่องจาก data type แบบ dictionary แตกต่างจาก data type แบบ set เพียงโดยการผูกข้อมูลเพิ่มเติมกับองค์ประกอบ โครงสร้างข้อมูลส่วนใหญ่สำหรับ sets รวมถึง arrays และ lists สามารถขยายเพื่อ implement dictionaries ได้ นี่เป็นกรณีสำหรับโครงสร้างข้อมูลที่แทนแต่ละองค์ประกอบของเซตอย่างชัดเจน เพราะในกรณีนั้นเราสามารถเพิ่มข้อมูลเพิ่มเติมเข้าไปกับคีย์ได้ นอกจากนี้ยังหมายความว่าโครงสร้างข้อมูลใด ๆ ที่ใช้เพื่อ implement dictionary ก็สามารถใช้เพื่อ implement set ได้เช่นกัน; เพียงเก็บข้อมูลที่ว่างหรือไม่มีความหมายไว้กับคีย์

When Order Matters (เมื่อลำดับมีความสำคัญ)

อย่างที่กล่าวใน chapter 3 การคำนวณจะมีคุณค่าเท่าที่การแทนข้อมูลที่ใช้อยู่เป็นดี ดังนั้น Sherlock Holmes และ Watson อยากให้เซตของผู้ต้องสงสัยสะท้อนสถานะของการสืบสวนให้ถูกต้อง โดยเฉพาะพวกเขาต้องการให้เซตมีขนาดเล็กที่สุดเท่าที่จำเป็น (เพื่อลดความพยายามกับเบาะแสที่ผิด) แต่ก็ต้องใหญ่พอเมื่อจำเป็น (เพื่อไม่ให้ฆาตกรหลุดรอด) นอกนั้นลำดับที่ผู้ต้องสงสัยถูกเพิ่มหรือลบออกจากเซตก็ไม่สำคัญสำหรับพวกเขา

สำหรับงานอื่น ๆ ลำดับของรายการในตัวแทนข้อมูลมีความสำคัญ ลองพิจารณาทายาทของ Sir Charles ที่ล่วงลับ ความแตกต่างระหว่างคนที่หนึ่งและคนที่สองในแถวคือสิทธิได้รับมรดกมูลค่าหนึ่งล้านปอนด์ ข้อมูลนี้ไม่เพียงเกี่ยวกับการตัดสินว่าใครรวยหรือไม่ แต่ยังให้เบาะแสเกี่ยวกับแรงจูงใจของผู้ต้องสงสัยด้วย ในความจริง ฆาตกร Stapleton เป็นคนที่สองในแถวและพยายามฆาคนที่หนึ่ง Sir Henry ขณะที่การสืบทอดมีความสำคัญ ลำดับผู้สืบทอดไม่ได้ถูกกำหนดโดยเวลาที่คนเข้าสู่คอลเลกชัน ตัวอย่างเช่น เมื่อมีทารกเกิดขึ้นกับผู้ให้พินัยกรรม ทารกนั้นจะไม่ได้อยู่ท้ายแถวแต่กลับได้สิทธิ์ก่อนคนเช่นหลานชาย โครงสร้างข้อมูลที่การจัดลำดับองค์ประกอบไม่ได้ถูกกำหนดโดยเวลาเข้าเรียกว่า priority queue ชื่อบอกว่าสถานะขององค์ประกอบในคิวถูกกำหนดโดยลำดับความสำคัญ เช่นความเกี่ยวข้องกับผู้ให้พินัยกรรมกรณีทายาท หรือความรุนแรงของบาดแผลในห้องฉุกเฉิน

ในทางตรงกันข้าม ถ้าลำดับการเข้าเป็นตัวกำหนดตำแหน่งในคอลเลกชัน data type จะเรียกว่า queue หากองค์ประกอบถูกลบออกตามลำดับที่ถูกเพิ่มเข้าไป หรือเรียกว่า stack หากถูกลบออกในลำดับย้อนกลับ คิวเป็นสิ่งที่คุณเจอในซูเปอร์มาร์เก็ต ร้านกาแฟ หรือจุดตรวจความปลอดภัยที่สนามบิน คุณเข้าจากปลายด้านหนึ่งแล้วออกทางอีกปลายหนึ่ง ผู้คนถูกให้บริการ (และออกจากคิว) ตามลำดับที่เข้ามา ดังนั้น data type แบบ queue จึงสื่อถึงนโยบาย first come, first serve ลำดับที่องค์ประกอบเข้าและออกจากคิวยังถูกเรียกว่า FIFO สำหรับ first in, first out

ใน stack ในทางกลับกัน องค์ประกอบจะออกในลำดับตรงกันข้ามกับที่ถูกเพิ่ม ตัวอย่างที่ดีคือกองหนังสือบนโต๊ะของคุณ หนังสือที่อยู่บนสุดซึ่งถูกวางไว้ทีหลังสุดจะต้องถูกเอาออกก่อนหนังสืออื่น ๆ เมื่อคุณนั่งที่ที่นั่งริมหน้าต่างบนเครื่องบิน คุณจะอยู่ด้านล่างของกองเมื่ออยากไปห้องน้ำ คนที่นั่งตรงกลางที่นั่งหลังคุณต้องลุกก่อน และพวกเขาต้องรอคนที่นั่งริมทางเดินซึ่งนั่งทีหลังสุดและอยู่บนสุดของกองอีกที ตัวอย่างอีกอันคือลำดับที่ Hansel และ Gretel วางและเยี่ยมชมก้อนกรวด ก้อนกรวดที่วางทีหลังสุดเป็นก้อนที่เยี่ยมพบเป็นอันดับแรก และถ้าพวกเขาใช้อัลกอริทึมที่ปรับปรุงเพื่อหลีกเลี่ยงการวนลูป ก้อนกรวดที่วางทีหลังสุดจะเป็นก้อนแรกที่พวกเขาหยิบขึ้นมา

ตอนแรก การใช้ data type แบบ stack อาจดูแปลก แต่ stack ดีมากในการจัดระเบียบ สำหรับ Hansel และ Gretel กองก้อนกรวดช่วยให้พวกเขากลับไปยังสถานที่ที่เคยไปก่อนหน้าอย่างเป็นระบบ ซึ่งนำพวกเขากลับถึงบ้านได้ ในทำนองเดียวกัน Theseus หนีออกจากเขาวงกตของ Minotaur ได้ด้วยความช่วยเหลือของด้ายที่ Ariadne มอบให้: การคลี่ด้ายคือการเพิ่มมันทีละนิ้วลงบน stack และการออกจากเขาวงกตโดยการม้วนด้ายคือการลบด้ายออกจาก stack ถ้าในชีวิตประจำวันเราถูกขัดจังหวะจากงานหนึ่งด้วยสายโทรศัพท์ ซึ่งถูกขัดโดยคนเคาะประตู เราจะเก็บงานเหล่านั้นไว้ในใจเป็น stack และทำงานล่าสุดให้เสร็จก่อนแล้วจึงกลับไปทำงานก่อนหน้า ลำดับที่องค์ประกอบเข้าและออกจาก stack จึงเรียกว่า LIFO สำหรับ last in, first out และถ้าต้องการจำคำย่อของ priority queue เราอาจเรียกมันว่า HIFO สำหรับ highest (priority) in, first out

สำหรับ data type แบบ set และ dictionary เราอยากรู้ว่าโครงสร้างข้อมูลใดสามารถใช้ implement (priority) queue และ stack ได้ มองเห็นได้ง่ายว่า stack สามารถ implement ได้ดีโดย list: โดยเพิ่มและลบองค์ประกอบเสมอที่หน้าของ list เราจะได้ลำดับ LIFO และใช้เวลาเพียง constant time เช่นเดียวกันโดยการเพิ่มองค์ประกอบที่ท้าย list และลบออกที่หัว เราจะได้พฤติกรรม FIFO ของ queue นอกจากนี้ยังเป็นไปได้ที่จะ implement queues และ stacks ด้วย arrays

คิวและสแตกรักษาลำดับขององค์ประกอบระหว่างการอยู่ในโครงสร้างข้อมูลจึงมีรูปแบบการออกที่คาดการณ์ได้ การรอคิวที่จุดตรวจความปลอดภัยที่สนามบินมักค่อนข้างน่าเบื่อ เรื่องจะน่าตื่นเต้นขึ้นเมื่อมีคนตัดคิวหรือมีเลนพิเศษสำหรับลูกค้าที่มี priority พฤติกรรมนี้สะท้อนใน data type แบบ priority queue

It Runs in the Family (มันวิ่งอยู่ในตระกูล)

ทายาทของ Sir Charles Baskerville เป็นตัวอย่างที่ดีของ priority queue เกณฑ์ความสำคัญที่กำหนดตำแหน่งของแต่ละทายาทคือความสัมพันธ์หรือระยะห่างจาก Sir Charles ผู้ล่วงลับ แต่จะวัดความใกล้ชิดนี้อย่างไร? กฎการสืบทอดง่าย ๆ ทั่วไปคือ ลูกของผู้ล่วงลับจะอยู่ในแถวก่อนตามลำดับอายุ โดยสมมติว่ามรดกถูกส่งต่อไปยังทายาทเอง กฎนี้หมายความว่าถ้าไม่มีลูก พี่น้องที่อายุมากที่สุดจะได้รับมรดกต่อไป ตามด้วยลูกของพวกเขา และถ้าไม่มีพี่น้อง การสืบทอดจะต่อไปยังป้า ลุงที่อายุมากสุดและลูกของพวกเขา และต่อเนื่องไปเช่นนี้

กฎนี้สามารถแสดงเป็นอัลกอริทึมได้: สมาชิกในครอบครัวทั้งหมดแทนด้วยโครงสร้างข้อมูลแบบ tree ที่สะท้อนความสัมพันธ์บรรพบุรุษ/ลูกหลาน จากนั้นอัลกอริทึมสำหรับการไล่ต้นไม้จะสร้างรายการของสมาชิกครอบครัวซึ่งตำแหน่งของบุคคลกำหนดลำดับความสำคัญในการรับมรดก ลำดับความสำคัญนี้จะถูกใช้เป็นเกณฑ์ใน priority queue ของทายาท แต่หากเรามีรายการทายาทที่ครบถ้วนและเรียงตามลำดับแล้ว ทำไมเราต้องใช้ priority queue? คำตอบคือเราไม่ต้องใช้ เราต้องการ priority queue เฉพาะเมื่อไม่ทราบต้นไม้ครอบครัวทั้งหมดตั้งแต่ต้น หรือเมื่อมันเปลี่ยนไป เช่น เมื่อมีเด็กเกิด ในกรณีนั้น ต้นไม้ครอบครัวจะเปลี่ยน และรายการที่คำนวณจากต้นไม้เก่าจะไม่สะท้อนลำดับการสืบทอดที่ถูกต้อง

ข้อมูลใน The Hound of the Baskervilles ระบุว่า Hugo Baskerville ผู้เป็นพ่อมีลูกสี่คน Charles เป็นลูกคนโตและรับมรดกจาก Hugo พี่ชายถัดมาคือ John ซึ่งมีลูกคนหนึ่งชื่อ Henry และน้องชายคนสุดท้องคือ Rodger มีลูกชายคือ Stapleton เรื่องระบุว่า Hugo Baskerville มีลูกสาว Elizabeth ซึ่งข้าพเจ้าสันนิษฐานว่าเป็นลูกคนสุดท้อง ชื่อในต้นไม้เรียกว่า nodes และเช่นในต้นไม้ครอบครัว เมื่อ node B (เช่น John) เชื่อมกับ node A ข้างบน (เช่น Hugo) B จะถูกเรียกว่าลูกของ A และ A เรียกว่า parent ของ B node ที่อยู่บนสุดของต้นไม้ซึ่งไม่มี parent เรียกว่า root และ node ที่ไม่มีลูกเรียกว่า leaves

กฎการสืบทอดที่ใช้กับต้นไม้ครอบครัวของ Baskerville กล่าวว่าคนสืบทอดควรเป็น Charles, John, Rodger, และ Elizabeth ตามลำดับที่ระบุ เนื่องจากกฎยังระบุว่าลูกได้รับมรดกก่อนพี่น้อง นั่นหมายความว่า Henry อยู่ก่อน Rodger และ Stapleton อยู่ก่อน Elizabeth กล่าวอีกนัยหนึ่ง รายการทายาทที่เรียงลำดับควรเป็นดังนี้:

Hugo → Charles → John → Henry → Rodger → Stapleton → Elizabeth

รายการทายาทนี้สามารถคำนวณได้โดยการไล่ต้นไม้ในลำดับหนึ่งซึ่งเยี่ยมชมแต่ละ node ก่อนลูก ๆ ของมัน การไล่ต้นไม้ดังกล่าวยังเยี่ยมชมหลานของลูกคนโตก่อนที่จะเยี่ยมชมลูกคนเล็กกว่า (และหลานของพวกเขา) อัลกอริทึมสำหรับการคำนวณรายการทายาทของ node หนึ่งในต้นไม้สามารถอธิบายได้ดังนี้:

เพื่อคำนวณรายการทายาทสำหรับ node N ให้คำนวณและต่อท้ายรายการทายาทของลูกทั้งหมดของมัน (จากเก่าที่สุดไปยังใหม่ที่สุด) แล้ววาง node N ไว้ที่จุดเริ่มต้นของผลลัพธ์

คำอธิบายนี้บ่งชี้ว่ารายการทายาทสำหรับ node ที่ไม่มีลูกประกอบด้วย node นั้นเพียงตัวเดียว ดังนั้นรายการทายาทสำหรับต้นไม้ได้จากการคำนวณรายการทายาทของ root อาจดูแปลกที่อัลกอริทึมอ้างถึงตัวมันเองในการบรรยาย แต่คำอธิบายเช่นนี้เรียกว่า recursive (ดู chapters 12 และ )

ต่อไปเป็นตัวอย่างการทำงานของอัลกอริทึมบนต้นไม้ตัวอย่าง สมมติว่า Henry มีลูกสองคนคือ Jack และ Jill และมีน้องสาวคนหนึ่งชื่อ Mary:

ถ้าเรารันอัลกอริทึมบนต้นไม้นี้เริ่มจาก Hugo เราต้องคำนวณรายการทายาทสำหรับลูกแต่ละคนของ Hugo เริ่มจากลูกคนโต รายการทายาทสำหรับ Charles ประกอบด้วยตัวเขาเองเท่านั้นเพราะเขาไม่มีลูก สถานการณ์น่าสนใจกว่าสำหรับ John ในการคำนวณรายการทายาทของเขา เราต้องคำนวณรายการทายาทของ Henry และ Mary แล้วต่อเข้าด้วยกัน รายการทายาทของ Henry ประกอบด้วยลูกของเขาพร้อมตัวเขาเอง และเพราะ Mary ไม่มีลูก รายการทายาทของเธอมีเพียงตัวเธอเอง เท่าที่นี้เราได้คำนวณรายการทายาทดังนี้:

Node	Inheritance List
Charles	Charles
John	John → Henry → Jack → Jill → Mary
Henry	Henry → Jack → Jill
Mary	Mary
Jack	Jack
Jill	Jill

รายการทายาทของ node จะเริ่มด้วย node นั้นเอง และรายการทายาทของ node ที่ไม่มีลูกเป็นรายการที่ประกอบด้วย node ตัวนั้นเท่านั้น ยิ่งไปกว่านั้น รายการทายาทของ Henry และ John แสดงให้เห็นว่ารายการทายาทของ node ที่มีลูกได้มาจากการต่อรายการทายาทของลูก ๆ ของมัน รายการทายาทของ Rodger และ Elizabeth ถูกคำนวณในลักษณะเดียวกัน และถ้าเราต่อรายการทายาทของลูกทั้งสี่ของ Hugo แล้วเพิ่มเขาไว้ด้านหน้า เราจะได้รายการทายาทที่เรียงลำดับดังนี้:

Hugo → Charles → John → Henry → Jack → Jill → Mary → Rodger → Stapleton → Elizabeth

อัลกอริทึมการสืบทอดเป็นตัวอย่างของ tree traversal อัลกอริทึมที่เยี่ยมชมทุก node ของต้นไม้ เนื่องจากมันทำงานจากบนลงล่าง จาก root สู่ leaves และเยี่ยมชม node ก่อนลูก ๆ ของมัน มันถูกเรียกว่า preorder traversal คิดภาพกระรอกที่ค้นหาถั่วในต้นไม้ เพื่อไม่ให้พลาดถั่วใด ๆ มันต้องเยี่ยมชมทุกกิ่งของต้นไม้ มันสามารถทำเช่นนั้นได้โดยใช้กลยุทธ์ต่าง ๆ ทางหนึ่งคือขึ้นไประดับความสูงและเยี่ยมชมกิ่งทั้งหมดในระดับหนึ่งก่อนจะไปยังระดับถัดไป อีกวิธีหนึ่งคือเดินตามกิ่งจนสุดก่อนจะเปลี่ยนไปยังกิ่งอื่น ทั้งสองวิธีรับประกันว่ากิ่งทั้งหมดจะถูกเยี่ยมชมและถั่วจะถูกเก็บ แต่ความแตกต่างคือลำดับที่กิ่งถูกเยี่ยมชม ความแตกต่างนี้ไม่สำคัญสำหรับกระรอกเพราะมันจะเก็บถั่วทั้งหมดไม่ว่าอย่างไร แต่ลำดับของการเยี่ยมชม node ในต้นไม้ครอบครัวมีความสำคัญเมื่อพูดถึงการสืบทอด เพราะคนแรกที่ถูกพบจะได้รับมรดกทั้งหมด preorder traversal ของอัลกอริทึมการสืบทอดเป็นการไล่ต้นไม้แบบที่สอง นั่นคือ ตามกิ่งจนสุดก่อนจะเปลี่ยน

การใช้งานสำคัญหนึ่งของ data types และการ implement ผ่านโครงสร้างข้อมูลคือการรวบรวมข้อมูลไว้ที่จุดหนึ่งในอัลกอริทึมและนำกลับมาใช้ต่อในภายหลัง เนื่องจากการค้นหาสมาชิกเฉพาะในคอลเลกชันเป็นปฏิบัติการที่สำคัญและใช้บ่อย นักวิทยาการคอมพิวเตอร์จึงทุ่มเทความพยายามในการศึกษาโครงสร้างข้อมูลที่รองรับปฏิบัติการนี้อย่างมีประสิทธิภาพ หัวข้อนี้ถูกสำรวจอย่างละเอียดใน chapter 5