DTS : 11-16/09/2552

Summary B4 Final

ทรี (Tree)

เป็นโครงสร้างข้อมูลที่มีความสัมพันธ์ระหว่างโหนด จะมีความสัมพันธ์เป็นขั้น ส่วนมากจะนำไปประยุกต์ใช้งานสำหรับแสดงความสัมพันธ์ระหว่างข้อมูล เช่น แผนผังองค์ประกอบของหน่วยงานต่างๆ โครงสร้างสารบัญหนังสือ เป็นต้น

การท่องไปในไบนารีทรี

วิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบ สามารถเยือนโหนดได้โหนดละหนึ่งครั้ง วิธีการท่องเข้าไปในทรีมี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่ที่นิยมใช้กันคือ 3 วิธีแรก ซึ่งขั้นตอนการท่องไปแต่ละแบบ มีดังนี้
1. การท่องไปแบบพรีออร์เดอร์(Preorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
- เยือนโหนดราก
- ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
- ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่างๆในทรีด้วยวิธี LNR มีขั้นตอนการเดินดังต่อไปนี้
- ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
- เยือนโหนดราก

- ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์(Postorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่างๆในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
- ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
- ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
- เยือนโหนดราก

ไบนารีเซิร์ชทรี (Binary Search Tree)
เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุกๆโหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน

กราฟ (Graph)

มีการเปลี่ยนงแปลงตลอดเวลา จึงใช้วิธีแอดจาเซนซีลิสต์ เป็นวิธีคล้ายการจัดเก็บกราฟด้วยโหนดและพอยน์เตอร์ ต่างกันตรงที่ใช้ลิงค์ลิสต์แทน เพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข

การท่องไปในกราฟ
1. การค้นหาแบบกว้าง(Breadth-first Search) ในกราฟแบบไม่มีทิศทาง รายชื่อโหนดที่พบจากการค้นหา มีได้หลายรายการขึ้นกับลำดับการเรียงโหนดประชิด ในกราฟแบบมีทิศทาง การค้นหาโหนดทำได้ง่ายขึ้นถ้าใช้คิวเก็บลำดับของโหนดประชิดที่ต้องเยี่ยมต่อไป
2. การค้นหาแบบลึก (Depth-first Search)

กราฟมีน้ำหนัก หมายถึง กราฟที่ทุกเอดจ์มีค่าน้ำหนักกำกับ ซึ่งค่าน้ำหนักอาจสื่อถึงระยะทาง เวลา ค่าใช้จ่าย เป็นต้น

Sorting
การเรียงลำดับแบบเร็ว (quick sort)
เป็นวิธีที่ใช้เวลาน้อย เหมาะสำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรววดเร็วในการทำงาน วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูลขึ้นมาหนึ่งค่าเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ จากนั้นแบ่งข้อมูลจากค่าหลักออกเป็นสองส่วน ถ้าเป็นการเรียงลำดับจากน้อยไปหามาก ส่วนแรกอยู่ตอนหน้าของข้อมูล ทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่งส่วน อีกส่วนจะอยู่ตอนหลังของข้อมูล จะมีค่ามากกว่าค่าหลัก นำแต่ละส่วนย่อยไปแบ่งย่อยในลักษณะเดียวกันต่อไป จนกระทั่งไม่สามารถแบ่งส่วนย่อยได้อีก ถ้าเป็นการเรียงลำดับจากมากไปหาน้อยการเปรียบเทียบเพื่อหาตำแหน่งให้กับค่าหลักตัวแรกเริ่มจากข้อมูลในตำแหน่งแรกหรือสุดท้ายก็ได้ ถ้าให้ตำแหน่งที่ 1 เป็นค่าหลัก พิจารณาเปรียบเทียบค่าหลักกับข้อมูลในตำแหน่งสุดท้าย ถ้าค่าหลักมีค่าน้อยกว่าให้เปรียบเทียบข้อมูลในตำแหน่งรองสุดท้ายไปเรื่อยๆจนกว่าจะพบค่าน้อยกว่าค่าหลัก แล้วสลับตำแหน่งกัน เมื่อสลับตำแหน่งแล้วนำค่าหลักมาเปรียบเทียบกับข้อมูลในตำแหน่งที่ 2, 3 ไปเรื่อยๆจนกว่าจะพบ่าที่มีมากกว่าค่าหลัก ทำเช่นนี้ไปเรื่อยๆจนกว่าจะได้ตำแหน่งที่ถูกต้อง จากนั้นแบ่งข้อมูลออกเป็นสองส่วน ส่วนแรกข้อมูลทั้งหมดจะมีค่าน้อยกว่าค่าหลัก และส่วนที่สองข้อมูลทั้งหมดจะมีค่ามากกว่าค่าหลัก

การค้นหาข้อมูล (Searching)

คือ การใช้วิธีการค้นหาโครงสร้างข้อมูล เพื่อดูว่าข้อมูลที่ต้องการถูกเก็บในโครงสร้างแล้วหรือยัง การค้นหาข้อมูลทำเพื่อดูรายละเอียดเฉพาะข้อมูลส่วนที่ต้องการ ดึงข้อมูลที่ค้นหาออกจากโครงสร้าง เปลี่ยนแปลงแก้ไขรายละเอียดข้อมูลตัวที่ค้นพบ หรือเพิ่มข้อมูลตัวที่ค้นพบแล้วพบว่ายังไม่เคยเก็บไว้ในโครงสร้างเลยเข้าไปเก็บไว้ในโครงต่อไป

วิธีการค้นหาข้อมูล
1. การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ(Linear) เป็นวิธีที่ใช้กับข้อมูลที่ยังไม่ได้เรียงลำดับ วิธีการ คือ นำข้อมูลที่จะหามาเปรียบเทียบกับข้อมูลลูกค้าแรกในแถวลำดับ ถ้าไม่เท่ากันให้เปรียบเทียบข้อมูลถัดไป ถ้าเท่ากันให้หยุดค้นหา
2. การค้นหาแบบเซนทินัล(Sentinel) เป็นวิธีที่การค้นหาแบบเดียวกับวิธีการค้นหาแบบเชิงเส้นแต่ประสิทธิภาพดีกว่าตรงที่เปรียบเทียบน้อยครั้งกว่า วิธีการ คือ

- เพิ่มขนาดของแถวลำดับ ที่ใช้เก็บข้อมูลอีก 1 ที่
- นำข้อมูลที่จะใช้ค้นหาข้อมูลใน Array ไปฝากที่ต้นหรือ ท้าย Array
- ตรวจสอบผลลัพธ์จากการหา โดยตรวจสอบจากตำแหน่งที่พบ ถ้าตำแหน่งที่พบมีค่าเท่ากับ n-1แสดงว่าหาไม่พบ นอกนั้นถือว่าพบข้อมูลที่ค้าหา
3. การค้นหาแบบไบนารี(Binary Search) การค้นหาแบบไบนารีใช้กับข้อมูลที่ถูกจัดเรียงแล้วเท่านั้น วิธีการ คือ ข้อมูลถูกแบ่งออกเป็นสองส่วน แล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา

- หาตัวแทนข้อมูลเพื่อนำมาเปรียบเทียบกับค่าที่ต้องการค้นตำแหน่งตัวแทน หาได้จากสูตร

mid = (low+high)/2
mid คือ ตำแหน่งกลาง ,low คือ ตำแหน่งต้นแถวลำดับ
high คือ ตำแหน่งท้ายของแถวลำดับ

- นำผลการเปรียบเทียบ กรณีที่หาไม่พบมาใช้ในการค้นหารอบต่อไป