โครงสร้างข้อมูลการค้นหาด้วยนิ้วแบบไดนามิกควรดำเนินการแทรกและลบองค์ประกอบที่ตำแหน่งที่กำหนดโดยนิ้วนอกเหนือจากการค้นหาด้วยนิ้วด้วย Finger search tree ถูกกำหนดให้เป็นตัวแปรของ B-trees ที่รองรับการค้นหาด้วยนิ้วในเวลา O(log d) และอัปเดตในเวลา O(1) โดยถือว่ามีเพียง O(1) ที่เคลื่อนย้ายได้เท่านั้น การเคลื่อ

ในส่วนนี้ เราจะอธิบายวิธีที่ (2,4) -trees สามารถสนับสนุนการค้นหานิ้วอย่างมีประสิทธิภาพโดยการแนะนำการเชื่อมโยงระดับ แนวคิดที่อธิบายในส่วนนี้ยังนำไปใช้กับประเภททั่วไปของต้นไม้ที่มีความสูงสมดุลซึ่งแสดง (a, b) - ต้นไม้สำหรับ b ≥ 2a ต้นไม้ (2,4)-ถูกกำหนดให้เป็นต้นไม้ค้นหาที่มีความสูงสมดุล โดยที่ใบทั้งหม

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

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

การจัดเรียงการผสานแบบปรับได้ Adaptive Merge Sort ทำการผสานการเรียงลำดับการผสานรายการย่อยที่เรียงลำดับแล้ว อย่างไรก็ตาม ขนาดของรายการย่อยเริ่มต้นขึ้นอยู่กับการมีอยู่ของการจัดลำดับในรายการองค์ประกอบ แทนที่จะมีรายการย่อยขนาด 1 ตัวอย่างเช่น พิจารณารายการในรูป ประกอบด้วยรายการย่อยที่จัดเรียง 2 ราย

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

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

ทฤษฎีบทนิ้วคงที่ − ให้ f เป็นองค์ประกอบเฉพาะที่เรียกว่านิ้ว จากนั้นนิพจน์ด้านล่างผูกกับค่าใช้จ่ายในการแสดงลำดับ O(m + n log(n) + Σ Sum log (|f - i[j]| + 1))j หมายเหตุ − |f-i| จะแสดงเป็นระยะห่างในการเรียงลำดับสมมาตรของสิ่งของระหว่างนิ้วกับรายการ i โดยที่ m ถูกระบุเป็นจำนวนของการดำเนินการอัปเด

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

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

รหัสฮัฟฟ์แมน รหัส Huffman ถูกกำหนดให้เป็นประเภทเฉพาะของรหัสนำหน้าที่เหมาะสมที่สุดซึ่งมักใช้สำหรับการบีบอัดข้อมูลแบบไม่สูญเสียข้อมูล กระบวนการในการค้นหาหรือใช้รหัสดังกล่าวดำเนินการโดยใช้การเข้ารหัส Huffman ซึ่งเป็นอัลกอริทึมที่พัฒนาโดย David A. Huffman ขณะที่เขาเป็น Sc.D. เป็นนักศึกษาที่ MIT และตีพ

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

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

ปัญหาในการค้นหาโค้ดที่ไม่มีส่วนนำหน้าที่เหมาะสมที่สุดสำหรับต้นทุนตัวอักษรที่ไม่เท่ากันประกอบด้วยการคำนวณโค้ดที่ไม่มีส่วนนำหน้าต้นทุนขั้นต่ำ ซึ่งตัวอักษรสำหรับเข้ารหัสประกอบด้วยตัวอักษรต้นทุน (ความยาว) ที่ไม่เท่ากัน มีความยาว α และ β โดยที่ α ≤ β เราจำกัดตัวเองไว้ที่ไบนารีทรี รหัสนี้แสดงด้วยต้นไม้ไม

Bucketing builds ตารางแฮชเป็นอาร์เรย์ 2D แทนที่จะเป็นอาร์เรย์มิติเดียว ทุกรายการในอาร์เรย์มีขนาดใหญ่พอที่จะเก็บรายการ M ได้ (M ไม่ใช่ปริมาณข้อมูล แต่เป็นค่าคงที่) ปัญหา สร้างพื้นที่ที่สูญเปล่าจำนวนมาก หากเกิน M จะต้องดำเนินการตามกลยุทธ์อื่น ประสิทธิภาพไม่ดีนักสำหรับการใช้งานตามหน่วยความจำ แต่ทำได้

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

ในกรณีของเรขาคณิตเชิงคำนวณ กราฟเส้นตรงระนาบระนาบ หรือ PSLG แบบสั้น (หรือกราฟระนาบเส้นตรง หรือกราฟเส้นตรงระนาบ) ถูกกำหนดให้เป็นคำที่ใช้สำหรับการฝังกราฟระนาบในระนาบในลักษณะที่ ขอบของมันถูกแมปเป็นส่วนเส้นตรง คำชี้แจงของทฤษฎีบทของฟารี (1948) คือกราฟระนาบทุกกราฟมีการฝังแบบนี้ ในกรณีของเรขาคณิตเชิงคำนวณ

แนะนำตัว HDS สำหรับพารามิเตอร์เทมเพลตหรือโครงสร้างข้อมูล halfedge (ย่อมาจาก HalfedgeDS) ถูกกำหนดให้เป็นโครงสร้างข้อมูลแบบ edge-centered ที่สามารถรักษาข้อมูลอุบัติการณ์ของจุดยอด ขอบและใบหน้าได้ เช่น แผนที่ระนาบ รูปทรงหลายเหลี่ยม หรือทิศทางแบบสองมิติอื่นๆ พื้นผิวที่ฝังอยู่ในมิติสุ่ม ขอบแต่ละด้านแบ่งอ

ต้นไม้ช่วงถูกกำหนดให้เป็นโครงสร้างข้อมูลต้นไม้ที่ได้รับคำสั่งเพื่อเก็บรายการจุด อนุญาตให้ดึงข้อมูลทุกจุดภายในช่วงที่กำหนดได้อย่างมีประสิทธิภาพ และโดยทั่วไปจะใช้ในมิติสองมิติขึ้นไป มันเหมือนกับ kd-tree ยกเว้นว่ามีเวลาสืบค้นเร็วขึ้นของ O(logd n + k) แต่การจัดเก็บ O(n logd-1 n) โดย d ระบุขนาดของช่องว่า

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