สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง ทรี tree(ต่อ) และ เรื่องกราฟ Graph
ไบนารี่เสิร์ชทรี
เป็นไบนารี่ทรีที่รวบรวมค่าของ N เรคคอร์ดซึ่งเป็นคีย์ (Key) ตั้งแต่ K1 , K2 ,…….Kn โดยแต่ละโหนด Ri จะมี Ki เพียงคีย์เดียวสำหรับ i=1,2,….,N คีย์เป็นค่าสร้างความแตกต่าง (Identifier) ให้แต่ละโหนด ในการค้นหาโหนดที่ต้องการจะกระทำโดยค้นหาค่าของคีย์ และโหนด Ri ของไบนารี่เสิร์ชทรีจะถูกจัดการตามคุณสมบัติ ดังนี้
1. ทุก ๆ คีย์ของโหนดที่อยู่ในทรีย่อยด้านซ้ายของ Ri เป็นค่าที่มาก่อนหรือน้อยกว่าคีย์ของ Ri If Ri € Left (Ri) Then Kj <>
- ทุก ๆ คีย์ของโหนดที่อยู่ในทรีย่อยด้านขวาของ Ri เป็นค่าที่ตามหลังหรือมากกว่าคีย์ของ Ri
If Ri € Right (Ri) Then Kj > Ki จะได้ว่าคีย์ที่มาก่อนจะถูกพิจารณาตามลำดับเชิงเส้นและขึ้นกับลำดับการรวบรวม เมื่อพิจารณาตามคุณสมบัติที่ผ่านมาการค้นหาจะได้คีย์ A,B,C,D ตามลำดับและมีหลายวิธีที่จะจัดการกับไบนารี่เสิร์ชทรี จากรูปดังกล่าวจะมีไบนารี่เสิร์ชทรีหลายแบบแต่ลำดับของคีย์เหมือนกัน
วิธีการดึงโหนดออก แยกได้ 3 วิธี
1. กรณีโหนดที่จะดึงออกเป็นโหนดใบ สามารถดึงได้เลยเพราะไม่มีผลกระทบต่อโหนดอื่นๆ แล้วเป็นวิธีที่ง่ายที่สุด
2. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยด้านซ้ายหรือทรีย่อยด้านขวาเพียงด้านใดด้านหนึ่ง สามารถทำได้เหมือนวิธีแรก เพียงให้โหนดแม่ของโหนดที่ต้องการดึงออกชี้ไปยังโหนดลูกของโหนดนั้นแทน
3. กรณีโหนดที่ต้องการดึงออกมีทั้งทรีย่อยด้านซ้ายและทรีย่อยด้านขวา ต้องทำการเลือกว่าจะนำทรีย่อยด้านใดมาแทนโหนดที่ถูกดึงออก
กราฟ (Graph)
เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด
กราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง vertex และ edge กราฟจะประกอบด้วยกลุ่มของ vertex ซึ่งแสดงในกราฟด้วยสัญลักษณ์รูปวงกลม และ กลุ่มของ edge (เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์กัน ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้
กราฟสามารถเขียนแทนด้วยสัญลักษณ์ ดังนี้
G = ( V , E )
G คือ กราฟ
V คือ กลุ่มของ vertex
E คือ กลุ่มของ edge
ศัพท์ที่เกี่ยวข้อง
1.เวอร์เทก (Vertex) หมายถึง โหนด
2.เอดจ (Edge) หมายถึง เส้นเชื่อมของโหนด
3.ดีกรี (Degree) หมายถึง จำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด
4.แอดจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเชื่อมโยงกัน
Graph แบ่งเป็น
1. Directed Graph (Digraph) (Arc) แบบระบุทิศทาง
2. Undirected Graph แบบไม่ระบุทิศทาง
การเก็บข้อมูลในหน่วยความจำสามารถทำได้ 2 แบบ ดังนี้
1. Adjacency Matrix (แอดจาเซนซี เมตริก) : ใช้อาร์เรย์เก็บข้อมูล
2. Adjacency List (แอดจาเซนซี ลิส) : ใช้ลิงค์ลิสต์เก็บข้อมูล
Adjacency Matrix
เป็นโครงสร้างที่ประกอบไปด้วยโหนดและเส้นเชื่อมต่อที่บอกถึงเส้นทางของการเดินทาง หรือความสัมพันธ์ในทิศทางซึ่งสามารถนำมาแทนความสัมพันธ์นั้นด้วยการกำหนดเมตริกซ์ n x n
Mk เป็นเมทริกซ์ของกราฟใด ๆ k คือทางเดินที่มีความยาว k จากโหนดหนึ่งไปอีกโหนดหนึ่ง
Adjacency Matrix
0 : ไม่เป็นแอดจาเซนซีกัน
1 : เป็นแอดจาเซนซีกัน
การท่องไปในกราฟ
เป็นการไปเยือนโหนดในกราฟ ซึ่งแต่ละโหนดจะถูกเยือนเพียงครั้งเดียว แต่กราฟนั้นมาหลายเส้นทางเมื่อเยือนแล้วต้องทำเครื่องหมายว่าได้เยือนเรียบร้อย การท่องไปในกราฟมี 2 แบบ คือ
1.การท่องแบบกว้าง เป็นการกำหนดโหนดที่จะเยือนหรือโหนดเริ่มต้นแล้วทำการเยือนไปยังโหนดที่ใกล้เคียงจนกระทั่งครบทุกโหนด
2.การท่องแบบลึก โดยกำหนดเริ่มต้นที่โหนดแรกแล้วเยือนโหนดถัดไปตามแนววิถีจนถึงปลายวิถี แล้วย้อนกลับมาเพื่อเยือนโหนดอื่นๆ
ไม่มีความคิดเห็น:
แสดงความคิดเห็น