�ݺ�ߣ

โครงสร้างข้อมูลทรี Tree

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

สายงานการบังคับบัญชาในหน่วยงาน ผู้อำนวยการ หัวหน้าฝ่ายธุรการ หัวหน้าฝ่ายทะเบียน หัวหน้าฝ่ายวิชาการ แผนกบันทึกข้อมูล แผนกวัดผล

ข้อมูลแต่ละชุดในทรี จะเรียกว่าโหนด แต่ละโหนดจะมีความสัมพันธ์กับโหนดที่ต่ำกว่า จะกี่โหนดก็แล้วแต่งาน โดยทั่วไปโหนดที่อยู่บนสุด จะมีอยู่โหนดเดียวเรียกว่า โหนดรากหรือรูต (Root Node) โหนดลำดับต่อมาอาจจะเป็นโหนดแม่ (Parent Node) หรือโหนดลูก (Child Node) ทั้งนี้โหนดแม่จะหมายถึงโหนดที่มีลำดับความสัมพันธ์กับโหนดลำดับถัดไป ซึ่งโหนดที่อยู่ถัดไปจากโหนดแม่คือโหนดลูก ดังนั้นโหนดลูกจะหมายถึงโหนดที่อยู่ต่ำลงมาอีก 1 ระดับจากโหนดแม่ นอกจากนี้ถ้าโหนดลูกโหนดใด ไม่มีความสัมพันธ์กับโหนดที่อยู่ระดับต่ำลงมาอีกหรือไม่มีโหนดลูกอีก จะเรียกโหนดนั้นว่าโหนดใบ (Leaf Node) สำหรับโหนดใดถ้าอยู่ระดับเดียวกันกับโหนดอื่น ๆ จะเรียกโหนดที่อยู่ระดับเดียวกันนี้ว่าโหนดพี่น้อง (Sibling Node) ความหมายและหลักการ

โครงสร้างระดับต่าง ๆ ของทรี A B C D E F G H I

จากรูปสามารถสรุปได้ดังนี้ - โหนด A เป็นโหนดราก - โหนด A C D E เป็นโหนดแม่ - โหนด B C D E F G H I เป็นโหนดลูก - โหนด B C D เป็นโหนดลูกของโหนด A และเป็นโหนดพี่น้องกัน - โหนด E F เป็นโหนดลูกของโหนด C และเป็นโหนดพี่น้องกัน - โหนด G เป็นโหนดลูกของโหนด D - โหนด H I เป็นโหนดลูกของโหนด E และเป็นโหนดพี่น้องกัน - โหนด B H F I G เป็นโหนดใบ ความหมายและหลักการ

ป่า ก ข ค ทรีที่ไม่มีโหนดจะเรียกว่า นัลทรี (Null Tree) กลุ่มของทรีทีอยู่รวมกันจะเรียกว่า ป่า (Forest) ดังแสดงในรูป ซึ่งมีต้นไม้อยู่ 3 ต้น โดยที่ต้น ( ข ) เป็นต้นนัลทรี A B C D E F G H I 1 2 3 4 5

ทรีจำนวน 2 ต้น ที่มีโครงสร้างเหมือนกัน สามารถที่จะนำมาพิจารณาความแตกต่างและสามารถที่จะบอกลักษณะความเหมือนหรือความแตกต่างกันได้ ในการพิจารณาความแตกต่างถ้ายึดความสำคัญของตำแหน่งโหนดหรือข้อมูลในโหนดเป็นหลัก จะเรียกว่า แบบอันดับ (Ordered Tree) อาจจะทำให้ทรี 2 ต้นมีความแตกต่างกันได้ แม้ว่าจะมีโครงสร้างที่เหมือนกัน ดังแสดงในรูป ( ก ) และ ( ข ) จะเห็นว่าในทรีที่มีโครงสร้างเหมือนกันแต่การวางโหนด E F จะสลับกัน แต่อย่างไรก็ตาม สามารถเรียกทรีตามรูป ( ก ) และ ( ข ) เป็นทรีคล้าย (Similar Tree) ถ้าหากยึดตามโครงสร้างของทรีเป็นหลัก แต่ไม่คำนึงถึงการจัดวางโหนด ในการพิจารณาความเหมือนของทรี 2 ต้น จะเรียกว่าทรีเหมือน (Equivalent Tree) ก็ต่อเมื่อทรีทั้ง 2 ต้นจะต้องเหมือนกันทั้งโครงสร้างและการวางตำแหน่งของโหนด ความหมายและหลักการ

ทรีต่างกัน ก ข A B C E F A B C E F

ชนิดของต้นไม้ tree 1. ทรีทั่วไป 2. ไบนารีทรี 2.1 นิพจน์ทรี (Expresion Tree) 2.2 ไบนารีเซิร์สทรี (Binary Search Tree) 2.3 ฮีพ (Heap Tree)

ทรีทั่วไป ทรีทั่วไป (General Tree) คือทรีที่มีโหนดจำนวนจำกัด (Finite Set) ที่อาจจะมีจำนวนโหนดตั้งแต่ศูนย์หรือมากกว่า โหนดที่เป็นรากของทรี เมื่อตัดออกส่วนที่เหลือก็ยังเป็นทรีเหมือนเดิม ดังแสดงในรูป โหนด R เป็นโหนดราก เมื่อตัดโหนด R ออกจะพบว่ามีทรีจำนวน 4 ต้น คือ T 1 T 2 T 3 และ T 4 และเรียก T 1 T 2 T 3 และ T 4 ว่าเป็นทรีย่อย (Sub Tree) ของโหนดราก R

ไบนารีทรี ไบนารีทรี (Binary Tree) เป็นทรีที่แตกต่างจากทรีทั่ว ๆ ไป ตรงที่โหนดที่เป็นโหนดแม่ จะมีโหนดลูกได้เพียงแค่ 2 โหนดเท่านั้นคือโหนดซ้าย (Left Node) และโหนดขวา (Right Node) ตัวอย่างเช่น โหนดรากที่มีโหนดลูกเพียงแค่ 2 โหนด ลูกของรากจะมีโหนดลูกอีกก็จะมีได้เพียงแค่ 2 โหนดเท่านั้น ดังแสดงในรูป จะเห็นได้ว่าโหนด A ซึ่งเป็นโหนดรากจะมีโหนดลูกได้แค่ 2 โหนดได้แก่ โหนด B และโหนด C ทำนองเดียวกันโหนด B หรือ โหนด C หากจะมีโหนดลูกต่อไปอีกก็จะมีได้เพียง 2 โหนดเท่านั้น และจะเรียกทรีย่อยที่อยู่ด้านซ้ายของโหนดราก A ว่าทรีย่อยด้านซ้าย (Left Subtree) และเรียกทรีย่อยที่อยู่ทางด้านขวาของโหนดราก A ว่าทรีย่อยด้านขวา (Right Subtree)

ไบนารีทรีตามรูปจะถือว่าเป็นไบนารีทรีแบบสมบูรณ์ (Complete Binary Tree) หมายถึง ทุกโหนดที่ไม่ใช่โหนดใบ จะมีโหนดลูกครบทั้งสองข้างคือด้านซ้ายและด้านขวา และโหนดใบทุกโหนดจะต้องอยู่ระดับล่างสุดเหมือนกันเท่านั้น ในการคำนวณหาจำนวนโหนดของไบนารีทรีแบบสมบูรณ์จะสามารถคำนวณได้จากสูตร จำนวนโหนดของไบนารี่ทรีแบบสมบูรณ์ ( n ) = 2 l -1 เมื่อ n = จำนวนโหนด l = ระดับสูงสุดของไบนารีทรี ตัวอย่างของการคำนวนตามสูตรข้างบน เช่น จะหาจำนวนโหนดของไบนารีทรีตามรูปที่ ซึ่งไบนารีตามรูปจะมี 4 ระดับแต่ระดับสูงสุดคือ 3 เนื่องจากระดับของโหนดรากจะถือว่าอยู่ระดับ 0 ดังนั้นเมื่อแทนค่าสูตร n = 2 l -1 จะได้ n = 2 3 -1 จะทำให้ได้จำนวนโหนดเท่ากับ 7 โหนดอย่างไรก็ตามไบนารีทรียังมีชื่อเรียกที่แตกต่างออกไป ตามการนำไปประยุกต์ใช้ ดังนี้ ไบนารีทรี

นิพจน์ทรี (Expression Tree) นิพจน์ทรี (Expression Tree) คือไบนารีทรีที่ใช้ในการเก็บนิพจน์คณิตศาสตร์ โดยที่ตัวถูกดำเนินการ (Operand) จะถูกเก็บอยู่ในโหนดใบ ส่วนตัวดำเนินการจะถูกเก็บที่โหนดแม่ ดังแสดงในรูป ในการสร้างไบนารีทรีเพื่อจัดเก็บนิพจน์คณิตศาสตร์ จะต้องคำนึงถึงลำดับความสำคัญของตัวดำเนินการ เนื่องจากนิพจน์อาจจะมีตัวดำเนินการ จำนวนมากกว่า 2 ตัวขึ้นไป ลำดับความสำคัญของตัวดำเนินการแสดงในตาราง

ลำดับความสำคัฤญของตัวดำเนินการ หมายเหตุ : ถ้าเครื่องหมายลำดับเดียวกันให้ปฏิบัติการจากซ้ายไปขวา ความสำคัญ สัญลักษณ์ หมายเหตุ 1 Function - 2 () - 3 ^ เครื่องหมายยกกำลัง 4 Unary เครื่องหมายหน้าตัวเลข 5 *, / - 6 +, - -

นิพจน์ทรี (Expression Tree)

ไบนารีเซิร์สทรี (Binary Search Tree) ไบนารีเซิร์สทรี (Binary Search Tree) เป็นไบนารีที่มีคุณสมบัติการจัดเก็บข้อมูล โดยค่าของข้อมูลในโหนดแม่ทุกโหนด จะต้องมากกว่าค่าของข้อมูลในโหนดลูกด้านซ้ายมือและจะมีค่าน้อยกว่าค่าของข้อมูลของโหนดลูกด้านขวามือ ดังแสดงในรูป ในการสร้างไบนารีเซิร์สทรี ค่าข้อมูลตัวแรกจะให้เป็นโหนดราก หลังจากนั้นก็จะอ่านข้อมูลตัวต่อไป แล้วพิจารณาตามเส้นทางที่ควรจะอยู่ในตำแหน่งที่เหมาะสมโดยพิจารณาจากค่าข้อมูลถ้าค่ามากกว่าข้อมูลโหนดรากก็จะพิจารณาเส้นทางตำแหน่งที่อยู่ทางด้านขวา แต่ถ้าค่าน้อยกว่าโหนดราก ก็จะพิจารณาเส้นทางด้านซ้ายของโหนดราก ตัวอย่างการสร้างไบนารีเซิร์สทรี แสดงในรูป

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

การท่องไปในทรี การท่องไปในทรี ( Tree Traversal ) หมายถึง การเดินหรือการท่องไปในทรีอย่างมีระเบียบแบบแผน โดยการเยี่ยมโหนดทุก ๆ โหนด โหนดละ 1 ครั้ง เพื่อนำข้อมูลของโหนดมาแสดงหรือประมวลผลอย่างใดอย่างหนึ่ง ดังนั้นการเยี่ยมโหนดจะทำให้ข้อมูลในโหนดเหล่านั้นถูกนำออกมาเรียงกันในแนวเส้นตรงซึ่งการท่องไปในทรีจะแยกเป็นการท่องไปในทรีทั่วไปและการท่องไปในไบนารีทรี

การท่องไปในทรีทั่วไป การท่องไปในทรีทั่วไปสามารถท่องได้หลายแบบ จะอธิบายการท่องไปในทรีทั่วไปแต่ละแบบ โดยใช้รูปประกอบดังนี้

1 การท่องแบบพรีฟิกซ์วอล์ก ( Prefix Walk ) เป็นวิธีการท่องโดยเยี่ยมโหนดรากก่อน แล้วจึงเยี่ยมทรีย่อยด้านซ้ายมือให้ครบทุกโหนด แล้วขยับไปเยี่ยมทรีย่อยด้านขวาจนครบทุกโหนดก็ถือว่าเป็นการสิ้นสุดการท่องแบบพรีฟิกซ์วอล์ก จากรูปการเยี่ยมแบบพรีฟิกซ์วอล์ก จะได้ผลลัพธ์คือ A B C E F I J G D H K 2 การท่องแบบโพสฟิกซ์วอล์ก (Postfix Walk) เป็นวิธีการท่องโดยการเยี่ยมโหนดที่อยู่ด้านซ้ายสุดที่เป็นโหนดใบก่อน แล้วไปเยี่ยมโหนดที่อยู่ด้านขวา หลังจากนั้นจึงเยี่ยมโหนดที่เป็นโหนดแม่ จากรูปการเยี่ยมแบบโพสฟิกซ์วอล์ก จะได้ผลลัพธ์คือ B E I J F G C K H D A การท่องไปในทรีทั่วไป

3 การท่องแบบเรียงลำดับ (Level by Level Walk ) วิธีนี้สามารถเยี่ยมโหนดได้สองแบบคือการเยี่ยมโหนดจากบนลงล่าง ( Top-down Walk ) โดยเริ่มจากโหนดรากลงไปในแต่ละระดับ และในแต่ละระดับจะเยี่ยมจากโหนดซ้ายก่อนและเยี่ยมโหนดถัดไปด้านขวามือตามลำดับจากรูปทการเยี่ยมแบบเรียงลำดับจากบนลงล่างได้ผลลัพธ์คือ A B C D E F G H I J K สำหรับการเยี่ยมแบบที่สองคือการเยี่ยมโหนดจากล่างขึ้นบน ( Botton-Up Walk ) เป็นการเยี่ยมโหนดจากระดับล่างสุดไปหาระดับบนสุด ในการเยี่ยมโหนดแต่ละระดับก็จะเยี่ยมโหนดด้านซ้ายไปหาด้านขวาตามลำดับ จากรูปการเยี่ยมแบบเรียงลำดับจากล่างขึ้นบน ได้ผลลัพธ์คือ I J K E F G H B C D A การท่องไปในทรีทั่วไป

การท่องไปในทรีไบนารีทรี เนื่องจากคุณสมบัติของไบนารีทรี โหนดรากหรือโหนดแม่จะมีโหนดลูกได้ไม่เกิน 2 โหนด ในการเยี่ยมโหนดแต่ละครั้ง อาจจะเยี่ยมโหนดแม่ก่อน ซึ่งจะแทนด้วย N หรืออาจจะเยี่ยมทรีย่อยด้านซ้ายซึ่งจะแทนด้วย L และอาจจะเยี่ยมทรีย่อยด้านขวาก่อน ซึ่งแทนด้วย R จากการที่องค์ประกอบของทรีมีโหนด 3 โหนดทำให้ทิศทางในการเยี่ยมโหนดเป็นไปได้ 3 ทางขึ้นอยู่กับว่าจะเลือกเยี่ยมโหนดใดก่อน ดังนั้นการท่องไปในไบนารีทรีจึงสามารถท่องได้ 6 แบบ ดังแสดงในตารางอย่างไรก็ตามมีเพียง 3 ลำดับแรกที่นิยมใช้กันมาก โดยเฉพาะอย่างยิ่งการเยี่ยมโหนดแบบ LNR เป็นวิธีที่นิยมมากเนื่องจากผลลัพธ์ของการท่องแบบนี้จะให้ข้อมูลที่เรียงลำดับจากน้อยไปหามากในกรณีที่เป็นไบนารีเซิร์สทรี

วิธีการท่องไปในไบนารี ลำดับที่ วิธี ชื่อ ลักษณะการท่อง 1 LNR อินออร์เดอร์ (Inorder) BAC 2 NLR พรีออร์เดอร์ (Preorder) ABC 3 LRN โพสต์ออร์เดอร์ (Postorder) BCA 4 RLN รีเวอร์สอินออร์เดอร์ (Reverse Inorder) CAB 5 NRL รีเวอร์สพรีออร์เดอร์ (Revers Preorder) ACB 6 RLN รีเวอร์สโพสออร์เดอร์ (Revers Postorder) CBA

การท่องไปในทรีไบนารีทรี จากตารางลักษณะการท่องของแต่ละวิธีจะเป็นผลจากการเยี่ยมโหนดของไบนารีทรีตามรูปซึ่งจะมีโหนดอยู่ 3 โหนด โดยมีโหนด A เป็นโหนดราก โหนด B เป็นโหนดทางด้านซ้ายและโหนด C เป็นโหนดทางด้านขวา จากลักษณะการท่องที่ได้ในตาราง จะพบว่ามีความสัมพันธ์กับชื่อเรียกแต่ละวิธี โดยพิจารณาจากโหนดรากเป็นเกณฑ์ เช่น วิธีการท่องเเบบ LNR มีชื่อเรียกว่าอินออร์เดอร์ผลที่ได้จากการท่องแบบอินออร์เดอร์คือ B A C ซึ่ง คำว่าอิน ( In ) แปลความหมายได้ว่า “กลาง” ดังนั้นจะเห็นได้ว่าลำดับการเยี่ยมจะเยี่ยมโหนด B ซึ่งเป็นโหนดด้านซ้ายก่อน และเยี่ยมโหนด A ซึ่งเป็นโหนดราก และตามด้วยการเยี่ยมโหนด C ซึ่งเป็นโหนดด้านขวามือตามลำดับ C A B

การท่องไปในทรีไบนารีทรี ทำนองเดียวกันลักษณะการท่องแบบ NLR มีชื่อเรียกว่า พรีออร์เดอร์ ผลที่ได้จากการท่องแบบพรีออร์เดอร์คือ A B C ซึ่ง พรี ( Pre ) แปลความหมายได้ว่า “ก่อน” แสดงว่าจะต้องเยี่ยมโหนดรากก่อนเสมอ และถ้าเป็นแบบ LRN มีชื่อเรียกว่า โพสต์ออร์เดอร์ ผลที่ได้จากการท่องแบบโพสต์ออร์เดอร์คือ B C A ซึ่งคำว่าโพสต์ (Post) แปลความหมายได้ว่า “หลัง” แสดงว่าการเยี่ยมจะต้องเยี่ยมโหนดรากเป็นลำดับหลังสุดเสมอ C A B

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

4 การท่องแบบรีเวิร์สอินออร์เดอร์ เป็นการท่องโดยการเยี่ยมทางด้านทรีย่อยด้านขวาก่อน แล้วจึงเยี่ยมโหนดรากหรือโหนดแม่ หลังจากนั้นจึงเยี่ยมโหนดทางทรีย่อยด้านซ้ายเป็นลำดับสุดท้าย 5 การท่องแบบรีเวิร์สพรีออร์เดอร์ เป็นการท่องโดยการเยี่ยมโหนดรากก่อน แล้วจึงเยี่ยมโหนดทางด้านทรีย่อยด้านขวา หลังจากนั้นจึงเยี่ยมโหนดทางด้านทรีย่อยด้านซ้ายเป็นลำดับสุดท้าย 6 การท่องแบบรีเวิร์สโพสต์ออร์เดอร์ เป็นการท่องโดยการเยี่ยมโหนดทางด้านทรีย่อยด้านขวาก่อน แล้วจึงเยี่ยมโหนดทางด้านทรีย่อยด้านซ้าย หลังจากนั้นจึงจะเยี่ยมโหนดรากเป็นลำดับถัดมา การท่องไปในทรีไบนารีทรี

การท่องไปในทรีไบนารีทรี A B C E D + A * C B F G

�ݺ�ߣ

Tree01

Recommended

More Related Content

What's hot (19)

Viewers also liked (7)

Tree01