TREE
ทรี (tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่างโหนดจะมีความสัมพันธ์ลดหลั่นกัน เป็นลำดับชั้น (hierarchical relationship) มีกี่ชั้นก็ได้แล้วแต่งาน ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงานต่าง ๆ อย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมูล ตัวอย่างที่มีการใช้โครงสร้างข้อมูลแบบทรี เช่น แผนผังแสดงองค์ประกอบของหน่วยงานต่าง ๆ โครงสร้างสารบัญหนังสือ และโครงสร้างแสดงสารบบในหน่วยความจำสำรองในเครื่องคอมพิวเตอร์ เป็นต้น
โดยทั่วไปแต่ละโหนดในทรีจะมีความ สัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้หลาย ๆ โหนด หรืออาจกล่าวได้ว่าแต่ละโหนดของทรีเป็น "โหนดแม่" (parent or mother node) ของ "โหนดลูก" (child or son node) ซึ่งเป็นโหนดที่อยู่ในระดับต่ำลงมาหนึ่งระดับโดยสามารถมีโหนดลูกได้หลาย ๆ โหนด และโหนดต่าง ๆ ที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า "โหนดพี่น้อง" (siblings) ทุก ๆ โหนดต้องมีโหนดแม่เสมอยกเว้นโหนดในระดับสูงสุดไม่มีโหนดแม่เรียกโหนดนี้ว่า "โหนดราก" (root node) โหนดที่ไม่มีโหนดลูกเลยเรียกว่า "โหนดใบ" (leave node) และเส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า "กิ่ง" (branch) สังเกตได้จากตัวอย่าง แสดงระดับของทรีและส่วนต่าง ๆ ของทรี
(2) "ทรีที่มีแบบแผน" (ordered tree) หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน
(3) "ทรีคล้าย" (similar tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกันนั่นเองโดยไม่คำนึงถึงข้อมูลที่อยู่ใน แต่ละโหนด
(4) "ทรีเหมือน" (equivalent tree) หมายถึง ทรีที่เหมือนกันโดยสมบูรณ์ (equivalence) โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
(5) "กำลัง" (degree) หมายถึง จำนวนทรีย่อยของโหนดนั้น ๆ
(6) "ระดับของโหนด" (level of node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่โครงสร้างข้อมูลแบบทรีในความ จำหลักสามารถแทนที่แบบสแตติก หรือแบบไดนามิกก็ได้ โดยมีพอยน์เตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละโหนดต้องมีลิงค์ฟิลด์หลายลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่าง ๆ นั่นคือ จำนวนลิงค์ฟิลด์ของแต่ละโหนดขึ้นอยู่กับจำนวนของโหนดลูก การแทนที่ทรีซึ่งแต่ละโหนดมีจำนวนลิงค์ฟิลด์ไม่เท่ากัน ทำให้ยากต่อการปฏิบัติการเป็นอย่างยิ่ง มีวิธีการแทนที่ทรีในหน่วยความจำหลายวิธี วิธีที่ง่ายที่สุดคือทำให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์เท่ากัน
โดยทั่วไปแต่ละโหนดในทรีจะมีความ สัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้หลาย ๆ โหนด หรืออาจกล่าวได้ว่าแต่ละโหนดของทรีเป็น "โหนดแม่" (parent or mother node) ของ "โหนดลูก" (child or son node) ซึ่งเป็นโหนดที่อยู่ในระดับต่ำลงมาหนึ่งระดับโดยสามารถมีโหนดลูกได้หลาย ๆ โหนด และโหนดต่าง ๆ ที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า "โหนดพี่น้อง" (siblings) ทุก ๆ โหนดต้องมีโหนดแม่เสมอยกเว้นโหนดในระดับสูงสุดไม่มีโหนดแม่เรียกโหนดนี้ว่า "โหนดราก" (root node) โหนดที่ไม่มีโหนดลูกเลยเรียกว่า "โหนดใบ" (leave node) และเส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า "กิ่ง" (branch) สังเกตได้จากตัวอย่าง แสดงระดับของทรีและส่วนต่าง ๆ ของทรี
นิยามของ TREE
1. "นิยามทรีด้วยนิยามของกราฟ" เนื่องจากรูปแบบของทรี เป็นรูปแบบเฉพาะอย่างหนึ่งของกราฟ (graph) ดังนั้นเราอาจจะกำหนดนิยามของทรีด้วยนิยามของกราฟดังนี้
ทรี คือ กราฟที่ต่อเนื่องกันโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใด ๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น ทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น การเขียนรูปแบบทรีอาจเขียนได้ 4 แบบ คือ
2. "นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ" การกำหนดนิยามของ ทรีอาจกำหนดได้อีกวิธีหนึ่งเป็นการนิยามแบบรีเคอร์ซีฟ คือ ทรีประกอบด้วยสมาชิกที่เรียกว่า โหนด โดยที่ ถ้าว่าง ไม่มีโหนดเลยเรียกว่า นัลทรี (null tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือแบ่งเป็นทรีย่อย (sub tree) T1, T2, T3, ... , Tk (โดยที่ k³0) และทรีย่อยต้องมีคุณสมบัติเป็นทรี เช่นกันทรี คือ กราฟที่ต่อเนื่องกันโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใด ๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น ทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น การเขียนรูปแบบทรีอาจเขียนได้ 4 แบบ คือ
นิยามที่เกี่ยวข้องกับ TREE มีนิยามต่าง ๆ ที่เกี่ยวข้องกับ ทรีมากมายดังต่อไปนี้
1. "ฟอร์เรสต์" (forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออก หรือเซตของทรีที่แยกจากกัน (disjoint trees)(2) "ทรีที่มีแบบแผน" (ordered tree) หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน
(3) "ทรีคล้าย" (similar tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกันนั่นเองโดยไม่คำนึงถึงข้อมูลที่อยู่ใน แต่ละโหนด
(4) "ทรีเหมือน" (equivalent tree) หมายถึง ทรีที่เหมือนกันโดยสมบูรณ์ (equivalence) โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
(5) "กำลัง" (degree) หมายถึง จำนวนทรีย่อยของโหนดนั้น ๆ
(6) "ระดับของโหนด" (level of node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่โครงสร้างข้อมูลแบบทรีในความ จำหลักสามารถแทนที่แบบสแตติก หรือแบบไดนามิกก็ได้ โดยมีพอยน์เตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละโหนดต้องมีลิงค์ฟิลด์หลายลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่าง ๆ นั่นคือ จำนวนลิงค์ฟิลด์ของแต่ละโหนดขึ้นอยู่กับจำนวนของโหนดลูก การแทนที่ทรีซึ่งแต่ละโหนดมีจำนวนลิงค์ฟิลด์ไม่เท่ากัน ทำให้ยากต่อการปฏิบัติการเป็นอย่างยิ่ง มีวิธีการแทนที่ทรีในหน่วยความจำหลายวิธี วิธีที่ง่ายที่สุดคือทำให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์เท่ากัน
การแปลงไบนารีทั่วไปให้เป็นไบนารีทรี
ขั้น ตอนการแปลงทรีทั่ว ๆ ไปให้เป็นไบนารีทรี ที่ความสัมพันธ์ของการจัดเก็บเหมือนกับที่กล่าวมาแล้วข้างต้น นั่นคือ แต่ละโหนดมี 2 ลิงค์ฟิลด์ ค่าพอยน์เตอร์ในลิงค์ฟิลด์แรกเก็บที่อยู่ของโหนดลูกคนโต และค่าพอยน์เตอร์ในลิงค์ฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องคนถัดไป มีลำดับขั้นตอนการแปลงดังต่อไปนี้
(1) ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
(2) ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
(3) จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
(1) ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
(2) ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
(3) จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
ดังตัวอย่าง การแสดงขั้นตอนการแปลงทรีทั่วไปในภาพให้เป็นไบนารีทรี
การท่องไปในไบนารีทรี
ปฏิบัติ การที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี (traversing binary tree) เพื่อเข้าไปเยือนทุก ๆ โหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้ง วิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการ เยือนอย่างไรในการเยือนแต่ละครั้ง โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N) ทรีย่อยทางซ้าย (แทนด้วย L) หรือทรีย่อยทางขวา (แทนด้วย R) มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นซึ่งลักษณะการนิยามเป็นนิยามแบบรีเคอร์ซีฟ (recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้
1. "การท่องไปแบบพรีออร์เดอร์" (preorder traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2. "การท่องไปแบบอินออร์เดอร์" (inorder traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี LNR ซึ่งมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. "การท่องไปแบบโพสออร์เดอร์" (postorder traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรี ด้วยวิธี LRN ซึ่งมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสออร์เดอร์
(3) เยือนโหนดราก
การท่องไปในไบนารีทรี
ปฏิบัติ การที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี (traversing binary tree) เพื่อเข้าไปเยือนทุก ๆ โหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้ง วิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการ เยือนอย่างไรในการเยือนแต่ละครั้ง โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N) ทรีย่อยทางซ้าย (แทนด้วย L) หรือทรีย่อยทางขวา (แทนด้วย R) มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นซึ่งลักษณะการนิยามเป็นนิยามแบบรีเคอร์ซีฟ (recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้
1. "การท่องไปแบบพรีออร์เดอร์" (preorder traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2. "การท่องไปแบบอินออร์เดอร์" (inorder traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี LNR ซึ่งมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. "การท่องไปแบบโพสออร์เดอร์" (postorder traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรี ด้วยวิธี LRN ซึ่งมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสออร์เดอร์
(3) เยือนโหนดราก
ไม่มีความคิดเห็น:
แสดงความคิดเห็น