Summary

Tree

ทรี (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

เรื่อง Sorting

การเรียงลำดับ (Sorting)

การเรียงลำดับ - เป็นการจัดให้เป็นระเบียบมีแบบแผน

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

การเรียงลำดับอย่างมีประสิทธิภาพ

หลักเกณฑ์ในการพิจารณาเพื่อเลือกวิธีการเรียงลำดับ
ที่ดีและเหมาะสมกับระบบงานเพื่อให้ประสิทธิภาพใน
การทำงานสูงสุดควรจะต้องคำนึงถึงสิ่งต่างๆดังต่อไปนี้

(1) เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม
(2) เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตาม
โปรแกรมที่เขียน
(3) จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่

วิธีการเรียงลำดับ

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


(1)การเรียงลำดับแบบภายใน (internal sorting)

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

(2) การเรียงลำดับแบบภายนอก(external sorting)

เป็นการเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรองซึ่ง
เป็นการเรียงลำดับข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ในการ
เรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่างการถ่ายเทข้อมูล
จากหน่วยความจำหลักและหน่วยความจำสำรองนอกเหนือจาก
เวลาที่ใช้ในการเรียงลำดับข้อมูลแบบภายใน

การเรียงลำดับแบบเลือก (selection sort)

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

1. ในรอบแรกจะทำการค้นหาข้อมูล
ตัวที่มีค่าน้อยที่สุดมาเก็บไว้ที่ตำแหน่งที่ 1
2. ในรอบที่สองนำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บไว้ที่
ตำแหน่งที่สอง
3. ทำเช่นนี้ไปเรื่อยๆจนกระทั่งครบทุกค่าในที่สุดจะได้ข้อมูล
เรียงลำดับจากน้อยไปมากตามที่ต้องการ




การเรียงลำดับแบบฟอง (Bubble Sort)

เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลใน
ตำแหน่งที่อยู่ติดกัน1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับ
ที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน2. ถ้าเป็นการเรียง
ลำดับจากน้อยไปมากให้นำข้อมูลตัวที่มีค่าน้อยกว่าอยู่
ในตำแหน่งก่อนข้อมูลที่มีค่ามากถ้าเป็นการเรียงลำดับ
จากมากไปน้อยให้นำข้อมูลตัวที่มีค่ามากกว่าอยู่ใน
ตำแหน่งก่อนข้อมูลที่มีค่าน้อย

การจัดเรียงลำดับแบบฟองเป็นวิธีที่ไม่ซับซ้อนมากนัก

เป็นวิธีการเรียงลำดับที่นิยมใช้กันมากเพราะมีรูปแบบที่

เข้าใจง่ายแต่ประสิทธิภาพการทำงานค่อนข้างต่ำพอๆ

กับการเรียงลำดับแบบเลือกในหัวข้อที่ผ่านมาถ้ามีจำนวน

ข้อมูลทั้งหมด n ตัวไม่ว่าข้อมูลจะเป็นอย่างไรก็ตามต้อง

ทำการเปรียบเทียบทั้งหมด n .1 รอบและจำนวนครั้งของ

การเปรียบเทียบในแต่ละรอบเป็นดังนี้

การเรียงลำดับแบบเร็ว (quick sort)

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


การเรียงลำดับแบบแทรก (insertion sort)

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





การเรียงลำดับแบบฐาน (radix sort)

เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก
1. เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อนนั่นคือถ้าข้อมูล
เป็นเลขจำนวนเต็มจะพิจารณาหลักหน่วยก่อน
2. การจัดเรียงจะนำข้อมูลเข้ามาทีละตัวแล้วนำไปเก็บไว้ที่
ซึ่งจัดไว้สำหรับค่านั้นเป็นกลุ่มๆตามลำดับการเข้ามา






DTS : 10-13-08-2552

เรื่อง Graph

Graph

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

นิยามของกราฟ
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ
ด้วยกลุ่มของสิ่งสองสิ่ง คือ
(1) โหนด (Nodes) หรือเวอร์เทกช์ (Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็ก (Edges)


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




กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและ
เอ็จโดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง
(Empty Graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด
หรือเชื่อมตัวเองเอ็จไม่มีทิศทางกำกับลำดับของการเชื่อมต่อ
กันไม่สำคัญนั่นคือไม่มีโหนดใดเป็นโหนดแรก (First Node)
หรือไม่มีโหนดเริ่มต้นและไม่มีโหนดใดเป็นโหนดสิ้นสุด



การแทนกราฟในหน่วยความจำ

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

การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal) คือ
กระบวนการเขื้โดยมีกในการเข้าไปเยือน

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


1. การท่องแบบกว้าง (Breadth First Traversal)
วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้นต่อมาให้เยือน
โหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่ง
เยือนหมดทุกโหนดในกราฟ

2. การท่องแบบลึก (Depth First Traversal)

การทำงานคล้ายกับการท่องทีละระดับของทรีโดย

กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตาม

แนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้นจากนั้นย้อนกลับ
(backtrack) ตามแนววิถีเดิมนั้นจนกระทั่งสามารถดำเนิน

การต่อเนื่องเข้าสู่แนววิถีอื่นๆเพื่อเยือนโหนดอื่นๆต่อไป

จนครบทุกโหนด

DTS : 09-13-08-2552