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