สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง ทรี(Tree)
ทรีเป็นกราฟแบบมีทิศทาง ที่มีโครงสร้างแบบลำดับชั้น ทิศทางของกราฟที่แทนทรีจะมีทิศทางจากบนลงล่าง ดังนั้นการกวาดทรี เราจึงไม่นิยมแสดงทิศทางของเส้นเชื่อม
การให้นิยามในรูปของการเรียกซ้ำซึ่งสอดคล้องกับลักษณะธรรมชาติ ของทรี ดังนี้ คือ ทรีประกอบด้วยโหนด R ซึ่งเรียกว่า โหนดราก (root) และ ทรีย่อย (subtree) จำนวนศูนย์ หรือมากกว่าศูนย์ ซึ่งแต่ละทรีย่อยจะเชื่อมกับโหนดราก (R)โดยตรงด้วยเส้นเชื่อม
การเรียกชื่อองค์ประกอบของทรี
โหนดที่อยู่ระดับบนสุดของทรี เรียกว่า โหนด R ,โหนดราก, พ่อ (father)
โหนดรากของทรีย่อยของ R เรียกว่า ลูก (child) ของ R
โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (leaf node)
เส้นเชื่อมโหนดทรี เรียกว่า กิ่ง (branch)
โหนดที่มีทั้งพ่อทั้งลูก เรียกว่า โหนดกิ่ง (branch node)
โหนดที่มีพ่อเดียวกัน เรียกว่า โหนดพี่น้อง (sibling) และยังอาจนิยามโหนดว่าเป็น โหนดปู่ (grandfather) หรือ โหนดหลาน (gtrandchild) ได้ในลักษณะเดียวกัน
เส้นทาง (path) จากโหนด n1 ไปยังโหนด nk ใดๆ จะเป็นลำดับของโหนด n1,n2,...,nk
ความยาว (length) ของเส้นทางจะเป็นจำนวนของเส้นเชื่อมที่อยู่ในเส้นทาง ซึ่งเท่ากับ k-1 เส้นทาง จากโหนดใดๆ ไปยังตัวเองจะมีความยาวเป็ยศูนย์ และในทรีแต่ละทรี จะมีเส้นทางหนึ่งเส้นเท่านั้นจากโหนดรากไปยัง โหนดใดๆ ความลึก (depth) เป็น ความยาวของเส้นทางจากโหนดรากไปยังโหนด n โซึ่งมีเส้นทางเดียวที่ไม่ซ้ำกัน) ความสูง (height) เป็น เส้นทางทีสุดจากโหนด n ไปยังโหนดใบถ้ามีเส้นทางจาดโหนด n1 ไปยังโหนด n2 จะเป็น บรรพบุรุษ (ancestor) ของ n2 และ n2 จะเป็น ลูกหลาน (descendant) ของ n1 ถ้า n1 != n2 ดังนั้น n1 จะเป็น บรรพบุรุษที่แท้จริง (proper ascestor) ของ n1 และ n2 ลูกหลานที่แท้จริง (proper descendant)
ทรีแบบลำดับ
ทรีแบบราก (rooted tree ) เป็นทรีที่สามารถวาดได้อิสระ โดยเชื่อมโหนดในระดับต่ำลงไป และมีโหนด ใบอยู่ในระดับล่าง มีโครงสร้างไม่เหมาะสมก่การใช้งาน เนื่องจากวิธีการเรียกชื่อโหนดจากลำดับซ้ายไปขวา "ทรีแบบลำดับ (ordered tree)" คือ ทรีแบบรากที่โหนดลูกของแต่ละโหนดถูกกำหนดลำดับดังรูป ถ้าต้องการจะใช้ทรีแบบลำดับเป็นโครงสร้างข้อมูล ในแต่ละโหนดจะต้องมีจำนวนเขตข้อมูลมากพอๆ กับจำนวน ของโหนดนั้น ดังนั้นถ้ามีบางโหนดในทรีมีจำนวนทรีมากกว่า 10 ทรีย่อย จะต้องมีเขตข้อมูลสำหรับลิงค์ของ แต่ละโหนดถึง 10 เขต ซึ่งแต่ละเขตลิงค์ต่างๆ เหล่านี้ส่วนใหญ่จะมีค่าเป็น NULL ซึ่งทำให้เนื้อที่จำนวนมาก ไม่ได้ใช้งาน
ไบนารีทรี
ไบนารีทรี เป็น ทรีว่าง หรือทรีที่ประกอบด้วยโหนดรากที่เรียกว่า ราก กับ ไบนารีทรี 2 ทรี เรียกว่า ทรีย่อยทางซ้าย (left subtree) และ ทรีย่อยทางขวา (right subtree) ของราก การสร้างไบนารีทรี ที่มีโหนดเดียว สามารถสร้างโหนดนั้นเป็นโหนดรากที่มีทรีย่อยทางซ้าย และทรีทางขวาเป็นทรีว่าง จะเห็นว่าไบนารีทรีแตก ต่างจากทรีทั่วไป เนื่องจากในไบนารีทรี ความหมายของคำว่า ซ้าย หรือ ขวา มีความสำคัญ ไบนารีทรี 2 โหนด ดังนั้นไบนารีทรีสามรถได้มาจากทรีแบบลำดับที่เหมาะสมกัน โดยการแยกกิ่งทางซ้ายออกจากกิ่งทางขวา
การเปลี่ยนทรีทั่วไปเป็นไบนารีทรี
ไบนารีทรีเป็นโครงสร้างข้อมูลที่มีประสิทธิภาพ แต่มีข้อจำกัดว่า แต่ละโหนดมีลูกได้ไม่เกิน 2 และในการประยุกต์ ใช้งานส่วนใหญ่ โครงสร้างข้อมูลเป็นจำนวนใดๆ ได้ตามใจ การเปลี่ยนทรีทั่วไปเป็นไบนารีทรี เริ่มต้นจะเชื่อมโหนด แต่ละโหนดกับโหนดลูกซ้ายสุดของโหนดนั้น ซึ่งเรียกว่าโหนดแรก ต่อมาเชื่อมแต่ละโหนดยกเว้นโหนดรากกับโหนดถัดไป ที่มีพ่อเดียวกัน(พี่น้อง) ซึ่งเรียกว่าเชื่อมโหนดลูกถัดไป
เพื่อให้โครงสร้างของไบนารีทรีที่ดีกว่านี้ จะต้องหมุนทรีเล็กน้อยตามเข็มนาฬิกา ซึ่งจะทำให้เส้นเชื่อมที่ชี้ลงล่าง ชี้ลงไปทางซ้าย และเส้นเชื่อมที่ชี้ตามแนวนอน ชี้ลงไปข้างล่างทางขวา
ป่าและสวน
ป่า (forest) หมายถึงของทรีที่เป็นทรีแบบรก และ สวน (orchard) หมายถึง ชุดของทรีแบบลำดับ แต่โดยทั่วไป แล้วป่ากับสวนมีความหมายเดียวกัน คือ ชุดของทรีทั่วไป
สามารถสร้างป่าหรือสวนได้ โดยการขจัดรากออกไปจากทรีแบบราก หรือแบบลำดับและทำนองเดียวกัน สามารถแปลง จากป่าแสวนไปเป็นไบนารีทรีได้มีขั้นตอนดังต่อไปนี้
1.ขจัดเส้นเชื่อมเดิมออก
2.แปลงทรีแต่ละต้นให้เป็นไบนารีทรี
3.เชื่อมโหนดรากของทรีเขาด้วยกัน ในแนวนอนโดยใช้ความสัมพันธ์พี่น้อง
4.หมุนทรีที่ได้ 45 องศาตามเข็มนาฬิกา ซึ่งจะทำให้เส้นเชื่อมในแนวตั้งกลายเป็นเส้นเชื่อมทางซ้าย และเส้นเชื่อมในแนวนอนกลายเป็นเส้นเชื่อมทางขวา
การท่องไบนารีทรี (traversal of binary tree)
เป็นการเคลื่อนที่ไปยังโหนดทุกโหนดของไบนารีของทรี หรือการเยี่ยมโหนดทุกโหนดของทรี ในข้อมูลแบบทรีโหนด ทุกโหนดที่จะท่องมีลำดับแตกต่างกัน ที่โหนดใด ไๆที่กำหนดให้จะต้องมีการกระทำ 3 อย่าง ในลำดับใดๆ คือ
1. เยี่ยมโหนดนั้น
2. ท่องไปยังทรีย่อยทางซ้ายของโหนดนั้น
3. ท่องไปยังทรีย่อยทางขวาของโหนดนั้น
จุดสำคัญของของการท่องไบนารีทรีคือ จะเยี่ยมททรีย่อยก่อนการท่องทรีย่อยที่มีอยู่ หรือจะเยี่ยมโหนดนั้นใน ระหว่างการท่องทรีย่อยของโหนดนั้น หรือจะเยี่ยมดหนดนั้นในระหว่างการท่องทรีย่อยภายหลังจากการท่องทรีย่อย ทั้งสองของโหนดนั้นเสร็จเรียบร้อยแล้ว
ไม่มีความคิดเห็น:
แสดงความคิดเห็น