ต้นไม้สุ่มค้นหาด้วยนิ้วในโครงสร้างข้อมูล

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

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

ข้ามรายการ

ในรายการข้าม เราสามารถใช้นิ้วค้นหาองค์ประกอบ a จากโหนดที่มีองค์ประกอบ b โดยเพียงแค่ทำการค้นหาต่อจากจุดนี้ โปรดทราบว่าหาก a b การค้นหาจะดำเนินการในทิศทางไปข้างหน้า ตัวพิมพ์ย้อนกลับมีความสมมาตรกับการค้นหาปกติในรายการข้าม แต่กรณีไปข้างหน้านั้นซับซ้อนกว่าจริง โดยปกติ การค้นหาในรายการข้ามคาดว่าจะรวดเร็ว เนื่องจากผู้รักษาการณ์ที่จุดเริ่มต้นของรายการถือเป็นโหนดที่สูงที่สุด อย่างไรก็ตาม นิ้วของเราอาจสัมพันธ์กับโหนดที่มีความสูง 1 ด้วยเหตุนี้ เราจึงแทบจะไม่ปีนขึ้นไปขณะพยายามค้นหา สิ่งที่ไม่เคยเกิดขึ้นตามปกติ อย่างไรก็ตาม แม้จะมีความยุ่งยากนี้ เราก็สามารถบรรลุ O(log d) เวลาค้นหาที่คาดไว้ได้