บทที่ 7 Binary Tree

Binary Tree

            Binary Tree มีลักษณะเหมือนกับ Tree ปกติแต่มีคุณสมบัติพิเศษ คือ “แต่ละโหนดจะมีโหนดลูกได้ไม่เกิน 2 โหนด” หรือพูดอีกนัยหนึ่งก็คือ แต่ละโหนดใน binary tree จะมีดีกรีได้ไม่เกิน 2
Complete Binary Tree
            Complete Binary Tree หรือต้นไม้ไบนารีแบบสมบูรณ์ มีลักษณะคล้ายกับ Binary Tree แต่มีข้อพิเศษ คือ

1.      ทุกโหนดที่ไม่ใช่ Leaf Node จะต้องมีโหนดลูก 2 โหนด

2.      Leaf Node จะต้องอยู่ในระดับเดียวกัน

Almost  Complete  Binary  Tree
            Almost  Complete  Binary  Tree หรือ ไบนารี่ทรีเกือบ จะมีโหนดเฉพาะบางส่วนอาจเป็นโหนดซ้ายหรือโหนดขวา 

การท่องไปในทรี (Tree Traversal)สามารถท่องเข้าไปในทรีเพื่อดูข้อมูล ได้ 3 วิธีด้วยกันคือ
1. Pre-order
2. In-order
3. Post-order
1.แบบพรี-ออเดอร์ (Pre-order)
            มีลักษณะการวิ่งในแนวลึกก่อน (Depth-first Order)
อัลกอริทึมการวิ่งแบบพรี-ออเดอร์

2.แบบอิน-ออเดอร์ (In-Order)
            มีการวิ่งลักษณะแบบสมดุล (Symmetric Order)
อัลกิริทึมการวิ่งแบบอิน-ออเดอร์
3.แบบโพสต์-ออเดอร์(Post-Oder)
             อัลกิริทึมการวิ่งแบบโพส-ออเดอร์

บทที่ 6 โครงสร้างข้อมูลแบบ Queue

 โครงสร้างข้อมูลแบบ Queue
        โครงสร้าง  Queue เป็น list ของ Element (รายการ) ที่มีการเพิ่ม 1 ทางและลบข้อมูลออก 1 ทางมีคุณสมบัติที่เข้าก่อนออกก่อน FIFO (First in First out) ซึ่งในชีวิตประจำวันเช่น การเข้าQueue เพื่อเข้ารับการบริการอย่างไรอย่างหนึ่ง เช่น การเข้า Queue เพื่อจ่ายเงินหรือซื้อของ สำหรับระบบการแบ่งเวลาในการใช้งานคอมพิวเตอร์จะมีการกำหนดลำดับความสำคัญ และการเข้า Queue ทำงานตามลำดับก่อนหลัง
การสร้าง Queue
        ในการสร้าง Queue สามารถจัดเก็บได้หลายลักษณะ แต่ทั่วไปจะใช้การเก็บแบบ list ทางเดียวหรือ Array แบบต่อเนื่องโดยต้องใช้ pointer อีก 2 ตัว ชื่อว่า F (front pointer) เป็นตัวชี้ที่เก็บตำแหน่งส่วนหน้า และ R (rear pointer) เป็นตัวชี้ที่เก็บตำแหน่งส่วนท้าย โดยข้อมูลจะเข้าไปทาง rear หรือส่วนท้ายและจะออกจาก Queue ทาง front หรือส่วนหน้าเท่านั้น ถ้าQueue ว่างเปล่า F และ R มีค่า = 0 ทั้งคู่ หรือ F = 0 = null มีการทำงาน 2 อย่าง คือการเข้า Queue (insertion) และการออกจาก Queue (deletion) ถ้า Queue มีชื่อ Q(5)หมายถึงชื่อ Q มีเนื้อนที่ 5 ที่

การทำงานของคิว
      ถ้ามีการกำหนดการสร้าง Queue โดย Array ยังคงตัวชื้ 2 ตัวเช่นเดียวกับแบบ list ค่า F=R=0 หรือ null

 
การดำเนินงานของคิว(Queue Operations)
        การดำเนินการพื้นฐานของคิว ข้อมูลสามารถเพิ่มได้ตรงส่วน Rear ในขณะที่การลบข้อมูลจะลบตรงส่วน Front ส่วนการอ่านข้อมูลก็สามารถทำการอ่านได้ทั้งส่วน Front และส่วน Rear ถึงแม้ว่าโครงสร้างข้อมูลแบบคิวจะมีส่วนคล้ายคลึงกับโครงสร้างข้อมูลแบบ สแต็ก แต่หนึ่งในโครงสร้างที่แสดงถึงความแตกต่างระหว่างโครงสร้างทั้งสองก็คือ ในการสร้างคิวเพื่อใช้งานจำเป็นต้องมีส่วนที่ใช้ติดตามทั้งส่วนหัวคิวและ ท้ายคิว นั่นหมายความว่าจะต้องมีพอยน์เตอร์ถึงสองตัวโดยพอยน์เตอร์แต่ละตัวจะชี้ตรง ตำแหน่งปลายทั้งสองด้าน ซึ่งก็คือส่วน Front และ Rear นั่นเอง ในขณะที่สแต็กจะมีเพียงพอยน์เตอร์เดียวที่ใช้จัดเก็บข้อมูลตรงส่วน Top ของแสต็กเท่านั้น
ฟังก์ชั่นการดำเนินงานพื้นฐานของคิวประกอบด้วย
          1. ฟังก์ชั่น Enqueue
          2. ฟังก์ชั่น Dequeue
          3. ฟังก์ชั่น Queue Front
          4. ฟังก์ชั่น Queue Rear
ฟังก์ชั่น Enqueue
         ฟังก์ชั่น Enqueue เป็นการนำข้อมูลเพิ่มเข้าไปในคิว โดยหลังจากที่ข้อมูลได้เพิ่มเข้าไปในคิวแล้วสมาชิกใหม่ที่เพิ่มเข้าไปจะนำไป ต่อจากส่วน Rear  ซึ่งการเพิ่มข้อมูลเข้าไปในคิวก็ไม่ได้แตกต่างไปจากสแต็กตรงที่จะต้องมี พื้นที่ว่างพอที่จะใส่สมาชิกใหม่เข้าไป  ดังนั้นหากมีพื้นที่ไม่เพียงพอต่อการเพิ่มสมาชิกใหม่เข้าไปในคิวก็จะเกิด สถานะ Overflow
ฟังก์ชั่น Dequeue
        ฟังก์ชั่น Dequeue เป็นการลบข้อมูลออกจากคิว โดยข้อมูลที่อยู่ส่วน Front จะถูกคืนค่าส่งไปยังยูสเซอร์หรือโมดูลที่เรียกใช้จากนั้นก็จะนำข้อมูลนี้ออก จากคิวในกรณีที่มีการเรียกใช้ฟังก์ชั่นนี้และหากภายในคิวไม่มีข้อมูล ก็จะทำให้เกิดสถานะ Underflow
ฟังก์ชั่น Queue Front
        ฟังก์ชั่น Queue Front ข้อมูลที่อยู่ส่วน Front นั้น สามารถดึงขึ้นมาใช้งานได้ด้วยฟังก์ชั่น Queue Front ฟังก์ชั่นดังกล่าวจะทำการคืนค่าข้อมูลกลับไปยังผู้เรียกใช้โดยไม่มีการ เปลี่ยนแปลงใด ๆ ในคิวอย่างไรก็ตามหากในคิวว่างเปล่า และมีการเรียกใช้งานฟังก์ชั่นนี้  ก็จะทำให้เกิดสถานะของข้อผิดพลาดที่เรียกว่า Underflow
ฟังก์ชั่น Queue Rear
        ฟังก์ชั่น Queue Rear มีลักษณะการทำงานเช่นเดียวกันกับฟังก์ชั่น Queue Front แต่จะแตกต่างกันตรงที่เป็นการดึงข้อมูลตรงส่วนท้ายคิวหรือ Rear ออกมาใช้งานในกรณีที่เรียกใช้ฟังก์ชั่นนี้และปรากฏว่าภายในคิวว่างเปล่าก็จะ ทำให้เกิดสถานะของข้อผิดพลาดที่เรียกว่า Underflow
การออกแบบคิวด้วยอาร์เรย์ (Queue Array Design)
          ถึงแม้ว่าการสร้างคิวด้วยโครงสร้างข้อมูลแบบลิงก์ลิสต์จะเป็นที่ นิยมมากก็ตามแต่ลิงก์ลิสต์ก็ไม่ใช่หนทางเดียวที่นำมาสร้างคิว ดังนั้นในที่นี้จึงขอกล่าวรายละเอียดการสร้างคิวด้วยอาร์เรย์ซึ่งถือเป็น วิธีหนึ่งที่มีความนิยมเช่นกัน เนื่องจากพัฒนาได้ง่ายกว่าในทำนองเดียวกันการเพิ่มข้อมูลเข้าไปในคิวด้วย โครงสร้างข้อมูลแบบอาร์เรย์นั้น ก็จะเพิ่มเข้าในส่วนท้ายคิวที่เรียกว่า Rear ส่วนการนำข้อมูลออกก็จะดำเนินการที่ส่วนของหัวคิวที่เรียกว่า Front ให้พิจารณารูปที่ 1 ที่เปรียบเทียบหลักการของคิวกับคิวที่สร้างด้วยอาร์เรย์ ให้สังเกตรูปที่ 1 จะเห็นว่ามี 5 ช่องแรกที่ว่างซึ่งเกิดจากการ Dequeue ข้อมูล A,B,C,D และ E ออกไป ทำให้เกิดพื้นที่ว่าง ในขณะที่ส่วนท้ายคิวก็ยังมีพื้นที่ว่างเหลือพอที่จะเพิ่มข้อมูลต่อท้ายเข้า ไปอีก

จากรูปที่ 1 จะเห็นได้ว่า ภายในคิวสามารถบรรจุสมาชิกได้สูงสุด 17 อิลิเมนต์ด้วยกัน โดยขณะนี้มีข้อมูลภายในคิวอยู่ 7 ข้อมูลคือ F,G,H,I,J,K และ L พอยน์เตอร์ส่วน Front ชี้ไปยังดรรชนี 5 และ พอยน์เตอร์ส่วน Rear ชี้ไปยังดรรชนี 11 ซึ่งการอ้างอิงตำแหน่งคิวด้วยอาร์เรย์นั้นจะใช้เลขดรรชนีเป็นหลัก
และด้วยการใช้โครงสร้างอาร์เรย์ในการสร้างคิว จะเป็นการจัดสรรหน่วยความจำแบบคงที่ ดังนั้น จึงสามารถเกิดกรณีคิวเต็มได้ หากมีการเพิ่มจำนวนสมาชิกมากกว่าที่ประกาศไว้ แต่อย่างไรก็ตามในกรณีที่มีการเพิ่มข้อมูลต่อท้ายจนเต็ม ในขณะที่ส่วนหน้าของ Front ที่ถูก Dequeue ไปยังมีที่ว่างอยู่ เช่นดังรูปที่ 2

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

ครงสร้างข้อมูลแบบคิววงกลม (Circular Queue) หรือ Dequeue

         การจัด Array ให้ทำงานเป็น Queue แบบธรรมดา มีข้อจำกัดคือ บางครั้ง Queue มีที่ว่างอยู่ด้าน F แต่ด้าน R เต็ม ทำให้ไม่สามารถนำข้อมูลเข้า Queue ได้ ดังนั้นการนำที่ว่างในส่วนหน้า (F) มาใช้อีก ทำได้โดยให้ส่วนท้ายของ Queue   โครงสร้าง Queue   แบบนี้เรียกว่า   Circular Queue หมายความว่า Queue นั้นเต็ม แต่ Queue แบบ Circular เมื่อ R=N จะปรับให้ R=1   ในกรณีค่า R=ค่าสุดท้ายใน Array ทั่วไป จะหมายถึง Queue เต็ม แต่กรณีของ  Circular Queue สามารถให้ R เลื่อนกลับตำแหน่งแรกได้ ถ้าตำแหน่งนั้นว่าง