ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ ระหว่างโหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship) ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงานต่าง ๆ อย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมูล เช่น แผนผังองค์ประกอบของหน่วยงานต่าง ๆ โครงสร้างสารบัญหนังสือ แต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้หลาย ๆ โนด เรียกโหนดดังกล่าวว่า โหนดแม่ (Parent or Mother Node) โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับ เรียกว่า โหนดลูก(Child or Sun Node) โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่ เรียกว่า โหนดราก (Root Node) โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน เรียกว่า โหนดพี่น้อง (Siblings) โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (Leave Node) เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง (Branch) Ancestor Node หรือ บรรพบุรุษของโหนดใด ๆ หมายถึง โหนดที่มาก่อนโหนดใด ๆ Decendant Node หรือ ผู้สืบสกุล หมายถึง โหนดที่ตามหลังโหนดใด ๆ
1. นิยามทรีด้วยนิยามของกราฟ ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใด ๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น การเขียนรูปแบบทรี อาจเขียนได้ 4 แบบ คือ
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ ทรีประกอบด้วยสมาชิกที่เรียกว่า โหนด โดยที่ถ้าว่าง ไม่มีโหนดเลย เรียกว่า นัลทรี (Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree) T1, T2, T3,…,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี
3. นิยามที่เกี่ยวข้องกับทรี 1. ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออก หรือ เซตของทรีที่แยกจากกัน (Disjoint Trees)
2. ทรีที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ไปทางขวาไปทางซ้าย เป็นต้น
3. ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree) หมายถึง จำนวนทรีย่อยของโหนดนั้น
6. ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้โหนดรากของทรีนั้นอยู่ระดับ 1 และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1 หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1 และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่างจากโหนดราก เรียกว่า ความสูง (Height) หรือความลึก (Depth)
ไบนารีทรี คือ โหนดทุกโหนดใน Binary tree จะมีลูกไม่เกินสอง คือ 0 , 1 หรือ 2
จะได้โครงสร้างทรีที่แต่ละโหนดมีลิงค์ฟิลด์แค่สองลิงค์ฟิลด์ ซึ่งช่วยให้ประหยัดเนื้อที่ในการจัดเก็บได้มาก เรียกโครงสร้างทรีที่แต่ละโหนดมีจำนวนโหนดลูกไม่เกินสอง หรือแต่ละโหนดมีจำนวนทรีย่อยไม่เกินสองนี้ว่า ไบนารีทรี (Binary Tree)
ไบนารีทรีที่ทุก ๆ โหนดมีทรีย่อยทางซ้ายและทรีย่อยทางขวา ยกเว้นโหนดใบ และโหนดใบทุกโหนดจะต้องอยู่ที่ระดับเดียวกันเรียกว่า ไบนารีทรีแบบสมบูรณ์ (complete binary tree) สามารถคำนวณจำนวนโหนดทั้งหมดในไบนารีทรีแบบสมบูรณ์ได้ ถ้ากำหนดให้ L คือระดับของโหนดใด ๆ และ N คือจำนวนโหนดทั้งหมดในทรีจะได้ว่า ระดับ 1 มีจำนวนโหนด 1 โหนด ระดับ 2 มีจำนวนโหนด 3 โหนด ระดับ 3 มีจำนวนโหนด 7 โหนด ระดับ 4 มีจำนวนโหนด 15 โหนดระดับ L มีจำนวนโหนด 2L – 1 โหนด นั่นคือ จำนวนโหนดทั้งหมดในทรีสมบูรณ์ที่มี L ระดับสามารถคำนวณได้จากสูตรดังนี้
Strictly Binary tree หมายถึง ไบนารีทรีที่ non-Leaf Node ทุก ๆ โหนดจะต้องโหนดลูกอยู่ครบทั้ง 2 ข้าง
Almost Complete Binary tree (ไบนารีทรีแบบเกือบสมบูรณ์) หมายถึงไบนารีทรีที่ Height มีค่าเท่ากับ H ใดๆ (เมื่อ H มีค่าเป็นจำนวนเต็มใด ๆ) และ non-Leaf Node ทุก ๆ โหนดจะต้องอยู่ที่ 2 level ล่างสุดเท่านั้น (level ที่ H และ H-1)
การเก็บโครงสร้างข้อมูลแบบไบนารีทรีลงในหน่วยความจำมี 2 วิธี ซึ่งลักษณะเหมือนกับโครงสร้างข้อมูลประเภทลิเนียร์ (linear) กล่าวคือ การเก็บเป็นแบบอาร์เรย์ และลิงค์ลิสต์ โดยทั่วไปการเก็บหน่วยความจำแบบใดนั้นจะขึ้นอยู่กับความต้องการในการเข้าถึงข้อมูลได้โดยตรง โดยมีวิธีการต่อไปนี้ 1. การแทนที่ไบนารีทรีด้วยอาร์เรย์ (Array)การแทนทรีไบนารีทรีด้วยแบบสแตกหมายถึงการแทนที่ด้วยอาร์เรย์ ซึ่งจะต้องเป็นไบนารีทรีที่สมบูรณ์หรือเกือบสมบูรณ์ ให้ a เป็นอาร์เรย์มีขนาด n การดำเนินการบนอาร์เรย์โดยให้สมาชิกของ Root Node มาแทนที่ในตำแหน่งแรกของอาร์เรย์ คือ a[0] และนำสมาชิกโหนดซ้ายมาใส่ในตำแหน่งที่สองในอาร์เรย์ คือ a[1] และนำสมาชิกของโหนดขวามาใส่ในตำแหน่งที่สามในอาร์เรย์ คือ a[2] และนำสมาชิกโหนดซ้ายและขวาถัดไปมาใส่ในอาร์เรย์ไว้ตามลำดับ
2. การแทนที่ไบนารีทรีด้วยลิงค์ลิสต์ (Linked List) ไบนารีทรีจะเก็บในลักษณะไดนามิก (Dynamic) ก็คือลิงค์ลิสต์ ซึ่งมีการใช้พอยน์เตอร์ (Pointer) ใช้ชี้โหนดลูกซ้ายและขวาในหน่วยความจำ ถ้าหากโหนดใดไม่มีโหนดลูก หรือเป็น Leaf Node ก็ให้ค่าพอยเตอร์ในลิงค์ฟิลด์นั้นมีค่าเป็น NULL การแทนที่ข้อมูลทรีด้วยลิงค์ลิสต์นั้น จะทำการเก็บพอยน์เตอร์ซ้ายและขวา และถ้าเป็น Leaf Node พอยน์เตอร์ทั้งสองจะมีค่าเป็น 0
การท่องไปในทรี
ปฏิบัติการที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี (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) เยือนโหนดราก
เส้นทางการท่องในทรีแบบโพสต์ออร์เดอร์ จะได้ GDBHIEFCA
เส้นทางการท่องในทรีแบบอินออร์เดอร์ จะได้ DGBAHEICF
เส้นทางการท่องในทรีแบบพรีออร์เดอร์ จะได้ ABDGCEHIF
ไม่มีความคิดเห็น:
แสดงความคิดเห็น