Tree
ทรี (Tree)เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship)ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงานต่าง ๆ อย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมูลเช่น แผนผังองค์ประกอบของหน่วยงานต่าง ๆโครงสร้างสารบัญหนังสือ
การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี (Traversing Binary Tree) เพื่อเข้าไปเยือนทุก ๆโหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้งวิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการเยือนอย่างไร โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)
ทรีย่อยทางซ้าย (แทนด้วย L) หรือทรีย่อยทางขวา (แทนด้วย R)
มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ
NLR LNR LRN NRL RNL และ RLN
แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นคือNLR LNR และ LRN ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้
1. การท่องไปแบบพรีออร์เดอร์(Preorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรี
2.การท่องไปแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์
ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree)เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน
Graph
กราฟที่มีการเปลี่ยนแปลงตลอดเวลาอาจจะใช้วิธีแอดจาเซนซีลิสต์(Adjacency List) ซึ่งเป็นวิธีที่คล้ายวิธีจัดเก็บกราฟด้วยการเก็บโหนดและพอยน์เตอร์ แต่ต่างกันตรงที่ จะใช้ ลิงค์ลิสต์แทนเพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข
การท่องไปในกราฟ มี 2 แบบ คือ
1. การค้นหาแบบกว้าง (Breadth-first Search)
2. การค้นหาแบบลึก (Depth-first Search)
กราฟ มีน้ำหนัก หมายถึง กราฟที่ทุกเอดจ์ มีค่าน้ำหนักกำกับ ซึ่งค่าน้ำหนักอาจสื่อถึงระยะทาง เวลาค่าใช้จ่าย เป็นต้น นิยมนำไปใช้แก้ปัญหาหลัก ๆ 2 ปัญหา คือ
1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด(Minimum Spanning Trees :MST) Prim’s Algorithm and Kruskal’s Algorithm
2. การหาเส้นทางที่สั้นที่สุด (Shortest path) Dijkstra’s Algorithmหาเส้นทางที่สั้นที่สุดจากโหนดต้นทางไปโหนดใด ๆ ในกราฟ มีน้ำหนัก และน้ำหนักไม่เป็นลบ
Sorting
การเรียงลำดับในลักษณะนี้ เป็นการปรับปรุงมาจากการเรียงลำดับแบบ Bubble เพื่อให้การเรียงลำดับเร็วขึ้น วีธีนี้เหมาะกับการเรียงข้อมูลที่มีจำนวนมาก หรือมีขนาดใหญ่ และเป็นวิธีการเรียงข้อมูลที่ให้ค่าเฉลี่ยของเวลาน้อยที่สุดเท่าที่ค้นพบวิธีหนึ่งการเรียงลำดับแบบ Quick Sortจะเป็นการเปรียบเทียบสมาชิกที่ไม่อยู่ติดกัน โดยกำหนดข้อมูลค่าหนึ่ง เพื่อแบ่งชุดข้อมูลที่ต้องการเรียงลำดับออกเป้น 2 ส่วน จากนั้นก็จะทำการแบ่งย่อยชุดข้อมูล 2 ส่วนนั้นลงไปอีก ทำแบบนี้ไปเรื่อยๆจนข้อมูลแต่ละชุดมีสมาชิกเหลือเพียงตัวเดียวและทำให้ชุดข้อมูลทั้งหมดมีการเรียงลำดับ
การค้นหา คือการใช้วิธีการค้นหากับโครงสร้างข้อมูล เพื่อดูว่าข้อมูลตัวที่ต้องการถูกเก็บอยู่ในโครงสร้างแล้วหรือยัง
วัตถุประสงค์ของการค้นหาโดยทั่วไป ได้แก่เพื่อดูรายละเอียดเฉพาะข้อมูลส่วนที่ต้องการ
ดึงข้อมูลตัวที่ค้นหาออกจากโครงสร้างเปลี่ยนแปลงแก้ไขรายละเอียดบางอย่างของข้อมูลตัวที่ค้นพบ และ/หรือเพิ่มข้อมูลตัวที่ค้นหาแล้วพบว่ายังไม่เคยเก็บไว้ในโครงสร้างเลย
เข้าไปเก็บไว้ในโครงสร้าง เพื่อใช้งานต่อไป
Searching
การค้นหาข้อมูล (Searching)
การค้นหา คือการใช้วิธีการค้นหากับโครงสร้างข้อมูล เพื่อดูว่าข้อมูลตัวที่ต้องการถูกเก็บอยู่ในโครงสร้างแล้วหรือยังวัตถุประสงค์ของการค้นหาโดยทั่วไป ได้แก่ เพื่อดูรายละเอียดเฉพาะข้อมูลส่วนที่ต้องการดึงข้อมูลตัวที่ค้นหาออกจากโครงสร้างเปลี่ยนแปลงแก้ไขรายละเอียดบางอย่างของข้อมูลตัวที่ค้นพบ และ/หรือเพิ่มข้อมูลตัวที่ค้นหาแล้วพบว่ายังไม่เคยเก็บไว้ในโครงสร้างเลย เข้าไปเก็บไว้ในโครงสร้าง เพื่อใช้งานต่อไป
การค้นหา แบ่งเป็น 2 ประเภท ตามแหล่งที่จัดเก็บข้อมูลเช่นเดียวกับการเรียงลำดับ
การค้นหาข้อมูลแบบภายใน (Internal Searching)
การค้นหาข้อมูลแบบภายนอก (External Searching)
1. การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ(Linear)
2. การค้นหาแบบเซนทินัล (Sentinel)
3. การค้นหาแบบไบนารี (Binary Search)
การค้นหาแบบไบนารี (Binary Search)
เริ่มการค้นหาแบบไบนารีด้วยการเปรียบเทียบกับค่ากลางในลิสต์ คือค่า a[4] ซึ่งเก็บค่า 8 ซึ่ง 12 > a[4] หมายความว่าค่า 12 ควรจะอยู่ในข้อมูลด้านขวาของ a[4] คือ ช่วง a[5] …a[8]
โดยไม่สนใจช่วงข้อมูล a[1] …a[3] และใช้วิธีการค้นหาแบบไบนารีเช่นเดิมอีกกับชุดข้อมูลครึ่งหลัง คือa[5] …a[8] นั่นคือ เปรียบเทียบกับค่ากลางของชุดข้อมูลครึ่งหลัง(a[5] …a[8] ) คือค่า a[6] ซึ่งเก็บค่า 12 ซึ่ง 12 = a[6] จะได้ว่าค่า 12 อยู่ในตำแหน่งที่ 6 ในลิสต์
DTS 11-16-09-2552
ไม่มีความคิดเห็น:
แสดงความคิดเห็น