DTS 09-02/09/52

สรุปเรื่อง Tree (ต่อ)
เอ็กซ์เพรสชันทรี (Expression Tree)เป็นการนำเอาโครงสร้างทรีไปใช้เก็บ
นิพจน์ ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนดเก็บตัวดำเนินการ
(Operator) และตัวถูกดำเนินการ(Operand) ของนิพจน์คณิตศาสตร์
นั้น ๆ ไว้ โดยมีความสำคัญตามลำดับดังนี้
- ฟังก์ชัน - วงเล็บ
- ยกกำลัง - เครื่องหมายหน้าเลขจำนวน (unary)
- คูณ หรือ หาร - บวก หรือ ลบ
- ถ้ามีเครื่องหมายที่ระดับเดียวกันห้ทำจากซ้ายไปขวา
ไบนารีเซิร์ชทรี (Binary Search Tree)
เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนดในทรี ค่าของโหนดรากมีค่ามาก
กว่าค่าของทุก โหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุก
โหนดในทรีย่อยทางขวา และในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกันมี
ปฏิบัติการดังต่อไปนี้
(1) การเพิ่มโหนดในไบนารีเซิร์ชทรี ถ้าทรีว่างโหนดที่เพิ่มเข้าไปก็จะเป็นโหนดรากของทรี ถ้าทรีไม่ว่างต้องทำการ
ตรวจสอบว่าโหนดใหม่ที่เพิ่มเข้ามานั้นมีค่ามากกว่าหรือน้อยกว่าค่าที่โหนดราก
ถ้ามีค่ามากกว่าหรือเท่ากันจะนำโหนดใหม่ไปเพิ่มในทรีย่อยทางขวาและถ้ามีค่า
น้อยกว่านำโหนดใหม่ไปเพิ่มในทรีย่อยทางซ้าย
(2) การดึงโหนดในไบนารีเซิร์ชทรี หลังจากดึงโหนดที่ต้องการออกจากทรีแล้ว
ทรีนั้นต้องคงสภาพไบนารีเซิร์ชทรีเหมือนเดิมก่อนที่จะทำการดึงโหนดใด ๆ ออก
จาก ไบนารีเซิร์ชทรี ต้องค้นหาก่อนว่าโหนดที่ต้องการดึงออกอยู่ที่ตำแหน่งไหน
ภายในทรี และต้องทราบที่อยู่ของโหนดแม่โหนดนั้นด้วยแล้วจึงทำการดึงโหนด
ออกจากทรีได้ ขั้นตอนวิธีดึงโหนดออกอาจแยกพิจารณาได้ 3 กรณีดังต่อไปนี้
ก. กรณีโหนดที่จะดึงออกเป็นโหนดใบการดึงโหนดใบออกในกรณีนี้ ทำได้
ง่ายที่สุดโดยการดึงโหนดนั้นออกได้ทันที เนื่องจากไม่กระทบกับโหนดอื่นมาก
นัก วิธีการก็คือให้ค่าในลิงค์ฟิลด์ของโหนดแม่ซึ่งเก็บที่อยู่ ของโหนดที่ต้องการ
ดึงออกให้มีค่าเป็น Null
ข. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยทางซ้ายหรือทรีย่อยทางขวาเพียง
ด้านใดด้านหนึ่ง วิธีการดึงโหนดนี้ออกสามารถใช้วิธีการเดียวกับการดึงโหนด
ออกจากลิงค์ลิสต์ โดยให้โหนดแม่ของโหนดที่จะดึงออกชี้ไปยังโหนดลูกของ
โหนดนั้นแทน
ค. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้าย และทรีย่อยทางขวาต้องเลือกโหนด
มาแทนโหนดที่ถูก ดึงออก โดยอาจจะเลือกมาจากทรีย่อยทางซ้ายหรือ ทรีย่อย
ทางขวาก็ได้

สรุป เรื่อง Graph
กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็น
โครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับ
ซ้อนเช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหา
เส้นทางที่สั้นที่สุด เป็นต้นนิยามของกราฟ กราฟ เป็นโครงสร้างข้อมูลแบบไม่
ใช่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์(Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนดถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะ
เรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง (Undirected Graphs)และ
ถ้ากราฟนั้นมีเอ็จที่มีลำดับ ความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า
กราฟแบบมีทิศทาง(Directed Graphs)บางครั้งเรียกว่า ไดกราฟ
(Digraph) โดยทั่ว ๆ ไปการเขียนกราฟเพื่อแสดงให้ เห็นความสัมพันธ์
ของสิ่งที่เราสนใจแทนโหนดด้วย จุด (pointes) หรือวงกลม (circles)
ที่มีชื่อหรือข้อมูลกำกับเพื่อบอกความแตกต่างของแต่ละโหนดและเอ็จแทนด้วย
เส้น หรือเส้นโค้งเชื่อมต่อระหว่างโหนดสองโหนด ถ้าเป็นกราฟแบบมีทิศทาง
เส้นหรือเส้นโค้งต้อง มีหัวลูกศรกำกับทิศทางของความสัมพันธ์ด้วย โหนดสอง
โหนดในกราฟแบบไม่มีทิศทางถือว่า เป็นโหนดที่ใกล้กัน (Adjacent)
ถ้ามีเอ็จเชื่อมจาก โหนดที่หนึ่งไปโหนดที่สอง
กราฟ (ก) แสดงกราฟที่มีลักษณะ ต่อเนื่อง (Connected)
เป็นกราฟที่มีเส้นทางเชื่อมจากโหนด ใด ๆ ไปยังโหนดอื่นเสมอ
กราฟ (ข) แสดงกราฟที่มีลักษณะเป็น วีถี (Path) มีเส้นทาง
เชื่อมไปยังโหนดต่าง ๆ อย่างเป็น ลำดับ โดยแต่ละโหนดจะเป็น
โหนดที่ใกล้กันกับโหนดที่อยู่ถัดไป
กราฟ (ค) แสดงกราฟที่เป็นวัฎจักร (Cycle) ซึ่งต้องมีอย่าง
น้อย 3 โหนด ที่โหนดสุดท้ายต้อง เชื่อมกับโหนดแรก
กราฟ (ง) แสดงกราฟที่มีลักษณะ ไม่ต่อเนื่อง
(Disconnected) เนื่องจากไม่มีเส้นทางเชื่อมจาก
โหนด 3 ไปยังโหนดอื่นเลย
กราฟ (จ) แสดงกราฟที่เป็นทรี โดยทรีเป็น กราฟที่ต่อเนื่อง
ไม่มีทิศทาง และไม่เป็นวัฏจักร
การแทนกราฟในหน่วยความจำ
ในการปฏิบัติการกับโครงสร้างกราฟ สิ่งที่ต้องการจัดเก็บ จากกราฟโดย
ทั่วไปก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างโหนดสองโหนด มีวิธีการจัดเก็บ
หลายวิธี วิธีที่ง่ายและตรงไปตรงมาที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ
การจัดเก็บกราฟด้วยวิธีเก็บโหนดและพอยน์เตอร์ นี้ยุ่งยาก ในการจัดการเพิ่ม
ขึ้นเนื่องจากต้องเก็บโหนด และพอยน์เตอร์ในแถวลำดับ 2 มิติ และต้องจัดเก็บ
โหนดที่สัมพันธ์ด้วยในแถวลำดับ 1 มิติ อย่างไรก็ตามทั้งสองวิธีไม่เหมาะกับ
กราฟที่มีการ เปลี่ยนแปลง ตลอดเวลา ควรใช้ในกราฟที่ไม่มีการ เปลี่ยนแปลง
ตลอดการใช้งาน เพราะถ้ามีการเปลี่ยนแปลงส่วนใดส่วนหนึ่งของกราฟจะกระ
ทบกับส่วนอื่น ๆ ที่อยู่ในระดับที่ต่ำกว่าด้วยเสมอ
การท่องไปในกราฟ (graph traversal)
คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการ ทำงานคือ แต่ละ
โหนดจะถูกเยือนเพียงครั้งเดียว สำหรับ การท่องไปในทรีเพื่อเยือนแต่ละโหนด
นั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้น
เพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำ เครื่องหมายบริเวณ
ที่ได้เยือนเสร็จเรียบร้อยแล้ว เพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไป
ในกราฟมี 2 แบบดังนี้
1. การท่องแบบกว้าง (Breadth First Traversal) วิธีนี้ทำโดย
เลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนด อื่นที่ใกล้กันกับโหนดเริ่มต้นที
ละระดับจนกระทั่งเยือนหมดทุก โหนดในกราฟ
2. การท่องแบบลึก (Depth First Traversal) การทำงานคล้าย
กับการท่องทีละระดับของทรี โดย กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนด
ถัดไปตาม แนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อนกลับ
(backtrack) ตามแนววิถีเดิมนั้น จนกระทั่ง สามารถดำเนินการต่อ
เนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือน โหนดอื่น ๆ ต่อไปจนครบทุกโหนด