ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์
ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับ
ชั้น (Hierarchical Relationship)
ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงาน
ต่าง ๆ อย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดง
ความสัมพันธ์ระหว่างข้อมูล แต่ละโหนดจะมีความสัมพันธ์กับโหนดใน
ระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆ โหนด
เรียกโหนดดังกล่าวว่า โหนดแม่ (Parent or
Mother Node)
โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับ
เรียกว่า โหนดลูก (Child or Son Node)
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่
เรียกว่า โหนดราก (Root Node) โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน
เรียกว่า โหนดพี่น้อง (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) หมายถึง
จำนวนทรีย่อยของโหนด นั้น ๆ
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 โหนด
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็น
ไบนารีทรี มีลำดับขั้นตอนการแปลง ดังต่อไปนี้
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) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
(3) เยือนโหนดราก
เอ็กซ์เพรสชันทรี (Expression Tree)
เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์
ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนด
เก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ
(Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรือ
อาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression)
นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอน
ในการคำนวณตามความสำคัญของเครื่องหมายด้วย
โดยมีความสำคัญตามลำดับดังนี้
- ฟังก์ชัน
- วงเล็บ
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน (unary)
- คูณ หรือ หาร
- บวก หรือ ลบ
- ถ้ามีเครื่องหมายที่ระดับเดียวกัน
ให้ทำจากซ้ายไปขวา
ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree)
เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนด
ในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุก
โหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่า
หรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวา
และในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน
ปฏิบัติการในไบนารีเซิร์ชทรี ปฏิบัติการ
เพิ่มโหนดเข้าหรือดึงโหนดออกจากไบนารีเซิร์ชทรี
ค่อนข้างยุ่งยากกว่าปฏิบัติการในโครงสร้างอื่น ๆ
เนื่องจากหลังปฏิบัติการเสร็จเรียบร้อยแล้วต้อง
คำนึงถึงความเป็นไบนารีเซิร์ชทรีของทรีนั้นด้วย
ซึ่งมีปฏิบัติการดังต่อไปนี้
(1) การเพิ่มโหนดในไบนารีเซิร์ชทรี การเพิ่มโหนดใหม่
เข้าไปในไบนารีเซิร์ชทรี ถ้าทรีว่างโหนดที่เพิ่มเข้าไปก็จะเป็น
โหนดรากของทรี ถ้าทรีไม่ว่างต้องทำการตรวจสอบว่าโหนดใหม่
ที่เพิ่มเข้ามานั้นมีค่ามากกว่าหรือน้อยกว่าค่าที่โหนดราก ถ้ามีค่า
มากกว่าหรือเท่ากันจะนำโหนดใหม่ไปเพิ่มในทรีย่อยทางขวา
และถ้ามีค่าน้อยกว่านำโหนดใหม่ไปเพิ่มในทรีย่อยทางซ้าย
ในทรีย่อยนั้นต้องทำการเปรียบเทียบในลักษณะเดียวกันจน
กระทั่งหาตำแหน่งที่สามารถเพิ่มโหนดได้ ซึ่งโหนดใหม่ที่
เพิ่มในทรีในที่สุดจะต้องเป็นโหนดใบ
(2) การดึงโหนดในไบนารีเซิร์ชทรี
หลังจากดึงโหนดที่ต้องการออกจากทรีแล้ว
ทรีนั้นต้องคงสภาพไบนารีเซิร์ชทรีเหมือน
เดิมก่อนที่จะทำการดึงโหนดใด ๆ ออกจาก
ไบนารีเซิร์ชทรี ต้องค้นหาก่อนว่าโหนดที่
ต้องการดึงออกอยู่ที่ตำแหน่งไหนภายในทรี
และต้องทราบที่อยู่ของโหนดแม่โหนดนั้นด้วย
แล้วจึงทำการดึงโหนดออกจากทรีได้ ขั้นตอน
วิธีดึงโหนดออกอาจแยกพิจารณาได้ 3
ก. กรณีโหนดที่จะดึงออกเป็นโหนดใบ
การดึงโหนดใบออกในกรณีนี้ทำได้ง่ายที่สุด
โดยการดึงโหนดนั้นออกได้ทันที เนื่องจาก
ไม่กระทบกับโหนดอื่นมากนัก วิธีการก็คือ
ให้ค่าในลิงค์ฟิลด์ของโหนดแม่ซึ่งเก็บที่อยู่
ของโหนดที่ต้องการดึงออกให้มีค่าเป็น Null
ข. กรณีโหนดที่ดึงออกมีเฉพาะ
ทรีย่อยทางซ้ายหรือทรีย่อยทางขวาเพียง
ด้านใดด้านหนึ่ง วิธีการดึงโหนดนี้ออก
สามารถใช้วิธีการเดียวกับการดึงโหนด
ออกจากลิงค์ลิสต์ โดยให้โหนดแม่ของ
โหนดที่จะดึงออกชี้ไปยังโหนดลูกของ
โหนดนั้นแทน
ค. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้าย
และทรีย่อยทางขวาต้องเลือกโหนดมาแทนโหนดที่ถูก
ดึงออก โดยอาจจะเลือกมาจากทรีย่อยทางซ้ายหรือ
ทรีย่อยทางขวาก็ได้
- ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรี
ย่อยทางซ้ายต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อย
ทางซ้ายนั้น
- ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมา
จากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุด
ในทรีย่อยทางขวานั้น
ไม่มีความคิดเห็น:
แสดงความคิดเห็น