แฮช (Hash Table)

เนื้อหาการเรียนรู้

- ตารางการเข้าถึงข้อมูลแบบตรง
- ตารางแฮช
- การชนกันของข้อมูล
- การแก้ปัญหาการชนกันของข้อมูล
- วิธีการสร้างฟังก์ชันแฮช

จุดประสงค์การเรียนรู้

1. เพื่อให้นักศึกษาทราบถึงวิธีการเข้าถึงข้อมูลแบบตรง
2. เพื่อให้นักศึกษาทราบวิธีการสร้างฟังก์ชันแฮช
3. เพื่อให้นักศึกษาทราบวิธีการตรวจสอบข้อมูล
4. เพื่อให้นักศึกษาสามารถแก้ไขปัญหาการชนกันของข้อมูล
5. เพื่อให้นักศึกษาทราบวิธีการชนกันของข้อมูล

ตารางข้อมูลแบบตรง (Direct-address table)
สมมติว่ามีการกำหนดให้คีย์มาจากเอกภพสัมพัทธ์ U = {0,1,…,m-1} การแก้ไขปัญหาคือใช้ตาราง T[0..m-1] การสร้างดัชนีโดยคีย์ เพื่อใช้ในการ เชื่อมโยงข้อมูล เข้าด้วยกันเพื่อเก็บข้อมูลเข้าในตำแหน่งที่ถูกต้อง

เมื่อขนาดของเอกภพสัมพัทธ์เพิ่มมากขึ้น ตามหลักการยังคง สามารถทำงานได้ แต่ขนาดของตาราง T จะมีผลกระทบทางแก้ปัญหาคือต้องหาวิธีการจับคู่คีย์ให้มีช่วงกว้างที่เล็กลงโดยเรียกวิธีการนี้ว่า
ฟังก์ชันแฮช (Hash Function)
ผลลัพธ์ที่ได้เรียกว่า
ตารางแฮช (Hash Table)

การเข้าถึงข้อมูลโดยตรง กำหนด ให้ k เป็นคีย์ ถูกจัดเก็บอยู่ใน ช่อง k ด้วยการทำแฮชด้วยพื้นฐาน การจัดเก็บในช่องที่ h(k) โดย
ใช้ฟังก์ชัน h เพื่อคำนวณหาช่องของคีย์โดยการจับคู่กับเอกภพสัมพัทธ์U ในตาราง T
h: U 􀃆 {0,1,…,m-1}

ฟังก์ชัน แฮช จะทำงานแบบสุ่ม ตัวอย่างเช่น h(k) = k mod m เมื่อ m เป็นค่าหลัก (prime number) จำนวนช่อง (Slot)
แนวคิดการจัดเก็บ ค่าคีย์ของ k ในตำแหน่ง ที่ T[h(k)] เมื่อ k ∈ U , h(k) ∈ [0..m-1] แนวคิดหลัก คือ ลด ขนาดอะเรย์ของดัชนีการที่แทรกคีย์ในตาราง ที่จัดเก็บนั้นมีโอกาสที่คีย์ที่ถูกสร้างจากฟังก์ชัน ในช่องเดียวกันอย่างไรก็ตามการเกิดการชนกันก็ยังคงต้องมีอย่างน้อยหนึ่งครั้ง

จากรูป ฟังก์ชัน h การจับคู่ระหว่าง k กับ j ในช่องทางเดียวกันซึ่ง อาจจะชนกันสามารถแบ่งวิธีการในการรองรับการชนกันของ
ตารางแฮชคือการทำแบ่งห่วงโซ่ (Chaining) แบบการเปิดที่อยู่ (Open Addressing)

การแก้ไขปัญหาชนกันของข้อมูล แบบห่วงโซ่(Chaining)

1. กรณีที่เลวร้ายที่สุด ในการแทรกข้อมูลคือ o(1)
2. การลบสมาชิก สามารถทำได้ด้วยเวลาที่น้อยที่สุดของ o(1)
ทางปฏิบัติ ใช้เทคนิค ฮิวริสติก (Heuristic) ในการสร้างฟังก์ชันแฮช แนวทางหนึ่งที่ดีคือ การแปลงค่าของข้อมูลที่มีอยู่แล้วด้วยข้อมูลที่มีอยู่ (วิธีการหาร:Division method) ฟังก์ชันแฮช คือการกำหนดค่าคีย์ที่เกิดขึ้นในเอกภพสัมพัทธ์จากตัวเลขธรรมชาติ

วิธีการสร้างฟังก์ชันแฮช (Method for Creating Function)

1.วิธีการหาร (The Division Method)
2.วิธีการคูณ(The Multiplication Method)
3.วิธีทั่วไป (Universal hashing)

วิธีการหาร (The Division Method)

Open Addressing
ฟังก์ชันแฮช คือ
h: ν{0, 1, . . . m -1 }--> {0, 1, . . . , m-1}
ลำดับในการตรวจสอบ(probe sequence) คือ
<>

เทคนิคลำดับของการตรวจสอบ

1. การตรวจสอบเชิงเส้น (Linear Probing)
2.การตรวจสอบด้วยสมการกำลังสอง(Quadratic Probing)
3. การสร้างฟังก์ชันแฮชแบบสองเท่า(Double Hashing)

เทคนิคลำดับของการตรวจสอบ

1.การตรวจสอบเชิงเส้น (Linear Probing)รูปแบบของ ฟังก์ชันคือ
h(k, i) = (h` (k) + i) mod m เมื่อ i = 0, 1, 2, . . . , m-1
h` คือ auxiliary ของฟังก์ชันแฮช

2. การตรวจสอบด้วยสมการกำลังสอง(Quadratic Probing)รูปแบบของ ฟังก์ชันคือ
h(k, i) = (h` (k) + c1i + c2i2) mod m เมื่อ i = 0, 1, 2, . . . , m-1
h` คือ auxiliary ของฟังก์ชันแฮช c1 + c2 ≠ 0 เป็นค่าคงที่แบบ auxiliary

3. การสร้างฟังก์ชันแฮชแบบสองเท่า (Double Hashing)รูปแบบของ ฟังก์ชันคือ
h(k, i) = (h1, 9k) + ih2 (k)) mod m เมื่อ h1 และ h2 เป็น auxiliary ของฟังก์ชัน
ค่า k เป็นค่าเริ่มต้นของ ตำแหน่งการตรวจสอบ และค่า offset



แบบฝึกหัด

1.จงจัดชุดข้อมูลลงในตาราง Hash Table 13,25,63,69,45,78,59,17ขนาด 9 ช่อง โดยการแก้ปัญหาการชนกัน ใน
ลักษณะแบบเชน
2. จงอธิบายวิธีการแก้ไขปัญหาการชนกันของข้อมูล
3. วิธีในการสร้าง Hash Function มีวิธีใดบ้าง

Sorting

เนื้อหา

- การเรียงลำดับ
- วิธีการเรียงลำดับ
- การเรียงลำดับแบบเลือก (selection sort)
- การเรียงลำดับแบบฟอง (bubble Sort)
- การเรียงลำดับแบบเร็ว (quick sort)
- การเรียงลำดับแบบแทรก (insertion sort)
- การเรียงลำดับแบบฐาน (radix sort)

จุดประสงค์การเรียนรู้

1. เพื่อให้นักศึกษาเข้าใจวิธีการเรียงลำดับกระบวนการทำงาน ในรูปแบบต่างๆ
2. เพื่อให้นักศึกษาทราบวิธีการเรียงลำดับแบบเลือก
3. เพื่อให้นักศึกษาทราบวิธีการเรียงลำดับแบบฟอง
4. เพื่อให้นักศึกษาทราบวิธีการเรียงลำดับแบบเร็ว
5. เพื่อให้นักศึกษาทราบวิธีการเรียงลำดับแบบแทรก
6. เพื่อให้นักศึกษาทราบวิธีการเรียงลำดับแบบฐาน
7. เพื่อให้นักศึกษาสามารถตัดสินใจเรียงวิธีการเรียงลำดับที่เหมาะสมได้

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

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

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

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

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

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

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

จำนวนครั้งของการเปรียบเทียบทั้งหมด
= (n −1) + (n −2) + . . . + 3 + 2 + 1
= n (n −1) / 2 ครั้ง

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

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

จากตัวอย่าง การเปรียบเทียบจะเริ่มเปรียบเทียบจากคู่หลัง ในรอบที่ 1 เปรียบเทียบข้อมูลที่ตำแหน่งที่ 7 กับ 8 ได้ว่า 43 น้อยกว่า 82 ให้ทำการสลับตำแหน่งกันเพื่อให้ค่าที่น้อยกว่าอยู่ก่อนต่อไปเปรียบเทียบข้อมูลตำแหน่งที่ 6 กับ 7 ได้ว่า43 น้อยกว่า 99 ให้ทำการสลับตำแหน่งกันอีก ทำการเปรียบเทียบเช่นนี้ในคู่ต่อไปเรื่อย ๆ จนกระทั่ง

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ข้อมูลเริ่มต้น 12 ตัว
35 67 58 47 22 99 82 43 11 40 29 55

เมื่อจัดกลุ่มในรอบแรกเสร็จแล้วรวบรวมข้อมูลในทุกกลุ่มเริ่มตั้งแต่ข้อมูลในกลุ่ม 0 จนถึงกลุ่ม 9 ได้ข้อมูลเรียงตามลำดับดังนี้
40 11 22 82 43 35 55 67 47 58 99 29

ในรอบที่ 2 เมื่อทำการจัดกลุ่มเรียบร้อยแล้วให้รวบรวมข้อมูลในทุกกลุ่มเริ่มจากข้อมูลในกลุ่ม 0จนถึงกลุ่ม 9 ได้ข้อมูลเรียงตามลำดับดังนี้
11 22 29 35 40 43 47 55 58 67 82 99

การเรียงลำดับแบบฐานมีวิธีการที่ไม่ซับซ้อนแต่ค่อนข้างใช้เนื้อที่ในหน่วยความจำมาก เนื่องจากการจัดเรียงแต่ละรอบจะต้องเตรียมเนื้อที่สำหรับสร้างที่เก็บข้อมูลในแต่ละกลุ่ม เช่นถ้ามีจำนวนข้อมูล n ตัว และในแต่ละกลุ่มใช้วิธีจัดเก็บข้อมูลในแถวลำดับ ต้องกำหนดให้แต่ละกลุ่มมีสมาชิกได้ n ตัวเท่ากับจำนวนข้อมูลเผื่อไว้กรณีที่ข้อมูลทั้งหมดมีค่าในหลักนั้น ๆเหมือนกัน ถ้าเป็นเลขจำนวนใช้ทั้งหมด 10 กลุ่มกลุ่มละ n ตัวรวมทั้งหมดมีขนาดเท่ากับ (10 x n)



แบบฝึกหัด


1. เหตุใดจึงต้องมีการเรียงลำดับ
2. ท่านสามารถจัดเรียงข้อมูลได้อย่างไรบ้าง
3. การเรียงลำดับจะเกิดประสิทธิภาพได้เมื่อใด
4. จงเรียงลำดับจากตัวเลขที่กำหนดให้ต่อไปนี้25,15,10,8,7,9,24,32,18,21,29ตามแบบ selection , Buble
,radix,quick,insertion เป็นต้น

Graph

เนื้อหา

- โครงสร้างข้อมูลแบบกราฟ
- นิยามของกราฟ
- การแทนที่กราฟในหน่วยความจำ
- การท่องไปในกราฟ

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

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

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

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

โหนดสองโหนดในกราฟแบบไม่มีทิศทางถือว่าเป็นโหนดที่ใกล้กัน (Adjacent) ถ้ามีเอ็จเชื่อมจากโหนดที่หนึ่งไปโหนดที่สอง
กราฟ (ก) แสดงกราฟที่มีลักษณะ ต่อเนื่อง(Connected) เป็นกราฟที่มีเส้นทางเชื่อมจากโหนดใด ๆ ไปยังโหนดอื่นเสมอ
กราฟ (ข) แสดงกราฟที่มีลักษณะเป็น วีถี(Path) มีเส้นทางเชื่อมไปยังโหนดต่าง ๆ อย่างเป็นลำดับ โดยแต่ละโหนดจะเป็น
โหนดที่ใกล้กันกับโหนดที่อยู่ถัดไป
กราฟ (ค) แสดงกราฟที่เป็นวัฎจักร (Cycle)ซึ่งต้องมีอย่างน้อย 3 โหนด ที่โหนดสุดท้ายต้องเชื่อมกับโหนดแรก
กราฟ (ง) แสดงกราฟที่มีลักษณะ ไม่ต่อเนื่อง(Disconnected) เนื่องจากไม่มีเส้นทางเชื่อมจากโหนด 3 ไปยังโหนดอื่นเลย
กราฟ (จ) แสดงกราฟที่เป็นทรี โดยทรีเป็นกราฟที่ต่อเนื่อง ไม่มีทิศทาง และไม่เป็นวัฏจักร

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

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

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

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

วิธีแทนกราฟในความจำหลักอีกวิธีหนึ่งซึ่งเป็นที่นิยมใช้ กันมากที่สุดคือการแทนด้วยแอดจาเซนซีเมทริกซ์(Adjacency Matrix)โดยที่ถ้ากราฟ G มีทั้งหมด nโหนด แอดจาเซนซีเมทริกซ์เป็นเมทริกซ์จัตุรัสขนาด n x n สมมติว่าคือ
เมทริกซ์ M แต่ละ M(i,j) เมื่อ i, j = 1, 2, 3, . . ., n จะมีค่าเป็น 1 ถ้ามีเอ็จเชื่อมความสัมพันธ์ระหว่างโหนด i
ไปยังโหนด j และ มีค่าเป็น 0 ถ้าไม่มีเอ็จเชื่อมความสัมพันธ์จากโหนด i ไปยังโหนด j หรืออาจจะกำหนดด้วย ค่าตรรกะ (BooleanValue) ก็ได้ลักษณะที่น่าสนใจอย่างหนึ่งของแอดจาเซนซีเมทริกซ์ก็คือ สามารถหาได้ว่ามีจำนวนเส้นทางกี่เส้นทางจากโหนด Xi ไปยังโหนด Xj ใด ๆ ได้ โดยดูจากค่าในแอดจาเซนซีเมทริกซ์ เช่นถ้า M เป็นแอดจาเซนซีเมทริกซ์ Mk เป็นการคูณเมทริกซ์ M ด้วตัวมันเอง k ครั้ง และ Mk ij เป็นสมาชิกในแถวที่ i คอลัมน์ที่ j ของเมทริกซ์ Mkอาจกล่าวได้ว่า เมทริกซ์ M บอกให้ทราบว่ามีเส้นทางจากโหนดในแถวที่ i ไปยังโหนดในคอลัมน์ที่ j ขนาดหนึ่งจำนวนเส้นทางเมทริกซ์ M2 บอกให้เราทราบว่ามีเส้ทางจากโหนดในแถวที่ i ไปยังโหนดในคอลัมน์ที่ jขนาดสองจำนวนเส้นทาง เมทริกซ์ M3 บอกให้เราทราบว่ามีเส้นทางจากโหนดในแถวที่ iไปยังโหนดในคอลัมน์ที่ j ขนาดสามจำนวน

- ถ้า Mkij = 0 จะได้ว่าไม่มีเส้นทางขนาดk จากโหนดในแถวที่ i ไปยังโหนดในคอลัมน์ที่ j
- ถ้า Mkij = p เมื่อ pเป็นจำนวนเต็มบวกได้ว่ามีเส้นทางขนาด kจำนวน pเส้นทางจากโหนดในแถวที่ iไปยังโหนดในคอลัมน์ที่ j

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

1.การท่องแบบกว้าง (Breadth First Traversal)วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟผลลัพธ์จากการท่อง 1 4 6 2 3 8 5 7 9

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

แบบฝึกหัด

1. อธิบายโครงสร้างรูปแบบ กระบวนการทำงานของ กราฟ
2. กราฟ แบบ Directed แตกต่างจากUndirected หรือไม่อย่างไร
3. ให้อธิบายประโยชน์จากการนำกราฟไปประยุกต์ใช้ในชีวิตประจำวัน หรืองานที่เกิดขึ้น

Tree

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

จุดประสงค์การเรียนรู้

1. เพื่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบทรี
2. เพื่อให้ทราบนิยามของทรี และที่เกี่ยวข้อง
3. เพื่อให้นักศึกษาทราบวิธีการแทนที่ทรีใน หน่วยความจำหลัก
4. เพื่อให้นักศึกษาทราบการแปลงทรีให้เป็นไบ นารีทรี
5. เพื่อให้นักศึกษาทราบวิธีการท่องไปในทรี
6. เพื่อให้นักศึกษาทราบกระบวนการเอกซเพรสชั่นทรี
7. เพื่อให้นักศึกษาทราบวิธีการไบนารีเซิร์ซทรี

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

นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop)ในโครงสร้าง โหนดสองโหนด ใดๆในทรีต้องมีทางตัดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่ง ทั้งหมด N-1 เส้น การเขียนรูปแบบทรี อาจเขียนได้ 4

2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่า นัลทรี (Null Tree)และถามโหนดหนึ่งเป็นโหดราก ส่วนที่เหลือจะแบ่งเป็น ทรีย่อย (Sub Tree)T1, T2, T3,…,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี

นิยามที่เกี่ยวข้องกับทรี
1.ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออกหรือเซตของทรีทแยกจากกัน (Disjoint Trees)

2.ทรีที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมี ความสัมพันธ์ที่แน่นอน เช่น ไปทางขวา
ไปทางซ้าย เป็นต้น

3.ทรีคล้าย (Similar Tree) คือทรีที่มีโครงสร้างเหมือนกันหรือทรีที่มีรูปร่างของทรีเหมือนกันโดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด

4.ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน

5.กำลัง (Degree) หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ เช่น

ในรูปโหนด “B” มีกำลังเป็น 1 เพราะมีทรีย่อย คือ {“D”}ส่วนโหนด “C” มีค่ากำลังเป็นสองเพราะมีทรีย่อย คือ {“E”, “G”, “H”, “I”} และ {“F”}


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

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

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

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

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

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

ไบนารีทรีที่ทุก ๆ โหนดมีทรีย่อยทางซ้ายและทรีย่อยทางขวา ยกเว้นโหนดใบ และโหนดใบทุกโหนดจะต้องอยู่ที่ระดับเดียวกันเรียกว่า ไบนารีทรีแบบสมบูรณ์ (complete binary tree)สามารถคำนวณจำนวนโหนดทั้งหมดใน
ไบนารีทรีแบบสมบูรณ์ได้ถ้ากำหนดให้ Lคือระดับของโหนดใด ๆ และ N คือจำนวนโหนดทั้งหมดในทรีจะได้ว่า
ระดับ 1 มีจำนวนโหนด 1 โหนด
ระดับ 2 มีจำนวนโหนด 3 โหนด
ระดับ 3 มีจำนวนโหนด 7 โหนด
ระดับ L มีจำนวนโหนด 2L - 1โหนด
นั้นคือ จำนวนโหนดทั้งหมดในทรีสมบูรณ์ที่ มี L ระดับ สามารถคำนวณได้จากสูตรดั้งนี้

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

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

มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นคือ NLR LNR และ LRN ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้

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

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

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

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

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

การแทนนิพจน์ในเอ็กซ์เพรสชันทรี ตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบส่วนตัวดำเนินการจะเก็บในโหนดกิ่งหรือโหนดที่ไม่ใช่โหนดใบ
เช่น นิพจน์ A + B สามารถแทนในเอ็กซ์เพรสชันทรีได้ดังนี้

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

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

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

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

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

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

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

แบบฝึกหัด

1. ให้นักศึกษาอธิบายคำที่เกี่ยวข้องกับ ทรีดังนี้ Parent , Child , Root , Sibling
2. ไบนารีทรี คืออะไร มีหลักในการทำงานอย่างไร ได้แก่ข้อมูลที่มีลักษณะอย่างไรบ้าง
3. จากตัวเลขต่อไปนี้ ให้นักศึกษาดำเนินการให้เป็น ไบนารีทรี แบบสมบูรณ์10,5,8,7,15,20,28,9,12,6พร้อมทำการท่องไปในทรีแบบ NLR , LRN