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

ตัวอย่างของ 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 แสดงถึงรากเท่านั้น สันนิษฐานว่าขอบสามารถติดฉลากด้วยสตริงที่ว่างเปล่าเพื่อยุติสตริงที่จำเป็นและรากไม่มีขอบขาเข้า (อัลกอริทึมการค้นหาที่อธิบายข้างต้นจะไม่ทำงานเมื่อใช้สายอักขระว่างเปล่า)

Insert 'test' which is a prefix of 'tester'
Insert 'team' while splitting 'test' and creating a new edge label 'st'
Insert 'toast' while splitting 'te' and moving previous strings a level lower

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

การ Deletion แก้

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