สรุป
เอ็กซ์เพรสชั่นทรีเป็นการนำนิพจน์มาเก็บยังโครงสร้างทรี โดยแต่ละโหนดจะเก็บตัวดำเนินการ (Operator) และตัวถูกดำเนินการ (Operand) ซึ่งตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบ ส่วนตัวดำเนินการจะเก็บอยู่ที่โหนดกิ่ง แต่ต้องคำนึงถึงความสำคัญของเครื่องหมายตามลำดับด้วย คือ-ฟังก์ชั่น-วงเล็บ-ยกกำลัง-เครื่องหมายหน้าเลขจำนวน-คูณ หาร-บวก ลบ***ถ้ามีความสำคัญในระดับเดียวกันให้ทำจากซ้ายไปขวาไบนารีเซิร์ซทรีค่าของโหนดรากจะมีค่ามากกว่าโหนดย่อยทางด้านซ้าย และมีค่าน้อยกว่าหรือเท่ากับโหนดย่อยทางด้านขวาการเพิ่มโหนดในไบนารีเซิร์ซทรี ถ้าทรีว่างโหนดที่เพิ่มจะเป็นโหนดราก ถ้าทรีไม่ว่างต้องทำการตรวจสอบโหนดใหม่ว่ามีค่ามากกว่าหรือน้อยกว่าค่าที่โหนดราก
***ถ้ามีค่ามากกว่าหรือเท่ากันจะนำโหนดที่เพิ่มไปเพิ่มยังทรีย่อยด้านขวา แต่ถ้ามีค่าน้อยกว่าจะนำไปเพิ่มที่ทรีย่อยด้านซ้าย
การดึงโหนดในไบนารีเซิร์ซทรี ต้องทำการค้นหาตำแหน่งที่ต้องการดึงก่อนว่าอยู่ตำแหน่งใดแล้วต้องรู้ด้วยว่าโหนดแม่ของโหนดนั้นคือโหนดไหน จึงจะสามารถทำการดึงได้ แต่เมื่อดึงโหนดออกแล้ว ทรีนั้นต้องคงสภาพเนไบนารีเซิร์ซทรีเหมือนเดิม
วิธีการดึงโหนดออก แยกได้ 3 วิธี
1. กรณีโหนดที่จะดึงออกเป็นโหนดใบ สามารถดึงได้เลยเพราะไม่มีผลกระทบต่อโหนดอื่นๆ แล้วเป็นวิธีที่ง่ายที่สุด
2. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยด้านซ้ายหรือทรีย่อยด้านขวาเพียงด้านใดด้านหนึ่ง สามารถทำได้เหมือนวิธีแรก เพียงให้โหนดแม่ของโหนดที่ต้องการดึงออกชี้ไปยังโหนดลูกของโหนดนั้นแทน
3. กรณีโหนดที่ต้องการดึงออกมีทั้งทรีย่อยด้านซ้ายและทรีย่อยด้านขวา ต้องทำการเลือกว่าจะนำทรีย่อยด้านใดมาแทนโหนดที่ถูกดึงออก
***ถ้าเลือกทรีย่อยด้านซ้ายต้องเลือกโหนดที่มีค่ามากที่สุดมาแทน แต่ถ้าเลือกทรีย่อยด้านขวาต้องเลือกโหนดที่มีค่น้อยที่สุดมาแทน
Graph
เป็นโครงสร้างข้อมูลแบบไม่เชิงเส้น ประกอบด้วยกลุ่มของสิ่งสองสิ่ง คือ
1.โหนด แทนด้วย N
2.เส้นเชื่อมระหว่างโหนด แทนด้วย E
*** กราฟที่มีเส้นเชื่อมระหว่างโหนดที่ไม่มีลำดับ จะเรียกกราฟนั้นว่า กราฟแบบไม่มีทิศทาง
ส่วนกราฟที่มีเส้นเชื่อมระหว่างโหนดที่มีลำดับ จะเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง หรือเรียกว่า ไดกราฟ
ในการเขียนกราฟสิ่งที่สนใจจะถูกแทนด้วยจุด หรือ วงกลม ที่มีชื่อข้อมูลกำกับ ส่วนเอ็จจะแทนด้วยเส้นหรือเส้นโค้ง
กราฟแบบมีทิศทางเส้นเอ็จต้องมีลูกศรกำกับแสดงลำดับการเชื่อมต่อ โดยมีโหนดเริ่มต้นและโหนดสิ้นสุด
กราฟแบบไม่มีทิศทาง เอ็จจะเชื่อมต่อกันแบบไม่สำคัญ คือสามารถเชื่อมต่อไปยังโหนดใดก็ได้ ไม่มีโหนด
ใดเป็นโหนดแรก และไม่มีโหนดใดเป็นโหนดสิ้นสุด
การแทนกราฟในหน่วยความจำ
สิ่งที่ต้องการจัดเก็บก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างโหนดสองโหนด วิธีที่ง่ายคือ การเก็บเอ็จในแถวลำดับ 2 มิติ แต่จะเป็นการเปลืองเนื้อที่เพราะบางเอ็จมีการเก็บซ้ำ แต่สามารถแก้ปัญหานี้ได้โดยมิติแรกเก็บโหนดต่างๆ แล้วใช้พอยเตอร์ชี้ไปยังความสัมพันธ์กับโหนดในมิติ 2 แต่เป็นวิธีที่ยุ่งยาก ไม่เหมาะกับกราฟที่มีการเปลี่ยนแปลงตลอดเวลา กราฟที่มีการเปลี่ยนแปลงตลอดเวลา อาจใช้วิธีแอดจาเซนซีลิสต์ คือการใช้
ลิงค์ลิสต์ เพื่อความสะดวกในการเปลี่ยนแปลง นอกจากนี้ยังมีวิธีแทนกราฟในความจำหลักอีกวิธีหนึ่งซึ่งเป็นที่นิยมใช้กันมากที่สุดคือ การแทนด้วยแอดจาเซนซีเมทริกซ์ โดยที่ถ้ากราฟ L มีทั้งหมด nโหนด แอดจาเซนซีเมทริกซ์เป็นเมทริกซ์จัตุรัสขนาด n*n วิธีนี้สามารถหาจำนวนเส้นทางได้ว่ามีกี่จำนวนเส้นทาง
การท่องไปในกราฟ
เป็นการไปเยือนโหนดในกราฟ ซึ่งแต่ละโหนดจะถูกเยือนเพียงครั้งเดียว แต่กราฟนั้นมาหลายเส้นทางเมื่อเยือนแล้วต้องทำเครื่องหมายว่าได้เยือนเรียบร้อย การท่องไปในกราฟมี 2 แบบ คือ
1.การท่องแบบกว้าง เป็นการกำหนดโหนดที่จะเยือนหรือโหนดเริ่มต้นแล้วทำการเยือนไปยังโหนดที่ใกล้เคียงจนกระทั่งครบทุกโหนด
2.การท่องแบบลึก โดยกำหนดเริ่มต้นที่โหนดแรกแล้วเยือนโหนดถัดไปตามแนววิถีจนถึงปลายวิถี แล้วย้อนกลับมาเพื่อเยือนโหนดอื่นๆ
ไม่มีความคิดเห็น:
แสดงความคิดเห็น