Please enable JavaScript.
Coggle requires JavaScript to display documents.
บทที่ 6 ต้นไม้(Trees) :evergreen_tree: (บทนำ (ความสัมพันธ์ของจุดต่างๆ…
บทที่ 6 ต้นไม้(Trees) :evergreen_tree:
บทนำ
ต้นไม้ คือ กราฟที่มีลักษณะเฉพาะคือมีโครงสร้างแบบลำดับชั้น
นิยามที่ 6.1
ต้นไม้คือ กราฟแบบไม่มีทิศทางที่เชื่อมต่อกัน (connected undirected graph) ซึ่งไม่มีวงจรแบบง่าย
:red_cross: ต้นไม้ทุกต้นจะไม่มี
วงจรแบบง่าย
เส้นเชื่อมหลายเส้นระหว่างคู่ของจุด
ลูป
นิยามที่ 6.2
ต้นไม้มีราก (Rooted tree) คือ ต้นไม้ที่มีการกำหนดจุดๆ หนึ่งเป็นรากและทุกๆเส้นเชื่อมพุ่งไปในทิศทางที่ออกจากราก
เลขระดับ (Level number) คือ ความยาวของทางเดินจากรากไปยังจุดนั้นๆ
ความสูง (Height) ของต้นไม้จะมีค่าเท่ากับเลขระดับที่มีค่ามากที่สุดของจุดในต้นไม้นั้น
ความสัมพันธ์ของจุดต่างๆ ในต้นไม้มีราก
จุดพ่อ/แม่ (Parent) ของ v คือ จุด u ซึ่ง unique และมีเส้นเชื่อมโดยตรงจาก u มายัง v
ถ้าจุด u เป็นจุดระดับพ่อ/แม่ของ v จะเรียกจุด v ว่าจุดลูก (Child) ของ u
พี่น้อง (Sibling) คือ จุดสองใดๆที่มีพ่อแม่เดียวกัน
บรรพบุรุษ (Ancestors) ของจุดหนึ่งที่ไม่ใช่ราก คือ จุดอื่นๆ ที่อยู่ในทางเดินจากรากมายังจุดนั้นๆ (ยกเว้นจุดนั้นเองและราก)
ลูกหลาน (Descendants) ของจุด v คือ จุดอื่นๆ ที่มี v เป็นบรรพบุรุษ
ใบ (Leaf) คือ จุดใดๆ ในต้นไม้ที่ไม่มีลูก
ต้นไม้ย่อย (Subtree) ที่มีจุด v เป็นราก คือ กราฟย่อยของต้นไม้ที่ประกอบด้วยจุด v และลูกหลานทั้งหมดของจุด v
นิยามที่ 6.3
ต้นไม้มีรากจะเรียกว่าเป็น ต้นไม้แบบ m ภาค (m-ary tree) ถ้าทุกๆ จุดภายในมีลูกไม่เกิน m
ต้นไม้มีรากจะเรียกว่าเป็น ต้นไม้แบบเต็ม m ภาค (full m-ary tree) ถ้าทุกๆ จุดภายในมีลูกเท่ากับ m เท่านั้น
ในกรณีที่ m = 2 จะเรียกว่า “ต้นไม้แบบทวิภาค (binary tree)
กรณีที่ลูกของแต่ละจุดภายใน เรียงลำดับจากซ้ายไปขวาดังรูป A จะเรียกต้นไม้ดังกล่าวว่า “ต้นไม้มีรากแบบลำดับ (Ordered Rooted Tree)”
คุณสมบัติของต้นไม้
ทฤษฎีที่ 1 ต้นไม้ที่มีจำนวนจุด n จุดจะมีจำนวนเส้นเชื่อมเท่ากับ n-1 เส้น
ทฤษฎีที่ 2 ต้นไม้แบบเต็ม m ภาคซึ่งมีจุดภายในจำนวน i จุดจะมีจำนวนจุดทั้งหมด n = mi + 1 จุด
ทฤษฎีที่ 3 ต้นไม้แบบเต็ม m ภาคซึ่งมีจำนวนจุดทั้งหมดเท่ากับ n จำนวนจุดภายในเท่ากับ i และมีจำนวนจุดที่เป็นใบเท่ากับ l จะได้ความสัมพันธ์ดังนี้
ต้นไม้ที่มีจำนวนจุดทั้งหมดเท่ากับ n จะมี i = (n-1)/m และ l = [(m-1)n + 1]/m
ต้นไม้ที่มีจำนวนจุดภายในเท่ากับ i จะมี n = mi + 1 และ l = (m-1)i + 1
ต้นไม้ที่มีจำนวนใบเท่ากับ l จะมี n = (ml – 1)/(m – 1) และ i = (l -1)/(m -1)
ทฤษฎีที่ 4 ต้นไม้แบบ m ภาคซึ่งมีความสูง h จะเป็นต้นไม้แบบสมดุล (balanced tree) ถ้าทุกใบอยู่ที่ระดับ h หรือ h–1
ทฤษฎีที่ 5 ต้นไม้แบบ m ภาคซึ่งมีความสูง h จะมีจำนวนใบได้มากที่สุด mh ใบ
การแวะผ่านจุดในต้นไม้ (Tree Traversal)
ต้นไม้มีรากแบบลำดับสามารถใช้เพื่อแสดง
ข้อมูลที่เก็บในคอมพิวเตอร์
การแสดงค่าชนิดต่างๆ เช่น สูตรทางคณิตศาสตร
นิยามที่ 6.5
การแวะผ่านโดยให้ความสำคัญต้นไม้ย่อยของลูกซ้ายก่อน และกลับมาแวะที่ราก แล้วจึงแวะผ่านต้นไม้ย่อยทางขวา และกลับมาแวะที่ราก เช่นนี้ไปเรื่อยๆสลับกันไป จนถึงต้นไม้ย่อยของลูกสุดท้าย
นิยามที่ 6.4
การแวะผ่านโดยให้ความสำคัญรากก่อนแล้วจึงแวะผ่านต้นไม้ย่อยของลูกจากซ้ายไปขวา
นิยามที่ 6.6
การแวะผ่านต้นไม้ย่อยของลูกเรียงจากซ้ายไปขวา แล้วจึงแวะผ่านรากทีหลัง
infix notation
(a+b) × c
สามารถแสดงโดยใช้ต้นไม้มีรากหนึ่งต้น เรียกว่า “ต้นไม้นิพจน์ (Expression Tree)”
postfix notation
abc +
prefix notation
abc
Infix ---> Prefix
Use preorder traversal
Infix ---> Postfix
Use postorder traversal
ต้นไม้แบบแผ่ (Spanning Trees)
นิยามที่ 6.7
ให้ G เป็นกราฟแบบง่าย ต้นไม้แบบแผ่ของ G คือ กราฟย่อยของ G ที่เป็นต้นไม้ ซึ่งประกอบด้วยทุกๆ จุดของ G
จากนิยาม สามารถสรุปได้ว่า
กราฟแบบง่ายซึ่งเป็นกราฟแบบ connected ทุกๆ กราฟจะมีต้นไม้แบบแผ่
อัลกอริทึมสำหรับการสร้างต้นไม้แบบแผ่
การค้นตามความลึก (Depth-First Search) หรือการย้อนรอย (Backtracking)
การค้นตามความกว้าง (Breadth-First Search)
ต้นไม้แบบแผ่ที่เล็กที่สุด (Minimum Spanning Trees)
นิยามที่ 6.8
ต้นไม้แบบแผ่ที่เล็กที่สุดในกราฟแบบมีน้ำหนักที่เชื่อมต่อกัน คือ ต้นไม้แบบแผ่ที่มีผลรวมของน้ำหนักของเส้นเชื่อมที่น้อยที่สุด
สำหรับกราฟแบบมีน้ำหนัก การหาต้นไม้แบบแผ่จะพิจารณาจากผลบวกของน้ำหนักของเส้นเชื่อมที่มีค่าน้อยที่สุด
อัลกอริทึมสำหรับต้นไม้แบบแผ่ที่เล็กที่สุด
Prim's Algorithm
Kruskal's Algorithm
เปรียบเทียบระหว่าง Prim's algorithm และ Kruskal's algorithm
กรณีของ Prim's algorithm จะเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดซึ่งเชื่อมต่อกับจุดที่อยู่ในต้นไม้แบบแผ่และไม่ทำให้เกิดวงจรแบบง่าย
ในขณะที่ Kruskal's algorithm จะพิจารณาเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดและไม่ทำให้เกิดวงจรแบบง่าย โดยไม่สนใจว่าจะเชื่อมต่ออยู่กับจุดในต้นไม้แบบแผ่หรือไม่
การนำไปประยุกต์ใช้ในงานด้านคอมพิวเตอร์
การแทนโครงสร้างต้นไม้ในคอมพิวเตอร์ เพื่อใช้ในการเก็บข้อมูล
ถ้าใช้โครงสร้างแบบ Tree จะทำให้ใช้งานการค้นหาข้อมูลแบบ ทวิภาค ทำให้การค้นหาข้อมูลในระบบคอมพิวเตอร์มีประสิทธิภาพขึ้น
