DTS 11-16-09-2552

สรุปเรื่อง Searching (การค้นหาข้อมูล)

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

การค้นหาข้อมูลแบ่งได้เป็น 2 ประเภท คือ
1 การค้นหาข้อมูลแบบภายใน
2 การค้นหาข้อมูลแบบภายนอก

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

การค้นหาแบบเซนทินัล
เป็นวิธีการค้นหาแบบเดียวกับวิธีการค้นหาแบบ
เชิงส้นแต่ประสิทธิภาพดีกว่าตรงที่เปรียบเทียบ
น้อยครั้งกว่า พัฒนามาจากอัลกอริทึมแบบเชิงเส้น

การค้นหาแบบไบนารี
การค้นหาแบบไบนารีกับข้อมูลที่ ถูกจัดเรียงแล้วเท่านั้น
ถ้าข้อมูลมีการเรียงลำดับจากน้อยไปหามาก
เมื่อเปรียบเทียบแล้วคีย์มีค่ามากกว่าค่ากลาง
แสดงว่าต้องการทำการค้นหาข้อมูลในครั้งหลังต่อไป
จากนั้นนำข้อมูลครั้งหลังมาหาค่ากลางต่อ
ทำอย่างนี้ไปเรื่อย ๆ จนกว่าจะได้ข้อมูลที่ต้องการ
เช่นต้องการหาว่า 12 อยู่ในลิสต์
(1 4 6 8 10 12 18 19) หรือไม่

DTS 10-09-09-2552

สรุปเรื่อง Graph (ต่อ) และ Sorting

การท่องไปในกราฟ
อัลกอริทึมแบบลึก มีดังนี้
1 push โหนดเริ่มต้นไปเก็บในสแตก
และปรับ top ให้ชี้ที่ตำแหน่งโหนดเริ่มต้น
2 pop สมาชิกใหม่ออกจากสแตก 1 จำนวน
ปรับค่า pop ใหม่ดังนี้ top=top-1
3 push โหนดประชิดทั้งหมด ของโหนดที่
pop ครั้งสุดท้ายลงสแตกกำหนดโหนดที่จะ
push นั้นต้องไม่เคย push ไปเก็บในสแตกมาก่อน
และปรับค่า top ใหม่ดังนี้
top=top+จำนวนโหนดประชิดที่ push ลงในสแตก
4 ตรวจสอบสแตกถ้ามีข้อมูลให้ไปทำที่ข้อ 2
5 เลิกงาน

การท่องไปในกราฟ
อัลกอริทึมแบบกว้าง มีดังนี้
1 นำโหนดเริ่มต้นไปเก็บในคิว และปรับค่า front
และ rear=1
2 นำสมาชิกออกจากคิว 1 จำนวนและปรับค่า
front ใหม่ดังนี้ front=front+1
3 นำโหนดประชิดทั้งหมด ของโหนดที่ตำแหน่ง
front ไปเก็บในคิว โดยโหนดที่จะเข้าคิวนั้นต้องไม่เคย
ไปเก็บในคิวมาก่อน และปรับค่า rear ใหม่ดังนี้
rear=rear+จำนวนโหนดประชิดที่เก็บในคิว
4 ตรวจสอบคิว ถ้ามีข้อมูล ให้ไปทำข้อ 2
5 เลิกงาน

กราฟมีน้ำหนัก หมายถึง กราฟที่ทุกเอดจ์
มีค่าน้ำหนักกำกับ นิยมนำไปใช้แก้ปัญหา
หลัก ๆ 2 ปัญหา คือ
1 การสร้างต้นไม้ทอดข้ามน้อยที่สุด
2 การหาเส้นทางที่สั้นที่สุด

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

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

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

DTS 09-02-09-2552

สรุปเรื่อง ทรี Tree (ต่อ) และเรื่อง กราฟ Graph

การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญของในไบนารีทรี คือ
การท่องไปในไบนารีทรีเพื่อเข้าไปเยือนทุก ๆ
โหนดในทรี
ขั้นตอนการเยือนอย่างไรของโหนดที่ถูกเยือน
อาจเป็นโหนดแม่(แทนด้วย N)
ทรีย่อยทางซ้าย(แทนด้วย L)
หรือทรีย่อยทางขวา (แทนด้วย R)

1 การท่องไปแบบพรีออร์เดอร์
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
1 เยือนโหนดราก
2 ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
3 ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์

2 การท่องไปแบบอินออร์เดอร์
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LNR มีขั้นตอนการเดินดังต่อไปนี้
1 ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
2 เยือนโหนดราก
3 ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์

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

เอ็กซ์เพรสชั่นทรี (Expression Tree)
เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์
โดยแต่ละโหนดจะเก็บตัวดำเนินการ (Operator)
และตัวถูกดำเนินการ (Operand)
ซึ่งตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบ
ส่วนตัวดำเนินการจะเก็บอยู่ที่โหนดกิ่ง
แต่ต้องคำนึงถึงความสำคัญของเครื่องหมายตามลำดับด้วย คือ
-ฟังก์ชั่น
-วงเล็บ
-ยกกำลัง
-เครื่องหมายหน้าเลขจำนวน (unary)
-คูณ หรือ หาร
-บวก หรือ ลบ
-ถ้ามีเครื่องหมายที่ระดับเดียวกัน
ให้ทำจากซ้ายไปขวา

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

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

Graph (กราฟ)

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

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

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

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

DTS 08-26-08-2552

สรุปเรื่อง Tree

ทรี หรือจะเรียกกันอีกอย่างว่าโครงสร้างต้นไม้
เป็นอีกโครงสร้างที่มีความสัมพันธ์กัน
จะประกอบไปด้วยโหนด (Node)
แต่ละโหนดจะมีความสัมพันธ์กัน
และยังสามารถแตกโหนดออกมาเป็นโหนดย่อยๆ
ได้อีกหลายโหนดด้วยกันเรียกว่าโหนดลูก
เมื่อเรามีโหนดลูกแล้วก้อยังสามารถ
แตกโหนดออกไปเป็นโหนดพ่อโหนดแม่ได้อีก

ชนิดของทรี จะแบ่งออกได้2ชนิดคือ
1 ทรีทั่วไป
2 ไบนารี่ทรี

ในแต่ละโหนดที่มีโหนดแม่เป็นโหนดเดียวกันนั้น
เรียกว่า โหนดพี่น้อง (Siblings)
โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ
และเส้นที่แสดงความสัมพันธ์กันระหว่างโหนดสองโหนด
เรียกว่า กิ่ง

ระดับของโหนดคือ

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

ไบนารี่ทรีทุกๆโหนดมีทรีย่อยทั้งทางซ้ายและทางขวา
ยกเว้นโหนดใบ และโหนดใบทุกโหนดจะต้องอยู่ในระดับ
เดียวกัน เรียกว่า ไบนารี่ทรีแบบสมบูรณ์

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

1 ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต
แล้วลบความสัมพันธ์ ระหว่างโหนดแม่
และโหนดลูกอื่นๆ
2 ให้มีความเชื่อมความสัมพันธ์กันระหว่างโหนดพี่น้อง
3 จับให้ทรีย่อยทางขวาเอียงลงมา 45องศา

การท่องไปในไบนารี่ทรีมีด้วยกัน3แบบคือ

1 การท่องไปแบบพรีออร์เดอร์
เป็นการเดินเข้าไปเยือนในโหนดต่างๆ
ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
1 เยือนโหนดราก
2 ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
3 ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์

2 การท่องไปแบบอินออร์เดอร์
เป็นการเดินเข้าไปเยือนโหนดต่างๆ
ในทรีด้วยวิธี LNR
มีขั้นตอนการเดินดังต่อไปนี้
1 ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
2 เยือนโหนดราก
3 ท่องไปในทรีย่อยทางขวาแบบอืนออร์เดรอ์

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

*********