โครงสร้างข้อมูลแบบ Tree
Defination of a Tree Structure
ทรี หรือโครงสร้างข้อมูลแบบต้นไม้ ประกอบด้วยโหนด (node) ซึ่งเป็นส่วนที่เก็บข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก
Root Node จากรูป คือ โหนด A
Parent Node หรือโหนดพ่อแม่ โหนด B ที่เป็นโหนดลูกของโหนด A ก็สามารถแตกออกเป็นโหนดย่อยๆ ได้แก่ F และ G ดังนั้น B จึงเป็นโหนดพ่อแม่ของ F และ G ในทำนองเดียวกัน A ก็เป็นโหนด พ่อแม่ของ B , C , D และ E
กิ่ง (Branch or Edge) เป็นเส้นที่เชื่อมต่อระหว่างโหนดพ่อแม่กับโหนดลูก
Brother Node หรือโหนดพี่น้อง คือ โหนดที่มีพ่อแม่เดียวกัน เช่น B , C , D , E เป็นโหนดพี่น้องกันเพราะมีโหนดพ่อแม่เดียวกัน คือ โหนด A และ F และ G เป็นโหนดพี่น้องกันโดยมี B เป็นโหนดพ่อแม่
Leaf Node คือ โหนดที่ไม่มีโหนดลูก จากรูปโหนดที่ไม่มีโหนดลูก ได้แก่ F G H I J K L M
Branch Node คือ โหนดที่ไม่ใช่ Leaf Node เช่น โหนด B C D E เรียกว่า Branch Node
Degree คือ จำนวนลูกของโหนด x เช่น degree ของ โหนด A = 4 ได้แก่ B C D E จำนวน degree ของโหนด B = 2 จำนวนdegree ของโหนด F = 0 เนื่องจากโหนด F ไม่มีโหนดลูก
Direct Descendant Node คือโหนดที่มาทีหลังทันที จากรูป B C D E เป็น direct descendant node ของโหนด A เพราะเป็นโหนดที่มาทีหลังทันที
Descendant Node คือ โหนดลูกของโหนด x และโหนดที่ทุกโหนดที่แตกจากโหนดลูกของโหนด x ตัวอย่าง descendant ของโหนด A คือ ทุกโหนดที่เหลือในทรี
Direct Ancestor Node หรือโหนดที่มาก่อนทันที ตัวอย่าง Direct Ancestor ของโหนด H คือ โหนด C , Direct Ancestor ของโหนด C คือ โหนด A
Level หรือระดับ คือ หมายเลขแสดงระดับของโหนดในทรี ซึ่งรูทโหนดจะมีค่า Level = 0 ส่วนโหนดลูกของรูทโหนดก็จะมีค่า = 1 หากค่าโหนด x อยู่ในระดับ L โหนดลูกของ x ก็จะอยู่ในระดับ L + 1
Binary Tree
Binary Tree มีลักษณะเหมือนกับ Tree ปกติแต่มีคุณสมบัติพิเศษ คือ “แต่ละโหนดจะมีโหนดลูกได้ไม่เกิน 2 โหนด” หรือพูดอีกนัยหนึ่งก็คือ แต่ละโหนดใน binary tree จะมีดีกรีได้ไม่เกิน 2
ตัวอย่าง binary tree
Complete Binary Tree
Complete Binary Tree หรือต้นไม้ไบนารีแบบสมบูรณ์ มีลักษณะคล้ายกับ Binary Tree แต่มีข้อพิเศษ คือ
1. ทุกโหนดที่ไม่ใช่ Leaf Node จะต้องมีโหนดลูก 2 โหนด
2. Leaf Node จะต้องอยู่ในระดับเดียวกัน
ตัวอย่างแสดง Complete Binary Tree
Binary Search Tree
Binary Search Tree มีลักษณะคล้ายกับ Binary Tree แต่มีลักษณะพิเศษเพิ่มเติม คือ
ค่าของรูทโหนดมีค่ามากกว่าค่าในต้นไม้ย่อยซ้าย ( TL < R )
ค่าของรูทโหนดมีค่าน้อยกว่าหรือเท่ากับค่าในต้นไม้ย่อยขวา ( R <= TR )
ตัวอย่าง Binary Search Tree
การสร้างและเพิ่มข้อมูลใน Binary Search Tree
วิธีการสร้างและเพิ่มข้อมูลเริ่มจาก
1. ถ้า Binary Search Tree ยังไม่มีข้อมูล ให้โหนดที่เข้ามาใหม่เป็นรูทโหนดของ Binary Search Tree
2. ถ้า Binary Search Tree มีข้อมูลอยู่ ให้เพิ่มโหนดที่เข้ามาดังนี้
2.1 ถ้าค่าของโหนดใหม่ที่เข้ามา มากกว่า ค่าของรูทโหนด ให้เพิ่มโหนดใหม่ลงในต้นไม้ย่อยด้านขวา
2.2 ถ้าค่าของโหนดใหม่ที่เข้ามา น้อยกว่า ค่าของรูทโหนด ให้เพิ่มโหนดใหม่ลงในต้นไม้ย่อยด้านซ้าย
ตัวอย่างการสร้างและเพิ่มข้อมูล Binary Search Tree
มีค่าข้อมูลดังนี้ 12 , 9 , 2 , 18 , 23 , 11 , 14
การลบข้อมูลใน Binary Search Tree
กรณีที่ 1 หากโหนดที่ต้องการลบเป็น Leaf Node สามารถลบได้ทันที
กรณีที่2 ถ้าโหนดที่ต้องการลบมีต้นไม้ย่อยเพียงด้านเดียว เมื่อลบโหนดที่ไม่ต้องการทิ้งแล้ว ให้นำค่ารูทโหนดของต้นไม้ย่อยไปแทนที่โหนดที่ลบทิ้งไป
กรณีที่3 ถ้าโหนดที่ต้องการลบมีต้นไม้ย่อยทั้งสองด้าน เมื่อลบโหนดที่ไม่ต้องการแล้ว มีวิธีให้เลือกทำอยู่ 3 วิธี คือ
1. นำค่าที่น้อยที่สุดของต้นไม้ย่อยขวาไปแทนที่โหนดที่ลบทิ้งไป
2. นำค่าที่มากที่สุดของต้นไม้ย่อยซ้ายไปแทนที่โหนดที่ลบทิ้งไป
3. นำค่ารูทโหนดของต้นไม้ย่อยขวาไปแทนที่โหนดที่ลบทิ้งไป แล้วนำค่ารูทโหนดของต้นไม้ย่อยซ้ายไปเป็นโหนดลูกทางซ้ายของโหนดที่มีค่าน้อยที่สุดของต้นไม้ย่อยขวา
การท่องไปในทรี (Tree Traversal)
สามารถท่องเข้าไปในทรีเพื่อดูข้อมูล ได้ 3 วิธีด้วยกันคือ
1. Preorder
2. Inorder
3. Postorder
ในการท่องเข้าไปในทรีแต่ละแบบจะใช้สัญลักษณ์ดังนี้
Root = root node Left = ต้นไม้ย่อยซ้ายของ Root Right = ต้นไม้ย่อยขวาของ Root
วิธีในการท่องเข้าไปในทรีแต่ละแบบจะมีลักษณะดังนี้
1. Preorder = Root Left Right
2. Inorder = Left Root Right
3. Postorder = Left Right Root
โครงสร้างข้อมูลแบบกราฟ (Graphs)
โครงสร้างข้อมูลแบบกราฟ (Graphs)
โครงสร้างข้อมูลกราฟ กราฟ (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) หมายถึง โหนดที่มีการเชื่อมโยงกัน
ตัวอย่างของกราฟในชีวิตประจำวัน เช่น กราฟของการเดินทางระหว่างเมือง ซึ่ง vertex คือ กลุ่มของเมืองต่างๆ และ edge คือ เส้นทางเดินระหว่างเมือง หรือ ในเครือข่ายคอมพิวเตอร์ (Computer Network) vertex ก็คือ กลุ่มของเครื่องคอมพิวเตอร์ หรือโหนดต่างๆ และ edge ก็คือ เส้นทางการติดต่อสื่อสารระหว่างโหนดต่างๆ เป็นต้น
ประเภทของกราฟ
แบ่งเป็น 3 ประเภทโดยแบ่งตามประเภทของ edge ได้ดังนี้
1. Direct Graph (กราฟแสดงทิศทาง) เป็นกราฟที่แสดงเส้นเชื่อมระหว่าง vertex โดแสดงทิศทางของการเชื่อมต่อด้วย
เส้นทางคือการเดินทางจาก vertex หนึ่งไปยังอีก vertex หนึ่งที่ต้องการ โดยผ่าน edge ที่เชื่อมระหว่าง vertex
ความยาวของเส้นทาง (The length of path) คือ จำนวนของ edge ในเส้นทางเดินนั้น ว่ามีจำนวนเท่าไหร่ ในการเดินทางจาก vertex หนึ่ง ไปยังอีก vertex หนึ่ง ถ้าหากเส้นทางประกอบด้วย vertex จำนวน N ความยาวของเส้นทางจะเท่ากับ N-1
ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้
การแทนที่กราฟด้วยเมตริกซ์
โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้ โดยกราฟที่ประกอบด้วย vertex จำนวน N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N x N โดยค่าในเมตริกซ์จะประกอบด้วย ค่า 0 และ 1
ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง และ
ค่า 1 จะใช้แทนมี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง
ตัวอย่างจากรูปกราฟแบบ Direct Graph
จากการแทนที่กราฟด้วยเมตริกซ์ เราสามารถนำเมตริกซ์ที่ได้มาคำนวณหาจำนวนเส้นทางระหว่าง vertex ต้นทางและปลายทางที่มีจำนวน edge ต่างๆ ได้
ไม่มีความคิดเห็น:
แสดงความคิดเห็น