ทรี (Tree) เป็นโครงสร้างข้อมูลที่มีความสัมพันธ์ระหว่าง
โหนดจะมีความสัมพันธ์ ลดหลั่นกันเป็นลำดับชั้นได้มีการ
นำรูปแบบทรีไปประยุกต์ใช้ในงานต่างๆอย่างแพร่หลาย
ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมูล
เช่นแผนผังองค์ประกอบของหน่วยงานต่างๆโครงสร้างสาร
บัญหนังสือเป็นต้น
การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญในไบนารีทรีคือการท่องไปในไบนารีทรี
(Traversing Binary Tree) เพื่อเข้าไปเยือนทุกๆโหนดใน
ทรีซึ่ง วิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน
กันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการเยือน
อย่างไรโหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)
ทรีย่อยทางซ้าย(แทนด้วย L) หรือทรีย่อยทางขวา
(แทนด้วย R)มีวิธีการท่องเข้าไปในทรี 6 วิธีคือ NLR LNR
LRN NRL RNL และ RLN แต่ วิธีการท่องเข้าไปไบนารีทรี
ที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา3
แบบแรกเท่านั้นคือNLR LNR และLRN
ซึ่งลักษณะการนิยามเป็นนิยามแบบรีเคอร์ซีฟมีดังนี้
1. การท่องไปแบบพรีออร์เดอร์
เป็นการเดินเข้าไปเยือนโหนดต่างๆในทรีด้วยวิธีNLR
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่างๆในทรีด้วยวิธี LNR
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์(Postorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่างๆในทรีด้วยวิธี LRN
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
(3) เยือนโหนดราก
Graph
การท่องไปในกราฟ
1. การค้นหาแบบกว้าง (Breadth-first Search)
2. การค้นหาแบบลึก (Depth-first Search)
กราฟมีน้ำหนักหมายถึงกราฟที่ทุกเอดจ์มีค่าน้ำหนักกำกับ
ซึ่งค่าน้ำหนักอาจสื่อถึงระยะทางเวลาค่าใช้จ่ายเป็นต้นนิยม
นำไปใช้แก้ปัญหาหลักๆ 2 ปัญหาคือ
1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด
(Minimum Spanning Trees :MST)
2. การหาเส้นทางที่สั้นที่สุด(Shortest path)
sorting
การเรียงลำดับแบบเร็ว (quick sort)
เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะสำหรับข้อมูล
ที่มีจำนวนมากที่ต้องการความรวดเร็วในการทำงานวิธีนี้
จะเลือกข้อมูลจากกลุ่มข้อมูลขึ้นมาหนึ่งค่าเป็นค่าหลัก
แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้เมื่อได้ตำแหน่ง
ที่ถูกต้องแล้วใช้ค่าหลักนี้เป็นหลักในการแบ่งข้อมูลออก
เป็นสองส่วนถ้าเป็นการเรียงลำดับจากน้อยไปมากส่วนแรก
อยู่ในตอนหน้าข้อมูลทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็น
ตัวแบ่งส่วน
การค้นหาข้อมูล (Searching)
การค้นหาคือการใช้วิธีการค้นหากับโครงสร้างข้อมูลเพื่อ
ดูว่าข้อมูลตัวที่ต้องการถูกเก็บอยู่ในโครงสร้างแล้วหรือยัง
วัตถุประสงค์ของการค้นหาโดยทั่วไปได้แก่
เพื่อดูรายละเอียดเฉพาะข้อมูลส่วนที่ต้องการดึงข้อมูลตัว
ที่ค้นหาออกจากโครงสร้างเปลี่ยนแปลงแก้ไขรายละเอียด
บางอย่างของข้อมูลตัวที่ค้นพบและ/หรือ
เพิ่มข้อมูลตัวที่ค้นหาแล้วพบว่ายังไม่เคยเก็บไว้ในโครงสร้าง
เลยเข้าไปเก็บไว้ในโครงสร้างเพื่อใช้งานต่อไป
การค้นหาคือแบ่งเป็น 2 ประเภท
ตามแหล่งที่จัดเก็บข้อมูลเช่นเดียวกับการเรียงลำดับ
1. การค้นหาข้อมูลแบบภายใน (Internal Searching)
2. การค้นหาข้อมูลแบบภายนอก (External Searching)
DTS: 11-20-09-2552
ไม่มีความคิดเห็น:
แสดงความคิดเห็น