ต้นไม้เรดิกซ์

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา
An example of a radix tree

ตัวอย่างของ Radix Tree ในวิทยาการคอมพิวเตอร์ Radix Tree(เช่น radix trie หรือ compact prefix tree) เป็นโครงสร้างข้อมูลที่แสดงถึงพื้นที่ ที่มีการปรับแต่งพื้นที่อย่างเหมาะสมซึ่งแต่ะโหนด ที่เป็น child ที่อยู่คนเดียวจะถูกผสานเข้ากับ parent ผลที่ตามมาคือจำนวนของ Children ภายในที่อยู่ในราก radix r ของ radix Tree โดยที่ r เป็นจำนวนเต็มและยกกำลัง x ของ 2  มี X ≥ 1 ซึ่งแตกต่างจากปกติ  และมีลำดับของประกอบรวมทั้งองค์ประกอบเดียว สิ่งนี้ทำให้ radix tree มีประสิทธิ์ภาพมากขึ้นสำหรับชุดคำเล็กๆ (โดยเฉพาะชุดคำยาว) และชุดคำที่ใช้คำนำหน้ายาวๆ

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

Radix trie จะเป็นเลขฐานสอง (กล่าวคือเปรียบเทียบส่วนที่เป็นบิต 1บิต ของโหนด) ซึ่งจะช่วยลดค่าที่เพิ่มขึ้นข้องความลึก เช่นการเพิ่มค่าสูงสุดให้กับสตริง บิตที่ไม่มีการบิดเบือน  เมื่อ r เป็นจำนวนเต็ม 2 หรือมากกว่า 4 แล้วค่า radix trie คือ r-ary trie  ซึ่งลดความลึกของ radix trie ที่ค่าใช้จ่ายของ sparseness ที่อาจจะเกิดขึ้น

การประยุกต์ใช้งาน[แก้]

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

การดำเนินการ[แก้]

RadixTree  นั้นสนับสนุนการ Insertion การ Deletion และการ Searching  หลังการทำงานของทั้งหมดนี้คือ O(k) โดยที่ k คือความยาวสูงสุดของ สตริงทั้งหมด ในเซต ซึ้งความยาววัดได้ในปริมาณเท่ากับค่า radix ของ radix trie

Finding a string in a Patricia trie

การ Insertion[แก้]

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

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

ในรูปจะแสดง ถึงคำว่า testเป็นคำนำหน้าของคำว่า tester ในรูปต่อมาอธิบายถึงการ Insert คำว่า team เพิ่มเข้าไปใน tree ตอนแรกที่มีคำว่า testอยุ่ก่อนจะเห็นได้ว่าจะแยกเป็นสองโหนด โดยมีคำนำหน้าที่ใช้ร่วมกันคือ te

การ Deletion[แก้]

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