สรุปเรืื่อง Summary (ต่อจากสัปดาห์ที่แล้ว)

DTS:11-16-09-2552

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

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

กรณีที่ดีที่สุด คือ กรณีที่ค่าหลักที่เลือกแบ่งแล้วข้อมูลอยู่ตรงกลางกลุ่มพอดี และในแต่ละส่วนย่อยก็เช่นเดียวกันจำนวนครั้งของการเปรียบเทียบเป็นดังนี้จำนวนครั้งของการเปรียบเทียบ = n log2 n ครั้ง

กรณีที่แย่ที่สุด คือ กรณีที่ข้อมูลมีการเรียงลำดับอยู่แล้ว อาจจะเรียงจากน้อยไปมากหรือจากมากไปน้อย หรือค่าหลักที่เลือกในแต่ละครั้งเป็นค่าหลักที่น้อยที่สุดหรือมากที่สุด จำนวนครั้งของการเปรียบเทียบจะมากที่สุดดังนี้จำนวนครั้งของการเปรียบเทียบ
= (n −1) + (n −2) + . . . + 3 + 2 + 1
= n (n −1) / 2 ครั้ง


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

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

วัตถุประสงค์ของการค้นหาโดยทั่วไป ได้แก่

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

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

การค้นหาข้อมูลแบบภายใน(Internal Searching)
การค้นหาข้อมูลแบบภายนอก(External Searching)


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

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

3. การค้นหาแบบไบนารี(Binary Search)ใช้กับข้อมูลที่ถูกจัดเรียงแล้วเท่านั้นหลักการของการค้นหาคือ ข้อมูลถูกแบ่งออกเป็นสองส่วนแล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา
1.หาตัวแทนข้อมูลเพื่อนำมาเปรียบเทียบกับค่าที่ต้องการค้นตำแหน่งตัวแทนข้อมูลหาได้จากสูตร
mid = (low+high)/2
mid คือ ตำแหน่งกลาง ,
low คือ ตำแหน่งต้นแถวลำดับ
high คือ ตำแหน่งท้ายของแถวลำดับ

2. นำผลการเปรียบเทียบกรณีที่หาไม่พบมาใช้ในการค้นหารอบต่อไป
ถ้าข้อมูลมีการเรียงจากน้อยไปหามากเมื่อเปรียบเทียบแล้วคีย์มีค่ามากกว่าค่ากลาง แสดงว่าต้องทำการค้นหาข้อมูลในครึ่งหลังต่อไป จากนั้นนำข้อมูลครึ่งหลังมาหาค่ากลางต่อ ทำอย่างนี้ไปเรื่อย ๆ จนกว่าจะได้ข้อมูลที่ต้องการ

สรุปเรื่อง Sorting และ เรื่อง Summary

DTS:10-09-09-2552


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

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

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

วิธีการเรียงลำดับสามารถแบ่งออกเป็น 2 ประเภทคือ

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

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

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

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

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

รอบที่ 1 เปรียบเทียบเท่ากับ n −1 ครั้ง
รอบที่ 2 เปรียบเทียบเท่ากับ n – 2 ครั้ง
รอบที่ n – 1 เปรียบเทียบเท่ากับ 1 ครั้ง

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

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

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

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

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

การเรียงลำดับแบบฐาน (radix sort)เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก

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

เรื่อง Summary

ทรี(Tree)เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่างโหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship)ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงานต่างๆอย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมูลแต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลายๆโหนดเรียกโหนดดังกล่าวว่าโหนดแม่ (Parent orMother Node)โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่าโหนดลูก(Child or Son Node)โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหนดราก (Root Node) โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน เรียกว่า โหนดพี่น้อง (Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (LeaveNode)เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง (Branch)

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

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

วิธีการท่องเข้าไปไบนารีทรี:ที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา เท่านั้นคือ NLR LNR และ LR

ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบดังนี้

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

(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์

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

(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์

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

การท่องไปในกราฟ
1.การค้นหาแบบกว้างในกราฟไม่มีทิศทางรายชื่อโหนดที่พบจากการค้นหาแบบกว้างมีได้หลายรายการขึ้นกับลำดับการเรียงโหนดประชิด

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

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

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

LECTURE9

DTS:09-02-09-2552

เรื่อง TREE (ต่อจากสัปดาห์ที่แล้ว) และเรื่อง Graph

เอ็กซ์เพรสชันทรี (Expression Tree)

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

- ฟังก์ชัน
- วงเล็บ
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน (unary)
- คูณ หรือ หาร
- บวก หรือ ลบ
- ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา

ไบนารีเซิร์ชทรี (Binary Search Tree)

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

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

(1)การเพิ่มโหนดในไบนารีเซิร์ชทรี

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

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

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

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

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

เรื่อง Graph

นิยามของกราฟ

กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ

(1) โหนด (Nodes) หรือ เวอร์เทกซ์(Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)

-กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนดถ้าเอ็จไม่มีลำดับความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง (Undirected Graphs)และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง(Directed Graphs)บางครั้งเรียกว่า ไดกราฟ (Digraph)ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้

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

กราฟแบบไม่มีทิศทาง

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

กราฟแบบมีทิศทาง

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

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

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

การท่องไปในกราฟ (graph traversal) คือ

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

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

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