การเรียงลำดับข้อมูบ Soeting

บทที่ 8 
การเรียงลำดับข้อมูล ( Sorting )

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

 8.1 ประเภทการเรียงลำดับข้อมูล (Sort  Classifications)

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

1. การเรียงลำดับข้อมูลแบบภายใน (Internal  Sorting)

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

ข้อดี        - RAM ทำงานได้เร็ว
ข้อเสีย     - RAM มีความจุน้อย
             - เมื่อปิดเครื่องข้อมูลที่เรียงลำดับไว้จะหายไป

2. การเรียงลำดับข้อมูลแบบภายนอก  (External  Sorting)

                ใช้ Secondary Storage เช่น Hard disk  จะในกรณีที่ข้อมูลมีปริมาณมาก การ
จัดเรียงข้อมูลจะมีการแบ่งข้อมูลออกเป็นส่วนๆ  เพื่อดึงข้อมูลมาเรียงลำดับใน RAM ที่ละส่วน
  

ข้อดี        -  มีความจุสูง
              -  เมื่อปิดเครื่องข้อมูลที่เรียงลำดับไว้ยังอยู่
ข้อเสีย      -  ทำงานช้า

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

ความคงที่ในการเรียงลำดับข้อมูล (Sort  Stability)
                         ความคงที่ในการเรียงลำดับข้อมูล  ถือเป็นคุณสมบัติหนึ่งของการเรียงลำดับข้อ
มูล โดยเฉพาะข้อมูลที่มีคีย์ซ้ำกัน  โดยเมื่อมีการอินพุตกลุ่มข้อมูลที่มีคีย์ซ้ำกันเข้ามาจัดเรียงลำ
ดับและแสดงผลออกเป็นเอาต์พุตคุณสมบัติของความคงที่ก็คือ กลุ่มคีย์ซ้ำกันนั้นควรมีลำดับข้อมูล
เหมือนกับข้อมูลชุดเดิม  ให้พิจารณาจากรูปที่ 8.2 (a) ซึ่งเป็นข้อมูลที่อินพุตเข้ามาโดยยังไม่ได้
ผ่านการจัดเรียงให้สังเกตดี ๆว่าจะมีข้อมูลอยู่ 3เรคอร์ดด้วยกันที่มีคีย์ซ้ำกัน  ซึ่งก็คือหมายเลข
212 โดยหลังจากที่นำข้อมูลเหล่านี้มาผ่านการจัดเรียงด้วยอัลกอริทึมการเรียงลำดับข้อมูลแล้ว
จะเห็นได้ว่าเอาต์พุตจากรูปที่ 8.2 (b) และรูปที่ 8.2 ( c ) นั้น  ลำดับข้อมูลของกลุ่มคีย์ 212
นั้นไม่เหมือนกัน  โดยจากรูปที่ 8.2 (b) นั้นถือว่าเป็นการเรียงลำดับข้อมูลที่มีความคงที่ เนื่อง
จากกลุ่มคีย์  212ยังคงซึ่งลำดับเดิมเหมือนกับข้อมูลต้นฉบับคือ green, yellow และ blue
ในขณะที่รูปที่ 8.2 ( c  )นั้นมีความคลาดเคลื่อน  เนื่องจากตำแหน่งของ  blue ได้คลาดเคลื่อนไป
โดยถูกจัดไว้ในลำดับแรกภายในกลุ่ม  ซึ่งถือว่าไม่มีความคงที่ในการเรียงลำดับข้อมูล

8.2 ประสิทธิภาพของการเรียงลำดับข้อมูล  (Sort  Efficiency)

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

 8.3 วิธีการเรียงลำดับข้อมูล

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

วิธีต่อไปนี้
1.  การเรียงลำดับข้อมูลแบบ   Selection  Sort
2.  การเรียงลำดับข้อมูลแบบ   Heap  Sort
3.  การเรียงลำดับข้อมูลแบบ   Insertion  Sort
4.  การเรียงลำดับข้อมูลแบบ   Bubble   Sort
5.  การเรียงลำดับข้อมูลแบบ   Quick   Sort
6.  การเรียงลำดับข้อมูลแบบ   Merge   Sort

1. การเรียงลำดับข้อมูลแบบ  Selection  Sort

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

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

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

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

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

                รอบที่ 5:
                สำหรับรอบนี้จัดเป็นรอบสุดท้าย  เนื่องจากภายในลิสต์เหลือเพียงข้อมูลสอง
ตัวสุดท้ายคือ 78และ 56 ปรากฏว่าค่า 56 น้อยกว่า  จึงทำการสลับตำแหน่งกัน หลังจากนั้น
ก็คงเหลือไว้แต่เพียงข้อมูลที่ได้จัดเรียงไว้อย่างสมบูรณ์

   

2. การเรียงลำดับข้อมูลแบบ  Heap  Sort

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

3. การเรียงลำดับข้อมูลแบบ  Insertion  Sort

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

                     รูปที่ 8.7  หลักการเรียงลำดับข้อมูลแบบ  Insertion  Sort

                  ขั้นตอนการทำงานของการเรียงลำดับข้อมูลแบบ Insertion  Sort  นั้น ได้นำ
เทคนิคของการจัดเรียงแบบ  Insertion  มาปรับปรุง  กล่าวคือแทนที่จะอ่านหรือสแกนข้อ
มูลจนครบทุกตัวเพื่อหาค่าที่น้อยที่สุด  ก็จะทำการเปรียบเทียบค่ากับตำแหน่งถัดไปแทน
โดยถ้าตำแหน่งถัดไปนั้นมีค่าน้อยกว่า ก็จะนำมาสลับตำแหน่งกันด้วยการนำมาแทรกในตำ
แหน่งที่เหมาะสมของกลุ่มข้อมูลที่จัดเรียง  โดยขั้นตอนการทำงาน  เราจะนำเสนอด้วยการ
แสดงภาพพร้อมขั้นตอนการทำงานในแต่ละรอบ  โดยสมสุติว่ามีชุดตัวเลขที่ต้องการนำมา
จัดเรียงคือ  {23, 78, 45, 8, 32, 56}

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

               รอบที่ 2:
                   ตำแหน่งดรรชนี ณ ขณะนี้ขยับไปอยู่หน้าช่องที่ 3 ให้ทำการนำค่าตัวเลขจากช่อง
ที่ 3 ไปเปรียบเทียบกับชุดตัวเลขในส่วนที่จัดเรียงไว้แล้ว  ซึ่งอยู่ส่วนหน้า  ผลลัพธ์ที่ได้คือค่าตัว
เลข 45จะนำไปแทรกในตำแหน่งที่ 2 ซึ่งอยู่ระหว่างค่า 23 กับ 78

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

               

                รอบที่ 4:
                ตำแหน่งถัดไปคือช่วงที่ 5  ให้นำค่าตัวเลขจากช่องที่ 5 ซึ่งในที่นี้คือค่า 32ไป
เปรียบเทียบกับชุดตัวเลขในส่วนที่จัดเรียงทั้งหมด  ผลปรากฏว่า  ค่า 32 ซึ่งอยู่ตำแหน่งที่
5นี้จะนำไปแทรกไว้ที่ตำแหน่งในส่วนที่ได้จัดเรียงไว้โดยแทรกไว้หน้าค่า 45

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

4. การเรียงลำดับข้อมูลแบบ Bubble  Sort

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

  

 เริ่มต้นจากข้อมูลต้นฉบับ  โดยเปรียบเทียบค่าเริ่มต้นที่ท้ายลิสต์  ด้วยการจับคู่

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

5. การเรียงลำดับข้อมูลแบบ  Quick  Sort

                การเรียงลำดับข้อมูลแบบ   Bubble  Sort กับ  Quick  Sort  นั้น  ต่างก็เป็นวิธี
การเรียงลำดับข้อมูลแบบแลกเปลี่ยน (Exchange)แต่จะมีความแตกต่างกันตรงที่ การเรียง
ลำดับข้อมูลแบบ  Bubble Sort  นั้น จะทำการเปรียบเทียบค่าข้อมูลที่อยู่ติดกันและสลับตำ
แหน่งกันเพื่อให้ค่าตัวเลขน้อยๆลอยขึ้น แต่สำหรับ  Quick Sort นั้น จะใช้หลักการแบ่งส่วน
(Partition)ข้อมูลเป็นหลักซึ่งมีประสิทธิภาพมากกว่า เพราะว่าจำนวนของการสลับตำแหน่ง
จะมีน้อยกว่าการจัดเรียงแบบ  Bubble Sort

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

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

                        

 ดังนั้นตำแหน่งกึ่งกลางในลิสต์จากสูตร  set  mid  to (left+right)/2 จาก
ชุดคำสั่งลำดับที่ 1ในอัลกอริทึมที่ 9.5 จะได้เท่ากับ (1+12)/2 ก็คือตำแหน่งที่ 6 ดังนั้นก็
จะได้ Left Key = 78, Mid  Key = 62และ Right Key = 22  แต่ว่าทั้งสามอิลิเมนต์นั้น
ยังอยู่ในตำแหน่งที่ยังไม่ถูกต้อง  จึงต้องดำเนินการเปรียบเทียบเงื่อนไขตามอัลกอริทึมที่
9.5 เพื่อหาค่ากึ่งกลางที่ถูกต้องที่แสดงได้ดังต่อไปนี้

                   เมื่อได้ตำแหน่ง Left Key, Mid  Key และ Right Key

                   เปรียบเทียบค่า Left Key  > Mid  Key หรือไม่  ถ้าใช่ให้สลับตำแหน่ง

                   เปรียบเทียบค่า Left Key  >Right  Key หรือไม่  ถ้าใช่ให้สลับตำแหน่ง

                   เปรียบเทียบค่า mid Key  >Right  Key หรือไม่  ถ้าใช่ให้สลับตำแหน่ง

6. การเรียงลำดับข้อมูลแบบ Merge Sort

                สำหรับวิธีการเรียงลำดับข้อมูลทั้งหมดที่กล่าวไว้ข้างต้นนั้น ล้วนแล้วแต่เป็นวิธี
การจัดเรียงข้อมูลแบบภายใน(Internal Sort) ทั้งสิ้นโดยข้อมูลจะอยู่ภายในหน่วยความ
จำหลักทั้งหมดในระหว่างการประมวลผลดังนั้นเนื้อหาต่อไปนี้จะกล่าวถึงวิธีการจัดเรียงข้อ
มูลแบบภายนอก (External Sort)ซึ่งเป็นวิธีการจัดเรียงข้อมูลที่อนุญาตให้ข้อมูลที่ถูกจัด
เรียงบางส่วนถูกจัดเก็บไว้ในหน่วยความจำสำรองในระหว่างการประมวลผลและมีข้อมูลอีก
ส่วนหนึ่งกำลังจัดเรียงอยู่ภายในหน่วยความจำหลัก และหนึ่งในวิธีการเรียงลำดับข้อมูลแบบ
ภายนอกนี้ก็คือ วิธี Merge Sort หรือการเรียงลำดับข้อมูลแบบผสานนั่นเอง
                 กระบวนการเรียงลำดับข้อมูลแบบ Merge Sort มักนำไปใช้งานกับข้อมูลที่ต้อง
การจัดเรียงในปริมาณมาก ๆ กล่าวคือข้อมูลทั้งหมดที่ต้องการจัดเรียงนั้น ไม่สามารถนำไป
ประมวลผลที่หน่วยความจำหลักได้ในคราวเดียว  ดังนั้นจึงต้องมีการนำข้อมูลบางส่วนไปประ
มวลผลที่หน่วยความจำหลัก  ในขณะที่ข้อมูลที่เหลือก็จะถูกจัดเก็บไว้ในหน่วยความจำสำรอง
                 การดำเนินงานพื้นฐานของการเรียงลำดับข้อมูลแบบ Merge Sort นั้น เป็น
กระบวนการนำไฟล์ข้อมูลสองไฟล์ที่จัดเรียงแล้ว  มารวมกันเพื่อจัดเรียงข้อมูลตามคีย์ที่จัด
เรียง กล่าวคือเป็นการอ่านข้อมูลจาก File-1 และ File-2 และนำมาผสานรวมกัน ด้วยการ
เก็บเป็นเอาต์พุตไฟล์ไว้ที่ File - 3 ซึ่งเป็นไปดังรูปที่ 8.12

   

จากรายละเอียดที่ได้อธิบายไว้ในข้างต้น เป็นขั้นตอนของการนำไฟล์มาผสาน
รวมกันและต่อไปนี้จะแสดงถึงกระบวนการจัดเรียงข้อมูลที่ยังไม่ได้ผ่านการจัดเรียงมาก่อน
ซึ่งเรียกว่าขั้นตอนของการแบ่งส่วน (Distribution Phase) โดยมีหลักการอยู่ว่า ให้ทำการ
แบ่งข้อมูลออกเป็นกลุ่มย่อยด้วยการแบ่งส่วนข้อมูลออกทีละครึ่งจนกระทั่งไม่สามารถแบ่ง
ได้อีก จากนั้นก็จะเป็นขั้นตอนของการนำไฟล์มาผสานกัน (Merge Phase) เพื่อจะได้ไฟล์
ข้อมูลที่จัดเรียงเพียงไฟล์เดียวดังที่ได้กล่าวมาแล้วในข้างต้น
                     โดยสมมติว่า มีข้อมูลที่ต้องการนำมาจัดเรียงดังนี้คือ {1, 5, 3, 14, 17, 6, 7,
13}ซึ่งขั้นตอนการจัดเรียงเริ่มต้นด้วยการแบ่ง และท้ายสุดก็นำไฟล์มาผสานกัน ซึ่งเป็นไปดัง
รูปที่8.13 จากรูปที่ 8.13 จะเห็นขั้นตอนของการแบ่งขนาดของลิสต์ออกเป็นสองส่วนไปเรื่อย
ๆ ซึ่งเป็นการทำงานในลักษณะรีเคอร์ซีพ โดยมีการเรียกฟังก์ชันการทำงานแบบเดิมจำนวน
สองครั้ง และจะสิ้นสุดการทำงานแบบรีเคอร์ซีพเมื่อไม่สามารถแบ่งแยกได้อีก โดยจากรูปจะ
เห็นเส้นประแบ่งครึ่งซึ่งครึ่งแรกของภาพแสดงถึงการแบ่งส่วน ในขณะที่ครึ่งหลังของภาพ
แสดงถึงการผสานรวมกัน

         

ง

่การค้นหาข้อมูล Seaeching

บทที่ 7 
การค้นหาข้อมูล (Searching)

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

1.    Sequential Search
        1.1  Sentinel Search
        1.2  Probability Search
        1.3  Ordered List Search
2.     Binary Search
3.     Hashing Search

.

1 การค้นหาแบบลำดับ (Sequential  Search)

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

1. พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์ (Successful Search)
2. ไม่พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์ (Unsuccessful Search)

                  พิจารณาจากรูปที่ 91 โดยในที่นี้ได้กำหนดค่า Target ที่ต้องการค้นหาคือ 14 และทำ
การค้นหาตั้งแต่ตำแหน่งแรกคือตำแหน่งที่ 1 (ดรรชนี 0) และจะค้นหาไปเรื่อย ๆ จนกระทั่งพบค่า
ที่ต้องการซึ่งก็คือตำแหน่งที่ 4 (ดรรชนี 3)  สำหรับตัวอย่างดังรูปที่ 9.1 นี้ เป็นตัวอย่างการค้นหา
ข้อมูลในลิสต์แล้วพบ
                  ในขณะที่รูปที่ 9.2 นั้น จะเป็นตัวอย่างกรณีค้นหาข้อมูลในลิสต์แล้วไม่พบ จากตัวอย่าง
ดังรูปได้มีการค้นหาค่า Target ซึ่งในที่นี้คือค่า 72 โดยได้ทำการค้นหาข้อมูลตั้งแต่ตำแหน่งแรก
จนกระทั่งถึงตำแหน่งสุดท้ายปรากฏว่าผลลัพธ์ที่ได้คือ ค้นหาข้อมูลภายในลิสต์ไม่พบ

       

 2 การค้นหาข้อมูลแบบเซนทิเนล (Sentinel Search)

                  หากมีการตรวจสอบเงื่อนไขของอัลกอริทึม Sentinel Search ในอัลกอริทึมที่ 9.1
ตรงหมายเลขลำดับชุดคำสั่งที่ 2 แล้ว จะเห็นได้ว่า ภายในลูปนั้นจะมีการตรวจสอบเงื่อนไขถึง 2
เงื่อนไขด้วยกัน ซึ่ง Donald E.Knuth ได้บัญญัติไว้ว่า “หากภายในลูปของโปรแกรมได้มีการ
ทดสอบเงื่อนไขมากกว่า 2 เงื่อนไขขึ้นไปให้พยายามลดการทดสอบเงื่อนไขลงเหลือเพียงหนึ่ง
เงื่อนไข” ดังนั้นด้วยเทคนิคของเซนทิเนล  จึงได้ทำการเพิ่มสมาชิกพิเศษ (Sentinel  Entry)
ซึ่งก็คือค่า Target ที่ไว้ตรงตำแหน่งถัดจากลำดับจากลำดับสุดท้ายของอาร์เรย์ (Last+1) เพื่อ
ใช้ควบคุมการทดสอบเงื่อนไขการวนรอบให้เหลือเพียงเงื่อนไขเดียวโดยซูโดโค้ดสำหรับการ
ค้นหาข้อมูลแบบSentinel Search

3 การค้นหาข้อมูลแบบพรอบาบิลิตี้ (Probability  Search)

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

 4 การค้นหาข้อมูลแบบออร์เดอร์ลิสต์ (Ordered List Search)

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

 5 การค้นหาข้อมูลแบบไบนารี (Binary Search)

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

 1. ตัวแปร begin เป็นตัวแปรที่ใช้สำหรับกำหนดตำแหน่งเริ่มต้นของลิสต์

2. ตัวแปร mid เป็นตัวแปรที่ใช้สำหรับกำหนดตำแหน่งกึ่งกลางของลิสต์
3. ตัวแปรend เป็นตัวแปรที่ใช้สำหรับกำหนดตำแหน่งท้ายสุดของลิสต์

Mid = [ (begin + end) / 2]

                    โดยสมมติว่ามีชุดตัวเลขที่เรียงลำดับแล้วภายในลิสต์ดังนี้ คือ {4, 7, 8, 10, 14, 21,
22,36, 62, 77, 81, 91} และค่า Target ที่ต้องการค้นหาคือค่า 22
                    เริมต้นจากการคำนวณหาตำแหน่งกึ่งกลาง ซึ่งจะได้เท่ากับ (0+11)/2=5(ให้ตัดเศษ
ทิ้ง)ดังนี้ตำแหน่งดรรชนี 5 ภายในอาร์เรย์จึงเป็นจุดกึ่งกลางที่ใช้สำหรับแบ่งกลุ่ม

                   ให้ดำเนินการนำค่า Target ไปเปรียบเทียบกับค่ากึ่งกลาง (22>21)ผลปรากฏว่าค่า
Target มีค่ามากกว่า ดังนั้นให้ละทิ้งข้อมูลที่ต้องค้นหาตั้งแต่ตำแหน่งที่ 0 ถึง 5 เป็นต้นไปเนื่องจาก
ลิสต์ส่วนดังกล่าวมีค่าน้อยกว่าค่า Target ดังนั้นจึงไม่มีความจำเป็นที่จะต้องนำมาใช้เพื่อการค้นหา
อีกต่อไปในรอบที่สอง ให้ทำการหาค่ากึ่งกลางของลิสต์ส่วนครึ่งหลัง ผลที่ได้คือตำแหน่งดรรชนี 8
ซึ่งคำนวณได้จากสูตร(6+11)/2=8 และหลังจากนั้นให้นำค่า Target มีค่าน้อยกว่า ดังนั้นให้ละทิ้ง
ข้อมูลลิสต์ส่วนครึ่งหลังตั้งแต่ตำแหน่งที่ 8 ถึง 11ออกไป

 6 การค้นหาข้อมูลแบบแฮชชิง ( Hashing  Search )

                  การค้นหาข้อมูลแบบแฮชชิงจัดเป็นวิธีการค้นหาข้อมูลที่มีประสิทธิภาพวิธีหนึ่ง โดยวิธี
นี้สามารถเข้าถึงตำแหน่งข้อมูลได้โดยตรง กล่าวคือ สามารถค้นหาตำแหน่งข้อมูลที่ต้องการได้ภาย
ในครั้งเดียว ดังนั้นประสิทธิภาพการค้นหาข้อมูลแบบแฮชชิงนั้นจึงเป็นค่าคงที่ ซึ่งก็คือ O(1)การค้น
หาข้อมูลแบบแฮชชิงนั้นจะมีคีย์เพื่อใช้เป็นตัวค้นหา ซึ่งจะนำคีน์ไปผ่านฟังก์ชันแฮชเพื่อให้ได้มาซึ่ง
ตำแหน่งของข้อมูล โดยตำแหน่งที่ได้เรียกว่า Home Address  นั้นหมายความว่า คีย์จะถูกแปลง
เป็นตำแหน่งแอดเดรสของข้อมูลที่เก็บค่าข้อมูลนั้น(key-to-address) ดังนั้นแฮชชิงจึงสามารถ
เข้าถึงตำแหน่งข้อมูลด้วยคีย์ได้ทันทีนั่นเอง พิจารณาจากรูปที่ 9.4ซึ่งเป็นรูปแสดงการนำคีย์มา
ผ่านฟังก์ชันแฮชเพื่อจะได้ตำแหน่งแอดแดรสในขณะที่รูปที่ 9.5 เป็นหลักการของแฮชชิงเพื่อแสดง
ถึงคีย์เมื่อผ่านฟังก์ชันแฮชแล้ว ก็จะได้แอดเดรสที่สามารถชี้ไปยังตำแหน่งข้อมูลในตารางแฮชภาย
ในหน่วยความจำได้ทันที

7 แนวทางการแก้ไขเมื่อมีการชนกันของคีย์   (Collision  Resolution)

                  ข้อเสียประการหนึ่งของการใช้วิธีแฮชชิงก็คือ ความเป็นไปได้ของเหตุการณ์การชน
กันของคีย์ ซึ่งเหตุการณ์ดังกล่าวสามารถเกิดขึ้นได้เสมอ และเหตุการณ์การเกิดการชนของคีย์
จะมากหรือน้อยจะขึ้นอยู่กับขนาดของตารางแฮชด้วยและรวมถึงฟังก์ชันแฮชที่ได้รับการออกแบบ
ให้มีความสามารถในการกระจายคีย์ได้อย่างสม่ำเสมอหรือไม่แต่อย่างไรก็ตาม ถึงแม้จะมีการชน
ของคีย์ แต่ก็มีวิธีการแก้ปัญหาเมื่อเกิดการชนกัน โดยประกอบด้วยวิธีหลัก ๆ 3 วิธีด้วยกันคือ วิธี
Open Addressing, Linked Listและ Buckets พิจารณาจากรูปที่ 9.7 จะเห็นได้ว่า วิธี Open
Addressing จะประกอบด้วยหลายวิธีด้วยกัน แต่อย่างไรก็ตามสำหรับวิธี Open Addressing
ในที่นี้ขอกล่าวเพียงวิธี Linear Probe เท่านั้น

  จากการศึกษาเกี่ยวกับการค้นหาข้อมูลด้วยวิธีแอชชิง จะเห็นถึงปัญหาที่เกิดขึ้นได้
จากวิธีนี้ก็คือการชนกันของคีย์ แต่ก็มีแนวทางในการแก้ไขปัญหาที่หลากหลาย ดังนั้นในการทำ
งานจริง เราสามารถนำหลายๆ วิธีข้างต้นมาประยุกต์ใช้งานร่วมกันได้ ตัวอย่างเช่น ฐานข้อมูลที่
สร้างด้วยวิธีการแฮชแบบ Bucketถ้า Bucket เต็มก็สามารถใช้วิธี Linear Probe เข้ามาแก้ไข
หรืออาจใช้วิธีลิงก์ลิสต์ก็ได้เป็นต้น

ุ

กราฟ Geaphs

                                                                             บทที่ 6                                                                    กราฟ ( Graphs )

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

แนวคิดพื้นฐานเกี่ยวกับกราฟ (Basic Concepts)
                  กราฟ คือกลุ่มของโหนดที่เรียกว่า เวอร์เท็กซ์ (Vertex/Vertices) และกลุ่มของ
เอดจ์ (Edges) ที่ใช้เชื่อมโยงระหว่างเวอร์เท็กซ์ หรืออาจกล่าวอีกนัยหนึ่งว่า กราฟก็คือกลุ่มของ
เซต ซึ่งประกอบด้วยกลุ่มเซตของเวอร์เท็กซ์และเซตของเอดจ์นั่นเอง

                 ประเภทของกราฟ

กราฟยังสามารถแบ่งออกเป็น 2 ประเภทด้วยกันคือ

1. กราฟแบบมีทิศทาง (Directed Graph)                กราฟแบบมีทิศทาง  หรือเรียกสั้น ๆ ว่า ไดกราฟ (Digraphเป็นกราฟที่แต่ละเส้นจะมี
หัวลูกศรเพื่อชี้ไปยังโหนด   Successor   ซึ่งหัวที่มีลูกศรนั้นจัดเป็นการเชื่อมโยงแบบมีทิศทาง
ดังนั้นการเดินทางจะต้องเป็นไปตามทิศทางของลูกศเท่านั้น โดยเส้นที่เชื่อมโยงระหว่างเวอร์เท็กซ์
ในกราฟแบบมีทิศทางจะเรียกว่า อาร์ค (Arcs) จากรูปที่ 8.3 จะเห็นได้ว่าเวอร์เท็กซ์ที่ใช้แทนชื่อ
จังหวัด  คือจังหวัดเชียงรายและกรุงเทพ ฯ และมีอาร์คเป็นตัวเชื่อมโยงระหว่างจังหวัดกรุงเทพฯ
และเชียงราย โดยอาร์คคือเส้นทาง การเดินทางจากกรุงเทพฯ เพื่อไปยังจังหวัดเชียงรายเท่านั้น

                        

2. กราฟแบบไม่มีทิศทาง (Undirected Graph)

                   กราฟแบบไม่มีทิศทาง คือกราฟที่ไม่ได้ระบุทิศทาง กล่าวคือ เส้นที่เชื่อมโยงระหว่าง
เวอร์เท็กซ์จะไม่มีหัวลูก ศรระบุทิศทางเพื่อชี้ไปเช่นเดียวกับไดกราฟ  ดังนั้นเส้นทางการเชื่อมโยง
ระหว่างเวอร์เท็กซ์ในกราฟแบบไม่มีทิศทางนั้นจึงสามารถเชื่อมโยงไปมาระหว่างกันได้เส้นที่เชื่อม
โยงระหว่างเวอร์เท็กซ์ในกราฟแบบไม่มีทิศทางจะเรียกว่า  เอดจ์ (Edge) พิจารณาจากรูปที่ 7.3
จะเห็นได้ว่ามีเวอร์เท็กซ์เชียงราย และกรุงเทพฯซึ่งมีเส้น Edge เป็นตัวเชื่อมโยงระหว่างจังหวัด
กรุงเทพฯ และเชียงรายโดยสมมติว่า Edge ในที่นี้แทนเส้นทางการบิน นั่นหมายความว่า เส้นทาง
การบินระหว่างกรุงเทพฯกับเชียงรายจะเป็นไปทั้งสองทิศทางด้วยกันคือ  จะมีทั้งเส้นทางการบิน
จากกรุงเทพฯ-เชียงราย และจากเชียงราย-กรุงเทพฯ

      
            รูปที่ 7.3  กราฟแบบไม่มีทิศทางที่แสดงถึงการเดินทางจาก

กรุงเทพฯ-เชียงราย และเชียงราย-กรุงเทพฯ

            

เส้นทาง (Path)
                    เส้นทางหรือพาธ  คือลำดับของเวอร์เท็กซ์ในแต่ละเวอร์เท็กซ์ที่ประชิดต่อกันไปยังตัว
ถัดไป  โดยพิจารณาจากรูปที่ 8.6 (a) เส้นทาง {A , B , C , D , E} ก็เป็นเส้นทางหนึ่ง  ในขณะที่
เส้นทาง{A , B , E , F} ก็ถือเป็นเส้นทางอีกเส้นทาหนึ่ง  โดยกราฟทั้งแบบมีทิศทางและไม่มีทิศ
ทาง ต่างก็มีเส้นทางด้วยกันทั้งสิ้น   แต่สำหรับกราฟไม่มีทิศทาง เส้นทางในการเดินทางจะ
สามารถไปมาระหว่างกันได้

เวอร์เท็กซ์ประชิด (Adjacent Vertex)
                   เวอร์เท็กซ์ 2 เวอร์เท็กซ์ที่มีเส้นทางเชื่อมโยงกันจะเรียกว่า  เวอร์เท็กซ์ประชิด
(Adjacent Vertex)หรืออาจเรียกว่าโหนดเพื่อนบ้าน  เช่น ในรูปที่ 7.5 (a) เวอร์เท็กซ์ B คือ
โหนดประชิดของ A ส่วนเวอร์เท็กซ์ E นั้นไม่ใช่โหนดประชิดของ D ในอีกด้านหนึ่ง เวอร์เท็กซ์ D
คือโหนดประชิดของ E ส่วนในรูปที่ 7.5 (b)เวอร์เท็กซ์E และ D ต่างก็เป็นโหนดประชิด แต่เวอร์
เท็กซ์ D และ F นั้นไม่ใช่ เนื่องจากไม่มีเส้นทางเชื่อมโยงระหว่างกัน

ไซเคิลและลูป (Cycle and Loop)
               ไซเคิล คือเส้นทางที่ประกอบด้วยเวอร์เท็กซ์อย่างน้อย 3 เวอร์เท็กซ์ที่มีจุดเริ่มต้นและ
จุดสิ้นสุดอยู่บนเวอร์เท็กซ์เดียวกัน  โดยพิจารณาจากรูปที่ 7.5 (b) จะเห็นได้ว่า  B , C , D , E , B
คือไซเคิล แต่อย่างไรก็ตามในกลุ่มเวอร์เท็กซ์  B , C , D , E , B เดียวกันจากรูปที่ 7.5 (a) จะไม่
ถือว่าเป็นไซเคิล เนื่องจากว่าไดกราฟจะต้องเดินทางไปตามอาร์คของหัวลูกศรที่ชี้ทิศทางไว้เท่านั้น
นอกจากนี้ก็ยังมีลูป (Loop) ซึ่งจัดเป็นกรณีพิเศษของไซเคิลโดยจะมีเพียงอาร์คเดียวที่มีจุดเริ่มต้น
และจุดสิ้นสุดบนเวอร์เท็กซ์เดียวกัน

                          

ความต่อเนื่องของกราฟ (Connected)

                  ในส่วนของ (Connected) จะหมายถึงความต่อเนื่องของกราฟ กราฟที่มีความต่อ
เนื่องจะหมายถึงกราฟที่มีส้นทางเชื่อมจากโหนดหนึ่งเพื่อไปยังโหนดอื่นๆ ได้ กล่าวคือ แต่ละคู่ของ
เวอร์เท็กซ์จะมีเส้นทาง(Path)เชื่อมโยงถึงกันนั่นเอง โดยกราฟแบบมีทิศทางที่มี ความต่อเนื่อง
แบบแข็งแรง (Strongly Connected)จะหมายถึงมีเส้นทางแต่ละเวอร์เท็กซ์ไปยังทุกๆเวอร์เท็กซ์
ดังรูปที่ 7.7(a)ส่วนกราฟแบบมีทิศทางที่มี ความต่อเนื่องแบบอ่อนแอ (Weakly Connected) จะ
หมายถึงมีเวอร์เท็กซ์อย่างน้อยหนึ่งคู่ที่ไม่ได้เชื่อมโยงถึงกันซึ่งแสดงได้ดังรูปที่ 8.9 นอกจากนี้ยัง
มีกราฟแบบมีทิศทางที่ไม่มีความต่อเนื่อง (Unconnected/Disjoint Graph)ซึ่งหมายถึงมีบาง
เวอร์เท็กซ์แยกออกไปไม่มีเส้นทางเชื่อมโยงระหว่างกัน ซึ่งแสดงได้ดังรูปที่ 7.7 (c)

การดำเนินงานของกราฟ (Graph Operations)

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

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

การท่องเข้าไปในกราฟ  (Traverse  Graph)

                  สำหรับการท่องเข้าไปในกราฟ  จะมีอยู่ 2 วิธีมาตรฐานด้วยกันคือ  การท่องแบบ
แนวลึก  (Depth First)  และการท่องแบบแนวกว้าง  (Breadth First)ซึ่งทั้ง 2 วิธีต่างก็ใช้
ตัวแปร  Visited Flag  เพื่อเป็นการบ่งชี้ถึงสถานะของแต่ละเวอร์เท็กซ์นั้นว่าได้ผ่านการโปร
เซสมาแล้วหรือยัง

การท่องเข้าไปในกราฟแบบแนวลึก (Depth-First  Traversal)

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

1. เริ่มต้นจากการ  Push เวอร์เท็กซ์ลงในสแต็ก
2. เมื่ออยู่ในลูป  จะดำเนินการ Pop สแต็กเพื่อโปรเซสเวอร์เท็กซ์นั้น  จากนั้นก็ Push เวอร์เท็กซ์
ประชิด ทุกตัวลงในสแต็ก  ให้พิจารณาการโปรเซสเวอร์เท็กซ์  X  ในขั้นตอนที่ 2 ซึ่งจะ Pop ค่า X
ออกจาก    สแต็กเพื่อโปรเซสค่า  X โดยหลังจากนั้นก็จะ Push ค่า G  และ H ลงในสแต็ก  ซึ่งเป็น
ไปตามขั้นตอนที่ 3 ของรูปที่ 7.13(b)
3. เมื่อสแต็กว่างเปล่า นั่นหมายความว่าการท่องเข้าไปในกราฟได้เสร็จสมบูรณ์

การท่องเข้าไปในกราฟแบบแนวกว้าง (Breadtg-First Traversal)
                ในการท่องเข้าไปในกราฟแบบแนวกว้าง  จะทำการโปรเซสเวอร์เท็กซ์ประชิดทุก
ตัวก่อนที่จะลงสู่ในระดับถัดไป  การท่องเข้าไปมนกราฟแบบแนวกว้างนั้น  ก็ใช้หลักการเดียวกัน
กับทรี  ให้พิจารณาจากรูปที่ 8.18 ที่เป็นการท่องเข้าไปในกราฟ  ซึ่งได้ใช้โครงสร้างข้อมูลแบบ
คิวเข้าช่วย โดยเมื่อมีการโปรเซสแต่ละเวอร์เท็กซ์แล้ว  ก็จะนำเวอร์เท็กซ์ประชิดทุกตัวเข้าไป
แทนที่ในคิว  จากนั้นก็จะทำการคัดเลือกเวอร์เท็กซ์ตัวถัดไปเพื่อโปรเซส  และจะทำการลบเวอร์
เท็กซ์นั้นออกจากคิวหลังจากที่ได้โปรเซสแล้วเสร็จ  ซึ่งตรรกะดังกล่าวแสดงไว้ดังรูปที่ 7.14
โดยที่

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

                  ในกรณีเป็นกราฟแบบมีทิศทางหรือไดกราฟ  แมทริกซ์ประชิดจะมีลูกศรเป็นตัว
กำหนดทิศทาง ตัวอย่าง เช่น จากรูปที่ 7.15(b)

ลิสต์ประชิด (Adjacency List)
                ลิสต์ประชิดจะใช้โครงสร้างลิงก์ลิสต์ในการจัดเก็บข้อมูล  โดยในที่นี้  เราจะใช้
ซิงเกิลลิงก์ลิสต์เพื่อจัดเก็บเวอร์เท็กซ์  แต่ก็ขึ้นอยู่กับการประยุกต์ใช้งานเป็นสำคัญ  กล่าวคือ
ยังสามารถใช้ดับเบิลลิงก์ลิสต์หรือเซอร์คูลาร์ลิงก์ลิสต์แทนก็ได้ สำหรับพอยน์เตอร์ทางซ้ายมือ
ที่ชี้ไปตามแนวดิ่งนั้นเป็นลิสต์ที่เชื่อมโยงของแต่ละเวอร์เท็กซ์ ในขณะที่พอยน์เตอร์ที่ชี้ไปทาง
ขวาเป็นพอยน์เตอร์ที่ชี้จากเฮดพอยน์เตอร์ของเวอร์เท็กซ์เพื่อเชื่อมโยงไปยังเอดจ์โดยในที่นี้
จะเป็นตัวอย่างกราฟแบบไม่มีทิศทางดังรูปที่ 7.16 สังเกตเส้นทางจากเวอร์เท็กซ์  B ไปยัง
เวอร์เท็กซ์ A, C  และ E ซึ่งในการค้นหาเอดจ์ในลิสก์ประชิด  เราจะเริ่มต้นที่เวอร์เท็กซ์B
เพื่อท่องไปยังลิงก์ลิสต์ที่เชื่อมโยงไปยัง A แล้วไปยัง C โดยสิ้นสุดที่ E

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

 Minimum  Spanning  Tree

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

                  ต่อไปนี้เป็นตัวอย่างการหาระยะทางที่สั้นที่สุดในสแปนนิงทรีจากกราฟที่กำหนด
ให้ โดยเริ่มจากเวอร์เท็กซ์  

    

        

                  เริ่มจากเวอร์เท็กซ์     A หาเวอร์เท็กซ์ข้างเคียงของ A  พบว่า  B  C      และ
   D    คือ เวอร์เท็กซ์ข้างเคียง  จากเวอร์เท็กซ์ข้างเคียง  ทั้ง 3 เลือกเอดจ์ (แสดงเป็นเส้น
ประ) ที่มีน้ำหนักน้อยที่สุด พบว่าเอดจ์ (A,D) มีน้ำหนักน้อยสุด  คือ 1 จึงเลือกเวอร์เท็กซ์
D เป็นเวอร์เท็กซ์ถัดมา

         

                                                                         บทที่ 5 

ทรี  ( Trees )

ทรี

                       ทรีเปรียบเสมือนกับต้นไม้ที่มีราก (Root) และมีลำต้นที่แผ่กิ่งก้านสาขา  โดยแต่ละ
กิ่ง(Branch)ก็จะมีการผลิใบ (Leaf) ไปทั่ว ซึ่งเป็นไปตามความสัมพันธ์ในลักษณะแบบลำดับชั้น
(Hierarchical Relationship) และตัวทรีมีโครงสร้างแบบลำลับชั้นนี้เอง จึงมักนำไปใช้เพื่อนำ
เสนอเป็นแผนผังองค์กร (Organization Chart) โครงสร้างไดเรกทอรี (Diractory) หรือแม้กระ
ทั่งสมาชิกครอบครัวของทรีเอง

                   ทรีประกอบด้วยโหนด (Node) ที่ใช้สำหรับบรรจุข้อมูล โดยจะมีกิ่งซึ่งเป็นเส้นที่เชื่อม
โยงโหนดเข้าด้วยกันที่เรียกว่าบรานช์ (Branch) จำนวนของบรานช์ที่สัมพันธ์กับโหนดเรียกว่าดีกรี
(Degree) และ ถ้าหากทรีนั้นเป็นทรีที่ไม่ใช่ที่ว่าง โหนดแระจะเรียกว่ารูท (Root) โดยโหนดทุก ๆ
โหนดยกเว้นรูทโหนดจะมีเพียง 1 Predecessor ในขณะที่ Successor อาจเป็น 0 หรือ 1 หรือ
มากกว่า 1 ก็ได้

1. โหนดแรก (Root Node)

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

- โหนดพ่อ (Parents) คือโหนด A,B และ F ซึ่งก็คือโหนดที่มี Successor

- โหนดลูก (Children) คือโหนด B,E,F,C,D,G,H และ I ซึ่งก็คือโหนดที่มี Predecessor

- โหนดพี่น้อง (Siblings) คือโหนด {B,E,F},{C,D}และ{G,H,I}

- โหนดใบ (Leaf Node) คือโหนด C,D,E,G,H และ I ซึ่งก็คือโหนดที่ไม่มี Successor

- ดีกรีทั้งหมดของทรี มีค่าเท่ากับ 8

- ดีกรีทั้งหมดของโหนด F มีค่าเท่ากับ 3

- จำนวนของ Leaf โหนด มีค่าเท่ากับ 6

- ระดับความสูงหรือความลึกของทรี คำนวณได้จากสูตร Height =2+1=3

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

รูปแบบการนำเสนอโครงสร้างข้อมูลทรี (Tree Representation)

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

1. แบบโครงสร้างทรีทั่วไป (General Tree)
                   เป็นรูปแบบการนำเสนอเหมือนกับผังองค์กรทั่วไปที่ลดหลั่นเป็นลำดับชั้น ซึ่งรูปแบบดังกล่าว ถือว่าเป็นรูปแบบของทรีที่นิยมใช้งานโดยทั่วไป โดยตัวอย่างแสดงไว้ดังรูปที่6.3 (a)

2.แบบย่อหน้า (Indented List)
                เป็นรูปแบบที่คล้ายกับการเขียนโปรแกรมเชิงโครงสร้าง  ที่ใช้ย่อหน้าเป็นตัวกำหนดรูป
แบบของโครงสร้างในส่วนระดับย่อย ๆ ลงไป โดยตัวอย่างดังกล่าวแสดงไว้ดังรูปที่ 6.3 (b)

3.แบบวงเล็บ (Parenthetical List)
                 รูปแบบนี้มีความคล้ายคลึงกับการแทนข้อมูลด้วยนิพจน์คณิตศาสตร์ด้วยการใช้เครื่องหมาย
วงเล็บกำกับ  ซึ่งนำเสนอไว้ดังรูปที่ 6.3 ( c )

ไบนารีทรี (Binary Tees)

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

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

 - ความสูงน้อยที่สุดของทรี (Minimum Height)                   หากต้องการจัดเก็บโหนดจำนวน N โหนดในไบนารีทรี ความสูงน้อยที่สุดของทรีดัง
กล่าวสามารถคำนวณได้จากสูตร

Hmin = [log2N]+

- จำนวนโหนดน้อยที่สุด (Minimum Nodes)
                เราสามารถคำนวณเพื่อการตัดสินใจว่า จำนวนโหนดน้อยที่สุดที่สามารถมีได้ใน
ไบนารีทรีมีจำนวนเท่าไรได้จากสูตร

Nmin =H

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

Nmix =2H-1

- ความสมดุล (Balance)
                ความสมดุลของไบนารีทรีจะสามารถทราบได้จากค่า Balance Factor เท่ากับ
0 ซึ่งค่าดังกล่าวคำนวณได้จากการนำความสูงของซับทรีด้านซ้าย (HL) มาหักลบกับความสูงของ
ซับทรีด้านขวา (HR) ที่เป็นไปตามสูตรดังนี้

B = Hl-HR

และจากสูตรดังกล่าว  ความสมดุลของทรีจากรูปที่ 6.5 ก็คือ (a)=0,(b)=0,(c)=1,(d)=1,(e)=0,
(f)=1,(g)=-2 และ (h)=2

- แบบสมบูรณ์จะมี Subtree ด้านซ้ายและขวาเท่ากัน

             

   

- แบบเกือบสมบูรณ์ Subtree  ทางด้านซ้ายจะไม่มี

                

              

         

การแทนไบนารีทรีด้วยลิงก์ลิสต์

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

การท่องเข้าไปในไบนารีทรี (Binary tree traversals)
                          การท่องเข้าไปในไบนารีทรีซึ่งแต่ละโหนดอย่างน้อยจะต้องถูกกระทำ 1 ครั้งโดยตัว
อย่างการกระทำ เช่น การค้นหาที่ต้องเดินทางผ่านโหนดแต่ละโหนดตามลำดับ เป็นต้น และโดยปกติ
วิธีการท่องเข้าไปในทรีจะมีอยู่2วิธีด้วยกันคือ วิธีท่องแบบแนวลึก (Depth-First) วิธีการท่องแบบ
แนวกว้าง (Breadth First)

วิธีการท่องแบบแนวลึก (Depth-First Traversals)
                    เป็นวิธีการท่องเข้าไปในทรีด้วยการเดินทางผ่านรูทโหนดลงไปยังโหนดลูก ๆ ซึ่งมี
ทั้งฝั่งด้านซ้ายและด้านขวา ดังนั้นจึงมีการบัญญัติคำย่อเพื่อใช้งานดังนี้คือ

         N แทนรูทโหนด
         L แทนซับทรีด้านซ้าย
         R แทนซับทรีด้านขวา

                          สำหรับวิธีการท่องแบบแนวลึก ในที่นี้จะขอกล่าวเพียง 3 วิธีมาตรฐานที่นิยมใช้
กันอย่างแพร่หลาย ซึ่งประกอบด้วยวิธี Preorder,Inorder และ Postorder

  (a) Preorder traversal       

   

(b) Inorder traversal         

          

- แบบพรีออร์เดอร์ (Proerder Traversal : NLR)

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

- แบบอินออร์เดอร์ (Postorder Traversal:LRN)

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

- แบบโพสต์ออร์เดอร์ (Postorder Traversal : LRN)

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

- วิธีการท่องแบบแนวกว้าง (Breadth-First Traversals)
                    เป็นวิธีสุดท้ายของการท่องเข้าไปในทรีด้วยการกระทำทีละระดับจากบน
ลงล่าง  โดยจะเริ่มต้นจากรูทโหนด  แล้วจึงค่อยเข้าถึงแต่ละโหนดในแต่ละระดับตามแนว
กว้างจากซ้ายไปขวา จนกระทั่งครบทุกระดับ ซึ่งแสดงตัวอย่างการทำงานได้ดังรูปที่ 6.11

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

การค้นหาโหนดที่มีค่าต่ำสุด (Find the Smallest Node)
                 จากไบนารีเสิร์ชทรีดังรูปที่ 6.17 จะเห็นได้ว่าโหนดที่มีค่าต่ำสุดก็คือ 12 ซึ่งจะอยู่ตำ
แหน่งโหนดใบด้านซ้ายของทรี ดังนั้นการค้นหาโหนดที่เก็บค่าต่ำสุดในทรี ก็สามารถทำได้ง่ายมาก
ด้วยการเดินตามไปยัง บรานช์ทางซ้ายมือไปจนกระทั่งถึงโหนดใบ (Leaf Node) แล้วก็จะพบ
โหนดที่มีค่าต่ำที่สุดในไบนารีเสิร์ชทรีเอง

การค้นหาที่มีค่าสูงสุด (Find the Largest Node)
                      การค้นหาโหนดที่มีค่าสูงสุดใน BST จะเป็นวิธีแบบตรงกันข้ามกับแบบแรก ดังนั้น
การค้นหาจะเริ่มต้นจากรูทโหนดและเดินตามไปยังบรานช์ฝั่งขวา จนกระทั่งพบโหนดที่มีค่าสูงสุด

การค้นหาโหนดตามที่ต้องการ (Find a Requseted Node)
                การค้นหาข้อมูลตามที่ต้องการในไบนารีเสิร์ชนั้นทำงานอย่างไร โดยพิจารณาจากรูป
ที่ 6.18 โดยสมมติว่าค่า Target  ที่ต้องการค้นหาคือ 19 และเมื่อได้นำค่านี้ไปเทียบกับรูทโหนด
(ค่ากึ่งกลางในอาร์เรย์)แล้วก็จะพบว่าค่าที่ต้องการค้นหานั้นมีค่าน้อยกว่ารูทโหนด  ดังนั้นจึงทำการ
เปรียบเทียบค่า Target กับทรีด้านซ้ายเท่านั้น  ซึ่งก็คือซับทรี  16 นั่นเอง  ผลปรากฏว่าค่าที่ต้อง
การมีค่ามากกว่ารูทโหนดของซับทรี จึงทำการตรวจสอบกับโหนดด้านขวาต่อไปจนพบในที่สุด

           

การดำเนินงานในไบนารีเสิร์ชทรี (BST Operations)
                สำหรับการดำเนินงานในไบนารีเสิร์ชในที่นี้  จะกล่าวถึงฟังก์ชันการแทรกโหนดและ
การลบโหนดออกจากไบนารีเสิร์ชทรี

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

          

การลบโหนด (Deletion)

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

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

เอวีแอลเสิร์ชทรี  (AVL Search Trees)        
               หลังจากที่ได้ศึกษารายละเอียดเกี่ยวกับไบนารีเสิร์ชทรีแล้ว  คุณสมบัติของ BST
สามารถนำไปประยุกต์ใช้งานให้เกิดประโยชน์มากมาย  แต่อย่างไรก็ตาม  ก็มีปัญหาหนึ่งซึ่งถือ
ว่าเป็นปัญหาหลีกของ BST ก็ว่าได้  นั่นก็คือความไม่สมดุลของทรี  ซึ่งต่อมาจึงมีการคิดค้นและ
พัฒนาโครงสร้างทรีแบบเอวีแอลขึ้นเอวีแอลทรีก็คือไบนารีเสิร์ชทรีที่ซับทรีด้านซ้ายและซับทรี
ด้านขวาจะมีค่า Balance Factor เท่ากับ +1.0 หรือ -1 เท่านั้น ที่เป็นไปตามสูตรด้านล่างต่อ
ไปนี้  โดยที่ HL คือความสูงของซับทรีด้านซ้ายส่วน HR ก็คือซับทรีด้านขวา  ซึ่งทั้งสองจะอยู่
ภายใต้สัญลักษณ์ | | ที่หมายถึงเครื่องหมาย Absolute

                ค่า Balance Factor ของทุกโหนดจะต้องมีค่าเท่ากับ +1 ,0 หรือ-1 ดังนั้นผลลัพธ์
ที่ได้จากหนึ่งในสามนี้ หมายถึง

• +1 หมายถึง ซ้ายสูง (Left High : LH)
• 0   หมายถึง สูงเท่ากัน (Even High :EH)
• -1  หมายถึง ขวาสูง (Right High : RH)