เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ (Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรืออาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression) นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอนในการคำนวณตามความสำคัญของเครื่องหมายด้วย โดยมีความสำคัญตามลำดับดังนี้
1.ฟังก์ชัน
2.วงเล็บ
3.ยกกำลัง
4.เครื่องหมายหน้าเลขจำนวน (unary)
5.คูณ หรือ หาร
6.บวก หรือ ลบ
7.ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
การแทนนิพจน์ในเอ็กซ์เพรสชันทรี ตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบ ส่วนตัวดำเนินการจะเก็บในโหนดกิ่ง หรือโหนดที่ไม่ใช่โหนดใบ เช่น นิพจน์ A + B สามารถแทนในเอ็กซ์เพรสชันทรีได้ดังนี้
ตัวอย่างเอ็กซ์เพรสชันทรี
ไบนารีเซิร์ชทรี (Binary Search Tree)
เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวา และในแต่ละทรีย่อยก็มีคุณสมบัติเช่นเดียวกัน ค่าข้อมูลในทรีย่อยทางซ้าย < ค่าข้อมูลที่โหนดราก < ค่าข้อมูลในทรีย่อยทางขวา
ปฏิบัติการในไบนารีเซิร์ชทรี
ปฏิบัติการเพิ่มโหนดเข้า หรือดึงโหนดออกจากไบนารีเซิร์ชทรี ค่อนข้างยุ่งยากกว่าปฏิบัติการในโครงสร้างอื่น ๆ เนื่องจากหลังปฏิบัติการเสร็จเรียบร้อยแล้ว ต้องคำนึงถึงความเป็นไบนารีเซิร์ชทรีของทรีนั้นด้วย ซึ่งมีปฏิบัติการดังต่อไปนี้
1. การเพิ่มโหนดในไบนารีเซิร์ชทรี การเพิ่มโหนดใหม่เข้าไปในไบนารีเซิร์ชทรี ถ้าทรีว่างโหนดที่เพิ่มเข้าไปก็จะเป็นโหนดรากของทรี ถ้าทรีไม่ว่างต้องทำการตรวจสอบว่าโหนดใหม่ที่เพิ่มเข้ามานั้นมีค่ามากกว่าหรือน้อยกว่าค่าที่โหนดราก ถ้ามีค่ามากกว่าหรือเท่ากันจะนำโหนดใหม่ไปเพิ่มในทรีย่อยทางขวา และถ้ามีค่าน้อยกว่านำโหนดใหม่ไปเพิ่มในทรีย่อยทางซ้าย ในทรีย่อยนั้นต้องทำการเปรียบเทียบในลักษณะเดียวกันจนกระทั่งหาตำแหน่งที่ สามารถเพิ่มโหนดได้ ซึ่งโหนดใหม่ที่เพิ่มในทรีในที่สุดจะต้องเป็นโหนดใบ
2. การดึงโหนดในไบนารีเซิร์ชทรี หลังจากดึงโหนดที่ต้องการออกจากทรีแล้ว ทรีนั้นต้องคงสภาพไบนารีเซิร์ชทรีเหมือนเดิมก่อนที่จะทำการดึงโหนดใด ๆ ออกจากไบนารีเซิร์ชทรี ต้องค้นหาก่อนว่าโหนดที่ต้องการดึงออกอยู่ที่ตำแหน่งไหนภายในทรี และต้องทราบที่อยู่ของโหนดแม่โหนดนั้นด้วย แล้วจึงทำการดึง
โหนดออกจากทรีได้ ขั้นตอนวิธีดึงโหนดออกอาจแยกพิจารณาได้ 3 กรณีดังต่อไปนี้
ก. กรณีโหนดที่จะดึงออกเป็นโหนดใบ การดึงโหนดใบออกในกรณีนี้ทำได้ง่ายที่สุด โดยการดึงโหนดนั้นออกได้ทันที เนื่องจากไม่กระทบกับโหนดอื่นมากนัก วิธีการก็คือให้ค่าในลิงค์ฟิลด์ของโหนดแม่ซึ่งเก็บที่อยู่ของโหนดที่ต้องการดึงออกให้มีค่าเป็น Null
ข. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยทางซ้ายหรือทรีย่อยทางขวาเพียงด้านใดด้านหนึ่ง วิธีการดึงโหนดนี้ออกสามารถใช้วิธีการเดียวกับการดึงโหนดออกจากลิงค์ลิสต์ โดยให้โหนดแม่ของโหนดที่จะดึงออกชี้ไปยังโหนดลูกของโหนดนั้นแทน
ค. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้ายและทรีย่อยทางขวา ต้องเลือกโหนดมาแทนโหนดที่ถูกดึงออก โดยอาจจะเลือกมาจากทรีย่อยทางซ้ายหรือทรีย่อยทางขวาก็ได้
- ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรีย่อยทางซ้าย ต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อยทางซ้ายนั้น
- ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมาจากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อยทางขวานั้น
กราฟ(Graph)
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบด้วยกลุ่มของสิ่งสองสิ่งคือ
1. โหนด (nodes) หรือ เวอร์เทกซ์ (vertexes)
2. เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (edges)
กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด ถ้าเอ็จไม่มีลำดับความสัมพันธ์จะเรียกกราฟนั้นว่า กราฟแบบไม่มีทิศทาง (undirected graphs) และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง (directed graphs) บางครั้งเรียกว่า ไดกราฟ (digraph)
โดยทั่ว ๆ ไปการเขียนกราฟเพื่อแสดงให้เห็นความสัมพันธ์ของสิ่งที่เราสนใจแทนโหนดด้วย จุด (pointes) หรือวงกลม (circles) ที่มีชื่อหรือข้อมูลกำกับ เพื่อบอกความแตกต่างของแต่ละโหนด และเอ็จแทนด้วยเส้นหรือเส้นโค้งเชื่อมต่อระหว่างโหนดสองโหนด ถ้าเป็นกราฟแบบมีทิศทางเส้นหรือเส้นโค้งต้องมีหัวลูกศรกำกับทิศทางของความสัมพันธ์ด้วย
** กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (empty graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือเชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการเชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก (first node) หรือไม่มีโหนดเริ่มต้นไม่มีโหนดใดเป็นโหนดสิ้นสุด
**ส่วนกราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (empty graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น (source node) และโหนดสิ้นสุด (target node)
การแทนกราฟในหน่วยความจำ
ในการปฏิบัติการกับโครงสร้างกราฟ สิ่งที่เราต้องการจัดเก็บจากกราฟโดยทั่วไปก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างโหนดสองโหนด มีวิธีการจัดเก็บหลายวิธี วิธีที่ง่ายและตรงไปตรงมาที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ
กราฟที่มีการเปลี่ยนแปลงตลอดเวลา อาจจะใช้วิธีแอดจาเซนซีลิสต์ (adjacency list) ซึ่งเป็นวิธีที่คล้ายวิธีจัดเก็บกราฟด้วยการเก็บโหนดและพอยน์เตอร์ แต่ต่างกันตรงที่แทนที่จะเก็บโหนดที่มีความสัมพันธ์ด้วยไว้ในแถวลำดับ 1 มิติ จะใช้ลิงค์ลิสต์แทนเพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข
นอกจากนี้ยังมีวิธีแทนกราฟในความจำหลักอีกวิธีหนึ่งซึ่งเป็นที่นิยมใช้กันมากที่สุดคือ การแทนด้วยแอดจาเซนซีเมทริกซ์ (adjacency matrix)
การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้นเพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำเครื่องหมายมาร์คบิตบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้วเพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไปในกราฟมี 2 แบบดังนี้
1. การท่องแบบกว้าง (breadth first traversal) วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ
2.การท่องแบบลึก (depth first traversal) การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด
ไม่มีความคิดเห็น:
แสดงความคิดเห็น