ผู้เขียน หัวข้อ: ต้นไม้ (โครงสร้างข้อมูล) : J  (อ่าน 11 ครั้ง)

0 สมาชิก และ 1 บุคคลทั่วไป กำลังดูหัวข้อนี้

09-10-2018 , 23:20:51
  • Hero Member
  • *****
  • กระทู้: 2549
    • ดูรายละเอียด

องค์ประกอบของต้นไม้

เงื่อน (node) หมายคือสิ่งที่เก็บสมาชิกของต้นไม้ ufabet

ราก (root) เป็นเงื่อนที่พวกเราใช้เริ่มค้นหาข้างในต้นไม้ ถ้าเกิดเป็น null ซึ่งก็คือต้นไม้ว่าง (empty tree)

เงื่อนลูก (child node) เป็นเงื่อนที่แตกออกมาจากของเงื่อนดังที่กล่าวมาแล้ว ส่วนเงื่อนที่เงื่อนดังที่กล่าวมาข้างต้นแตกมาเรียกว่า เงื่อนบิดา (parent node) แล้วก็เรียกเงื่อนบิดาของเงื่อนบิดาว่า เงื่อนปู่ (grandparent node) แล้วก็เรียกเป็นลำดับการนับพี่น้องข้างบิดาไปเรื่อยส่วนเงื่อนลูกของเงื่อนลูกก็จะเป็นเงื่อนหลาน (grandchild node) ไปเรื่อยเป็นลำดับการเรียกพี่น้องข้างลูก

เงื่อนที่มีเงื่อนบิดาเป็นเงื่อนเดียวกันเรียกว่า เงื่อนลูกพี่ลูกน้อง (sibling node)

เงื่อนที่มี m ลูก พวกเราจะเรียกว่า เงื่อนแบบ m (m-type node)

ใบ (leaf node) หมายคือเงื่อนที่ไม่มีเงื่อนลูก

การเขียนต้นไม้มักเขียนเงื่อนรากอยู่ด้านบน แล้วก็เขียนแตกกิ่งลงมาให้เงื่อนใบอยู่ด้านล่าง

ความลึกของเงื่อน (node depth) คือปริมาณครั้งของความเชื่อมโยงเชิงบิดา-ลูก ระหว่าง เงื่อนรากถึงเงื่อนอะไรก็ตาม

ความสูง (tree height) เป็นความลึกของใบที่ลึกที่สุด สำหรับต้นไม้ซึ่งมีก็เพียงแต่รากจะสูง 0 และก็ต้นไม้ว่างบางทีอาจตั้งได้ว่าสูง -1

ต้นไม้ย่อย (subtree) หมายความว่าต้นไม้ย่อยที่ใช้สมาชิกของต้นไม้ที่พวกเราไตร่ตรอง ไปเป็นรากนำมาซึ่งการทำให้ เงื่อนลูกเงื่อนหลานที่อยู่ใต้สมาชิกตัวนั้นเปลี่ยนเป็นสมาชิกของต้นไม้ย่อยไปด้วย

ต้นไม้พิเศษ

ต้นไม้ค้นหา (search tree) ซึ่งก็คือต้นไม้ที่ตามเงื่อนอะไรก็แล้วแต่ต้นไม้ย่อยจะน้อยกว่า มากยิ่งกว่า หรืออยู่ระหว่าง สมาชิกของเงื่อนนั้น ในลักษณะการจัดลำดับ สำหรับต้นไม้ค้นหาที่มีเงื่อนแบบ m อะไรก็ตามย่อมมีสมาชิกให้เทียบ m-1 ตัวในเงื่อนนั้น ได้แก่ เงื่อนแบบสาม จะมีสมาชิกสองตัว

ต้นไม้ m ภาค (m-ary tree) คือต้นไม้ที่ใช้แม้กระนั้นเงื่อนแบบ m พูดอีกนัยหนึ่งมี m ลูก

ต้นไม้แบบทวิภาค (binary tree) หมายคือต้นไม้ซึ่งมีแต่เงื่อนแบบสอง

ต้นไม้ค้นหาแบบทวิภาค (binary search tree) หมายคือต้นไม้ซึ่งมีแต่เงื่อนแบบสอง โดยต้นไม้ย่อยของลูกซ้าย (left child subtree) จะมีค่าน้อยกว่าเงื่อนนั้นๆรวมทั้งต้นไม้ย่อยของลูกขวา (right child subtree) จะมีค่ามากยิ่งกว่าเงื่อนนั้นๆ

ต้นไม้รับรองการทำงาน หมายความว่าต้นไม้ที่รับรองความเร็วการทำงานเป็น O (log n)

ต้นไม้รับรองความสูง หมายคือต้นไม้ที่รับรองความสูงเป็น O (log n) ต้นไม้รับรองความสูงย่อมฯลฯไม้รับรองการทำงานไปด้วย สมัคร ufabet

ต้นไม้ได้ดุล (balanced tree) หมายคือต้นไม้ที่มีความสูงต่ำสุดเท่าที่เป็นได้สำหรับชุดข้อมูลอะไรก็แล้วแต่ต้นไม้ได้ดุลย่อมฯลฯไม้ที่รับรองความสูงไปด้วย

ต้นไม้เติมเต็ม (completed tree) เป็นต้นไม้ที่เงื่อนอะไรก็ตามสามารถมีลูกได้ก็เมื่อเงื่อนญาติด้านซ้ายมีลูกเพียงแค่นั้น ต้นไม้เติมเต็มย่อมฯลฯไม้ได้ดุลไปด้วย

ฮีป (heap) คือต้นไม้ที่เมื่อพินิจพิเคราะห์ในต้นไม้ย่อยใดๆก็ตามในต้นไม้ รากจะมีความจำเป็น (priority) สูงที่สุด