คืออะไร?
Left-Child Right-Sibling Representation เป็นการแทนค่าต้นไม้ n-ary แบบใหม่ แทนที่จะเก็บ pointer ไปยังทุกลูก โหนดจะเก็บเพียง สอง pointers:
- Pointer ไปยัง ลูกคนแรก (First Child)
- Pointer ไปยัง พี่น้องถัดไปทันที (Immediate Next Sibling)
การแปลงนี้ไม่เพียงแต่กำจัดความจำเป็นต้องรู้จำนวนลูกล่วงหน้า แต่ยังจำกัดจำนวน pointers สูงสุดไว้ที่สอง ทำให้เขียนโค้ดง่ายขึ้นมาก
กฎการเชื่อมต่อ
- เชื่อมลูกของพาเรนต์เดียวกันจากซ้ายไปขวา
- พาเรนต์เชื่อมกับลูกคนแรกอย่างเดียว
ตัวอย่าง
10 | 2 -> 3 -> 4 -> 5 | | 6 7 -> 8 -> 9
ข้อดี
- ประหยัดหน่วยความจำ – จำกัด pointers สูงสุด 2 ต่อโหนด
- เขียนโค้ดง่ายกว่า
ข้อเสีย
- การดำเนินการพื้นฐาน (ค้นหา/แทรก/ลบ) ใช้เวลานานกว่า – ต้องเดินทางผ่านพี่น้องทั้งหมดเพื่อหาตำแหน่งที่ถูกต้อง (ใน worst case)
