DTS 09-02-09-2552

สรุปเนื้อหาบทเรียน "Data Structure"

เรื่อง Tree (ต่อ) และ Graph

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

***ถ้ามีความสำคัญในระดับเดียวกันให้ทำจากซ้ายไปขวา

ไบนารีเซิร์ซทรี
ค่าของโหนดรากจะมีค่ามากกว่าโหนดย่อยทางด้านซ้าย และมีค่าน้อยกว่าหรือเท่ากับโหนดย่อยทางด้านขวา

การเพิ่มโหนดในไบนารีเซิร์ซทรี ถ้าทรีว่างโหนดที่เพิ่มจะเป็นโหนดราก ถ้าทรีไม่ว่างต้องทำการตรวจสอบโหนดใหม่ว่ามีค่ามากกว่าหรือน้อยกว่าค่าที่โหนดราก

***ถ้ามีค่ามากกว่าหรือเท่ากันจะนำโหนดที่เพิ่มไปเพิ่มยังทรีย่อยด้านขวา แต่ถ้ามีค่าน้อยกว่าจะนำไปเพิ่มที่ทรีย่อยด้านซ้าย

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

วิธีการดึงโหนดออก แยกได้ 3 วิธี

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

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

3. กรณีโหนดที่ต้องการดึงออกมีทั้งทรีย่อยด้านซ้ายและทรีย่อยด้านขวา ต้องทำการเลือกว่าจะนำทรีย่อยด้านใดมาแทนโหนดที่ถูกดึงออก

***ถ้าเลือกทรีย่อยด้านซ้ายต้องเลือกโหนดที่มีค่ามากที่สุดมาแทน แต่ถ้าเลือกทรีย่อยด้านขวาต้องเลือกโหนดที่มีค่น้อยที่สุดมาแทน

Graph

เป็นโครงสร้างข้อมูลแบบไม่เชิงเส้น ประกอบด้วยกลุ่มของสิ่งสองสิ่ง คือ

1.โหนด แทนด้วย N

2.เส้นเชื่อมระหว่างโหนด แทนด้วย E

*** กราฟที่มีเส้นเชื่อมระหว่างโหนดที่ไม่มีลำดับ จะเรียกกราฟนั้นว่า กราฟแบบไม่มีทิศทาง

ส่วนกราฟที่มีเส้นเชื่อมระหว่างโหนดที่มีลำดับ จะเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง หรือเรียกว่า ไดกราฟ

ในการเขียนกราฟสิ่งที่สนใจจะถูกแทนด้วยจุด หรือ วงกลม ที่มีชื่อข้อมูลกำกับ ส่วนเอ็จจะแทนด้วยเส้นหรือเส้นโค้ง

กราฟแบบมีทิศทางเส้นเอ็จต้องมีลูกศรกำกับแสดงลำดับการเชื่อมต่อ โดยมีโหนดเริ่มต้นและโหนดสิ้นสุด

กราฟแบบไม่มีทิศทาง เอ็จจะเชื่อมต่อกันแบบไม่สำคัญ คือสามารถเชื่อมต่อไปยังโหนดใดก็ได้ ไม่มีโหนดใดเป็นโหนดแรก และไม่มีโหนดใดเป็นโหนดสิ้นสุด

การแทนกราฟในหน่วยความจำ

สิ่งที่ต้องการจัดเก็บก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างโหนดสองโหนด วิธีที่ง่ายคือ การเก็บเอ็จในแถวลำดับ 2 มิติ แต่จะเป็นการเปลืองเนื้อที่เพราะบางเอ็จมีการเก็บซ้ำ แต่สามารถแก้ปัญหานี้ได้โดยมิติแรกเก็บโหนดต่างๆ แล้วใช้พอยเตอร์ชี้ไปยังความสัมพันธ์กับโหนดในมิติ 2 แต่เป็นวิธีที่ยุ่งยาก ไม่เหมาะกับกราฟที่มีการเปลี่ยนแปลงตลอดเวลา

กราฟที่มีการเปลี่ยนแปลงตลอดเวลา อาจใช้วิธีแอดจาเซนซีลิสต์ คือการใช้ลิงค์ลิสต์ เพื่อความสะดวกในการเปลี่ยนแปลง

นอกจากนี้ยังมีวิธีแทนกราฟในความจำหลักอีกวิธีหนึ่งซึ่งเป็นที่นิยมใช้กันมากที่สุดคือ การแทนด้วยแอดจาเซนซีเมทริกซ์ โดยที่ถ้ากราฟ L มีทั้งหมด nโหนด แอดจาเซนซีเมทริกซ์เป็นเมทริกซ์จัตุรัสขนาด n*n วิธีนี้สามารถหาจำนวนเส้นทางได้ว่ามีกี่จำนวนเส้นทาง

การท่องไปในกราฟ

เป็นการไปเยือนโหนดในกราฟ ซึ่งแต่ละโหนดจะถูกเยือนเพียงครั้งเดียว แต่กราฟนั้นมาหลายเส้นทางเมื่อเยือนแล้วต้องทำเครื่องหมายว่าได้เยือนเรียบร้อย การท่องไปในกราฟมี 2 แบบ คือ

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

2.การท่องแบบลึก โดยกำหนดเริ่มต้นที่โหนดแรกแล้วเยือนโหนดถัดไปตามแนววิถีจนถึงปลายวิถี แล้วย้อนกลับมาเพื่อเยือนโหนดอื่นๆ