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