DTS08-26-08-2552

สรุปสิ่งที่ได้จากการเรียน เรื่อง TREE

TREE

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

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

จากรูป อธิบายได้ว่า โหนด “A” คือโหนดรากของทรีนี้และเป็นโหนดแม่ของโหนด “B” “C” “D” และ “E” ขณะเดียวกันโหนด “B” “C” “D” และ “E” เป็นโหนดพี่น้องกันโดยทั้งหมดเป็นโหนดลูกของโหนด “A” โหนด “G” “H” “I” และ “J” เป็นโหนดพี่น้องกันเนื่องจากทั้งหมดเป็นโหนดลูกของโหนด “B” และโหนดที่ไม่มีลูกเลย เช่น โหนด “N” “O” “Q” “R” และ “S” ถือว่าเป็นโหนดใบ เป็นต้น

นิยามของ TREE

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

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

นิยามที่เกี่ยวข้องกับ TREE มีนิยามต่าง ๆ ที่เกี่ยวข้องกับ ทรีมากมายดังต่อไปนี้

1. "ฟอร์เรสต์" (forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออก หรือเซตของทรีที่แยกจากกัน (disjoint trees) เช่น ทรีในภาพด้านบน ถ้าตัดเอาโหนดราก “R” และตัดเส้นทางจากโหนด “R” ไปยัง โหนด “A” โหนด “B” และโหนด “C” ออกไปจากทรี ได้สามทรีย่อยที่แยกจากกันเรียกทั้งหมดว่า "ฟอร์เรสต์" ดังแสดงในภาพ
(2) "ทรีที่มีแบบแผน" (ordered tree) หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ก่อน ไปทางขวา ไปทางซ้าย เป็นต้น ทรีในภาพ (ก) และทรีในภาพ (ข) ด้านล่าง ถ้ากำหนดความสัมพันธ์ระหว่างโหนดไว้ถือว่า ทรีทั้งสองเป็นทรีที่ต่างกัน เนื่องจากทรีในภาพ (ก) โหนด “C” เป็นโหนดทางขวา ในขณะที่ ทรีในภาพ (ข) โหนด “C” เป็นโหนดทางซ้ายทำให้ทรีทั้งสองไม่เหมือนกัน และถ้าไม่ได้กำหนดความสัมพันธ์ระหว่างโหนดไว้ถือว่าทรีทั้งสองเป็นทรีที่เหมือนกัน เพราะมีจำนวนโหนดและจำนวนทรีย่อยเท่ากัน
(3) "ทรีคล้าย" (similar tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกันนั่นเองโดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด ตัวอย่าง ทรีในภาพ (ก) และ (ข) ด้านล่าง เป็นทรีที่คล้ายกันแต่ไม่เหมือนกัน เนื่องจากมีโครงสร้างทรีเหมือนกันแต่ข้อมูลในโหนดต่าง ๆ ที่ตำแหน่งเดียวกันไม่เหมือนกัน
(4) "ทรีเหมือน" (equivalent tree) หมายถึง ทรีที่เหมือนกันโดยสมบูรณ์ (equivalence) โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน ตัวอย่างทรีในภาพ (ก) และ (ข) ด้านล่าง ทรีทั้งสองเป็นทรีที่เหมือนกันเนื่องจากมีโครงสร้างทรีที่เหมือนกัน และในแต่ละโหนดที่ตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
(5) "กำลัง" (degree) หมายถึง จำนวนทรีย่อยของโหนดนั้น ๆ ตัวอย่างทรีในภาพด้านล่าง โหนด “B” มีค่ากำลังเป็น 1 เพราะมีทรีย่อยคือ {“D”} ส่วนโหนด “C” มีค่ากำลังเป็น 2 เพราะมีทรีย่อย {“E”, “G”, “H”, “I”} และ {“F”} จะเห็นว่าโหนดใบเป็นโหนดที่ไม่มีทรีย่อยเลย ดังนั้นโหนดใบทุกโหนดมีค่ากำลังเป็นศูนย์
(6) "ระดับของโหนด" (level of node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้โหนดรากของทรีนั้นอยู่ที่ระดับ 1 และกิ่งแต่ละกิ่งมีความเท่ากันหมดคือยาวเท่ากับ 1 หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1 เช่น โหนด “H” ของทรีในภาพด้านล่าง มีระดับเป็น 4 เป็นต้น และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่างจากโหนดรากเรียกว่า ความสูง (height) หรือ ความลึก (depth) เช่น โหนด D มีความลึกเป็น 2 เป็นต้น

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

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

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

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

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

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

ไบนารีทรีที่ทุก ๆ โหนดมีทรีย่อยทางซ้ายและทรีย่อยทางขวา ยกเว้นโหนดใบ และโหนดใบทุกโหนดจะต้องอยู่ที่ระดับเดียวกันเรียกว่า "ไบนารีทรีแบบสมบูรณ์" (complete binary tree) ดังแสดงตัวอย่างทรีในภาพด้านบน เป็นไบนารีทรีแบบสมบูรณ์ที่มี 4 ระดับ เราสามารถคำนวณจำนวนโหนดทั้งหมดในไบนารีทรีแบบสมบูรณ์ได้ ถ้ากำหนดให้ L คือระดับของโหนดใด ๆ และ N คือจำนวนโหนดทั้งหมดในทรีจะได้ว่า
ระดับ 1 มีจำนวนโหนด 1 โหนด
ระดับ 2 มีจำนวนโหนด 3 โหนด
ระดับ 3 มีจำนวนโหนด 7 โหนด
ระดับ 4 มีจำนวนโหนด 15 โหนด
.
.
ระดับ L มีจำนวนโหนด 2L – 1 โหนด

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

การแปลงไบนารีทั่วไปให้เป็นไบนารีทรี

ขั้นตอนการแปลงทรีทั่ว ๆ ไปให้เป็นไบนารีทรี ที่ความสัมพันธ์ของการจัดเก็บเหมือนกับที่กล่าวมาแล้วข้างต้น นั่นคือ แต่ละโหนดมี 2 ลิงค์ฟิลด์ ค่าพอยน์เตอร์ในลิงค์ฟิลด์แรกเก็บที่อยู่ของโหนดลูกคนโต และค่าพอยน์เตอร์ในลิงค์ฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องคนถัดไป มีลำดับขั้นตอนการแปลงดังต่อไปนี้
(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) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
ดังภาพ

ท่องแบบพรีออร์เดอร์ (NLR) ผลลัพธ์จากการเยือนโหนดต่าง ๆ ดังนี้ ABDGCEHIF

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

ท่องแบบอินออร์เดอร์ (LNR) ผลลัพธ์จากการเยือนโหนดต่าง ๆ ดังนี้ DGBAHEICF

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

ดังภาพ

ท่องแบบโพสออร์เดอร์ (LRN) ผลลัพธ์จากการเยือนโหนดต่าง ๆ ดังนี้ GDBHIEFCA