ความรู้ที่ได้รับจากเรื่อง Tree
Treeเป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่างโหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น(Hierarchical Relationship) ส่วนมากจะใช้แสดงความสัมพันธ์ระหว่างข้อมูล
ชื่อเรียกโหนดต่างๆ
1. โหนดแม่ (Parent or Mother Node) = โหนดที่มีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้หลายๆโหนด
2. โหนดลูก (Child or Son Node) = โหนดที่อยู่ต่ำกว่าโหนดแม่หนึ่งระดับ
3. โหนดราก (Root Node) = โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่
4. โหนดพี่น้อง (Siblings) = โหนดที่มีโหนดแม่เดียวกัน
5. โหนดใบ (Leave Node) = โหนดที่ไม่มีโหนดลูก
6. กิ่ง (Branch) = เส้นเชื่อม
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) โหนดสองโหนดใดๆ ในทรีจะติดต่อกันได้ทางเดียวเท่านั้นและทรีที่มี N โหนด จะต้องมีกิ่งทั้งหมด N-1 เส้น
การเขียนรูปแบบทรี เขียนได้ 4 แบบ คือ
- แบบที่มีรากอยู่ด้านบน
- แบบที่มีรากอยู่ด้านล่าง
- แบบที่มีรากอยู่ด้านซ้าย
- แบบที่มีรากอยู่ด้านขวา
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด ถ้าไม่มีโหนดใดๆ เรียกว่า นัลทรี (Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest) = กลุ่มของทรีที่เกิดจากการเอาโหนดรากออก
2. ทรีที่มีแบบแผน (Ordered Tree) = ทรีที่โหนดต่างๆ มีความสัมพันธ์แน่นอน เช่น ไปทางขวา
ไปทางซ้าย
3. ทรีคล้าย (Similar Tree) = ทรีที่มีโครงสร้างเหมือนกัน โดยไม่คำนึงถึงข้อมูลในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) = ทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree) = จำนวนทรีย่อยของโหนดนั้นๆ
6. ระดับของโหนด (Level of Node) = ระยะทางในแนวดิ่งของโหนด ที่อยู่ห่างจากโหนดราก เรียกว่า ความสูง (Height) หรือความลึก (Depth)
การแทนที่ทรีในหน่วยความจำหลัก
1. โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด
ทรีที่แต่ละโหนดมีจำนวนโหนดลูกที่แตกต่างกันมาก จะเป็นการสิ้นเปลืองเนื้อที่ในหน่วยความจำโดยเปล่าประโยชน์
2. แทนทรีด้วยไบนารีทรี
วิธีนี้ช่วยแก้ปัญหา การสิ้นเปลืองเนื้อที่ในหน่วยความจำ โดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์ 2 ลิงค์ฟิลด์
- ลิงค์ฟิลด์แรก เก็บที่อยู่ของโหนดลูกคนโต
- ลิงค์ฟิลด์ที่สอง เก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไปโหนดใดไม่มีโหนดลูกหรือไม่มีโหนดพี่น้องให้ค่าพอยน์เตอร์ในลิงค์ฟิลด์มีค่าเป็น Null
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกอื่นๆ
2. เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในไบนารีทรี มี 6 วิธี คือ
- NLR
- LNR
- LRN
- NRL
- RNL
- RLN
เอ็กซ์เพรสชันทรี (Expression Tree)
คือ การนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี โดยคำนวณตามความสำคัญของเครื่องหมาย ดังนี้
- ฟังก์ชัน
- วงเล็บ
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน (unary)
- คูณ หรือ หาร
- บวก หรือ ลบ
- ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
Treeเป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่างโหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น(Hierarchical Relationship) ส่วนมากจะใช้แสดงความสัมพันธ์ระหว่างข้อมูล
ชื่อเรียกโหนดต่างๆ
1. โหนดแม่ (Parent or Mother Node) = โหนดที่มีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้หลายๆโหนด
2. โหนดลูก (Child or Son Node) = โหนดที่อยู่ต่ำกว่าโหนดแม่หนึ่งระดับ
3. โหนดราก (Root Node) = โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่
4. โหนดพี่น้อง (Siblings) = โหนดที่มีโหนดแม่เดียวกัน
5. โหนดใบ (Leave Node) = โหนดที่ไม่มีโหนดลูก
6. กิ่ง (Branch) = เส้นเชื่อม
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) โหนดสองโหนดใดๆ ในทรีจะติดต่อกันได้ทางเดียวเท่านั้นและทรีที่มี N โหนด จะต้องมีกิ่งทั้งหมด N-1 เส้น
การเขียนรูปแบบทรี เขียนได้ 4 แบบ คือ
- แบบที่มีรากอยู่ด้านบน
- แบบที่มีรากอยู่ด้านล่าง
- แบบที่มีรากอยู่ด้านซ้าย
- แบบที่มีรากอยู่ด้านขวา
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด ถ้าไม่มีโหนดใดๆ เรียกว่า นัลทรี (Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest) = กลุ่มของทรีที่เกิดจากการเอาโหนดรากออก
2. ทรีที่มีแบบแผน (Ordered Tree) = ทรีที่โหนดต่างๆ มีความสัมพันธ์แน่นอน เช่น ไปทางขวา
ไปทางซ้าย
3. ทรีคล้าย (Similar Tree) = ทรีที่มีโครงสร้างเหมือนกัน โดยไม่คำนึงถึงข้อมูลในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) = ทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree) = จำนวนทรีย่อยของโหนดนั้นๆ
6. ระดับของโหนด (Level of Node) = ระยะทางในแนวดิ่งของโหนด ที่อยู่ห่างจากโหนดราก เรียกว่า ความสูง (Height) หรือความลึก (Depth)
การแทนที่ทรีในหน่วยความจำหลัก
1. โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด
ทรีที่แต่ละโหนดมีจำนวนโหนดลูกที่แตกต่างกันมาก จะเป็นการสิ้นเปลืองเนื้อที่ในหน่วยความจำโดยเปล่าประโยชน์
2. แทนทรีด้วยไบนารีทรี
วิธีนี้ช่วยแก้ปัญหา การสิ้นเปลืองเนื้อที่ในหน่วยความจำ โดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์ 2 ลิงค์ฟิลด์
- ลิงค์ฟิลด์แรก เก็บที่อยู่ของโหนดลูกคนโต
- ลิงค์ฟิลด์ที่สอง เก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไปโหนดใดไม่มีโหนดลูกหรือไม่มีโหนดพี่น้องให้ค่าพอยน์เตอร์ในลิงค์ฟิลด์มีค่าเป็น Null
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกอื่นๆ
2. เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในไบนารีทรี มี 6 วิธี คือ
- NLR
- LNR
- LRN
- NRL
- RNL
- RLN
เอ็กซ์เพรสชันทรี (Expression Tree)
คือ การนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี โดยคำนวณตามความสำคัญของเครื่องหมาย ดังนี้
- ฟังก์ชัน
- วงเล็บ
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน (unary)
- คูณ หรือ หาร
- บวก หรือ ลบ
- ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
ไม่มีความคิดเห็น:
แสดงความคิดเห็น