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) ตามแนววิถีเดิมนั้น จนกระทั่ง สามารถดำเนินการต่อ

เนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือน โหนดอื่น ๆ ต่อไปจนครบทุกโหนด