ชนิดของข้อมูลที่กล่าวถึงใน chapter 4 บรรยายรูปแบบการเข้าถึงของคอลเลกชันข้อมูลบางประเภท เพราะคอลเลกชันอาจเติบโตอย่างมาก การพิจารณาที่ใช้งานได้จริงคือการจัดการให้มีประสิทธิภาพ เราเห็นแล้วว่า data structures ต่างชนิดสามารถทำให้การดำเนินการบางอย่างเร็วขึ้นและต้องการพื้นที่จัดเก็บต่างกัน แม้การสร้างและแปลงคอลเลกชันจะสำคัญ การค้นหาไอเท็มในคอลเลกชันน่าจะเป็นงานที่จำเป็นที่สุด

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

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

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

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

The Key to Fast Search (กุญแจสู่การค้นหาที่รวดเร็ว)

ในเรื่อง The Last Crusade Indiana Jones ออกตามหาสองสิ่ง ครั้งแรกคือพ่อของเขา Henry Jones, Sr. แล้วทั้งคู่ร่วมกันออกตามหา Holy Grail ในฐานะศาสตราจารย์โบราณคดี Indiana Jones รู้เรื่องการค้นหาเป็นอย่างดี ในบรรยายครั้งหนึ่งเขาอธิบายนักศึกษาไว้ว่า

โบราณคดีคือการค้นหาข้อเท็จจริง

การค้นหาโบราณวัตถุ—หรือแม้แต่การค้นหาคน—ทำงานอย่างไร? ถ้ารู้ตำแหน่งของสิ่งที่ค้นหา ก็ไม่ต้องค้นหา แค่ไปที่นั่นแล้วหาได้เลย มิฉะนั้นกระบวนการค้นหาขึ้นกับสองสิ่ง: search space และเบาะแสหรือ keys ที่ช่วยแคบพื้นที่ค้นหา

ใน The Last Crusade Indiana Jones ได้รับสมุดบันทึกของพ่อที่มีข้อมูลเกี่ยวกับ Holy Grail ส่งมาจากเวนิส ซึ่งทำให้เขาเริ่มค้นหาที่นั่น ต้นทางของสมุดเป็นเบาะแสที่ช่วยแคบพื้นที่ค้นหาเริ่มต้นอย่างมาก—จากทั้งโลกมาเป็นเมืองเดียว ในตัวอย่างนี้ search space เป็นพื้นที่เชิงเรขาคณิตสองมิติ แต่โดยทั่วไปคำว่า search space หมายถึงสิ่งที่เป็นนามธรรมมากขึ้น เช่น โครงสร้างข้อมูลที่แทนคอลเลกชันของไอเท็มก็สามารถมองเป็น search space ที่สามารถค้นหาชื่อเฉพาะได้ รายชื่อผู้ต้องสงสัยของ Sherlock Holmes ก็เป็น search space แบบนี้ที่เราสามารถค้นหาชื่อได้

การค้นหาใน list เป็นอย่างไรบ้าง? ตามที่กล่าวใน chapter 4 ในกรณีแย่ที่สุดเราต้องตรวจทุกองค์ประกอบใน list ก่อนจะพบหรือยืนยันว่าไม่มีองค์ประกอบที่ต้องการ ซึ่งหมายความว่าการค้นหาใน list ไม่ได้ใช้ประโยชน์จากเบาะแสในการแคบ search space เลย

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

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

หลังจากมาถึงเวนิส การค้นหาของ Indiana Jones ดำเนินต่อในห้องสมุด การค้นหาหนังสือในห้องสมุดเป็นตัวอย่างที่ดีของแนวคิดขอบเขตและ key เมื่อชื่อหนังสือวางบนชั้นตามนามสกุลผู้แต่ง ชั้นมักติดป้ายด้วยชื่อผู้แต่งของหนังสือเล่มแรกและเล่มสุดท้าย สองชื่อนี้กำหนดช่วงของผู้แต่งที่มีหนังสือบนชั้นนั้น ซึ่งเป็นขอบเขตที่แยกหนังสือของผู้แต่งในช่วงจากหนังสือทั้งหมด สมมติเรากำลังหาหนังสือ The Hound of the Baskervilles ของ Arthur Conan Doyle เราสามารถใช้ชื่อนามสกุลผู้แต่งเป็น key เพื่อหาชั้นที่ช่วงชื่อครอบคลุมนามสกุลนั้น เมื่อพบแล้วเราจะค้นหาหนังสือบนชั้นนั้น การค้นหามีสองระยะ ระยะแรกหาชั้น แล้วหาหนังสือบนชั้น วิธีนี้ดีเพราะแบ่ง search space เป็นส่วนย่อยเล็กๆ ที่ไม่ซ้อนทับกัน (ชั้นต่างๆ)

การค้นหาผ่านชั้นสามารถทำได้หลายวิธี หนึ่งวิธีง่ายๆ คือดูชั้นทีละชั้นจนพบชั้นที่ช่วงชื่อรวมถึง Doyle วิธีนี้ถือว่าชั้นเป็น list และมีข้อเสียเหมือนกัน ในกรณีของ Doyle การค้นหาอาจไม่ใช้เวลานานนัก แต่ถ้ากำลังค้นหาหนังสือของ Yeats จะใช้เวลามาก คนส่วนใหญ่อาจไม่เริ่มที่ชั้น A แต่จะเริ่มใกล้ชั้น Z เพื่อหาใกล้ๆ วิธีนี้ขึ้นกับสมมติฐานว่าชั้นเรียงตามตัวอักษรของชื่อผู้แต่ง และถ้ามี 26 ชั้น (สมมติหนึ่งชั้นต่อหนึ่งตัวอักษร) จะเริ่มค้นหา Yeats ที่หนึ่งในยี่สิบห้าของชั้นสุดท้าย และหา Doyle ที่หนึ่งในสี่ของชั้น แนวคิดคือมองชั้นเป็น array ที่มีดัชนีเป็นตัวอักษร แน่นอนห้องสมุดไม่น่าจะมี 26 ชั้นเป๊ะ แต่วิธีนี้ขยายได้ตามจำนวนชั้น โดยเริ่มการค้นหาในส่วนที่คาดว่า Yeats จะอยู่ ปัญหาคือการแจกแจงของชื่อผู้แต่งไม่สม่ำเสมอ ทำให้วิธีนี้ไม่แม่นยำ ดังนั้นจึงต้องกลับไปมาเพื่อหาชั้นเป้าหมาย แต่การใช้ความรู้เกี่ยวกับการแจกแจงชื่อสามารถปรับปรุงความแม่นยำได้มาก แม้ว่าวิธีง่ายๆ ก็ยังใช้ได้ดีในทางปฏิบัติและขจัดชั้นจำนวนมากออกจากการพิจารณาได้เลย

การค้นหาหนังสือบนชั้นสามารถทำได้หลายวิธีอีกครั้ง หนึ่งสามารถสแกนหนังสือทีละเล่มหรือใช้กลยุทธ์คล้ายกับการหาชั้นโดยประมาณตำแหน่งหนังสือจากเบาะแสในช่วงของผู้แต่งสำหรับชั้นนั้น โดยรวมแล้ววิธีสองขั้นตอนนี้ทำงานได้ดีและเร็วกว่าการมองทุกเล่มทีละเล่มมาก ผมทำการทดลองค้นหา The Hound of the Baskervilles ในห้องสมุดสาธารณะ Corvallis ผมสามารถหาชั้นที่ถูกต้องได้ในห้าก้าวและหาหนังสือบนชั้นในอีกเจ็ดก้าว นี่เป็นการปรับปรุงอย่างมากเมื่อเทียบกับวิธีง่ายๆ โดย ณ ขณะนั้นห้องสมุดมีหนังสือในหมวดนวนิยายผู้ใหญ่ 44,679 เล่มบน 36 ชั้น

การตัดสินใจของ Indiana Jones ที่จะไปเวนิสเพื่อค้นหาพ่อของเขาขึ้นอยู่กับกลยุทธ์คล้ายกัน ในกรณีนี้โลกถูกมองเป็น array ที่เซลแทนภูมิภาคทางภูมิศาสตร์ที่มีดัชนีตามชื่อเมือง ที่อยู่ส่งคืนในจดหมายที่มีสมุดบันทึกของ Henry Jones, Sr. เป็นเบาะแสที่เลือกเซลที่มีดัชนีว่า "Venice" เพื่อดำเนินการค้นหา ในเวนิส การค้นหาพา Indiana Jones ไปยังห้องสมุด ที่นั่นเขาไม่ได้หาหนังสือแต่หาหลุมฝังศพของ Sir Richard หนึ่งในอัศวินแห่งการเดินทางครั้งแรก เขาพบหลุมฝังศพหลังจากเขาทุบกระเบื้องที่มีเครื่องหมาย X ซึ่งมีความขบขันเล็กน้อยเมื่อเทียบกับคำพูดก่อนหน้านั้นของเขาต่อนักศึกษา

X ไม่เคยเป็นตำแหน่งที่ถูกต้องเลย

กุญแจสู่การค้นหาที่รวดเร็วคือการมีโครงสร้างที่ช่วยให้แคบ search space ได้อย่างรวดเร็ว ยิ่ง "ด้านใน" ที่กำหนดโดย key เล็กลงเท่าไร ยิ่งดี เพราะจะทำให้การค้นหาเข้าหาจุดหมายได้เร็วขึ้น ในกรณีค้นหาหนังสือจะมีสองเฟสที่ถูกแบ่งโดยขั้นตอนการแคบพื้นที่ครั้งใหญ่หนึ่งครั้ง

Survival by Boggle (การเอาชีวิตรอดด้วยบ็อกเกิล)

การค้นหามักปรากฏในรูปแบบปลอมตัวและในสถานการณ์ที่คาดไม่ถึง ปลายเรื่อง The Last Crusade Indiana Jones มาถึง Temple of the Sun ที่ซึ่งเขาต้องฝ่าฟันสามความท้าทายก่อนจะเข้าห้องที่มี Holy Grail ความท้าทายที่สองคือการข้ามพื้นกระเบื้องที่มีช่องว่าง ปัญหาคือกระเบื้องบางอันปลอดภัยในขณะที่บางอันแตกและนำไปสู่ความตายพื้นนั้นมีประมาณ 50 แผ่น จัดในกริดไม่สม่ำเสมอ แต่ละแผ่นมีตัวอักษร ชีวิตนักโบราณคดีช่างยากลำบาก: บางวันต้องทุบกระเบื้องเพื่อไปต่อ บางวันต้องหลีกเลี่ยงมันให้สุดชีวิต

การหากระเบื้องที่ปลอดภัยไม่ใช่เรื่องง่าย เพราะถ้าไม่มีข้อจำกัดเพิ่มเติม จำนวนความเป็นไปได้นั้นมหาศาล: มากกว่าหนึ่งพันล้านล้าน—1 ตามด้วยศูนย์ 15 ตัว เบาะแสในการหาลำดับกระเบื้องที่นำไปสู่ฝั่งปลอดภัยคือว่ากระเบื้องควรสะกดคำ Iehova ข้อมูลนี้แทบจะแก้ปริศนาได้ แต่การระบุลำดับกระเบื้องที่ถูกต้องยังต้องทำงานพอสมควร น่าแปลกที่มันเกี่ยวข้องกับการ search ที่ค่อยๆ แคบพื้นที่ความเป็นไปได้

งานนี้คล้ายการเล่น Boggle ซึ่งเป้าหมายคือค้นหาสตริงของตัวอักษรที่เชื่อมกันบนกริดให้เป็นคำ งานของ Indiana Jones ดูเหมือนง่ายกว่าเพราะเขารู้อยู่แล้วว่าคำคืออะไร อย่างไรก็ตามใน Boggle ตัวอักษรติดต่อกันต้องอยู่บนกระเบื้องที่ติดกัน ซึ่งไม่ใช่ข้อจำกัดของปัญหาพื้นกระเบื้องนี้ จึงมีความเป็นไปได้มากกว่าและยากกว่า

เพื่ออธิบายปัญหาการค้นหา ให้สมมติพื้นกระเบื้องมีหกแถว แต่ละแถวมีแปดตัวอักษร ซึ่งได้กริดขนาด 48 แผ่น ถ้าทางที่ถูกต้องประกอบด้วยหนึ่งแผ่นในแต่ละแถว จะมี 8 × 8 × 8 × 8 × 8 × 8 = 262,144 ทางที่เป็นไปได้ ทั้งหมดนี้มีเพียงเส้นทางเดียวที่ปลอดภัย

แล้ว Indiana Jones จะหาทางอย่างไร? ด้วยเบาะแสเขาหากระเบื้องที่มีตัวอักษร I ในแถวแรกและเหยียบมัน การระบุนี้เองเป็นกระบวนการค้นหาที่ต้องทำหลายขั้น หากตัวอักษรบนแผ่นไม่เรียงตามอักษร Indiana Jones ต้องมองทีละแผ่นจนพบ I แล้วก้าวไปต่อเพื่อหาตัวอักษรถัดไป e ในแถวที่สอง และต่อไปเรื่อยๆ

ถ้าการค้นหาแบบทีละตัวทำให้นึกถึงการค้นหาใน list คุณถูกต้อง นี่คือสิ่งที่เกิดขึ้น ต่างกันตรงที่การค้นหาใน list ถูกใช้ซ้ำสำหรับแต่ละแถว นั่นคือ สำหรับแต่ละตัวอักษรของคำเบาะแส และนี่แหละคือพลังของวิธีนี้ ลองคิดดูผลกระทบต่อ search space ซึ่งมี 262,144 เส้นทางต่างๆ แต่ละกระเบื้องแถวแรกจะเป็นจุดเริ่มต้นที่ต่างกันที่สามารถต่อไปได้ 32,768 ทางโดยการเลือกตัวอักษรจากห้าแถวที่เหลือ เมื่อ Indiana Jones มองที่แผ่นแรก สมมติว่าเป็นตัว K เขาจะไม่เหยียบเพราะไม่ตรงกับ I การตัดสินใจนี้ทำให้เส้นทาง 32,768 เส้นถูกลบออกจาก search space และการปฏิเสธแต่ละแผ่นในแถวแรกก็ทำให้เกิดการลดแบบเดียวกัน

เมื่อ Indiana Jones ถึงแผ่นที่ถูกต้อง การลด search space ยิ่งเด่นชัดขึ้น เพราะเมื่อเขาเหยียบแผ่น การตัดสินใจสำหรับแถวแรกเสร็จสิ้น และ search space ลดลงเป็น 32,768 ทางที่สามารถก่อตัวได้จากห้าแถวที่เหลือ โดยรวมแล้ว ด้วยการตัดสินใจไม่เกินเจ็ดครั้ง (ซึ่งต้องใช้เมื่อแผ่น I อยู่ท้ายสุด) Indiana Jones ลด search space ลงเป็นหนึ่งในแปด และทำต่อกับแถวที่สองและตัวอักษร e อีกครั้ง search space ถูกลดลงเป็นหนึ่งในแปดเป็น 4,096 และเมื่อถึงแถวสุดท้ายจะเหลือแค่แปดทาง และด้วยการตัดสินใจไม่เกินเจ็ดครั้งก็สามารถจบเส้นทาง ในกรณีแย่สุดการค้นหานี้ต้องการ 6 × 7 = 42 “ขั้นตอน” (จริงๆ แล้วเดินแค่หกก้าว)—วิธีที่มีประสิทธิภาพอย่างน่าทึ่งในการหาหนึ่งเส้นทางจาก 262,144

อาจไม่ชัดเจน แต่ความท้าทายที่ Indiana Jones เอาชนะมีความคล้ายกับเรื่อง Hansel and Gretel ทั้งสองกรณีตัวละครต้องหาทางไปยังความปลอดภัย และในทั้งสองกรณีทางประกอบด้วยลำดับตำแหน่งที่ถูกทำเครื่องหมาย—ใน Hansel and Gretel ด้วยก้อนกรวด ใน Indiana Jones ด้วยตัวอักษร การค้นหาตำแหน่งถัดไปในเส้นทางต่างกัน: Hansel and Gretel เพียงต้องหาก้อนกรวดใดๆ (แต่ต้องระวังไม่ให้กลับไปที่เดิม) ขณะที่ Indiana Jones ต้องหาตัวอักษรเฉพาะ ทั้งสองตัวอย่างเน้นบทบาทของการแทนข้อมูลในการคำนวณ ความท้าทายของ Indiana Jones แสดงให้เห็นว่าลำดับของเครื่องหมาย (ตัวอักษร) สำหรับแต่ละแผ่นเป็นเครื่องหมายอีกชั้นหนึ่ง (คำ Iehova) สำหรับเส้นทาง นอกจากนี้คำ Iehova ที่แทนเส้นทางแสดงให้เห็นว่าการคำนวณที่เพียงค้นหาคำหนึ่งคำก็มีความหมายและสำคัญในโลกแห่งความเป็นจริง

วิธีที่ Indiana Jones หาแถวของคำบนกริดก็เหมือนการค้นหาในพจนานุกรม: ก่อนอื่นแคบกลุ่มหน้าที่มีคำที่ขึ้นต้นด้วยตัวเดียวกับเบาะแส จากนั้นแคบกลุ่มหน้าต่อไปที่ตรงกับตัวอักษรแรกและตัวที่สอง และทำต่อไปจนกว่าจะพบคำ

เพื่อเข้าใจ data structure ที่ซ่อนอยู่หลังกริดกระเบื้องและทำให้การค้นหาของ Indiana Jones มีประสิทธิภาพ เราจะดูวิธีการแทนคำและพจนานุกรมอีกแบบหนึ่งที่ใช้ trees เพื่อจัดระเบียบ search space

Counting with a Dictionary (การนับด้วยพจนานุกรม)

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

มาพิจารณาปัญหาพื้นกระเบื้องของ Indiana Jones อีกครั้ง ในหนังฉากก้าวแรกของเขากลายเป็นฉากดราม่าที่เขาเกือบถูกฆ่าจากการก้าวบนแผ่นที่ไม่ปลอดภัย เขาใช้สะกดว่า Jehova และก้าวบนตัว J ซึ่งแตกใต้เท้า นี่แสดงให้เห็นว่าปัญหาซับซ้อนกว่าที่คิดเพราะ Indiana Jones อาจไม่แน่ใจจริงๆ ว่าสะกดคำถูกต้องเป็นอย่างไร นอกจากการสะกดด้วย I และ J ยังมีอีกแบบที่ขึ้นต้นด้วย Y และชื่ออื่นๆ ที่อาจใช้ได้เช่น Yahweh และ God สมมติว่านี่คือความเป็นไปได้ทั้งหมดและ Indiana Jones กับพ่อมั่นใจว่าอย่างน้อยหนึ่งคำในนี้ชี้ทางที่ปลอดภัย

แล้วกลยุทธ์ที่ดีจะเป็นอย่างไรถ้าคำทั้งหมดมีโอกาสเท่ากัน เขาสามารถปรับโอกาสโดยเลือกตัวอักษรที่ปรากฏในมากกว่าหนึ่งชื่อ เช่นเลือก J (เหมือนที่เขาทำ) เพราะ J มีในชื่อเพียงหนึ่งจากห้าคำ จึงมีโอกาส 1 ใน 5 (20%) ว่าแผ่นนั้นจะปลอดภัย ในทางกลับกันการย่ำบนแผ่นที่มี v ปลอดภัยถึง 60% เพราะ v ปรากฏในสามชื่อ ถ้าคำใดคำหนึ่งในสามคำนี้ถูกต้อง แผ่น v จะปลอดภัย ดังนั้นการย่ำ v เพิ่มโอกาสรอดเป็น 3 ใน 5 สำหรับแผ่น v

ดังนั้นกลยุทธ์ที่ดีคือคำนวณความถี่ของตัวอักษรจากห้าคำแล้วเลือกกระเบื้องที่มีอัตราการเกิดสูงสุด แผนที่ที่แมปตัวอักษรกับความถี่นี้เรียกว่า histogram เพื่อคำนวณ histogram ของตัวอักษร Indiana Jones ต้องเก็บตัวนับสำหรับแต่ละตัวอักษร โดยการสแกนคำทั้งหมดเขาสามารถเพิ่มตัวนับสำหรับตัวอักษรที่พบ การเก็บตัวนับสำหรับตัวอักษรต่างๆ เป็นงานที่พจนานุกรม (dictionary) จัดการได้ (ดู chapter 4) ในแอปพลิเคชันนี้คีย์คือแต่ละตัวอักษร และข้อมูลที่เก็บกับแต่ละคีย์คือความถี่ของตัวอักษร

G:1 → o:1 → d:1 (ตัวอย่าง: รูปแบบการนับที่ได้จากคำว่า "God")

G:1 → o:1 → d:1 (ตัวอย่าง: รูปแบบการนับจากคำแรก) (ตัวอย่าง: รูปแบบการนับที่ได้จากคำว่า "God")

(แปลเป็นภาษาไทยโดยผู้แปล)

(ตัวอย่าง: การแทรกตัวอักษรใน list แสดงขั้นตอนที่ต้องทำและต้นทุนที่เกิดขึ้น)

โปรดสังเกตว่าการเพิ่ม G ใช้หนึ่งขั้นตอน การเพิ่ม o ใช้สองขั้นตอนเพราะต้องเพิ่มหลัง G และการเพิ่ม d ใช้สามขั้นตอนเพราะต้องเพิ่มหลัง G และ o แต่เราจะไม่เพิ่มตัวอักษรใหม่ไว้หน้าสุดเพราะต้องมั่นใจก่อนว่าตัวอักษรนั้นยังไม่มีใน list ดังนั้นต้องมองทุกตัวอักษรที่มีอยู่ก่อนจะเพิ่ม ถ้าตัวอักษรมีอยู่แล้ว เราจะเพิ่มตัวนับแทน ดังนั้นเราใช้ไปแล้ว 1 + 2 + 3 = 6 ขั้นตอนสำหรับคำแรก

G:1 → o:4 → d:1 → I:1 → e:4 → h:4 → v:3 → a:4 → J:1 → Y:2 → w:1 (ผลลัพธ์สุดท้ายของการสร้างรายการตัวอักษร)

G:1 → o:2 → d:1 → I:1 → e:1 → h:1 → v:1 → a:1 (ตัวอย่าง: ผลลัพธ์หลังประมวลผลคำที่สอง)

(แปลเป็นภาษาไทยโดยผู้แปล)

(รายการแสดงการอัปเดตตัวนับหลังการแทรกคำที่สอง)

การอัปเดตพจนานุกรมจากคำ Jehova ต้องใช้ 9 ขั้นตอนสำหรับการเพิ่ม J และอีก 5, 6, 2, 7, 8 ขั้นตอนสำหรับการอัปเดตตัวนับของตัวอักษรที่มีอยู่ รวมเป็น 75 ขั้นตอน หลังจากประมวลผลสองคำสุดท้าย Yahweh และ Yehova (ใช้ 40 และ 38 ขั้นตอนตามลำดับ) เราจะได้รายการสุดท้ายดังนี้: G:1 → o:4 → d:1 → I:1 → e:4 → h:4 → v:3 → a:4 → J:1 → Y:2 → w:1 (ผลลัพธ์สุดท้ายของการสร้างรายการตัวอักษร)

G:1 → o:4 → d:1 → I:1 → e:4 → h:4 → v:3 → a:4 → J:1 → Y:2 → w:1 (สรุปผลลัพธ์)

(แปลเป็นภาษาไทยโดยผู้แปล)

(ผลลัพธ์สุดท้ายของการสร้าง list พร้อมตัวนับรวม)

โปรดสังเกตว่าเราไม่ควรเพิ่ม h ตัวที่สองใน Yahweh เพราะการนับมันสองครั้งในคำเดียวจะทำให้โอกาสของตัวอักษรเพิ่มขึ้นอย่างผิดพลาด (ในกรณีนี้จาก 80% เป็น 100%) การสแกนสุดท้ายของ list แสดงให้เห็นว่าตัวอักษร o, e, h, และ a เป็นตัวที่ปลอดภัยเริ่มต้นทั้งหมด มีความน่าจะเป็น 80% จะอยู่ในคำที่ถูกต้อง

Lean Is Not Always Better (ความบางไม่ใช่คำตอบเสมอไป)

ข้อเสียหลักของการใช้ list เป็นการใช้งานพจนานุกรมคือค่าใช้จ่ายสูงเมื่อเข้าถึงไอเท็มที่อยู่ท้าย list บ่อยๆ

โครงสร้างข้อมูล binary search tree พยายามหลีกเลี่ยงปัญหานี้โดยแบ่ง search space ให้สมดุลขึ้นเพื่อรองรับการค้นหาที่เร็วขึ้น binary tree คือ tree ที่แต่ละ node มีลูกได้ไม่เกินสองคน ตามที่กล่าวไว้ node ที่ไม่มีลูกเรียกว่า leaf ส่วน node ที่มีลูกเรียกว่า internal node และ node ที่ไม่มี parent เรียกว่า root ของ tree

ลองดูตัวอย่าง binary tree ใน figure 5.1 ทางซ้ายเป็น tree หนึ่ง node—ต้นไม้ที่ง่ายที่สุด root ที่เป็น leaf ประกอบด้วยตัวอักษร G ต้นไม้นี้ไม่ค่อยดูเหมือนต้นไม้ มากเหมือน list หนึ่งองค์ประกอบ ตรงกลางเพิ่ม node หนึ่งคือ child o ของ root และในต้นไม้ขวา child d มีลูก a และ e ตัวอย่างนี้แสดงว่า ถ้าเราตัดลิงก์ถึง parent node หนึ่ง node จะกลายเป็น root ของต้นไม้แยก ซึ่งเรียกว่า subtree ของ parent ในกรณีนี้ tree ที่มี root d และสองลูก a และ e เป็น subtree ของ node G เช่นเดียวกับ tree หนึ่ง node ที่ root เป็น o นี่บ่งชี้ว่าต้นไม้เป็นโครงสร้างข้อมูลเชิง recursive และสามารถนิยามได้ดังนี้: ต้นไม้คือ node เดี่ยว หรือเป็น node ที่มีหนึ่งหรือสอง subtree (ซึ่งรากเป็นลูกของ node) โครงสร้าง recursive นี้ของต้นไม้ถูกกล่าวถึงใน chapter 4 ซึ่งนำเสนออัลกอริธึม recursive ในการ traverse family tree

แนวคิดของ binary search tree คือใช้ internal nodes เป็นขอบเขตที่แยก descendant ทั้งหมดออกเป็นสองประเภท: node ที่มีค่าน้อยกว่าขอบเขตจะอยู่ใน left subtree และ node ที่มีค่ามากกว่าจะอยู่ใน right subtree

การจัดเรียงนี้สามารถใช้ในการค้นหาได้ดังนี้ ถ้าเราต้องการหาค่าหนึ่งในต้นไม้ เราเปรียบเทียบมันกับ root ถ้าเท่ากันก็พบแล้ว สิ้นสุดการค้นหา มิฉะนั้น ถ้าค่าน้อยกว่า root เราจำกัดการค้นหาใน left subtree เท่านั้น เราไม่ต้องดู node ใดๆ ใน right subtree เพราะทุก node ถูกทราบว่าใหญ่กว่า root และจึงใหญ่กว่าค่าที่ค้นหา ในแต่ละกรณี internal node นิยามขอบเขตที่แยก "ด้านใน" (left subtree) จาก "ด้านนอก" (right subtree) เหมือนกับที่อยู่ในสมุดบันทึกของ Grail ที่กำหนด "ด้านใน" ของก้าวถัดไปของการค้นหาของ Indiana Jones

Figure 5.1 สามตัวอย่างของ binary trees. ซ้าย: ต้นไม้ที่มีเพียงโหนดเดียว. กลาง: ต้นไม้ที่รากมี right subtree หนึ่งโหนด. ขวา: ต้นไม้ที่รากมีสอง subtree. ทั้งสามต้นมีสมบัติ binary search ซึ่งบอกว่า node ใน left subtrees มีค่าน้อยกว่า root และ node ใน right subtrees มีค่ามากกว่า root.

ต้นไม้ทั้งสามใน figure 5.1 ทุกต้นเป็น binary search tree พวกมันเก็บตัวอักษรซึ่งสามารถเปรียบเทียบตามลำดับตัวอักษร เพื่อค้นหาค่าในต้นไม้นี้ ทำโดยเปรียบเทียบค่าที่ต้องการกับค่าที่ node ต่างๆ แล้วเลื่อนลงซ้ายหรือขวาตามผลการเปรียบเทียบ

สมมติว่าเราต้องการตรวจว่า e อยู่ในต้นไม้ด้านขวาหรือไม่ เราเริ่มที่ root และเปรียบเทียบ e กับ G เนื่องจาก e มาก่อน G ในอักษรและจึง "น้อยกว่า" G เราจึงค้นหาใน left subtree ซึ่งมีทุกค่าเล็กกว่า G ที่เก็บในต้นไม้นี้ เปรียบเทียบ e กับรากของ left subtree ซึ่งคือ d เราพบว่า e ใหญ่กว่า จึงค้นหาใน right subtree ซึ่งเป็นต้นไม้เพียง node เดียว การเปรียบเทียบ e กับ node นั้นทำให้การค้นหาสำเร็จ หากเราค้นหา f แทน ผลการค้นหาจะพาไปยัง node e แต่เนื่องจาก e ไม่มี right subtree การค้นหาจะสิ้นสุดที่นั่นและสรุปว่า f ไม่มีในต้นไม้

การค้นหาใดๆ จะเดินตามเส้นทางในต้นไม้ ดังนั้นเวลาที่ใช้ในการหาค่าหรือสรุปว่าไม่มี จะไม่เกินความยาวของเส้นทางที่ยาวที่สุดจาก root ไปยัง leaf ในต้นไม้ที่แสดงด้านขวาใน figure 5.1 ที่เก็บห้าค่า เส้นทางไปยัง leaf มีความยาว 2 หรือ 3 ซึ่งหมายความว่าเราสามารถหาค่าใดๆ ได้ในไม่เกินสามขั้นตอน เทียบกับ list ห้าตัวซึ่งการค้นหาสมาชิกสุดท้ายมักใช้ห้าขั้นตอน

เราพร้อมแล้วที่จะติดตามการคำนวณ histogram โดยใช้ binary search tree เพื่อแทนพจนานุกรม อีกครั้งเราจะเริ่มด้วยคำ God และเพิ่มตัวอักษรแต่ละตัวใน tree พร้อมตัวนับเริ่มต้นเป็น 1 เราจะได้ต้นไม้ต่อไปนี้ที่สะท้อนลำดับของตัวอักษรใน tree:

ในกรณีนี้การแทรก G ใช้หนึ่งขั้นตอน เช่นเดียวกับ list แต่การแทรก o และ d ใช้แค่สองขั้นตอนเพราะเป็นลูกของ G ดังนั้นเราประหยัดหนึ่งขั้นตอนสำหรับคำแรก (1 + 2 + 2 = 5 สำหรับ tree เทียบกับ 1 + 2 + 3 = 6 สำหรับ list)

การแทรกคำถัดมา Iehova ต้องใช้สามขั้นตอนสำหรับแต่ละตัวอักษร ยกเว้น o และ h ที่ต้องใช้สองและสี่ขั้นตอนตามลำดับ เช่นเดียวกับ list การประมวลผล o จะไม่สร้างองค์ประกอบใหม่แต่เพิ่มตัวนับขององค์ประกอบที่มีอยู่ การประมวลผลคำนี้จึงใช้ 18 ขั้นตอนและทำให้รวมเป็น 24 ขั้นตอน เทียบกับ 38 ขั้นตอนใน list คำ Jehova เปลี่ยนโครงสร้าง tree เล็กน้อยโดยเพิ่ม node สำหรับ J ซึ่งใช้สี่ขั้นตอน ด้วย 3 + 4 + 2 + 3 + 3 = 15 ขั้นตอนเพิ่มเติม ตัวนับของตัวอักษรที่มีอยู่ถูกอัปเดต ทำให้รวมเป็น 39 ขั้นตอน เทียบกับ 75 สำหรับ list:

สุดท้าย การเพิ่ม Yahwe(h) และ Yehova แต่ละคำต้องใช้ 19 ขั้นตอน เราจะได้ต้นไม้สุดท้ายที่ใช้รวม 76 ขั้นตอน นั่นคือครึ่งหนึ่งของ 153 ขั้นตอนที่ต้องใช้สำหรับ list

โครงสร้าง binary search tree นี้แทนพจนานุกรมเดียวกับ list แต่ในรูปแบบที่รองรับการค้นหาและการอัปเดตได้เร็วกว่า—อย่างน้อยก็โดยทั่วไป รูปร่างเชิงพื้นที่ของ list และ tree อธิบายความแตกต่างในประสิทธิภาพ โครงสร้างยาวและแคบของ list มักทำให้การค้นหาต้องไกลและต้องดูองค์ประกอบที่ไม่เกี่ยวข้อง ส่วนรูปกว้างและตื้นของ tree นำทางการค้นหาได้อย่างมีประสิทธิภาพและจำกัดองค์ประกอบที่ต้องพิจารณาและระยะทางที่ต้องเดิน อย่างไรก็ตามการเปรียบเทียบที่ยุติธรรมระหว่าง list และ binary search tree ต้องพิจารณาแง่มุมเพิ่มเติมบางประการ

Efficiency Hangs in the Balance (ประสิทธิภาพขึ้นอยู่กับสมดุล)

ในการวิทยาการคอมพิวเตอร์เราไม่ค่อยเปรียบเทียบโครงสร้างข้อมูลต่างๆ โดยนับจำนวนขั้นตอนที่แน่นอนสำหรับ list หรือ tree เฉพาะ เพราะอาจให้ภาพที่เข้าใจผิด โดยเฉพาะสำหรับโครงสร้างข้อมูลขนาดเล็ก ยิ่งไปกว่านั้นแม้ในการวิเคราะห์นี้เรายังเปรียบการดำเนินการที่ไม่ซับซ้อนเท่ากันและใช้เวลาเท่ากัน ตัวอย่างเช่น ใน list การเปรียบเทียบคือการทดสอบความเท่ากันของสององค์ประกอบ ในขณะที่ใน binary search tree เราต้องตัดสินด้วยว่าองค์ประกอบใดใหญ่กว่าเพื่อกำหนดทิศทางการค้นหา นั่นหมายความว่าหลายๆ การดำเนินการใน 153 ของ list อาจง่ายและเร็วกว่า operation บางอย่างใน 76 ของ tree ดังนั้นจึงไม่ควรตีความตัวเลขโดยตรงมากเกินไป

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

แล้วเมื่อเทียบกัน เวลาสำหรับการแทรกและค้นหาใน tree เป็นอย่างไร? ต้นไม้ตัวอย่างสุดท้ายมี 11 องค์ประกอบ และการค้นหาและแทรกใช้เวลาระหว่างสามถึงห้าขั้นตอน ความจริงคือเวลาในการหาหรือแทรกถูกจำกัดโดยความสูงของต้นไม้ ซึ่งมักจะเล็กกว่าจำนวนองค์ประกอบมาก ใน tree ที่ balanced ซึ่งทุกเส้นทางจาก root ไป leaf มีความยาวเท่ากัน (±1) ความสูงของต้นไม้จะเป็นลอการิทึมของขนาด นั่นคือความสูงเพิ่มขึ้นหนึ่งครั้งเมื่อจำนวนโหนดเพิ่มเป็นสองเท่า ตัวอย่างเช่น tree ที่ balanced ที่มี 15 โหนดมีความสูง 4, tree ที่มี 1,000 โหนดมีความสูง 10 และ 1,000,000 โหนดใส่ได้อย่างสบายใน tree ที่สูง 20 runtime แบบลอการิทึมดีกว่าแบบเชิงเส้นมาก และเมื่อขนาดพจนานุกรมใหญ่ขึ้น โครงสร้าง tree จะยิ่งดีกว่า list มากขึ้น

การวิเคราะห์นี้ขึ้นกับ binary search trees ที่ balanced เราจะรับประกันได้ไหมว่าต้นไม้ที่สร้างขึ้นจะ balanced และถ้าไม่เป็นเช่นนั้น runtime จะเป็นอย่างไรในกรณีต้นไม้ที่ไม่สมดุล? ต้นไม้สุดท้ายในตัวอย่างนี้ ไม่ balanced เพราะเส้นทางไปยัง leaf e ยาว 3 ในขณะที่เส้นทางไปยัง leaf w ยาว 5 ลำดับการแทรกตัวอักษรมีผลและอาจนำไปสู่ต้นไม้ต่างกัน เช่นถ้าเราแทรกตัวอักษรตามลำดับคำว่า doG เราจะได้ binary search tree ดังนี้ซึ่งไม่ balanced เลย

ต้นไม้นี้แย่มาก un_balanced—มันแทบไม่ต่างจาก list เลย และนี่ไม่ใช่ข้อยกเว้นแปลกๆ จากลำดับหกลำดับของตัวอักษร สองลำดับนำไปสู่ต้นไม้ที่ balanced (God และ Gdo) และอีกสี่ลำดับนำไปสู่ lists โชคดีที่มีเทคนิคเพื่อทำให้ต้นไม้ balance กลับมาหลังการแทรก แต่เทคนิคเหล่านี้เพิ่มค่าใช้จ่ายการแทรก แม้กระนั้นยังสามารถรักษาเวลาให้เป็นลอการิทึมได้

สุดท้าย binary search trees ใช้ได้เฉพาะกับองค์ประกอบที่สามารถเรียงลำดับได้เท่านั้น นั่นคือสำหรับคู่ขององค์ประกอบเราต้องบอกได้ว่าอันไหนใหญ่กว่าอันไหน การเปรียบเทียบนี้จำเป็นเพื่อจะตัดสินใจทิศทางที่จะไปในต้นไม้เพื่อหาหรือเก็บองค์ประกอบ อย่างไรก็ตามสำหรับบางชนิดของข้อมูล การเปรียบเทียบเช่นนี้ทำไม่ได้ สมมติว่าคุณเก็บบันทึกแบบลายผ้าควิลท์ สำหรับแต่ละแพทเทิร์นคุณอยากบันทึกผ้าและอุปกรณ์ที่ต้องการ ความยากระดับ การใช้เวลาในการทำ หากต้องเก็บข้อมูลแพทเทิร์นพวกนี้ใน binary search tree คุณจะตัดสินได้อย่างไรว่าแบบไหน "น้อย" หรือ "มาก" กว่ากัน เพราะแพทเทิร์นต่างกันทั้งจำนวนชิ้น รูปร่าง และสี จึงไม่ชัดเจนว่าจะกำหนดลำดับได้อย่างไร นี่ไม่ใช่เรื่องเป็นไปไม่ได้—คุณอาจแยกแพทเทิร์นเป็นส่วนประกอบและอธิบายด้วยรายการคุณลักษณะ (เช่นจำนวนชิ้นหรือสีและรูปร่าง) แล้วเปรียบเทียบแพทเทิร์นโดยการเปรียบเทียบรายการคุณลักษณะเหล่านั้น แต่สิ่งนี้ต้องใช้ความพยายามและอาจไม่ค่อยใช้งานจริง ดังนั้น binary search tree อาจไม่เหมาะสำหรับเก็บพจนานุกรมของแพทเทิร์นการเย็บผ้า อย่างไรก็ตามคุณยังใช้ list ได้ เพราะสำหรับ list สิ่งที่ต้องทำเพียงตัดสินใจว่าสองแพทเทิร์นเหมือนกันหรือไม่ ซึ่งง่ายกว่าการเรียงลำดับ

สรุป: Binary search trees ใช้กลยุทธ์ที่มนุษย์ใช้โดยธรรมชาติเพื่อแบ่งปัญหาการค้นหาให้เล็กลง ในความเป็นจริง binary search trees ทำให้แนวคิดนี้เป็นระบบและสมบูรณ์ยิ่งขึ้น ผลคือ binary search trees อาจมีประสิทธิภาพมากกว่า lists ในการแทนพจนานุกรม แต่ต้องใช้ความพยายามเพิ่มเติมเพื่อรับประกันการ balance และไม่เหมาะกับทุกชนิดของข้อมูล และนี่ควรตรงกับประสบการณ์ของคุณในการค้นหาเอกสารหรือเครื่องมือ หากคุณรักษาความเรียบร้อยเป็นประจำ โดยเก็บสิ่งของกลับที่เดิมหลังใช้งาน คุณจะหาของได้ง่ายกว่าการต้องค้นผ่านกองของไม่เป็นระเบียบ

Try a Trie (ลองใช้ Trie)

Binary search trees เป็นทางเลือกที่มีประสิทธิภาพกว่ารายการเมื่อต้องคำนวณ histogram ของความถี่ตัวอักษรในคำ แต่นี่เป็นเพียงการคำนวณหนึ่งที่ช่วย Indiana Jones แก้ปัญหาพื้นกระเบื้อง อีกการคำนวณคือการระบุลำดับกระเบื้องที่สะกดคำหนึ่งคำและนำไปสู่ฝั่งปลอดภัย

เราได้ระบุแล้วว่ากริดที่ประกอบด้วยหกแถวแต่ละแถวมีแปดตัวอักษร มี 262,144 เส้นทางต่างกันเพราะแต่ละเส้นทางสอดคล้องกับคำ เพราะทุกเส้นทางเป็นคำ เราจึงสามารถแทนการเชื่อมโยงของคำกับเส้นทางด้วยพจนานุกรม list จะเป็นตัวแทนที่ไม่ค่อยมีประสิทธิภาพเพราะคำเบาะแส Iehova อาจอยู่ใกล้ท้าย list และใช้เวลานานในการค้นหา tree ที่ balanced จะดีกว่าเพราะความสูงจะเป็น 18 ทำให้หาได้เร็ว แต่เราไม่มีต้นไม้ค้นหาที่ balanced ที่พร้อมใช้ และการสร้างมันต้องใช้เวลามาก เช่นเดียวกับ tree ที่เก็บตัวอักษร เราต้องแทรกองค์ประกอบทีละตัวและต้องไล่ต้นทางจาก root ไปยัง leaves โดยไม่วิเคราะห์รายละเอียด การสร้าง tree จะมากกว่าเวลาเชิงเส้น

อย่างไรก็ตาม เรายังสามารถระบุลำดับกระเบื้องได้อย่างมีประสิทธิภาพ (ไม่เกิน 42 ขั้นตอน) โดยไม่ต้องโครงสร้างข้อมูลเพิ่มเติม เพราะกริดกระเบื้องที่มีตัวอักษรบนกระเบื้องเป็น data structure ที่รองรับการค้นหาประเภทที่ Indiana Jones ต้องทำ โดย data structure นี้เรียกว่า trie, ซึ่งคล้ายกับ binary search tree แต่ต่างกันในจุดสำคัญ

จำได้ไหมว่า Indiana Jones ทุกครั้งที่ก้าวบนกระเบื้องจะลด search space ลงเป็นหนึ่งในแปด คล้ายกับการลงไปยัง balanced binary search tree ที่ลด search space ลงครึ่งหนึ่งโดยการเลือกหนึ่งในสองสาขา แต่ที่นี่ต่างออกไป ใน binary search tree แต่ละองค์ประกอบถูกเก็บใน node แยกต่างหาก ในขณะที่ trie เก็บตัวอักษรทีละตัวในแต่ละ node และแทนคำเป็นเส้นทางที่เชื่อมตัวอักษรต่างๆ เข้าด้วยกัน

เพื่อเข้าใจความแตกต่างระหว่าง binary search tree และ trie ให้พิจารณาตัวอย่างนี้ สมมติเราต้องการแทนชุดคำ bat, bag, beg, bet, mag, mat, meg, และ met ต้นไม้ค้นหาที่ balanced ซึ่งมีคำเหล่านี้เป็นรายการหน้าตาจะเป็นดังนี้:

เพื่อหาคำ bag ในต้นไม้นี้ เราเปรียบเทียบกับ root bet ซึ่งบอกให้ไปยัง left subtree การเปรียบเทียบนี้ต้องใช้สองขั้นตอนในการเปรียบเทียบตัวอักษรสองตัวแรกของคำ ต่อมาจึงเปรียบเทียบ bag กับ root ของ left subtree ซึ่งคือ bat การเปรียบเทียบนี้ต้องใช้สามขั้นตอนเพราะต้องเปรียบเทียบทั้งสามตัวอักษรของทั้งสองคำ สุดท้ายเราเปรียบเทียบ bat กับ node ซ้ายสุดของต้นไม้ซึ่งทำให้การค้นหาสำเร็จ การเปรียบเทียบครั้งสุดท้ายนี้ก็ต้องใช้สามขั้นตอน รวมทั้งหมดการค้นหาต้องใช้ 8 ครั้งในการเปรียบเทียบ

เราสามารถแทนชุดคำเดียวกันด้วยพื้นกระเบื้องขนาด 2×3 โดยแต่ละแถวมีตัวอักษรที่สามารถปรากฏในตำแหน่งนั้นของคำได้ เช่น แต่ละคำขึ้นต้นด้วย b หรือ m แถวแรกจึงต้องมีสองแผ่นสำหรับตัวอักษรเหล่านี้ แถวที่สองต้องมี a และ e และแถวที่สามต้องมี g และ t

เช่นเดียวกับ binary search trees และ lists แล้ว tries ก็มีทั้งข้อดีและข้อจำกัด ตัวอย่างเช่น โครงสร้างนี้ใช้ได้กับคีย์ที่สามารถแยกเป็นลำดับขององค์ประกอบได้เท่านั้น เหมือนกับ Indiana Jones ที่ท้ายที่สุดก็ไม่สามารถครอง Holy Grail ได้ จึงไม่มี Holy Grail ที่ใช้ได้กับโครงสร้างข้อมูลทุกรูปแบบ การเลือกโครงสร้างข้อมูลที่เหมาะสมขึ้นกับรายละเอียดของแอปพลิเคชันนั้นๆ

เช่นเดียวกับ binary search trees และ lists แล้ว tries ก็มีทั้งข้อดีและข้อจำกัด ตัวอย่างเช่น โครงสร้างนี้ใช้ได้กับคีย์ที่สามารถแยกเป็นลำดับขององค์ประกอบได้เท่านั้น เหมือนกับ Indiana Jones ที่ท้ายที่สุดก็ไม่สามารถครอง Holy Grail ได้ จึงไม่มี Holy Grail ที่ใช้ได้กับโครงสร้างข้อมูลทุกรูปแบบ การเลือกโครงสร้างข้อมูลที่เหมาะสมขึ้นกับรายละเอียดของแอปพลิเคชันนั้นๆ

(คำอธิบาย: ตารางข้างต้นแสดงตัวอักษรที่ปรากฏในแต่ละตำแหน่งของคำตัวอย่าง ซึ่งเป็นตัวอย่างการแทนคำด้วยกริดและชี้ให้เห็นว่า trie สามารถใช้ประหยัดพื้นที่ได้โดยการแชร์ส่วนที่เหมือนกัน)

(แปลเป็นภาษาไทยโดยผู้แปล)

การค้นหาคำบนพื้นกระเบื้องทำโดยไล่ตามแถว สำหรับแต่ละตัวอักษรของคำ แถวที่สอดคล้องกันจะถูกไล่จากซ้ายไปขวาจนกว่าจะเจอตัวอักษร ตัวอย่างเช่น เพื่อหาคำ bag บนพื้นนี้ เราเริ่มค้นหาตัวอักษรแรก b ในแถวแรก พบแผ่นในหนึ่งก้าว ต่อมาเราค้นหาตัวอักษรที่สอง a ในแถวที่สอง ซึ่งใช้หนึ่งก้าว และสุดท้ายหา g ในแถวที่สาม ก็ใช้หนึ่งก้าว รวมแล้วการค้นหานี้ใช้ 3 การเปรียบเทียบ

การค้นหาบนพื้นกระเบื้องต้องการขั้นตอนน้อยกว่าต้นไม้ค้นหาเพราะเราต้องเปรียบเทียบแต่ละตัวอักษรเพียงครั้งเดียว ในขณะที่การค้นหาใน tree ทำให้เกิดการเปรียบเทียบซ้ำของส่วนเริ่มต้นของคำ คำ bag เป็นกรณีที่ดีที่สุดสำหรับพื้นกระเบื้องเพราะแต่ละตัวอักษรถูกเจอในแผ่นแรก ในขณะที่คำ met ต้องการหกขั้นตอนเพราะแต่ละตัวอักษรอยู่บนแผ่นสุดท้าย แต่ไม่แย่กว่านี้เพราะต้องตรวจแผ่นแต่ละแผ่นอย่างมากสุดหนึ่งครั้ง (สำหรับการเปรียบเทียบ ค้นหา met ใน binary search tree ต้องใช้ 2 + 3 + 3 + 3 = 11 ขั้นตอน) กรณีที่ดีที่สุดสำหรับ binary search tree คือการหาคำ bet ซึ่งต้องใช้เพียงสามขั้นตอน แต่ยิ่งไกลจาก root มากเท่าไร การค้นหาด้วย binary จะก่อให้เกิดการเปรียบเทียบของส่วนเริ่มต้นของคำซ้ำมากขึ้น ดังนั้นในหลายกรณีการค้นหาใน trie จะเร็วกว่าการค้นหาใน binary search tree

การเปรียบเทียบกับพื้นกระเบื้องชี้ให้เห็นว่า trie อาจถูกแทนเป็นตาราง แต่ไม่เสมอไป ตัวอย่างนี้ทำงานดีเพราะทุกคำมีความยาวเท่ากันและทุกตำแหน่งในคำสามารถมีตัวอักษรเดียวกันได้ อย่างไรก็ตามสมมติว่าเราต้องการเพิ่มคำ bit และ big ในกรณีนี้แถวที่สองต้องมีตัวอักษร i เพิ่ม ซึ่งทำลายรูปสี่เหลี่ยม การเพิ่มสองคำนี้เผยความสม่ำเสมออีกอย่างที่ไม่มีในทั่วไป คำตัวอย่างถูกเลือกให้ prefixes ต่างกันของความยาวเดียวกันมี suffix ที่เป็นไปได้เหมือนกัน ซึ่งทำให้เกิดการแชร์ข้อมูล เช่น ba และ be สามารถต่อด้วย g หรือ t ได้เหมือนกัน แต่เมื่อเพิ่ม bit และ big จะเห็นว่าตอนนี้ b สามารถต่อด้วย 3 ตัวเลือก a, e, และ i ขณะที่ m ต่อได้แค่ a และ e ซึ่งหมายถึงต้องมีการต่อที่ต่างกัน

ดังนั้น trie มักแทนเป็นชนิดพิเศษของ binary tree ที่ node แต่ละตัวเก็บตัวอักษรเดียว left subtrees แทนการต่อคำ และ right subtrees แทนตัวเลือกของตัวอักษร (พร้อมการต่อของพวกมัน) ตัวอย่าง trie สำหรับคำ bat, bag, beg, และ bet เป็นดังนี้:

เนื่องจากรากไม่มีขอบขวา คำทั้งหมดจึงเริ่มด้วย b ขอบซ้ายจาก b ไปยัง subtree ที่มีราก a นำไปสู่การต่อที่เป็นไปได้ซึ่งเริ่มด้วย a หรือ e และ e เป็นทางเลือกของ a ที่ชี้โดยขอบขวาจาก a ความจริงที่ว่า ba และ be สามารถต่อด้วย g หรือ t แสดงโดยขอบซ้ายจาก a ไปสู่ subtree ราก g ซึ่งมีลูกขวาเป็น t ความจริงที่ว่า left subtrees ของ a และ e เหมือนกันหมายความว่าสามารถแชร์กันได้ ซึ่งถูกใช้ในตัวแทนพื้นกระเบื้องโดยมีแถวเดียวกันสำหรับกระเบื้อง ด้วยการแชร์นี้ trie มักต้องการพื้นที่จัดเก็บน้อยกว่า binary search tree

ในขณะที่ใน binary search tree แต่ละคีย์ถูกเก็บไว้ใน node แยก คีย์ที่เก็บใน trie ถูกแจกจ่ายไปตาม node ใดๆ ตามลำดับ โดมใดๆ ของ node จากรากของ trie เป็น prefix ของคีย์บางตัวใน trie และในกรณีของพื้นกระเบื้อง แผ่นที่เลือกเป็น prefix ของเส้นทางสุดท้าย นี่คือเหตุผลที่ trie เรียกอีกอย่างว่า prefix tree โครงสร้าง trie ที่แทนพื้นกระเบื้องที่ Indiana Jones เผชิญถูกแสดงใน figure 5.2

Figure 5.2 โครงสร้างข้อมูล trie และวิธีการค้นหา. ซ้าย: ตัวแทน trie ที่ left subtrees แสดงการต่อคำที่เป็นไปได้ของตัวอักษรใน node แม่ (แสดงด้วยสี่เหลี่ยมมุมโค้ง) และ right subtrees แสดงตัวเลือกอื่นๆ ด้านกลางบน: ตัวแทนพื้นกระเบื้องของ trie ทางซ้ายโดยที่ subtree ที่ใช้ร่วมกันถูกแชร์ผ่านแถวเดียว ด้านกลางล่าง: แผ่นที่เลือกสามแผ่นที่สะกดจุดเริ่มต้นของคำ Iehova ขวา: เส้นทางผ่าน trie ที่ทำเครื่องหมายด้วยขอบหนาสำหรับแผ่นที่เลือก โหนดที่วงกลมไว้สอดคล้องกับแผ่นที่เลือก.

เมื่อเราดูฉากในหนัง เรามักมองความท้าทายที่แท้จริงเป็นการหาคำเบาะแสหรือการกระโดดไปยังแผ่นเป้าหมายอย่างแม่นยำ มากกว่าการระบุแผ่นตามตัวอักษรของคำเบาะแส เรื่องนี้ดูชัดเจนน้อยจนเราแทบไม่คิดเลย ซึ่งแสดงให้เห็นอีกครั้งว่าการดำเนินการอัลกอริธึมที่มีประสิทธิภาพเป็นธรรมชาติกับเราอย่างไร เช่นเดียวกับ Hansel and Gretel และ Sherlock Holmes การผจญภัยของ Indiana Jones และการรอดชีวิตของเขาขึ้นอยู่กับหลักการคอมพิวติ้งพื้นฐาน

และสุดท้าย ถ้าคุณยังสงสัยเกี่ยวกับวิธีที่จะไม่ทำกุญแจรถหายอีก วิธีง่ายมาก: เมื่อกลับบ้าน ให้วางกุญแจที่ตำแหน่งหนึ่งตำแหน่งเสมอ ตำแหน่งนี้แหละคือกุญแจของกุญแจ แต่คุณคงรู้อยู่แล้ว