DTS 08-26-08-2552

สรุป Tree

ทรี หรือโครงสร้างข้อมูลแบบต้นไม้ ประกอบด้วยโหนด (node) ซึ่งเป็นส่วนที่เก็บข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก

โดยทั่วไปแต่ละโหนดในทรีจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้หลาย ๆ โหนด
หรืออาจกล่าวได้ว่าแต่ละโหนดของทรีเป็น
โหนดแม่ (parent or mother node) ของโหนดลูก (child or son node)
ซึ่งเป็นโหนดที่อยู่ในระดับต่ำลงมาหนึ่งระดับโดยสามารถมีโหนดลูกได้หลาย ๆ โหนด
และโหนดต่าง ๆ ที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (siblings)
ทุก ๆ โหนดต้องมีโหนดแม่เสมอยกเว้นโหนดในระดับสูงสุดไม่มีโหนดแม่เรียกโหนดนี้ว่า
โหนดราก (root node) โหนดที่ไม่มีโหนดลูกเลยเรียกว่า โหนดใบ (leave node)
และเส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง (branch)


Binary Tree

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

นิยามของทรี

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


นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
การกำหนดนิยามของ ทรีอาจกำหนดได้อีกวิธีหนึ่งเป็นการนิยามแบบรีเคอร์ซีฟ คือ ทรีประกอบด้วยสมาชิกที่เรียกว่า โหนด โดยที่
(1) ว่าง ไม่มีโหนดเลยเรียกว่า นัลทรี (null tree)
(2) มีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือแบ่งเป็นทรีย่อย (sub tree) T1, T2, T3, ... , Tk (โดยที่ k³0) และทรีย่อยต้องมีคุณสมบัติเป็นทรี


นิยามที่เกี่ยวข้องกับทรี มีนิยามต่าง ๆ ที่เกี่ยวข้องกับ ทรีมากมายดังต่อไปนี้
(1) ฟอร์เรสต์ (forest) หมายถึงกลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออก หรือเซตของทรีที่แยกจากกัน (disjoint trees)
(2) ทรีที่มีแบบแผน (ordered tree) หมายถึงทรีที่โหนดต่าง ๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ก่อน ไปทางขวา ไปทางซ้าย เป็นต้น
(3) ทรีคล้าย (similar tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกันนั่นเองโดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
(4) ทรีเหมือน (equivalent tree) หมายถึงทรีที่เหมือนกันโดยสมบูรณ์ (equivalence) โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
(5) กำลัง (degree) หมายถึง จำนวนทรีย่อยของโหนดนั้น ๆ
(6) ระดับของโหนด (level of node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้โหนดรากของทรีนั้นอยู่ที่ระดับ 1 และกิ่งแต่ละกิ่งมีความเท่ากันหมดคือยาวเท่ากับ 1 หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1


การแทนที่ทรีในความจำหลัก

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


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

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

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


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


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

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

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

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

DTS 07-05-08-2552

สรุป Queue

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

การทำงานของคิว (queue)

การใส่สมาชิกตัวใหม่ลงในคิวเรียกว่า Enqueue

และการนำข้อมูลออกจาก คิวเรียกว่า Dequeue

ซึ่งมีรูปแบบคือ enqueue () การแทนที่ข้อมูลของคิว (queue)

1.การแทนที่ข้อมูลแบบลิงค์ลิสตจะประกอบไปด้วย2ส่วนคือ

1.1Head Node จะประกอบไปด้วย3ส่วนคือ พอยเตอร์จำนวน2ตัวคือ Front และ Rear

กับจำนวนสมาชิกในคิว

1.2Data Node จะประกอบไปด้วยข้อมูล Data และพอยเตอร์ที่่ชี้ไปยัง ข้อมูลตัวถัดไป

2.การแทนที่ข้อมูลแบบอาร์เรย์

การนำข้อมูลเข้าสู่โครงสร้างคิว (enqueue)

เป็นกระบวนการอ่านข้อมูลจากภายนอกเข้าสู่โครงสร้างคิวทางด้านปลายที่พอยน์เตอร์ R

ชี้อยู่ โดยพอยน์เตอร์ R จะเปลี่ยนตำแหน่ง ชี้ไปยังตำแหน่งที่ว่างตำแหน่งถัดไป

ก่อนนำข้อมูลเข้าสู่โครงสร้างคิวข้อควรคำนึงถึง คือ ในขณะที่คิวเต็ม (Full Queues)

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

ซึ่งจะทำให้เกิดปัญหา “Overflow” ขึ้น

การดำเนินการเกี่ยวกับคิว ได้แก่
1.) Create Queue
เป็นการจัดสรรหน่วยความจำให้กับ Head Node และให้ค่า pointer ทั้ง 2 ตัวมีค่าป็น null และจำนวนสมาชิกเป็นศูนย์

2.) Enqueue
เป็นการเพิ่มข้อมูลเข้าไปในคิว ซึ่ง pointer rear จะเปลี่ยน

3.) Dequeue
เป็นการนำข้อมูลออกจากคิว ซึ่ง pointer front จะเปลี่ยน

4.) Queue Front
เป็นการนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดง

5.) Queue Rear
เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง

6.) Empty Queue
เป็นการตรวจสอบว่าคิวว่างหรือไม่

7.) Full Queue
เป็นการตรวจสอบว่าคิวเต็มหรือไม่

8.) Queue Count
เป็นการนับจำนวนสมาชิกที่อยู่ในคิว

9.) Destroy Queue
เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว วิธีการคือ ต้องทำการ Dequeue ทีละตัว แล้วจึงจะ Destroy

DTS 06-30-06-2552

stack (ต่อ)

การเเทนที่ข้อมูลของสเเตกแบบอะเรย์การดำเนินงานเกี่ยวกับสแตก ได้แก่

1.Creste stackคือ สร้าง stack head node
2.Push stackคือ เพิ่มรายการใน stack
3.Pop stackคือ ลบรายการใน stack
4.Stack topคือ เรียกใช้งานรายการข้อมูลที่อยู่บนสุดของ stack
5.Empty stackคือ ตรวจสอบว่า stack ว่างเปล่าหรือไม่
6.Full stackคือ ตรวจสอบว่า stack เต็มหรือไม่
7.Stack countคือ ส่งค่าจำนวนรายการใน stack
8.Destroy stackคือ การคืนหน่วยความจำของทุก node ใน stack ให้ระบบ

ลำดับการทำงานของตัวดำเนินการทางคณิตศาสตร์ (Operator Priority)
มีการลำดับความสำคัญของตัวดำเนินการจากลำดับสำคัญมากสุดไปน้อยสุด
คือ ลำดับที่มีความสำคัญมากที่ต้องทำก่อน ไปจนถึงลำดับที่มีความสำคัญน้อยสุดที่ไว้ทำทีหลัง ดังนี้

1. ทำในเครื่องหมายวงเล็บ
2. เครื่องหมายยกกำลัง ( ^ )
3. เครื่องหมายคูณ ( * ) , หาร ( / )
4. เครื่องหมายบวก ( + ) , ลบ ( - )

การใช้ สแตค เพื่อแปลรูปนิพจน์ทางคณิตศาสตร์รูปแบบนิพจน์ทางคณิตศาสตร์
• นิพจน์ Infix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator)
อยู่ระหว่างตัวดำเนินการ (Operands) เช่น A+B-C
• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator)
อยู่หลังตัวดำเนินการ (Operands) เช่น AC*+


การแปลงนิพจน์ Infix เป็น นิพจน์ Postfix
เราสามารถแปลงนิพจน์ Infix ให้เป็น Postfix ได้โดยอาศัยสแตค
ที่มีคุณสมบัติการเข้าหลังออกก่อนหรือ LIFO โดยมีอัลกอริทึมในการแปลงนิพจน์ ดังนี้

1. ถ้าข้อมูลเข้า (input) เป็นตัวถูกดำเนินการ (operand) ให้นำออกไปเป็นผลลัพธ์ (output)
2. ถ้าข้อมูลเข้าเป็นตัวดำเนินการ (operator) ให้ดำเนินการดังนี้
2.1 ถ้าสแตคว่าง ให้ push operator ลงในสแตค
2.2 ถ้าสแตคไม่ว่าง ให้เปรียบเทียบ operator ที่เข้ามากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค
2.2.1 ถ้า operator ที่เข้ามามีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตคให้ pusสแตค
2.2.2 ถ้า operator ที่เข้ามามีความสำคัญน้อยกว่าหรือเท่ากับ operator ที่อยู่ในตำแหน่ง TOP
ของสแตค ให้ pop สแตคออกไปเป็นผลลัพธ์ แล้วทำการเปรียบเทียบ operator
ที่เข้ามากับ operator ที่ตำแหน่ง TOP ต่อไป จะหยุดจนกว่า operator ที่เข้ามา
จะมีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตค แล้วจึง push operator
ที่เข้ามานั้นลงสแตค
3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตค
4. ถ้าข้อมูลเข้าเป็นวงเล็บปิด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์
จนกว่าจะถึงวงเล็บ เปิด จากนั้นทิ้งวงเล็บเปิดและปิดทิ้งไป
5. ถ้าข้อมูลเข้าหมด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าสแตคจะว่าง