DTS_ 9 02/09/2552

สรุปเรื่อง ทรี Tree (ต่อ)

เอ็กซ์เพรสชั่นทรี (Expreesion Tree)
เป็นการเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี
ซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และตัวถูกดำเนินการ
(Operand) ของนิพจน์คณิตศาสตร์นั้นๆไว้หรืออาจจะเก็บค่านิพจน์ทางตรรกะ
(Logical Expression) นิพจน์เหล่านี้เมื่อแทนที่ในทรีตองคำนึงลำดับขั้นตอน
ในการคำนวณตามความสำคัญของเครื่องหมายด้วยโดยมีความสำคัญตาม
ลำดับดังนี้
-ฟังก์ชั่น
-วงเล็บ
-ยกกำลัง
-เครื่องหมายหน้าเลขจำนวน(unary)
-คูณ หรือ หาร
-บวก หรือ ลบ
-ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
การแทนที่ในเอ็กซ์เพรสชั่นทรี ตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบ
ส่วนตัวดำเนินการจะเก็บในโหนดกิ่ง หรือโหนดที่ไม่ใช่โหนดใบ

ไบนารีเซิร์ชทรี

ไบนารีเซิร์ชทรี (Binary Search Tree) เป็นไบนารีทรีที่มีคุณสมบัติ
ที่ว่าทุกๆโหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนด
ในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดใน
ทรีย่อยทางขวาและในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน
ปฏิบัติการในไบนารีเซิร์ชทรี ปฏิบัติการเพิ่มโหนดเข้าหรือดึงโหนด
ออกจากไบนารีเซิร์ชทรีค่อยข้างยุ่งยากกว่าปฏิบัติการในโครงสร้าง
อื่นๆ เนื่องจากหลังปฏิบัติการเสร็จเรียบร้อยแล้วต้องคำนึงถึงความ
เป็นไบนารีทรีของทรีนั้นด้วยซึ่งมีปฏิบัติการดังต่อไปนี้

1.การเพิ่มโหนดในใบนารีทรี ถ้าทรีว่างโหนดที่เพิ่มเข้าไปก็จะเป็น
โหนดรากของทรี ถ้าทรีไม่ว่างต้องทำการตรวจสอบว่าโหนดใหม่
ที่เพิ่มเข้ามานั้นมีค่ามากกว่าหรือน้อยกว่าค่าที่โหนดราก ถ้ามีค่า
มากกว่าหรือเท่ากันจะนำโหนดใหม่ไปเพิ่มในทรีย่อยด้านขวา
และถ้ามีค่าน้อยกว่าให้ไปเพิ่มในทรีย่อยทางด้ายซ้าย ในทรีย่อย
นั้นต้องทำการเปรียบเทียบในลักษณะเดียวกันจนกระทั่งหาตำแหน่ง
ที่สามารถเพิ่มโหนดได้ ซึ่งโหนดใหม่ที่เพิ่มในทรีในที่สุดจะต้องเป็น
โหนดใบ

2.การดึงโหนดในไบนาทรีเซิร์ชทรีหลังจากดึงโหนดที่ต้องการออกจาก
ทรีแล้วทรีนั้นต้องคงสภาพไบนารีเซิร์ชทรีเหมือนเดิมก่อนที่จะทำการ
ดึงโหนดใดๆ ออกจากไบนารีเซิร์ชทรี ต้องค้นหาก่อนว่าโหนดที่ต้อง
การดึงออกอยู่ที่ตำแหน่งไหนภายในทรีและต้องทราบที่อยู่ของโหนด
แม่โหนดนั้นด้วยแล้วจึงทำการดึงโหนดออกจากทรีได้ ขั้นตอนวิธีดึง
โหนดออกอาจแยกพิจารณาได้ 3 กรณีดังต่อไปนี้

ก.กรณีที่โหนดที่จะดึงออกเป็นโหนดใบ การดึงโหนดใบออกในกรณีนี้
ทำได้ง่ายที่สุดโดยการดึงโหนดนั้นออกได้ทันที วิธีการก็คือให้ค่าใน
ลิงค์ฟิลด์ของโหนดแม่ซึ่งเก็บที่อยู่ของโหนดที่ต้องการดึงออกให้มี
ค่าเป็น Null

ข.กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยทางซ้ายหรือทรีย่อยทางขวา
เพียงด้านใดด้านหนึ่ง วิธีการดึงโหนดนี้ออกสามารถใช้วิธีการเดียวกับ
การดึงโหนดออกจากลิงค์ลิสต์ โดยให้โหนดแม่ของโหดนที่จะดึงออก
ชี้ไปยังโหนดลูกของโหนดนั้นแทน

ค.กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้ายและทรีย่อยทางขวาต้อง
เลื่อกมาจากทรีย่อยทางซ้ายหรือทรีย่อยทางขวาก็ได้
-ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรีย่อยทางซ้ายต้องเลือก
โหนดทีมีค่ามากที่สุดในทรีย่อยทางซ้ายนั้น
-ถ้าโหนดที่มีจะมาแทนที่เป็นโหนดที่เลือกมาจากทรีย่อยทางขวา
ต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อยทางขวา


เรื่อง Graph

กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง
กราฟเป็นโครงสร้างข้อมูลทีมีการนำไปใช้ในงานที่เกี่ยวข้องกับการ
แก้ปัญหาที่ค่อนข้างซับซ้อน เช่น การวางข่าย งานคอมพิวเตอร์
การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น

นิยามของกราฟ

กราฟเป็นโครงสร้างข้อมูลแบบไม่ใช้เชิงเส้นที่ประกอบด้วยกลุ่ม
ของสิ่งสองสิ่งคือ
1.โหนด (Nodes) หรือ เวอร์เทกซ์ (Vertexes)
2.เส้นเชื่อมระหว่างโหนดเรียก เอ็จ (Edges)
กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด ถ้าเอ็จไม่มีลำดับ
ความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง
(Undirected Graphs) และถ้ากราฟนั้นมีเอ็จที่มีลำดับ
ความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า
กราฟแบบมีทิศทาง (Directed Graphs) บางครั้งเรียกว่า
ไดกราฟ (Digraph)
การเขียนกราฟแสดงโหนดและเส้นความสัมพันธ์ ระหว่างโหนด
ไม่มีรูปแบบที่ตายตัว

ตัวอย่างรูปแบบของกราฟ

โหนดสองโหนดในกราฟแบบไม่มีทิศทางถือว่าเป็นโหนดที่ใกล้
กัน (Adjacent) ถ้ามีเอ็จเชื่อมจากโหดนที่หนึ่งไปโหนดที่สอง
กราฟ(ก) แสดงกราฟที่มีลักษณะต่องเนื่อง (Connected)
เป็นกราฟที่มีเส้นทางเชื่อมจากโหนดใดๆไปยังโหนดอื่นเสมอ