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