โครงสร้างปม ของ ต้นไม้แบบที

โครงสร้างปมของต้นไม้แบบที

ต้นไม้แบบที ประกอบจะประกอบไปด้วย ตัวชี้ไปยังปมพ่อ ตัวชี้ไปยังปมลูกซ้ายและขวา แถวลำดับของตัวชี้ข้อมูล และข้อมูลการควบคุมพิเศษ

ปมที่มีต้นไม้ย่อย (subtree) สองต้น เรียกว่า ปมภายใน (internal nodes) ปมที่ไม่มีต้นไม้ย่อย เรียกว่า ปมใบ (leaf nodes) และปมที่มีต้นไม้ย่อยเพียงแต่ต้นเดียว เรียกว่า ปมครึ่งใบ (half-leaf nodes) ปมจะถูกเรียกว่า ปมขอบเขต (bounding node) สำหรับค่าหนึ่ง ถ้าค่านั้นอยู่ระหว่างค่าน้อยสุดและมากสุดของปมนั้น

ค่าขอบเขต

ค่าที่มากที่สุดในต้นไม้ย่อยซ้ายของแต่ละปมภายใน เรียกว่า ขอบเขตล่างมากสุด (greatest lower bound) ค่าที่น้อยที่สุดในต้นไม้ย่อยขวาของแต่ละปมภายใน เรียกว่า ขอบเขตบนน้อยสุด (least upper bound) ซึ่งค่าทั้งสองนี้จะอยู่ที่ปมใบหรือปมครึ่งใบเสมอ ปมใบและปมครึ่งใบสามารถมีจำนวนข้อมูลได้ตั้งแต่หนึ่งจนถึงขนาดของแถวลำดับข้อมูล แต่จำนวนข้อมูลขั้นต่ำและมากสุดของปมภายในจะถูกกำหนดไว้ล่วงหน้าแล้ว

ใกล้เคียง

ต้นไม้ตัดสินใจ ต้นไม้ของพ่อ ต้นไม้แบบที ต้นไม้แห่งการรู้ถึงความดีและความชั่ว ต้นไม้ (ทฤษฎีกราฟ) ต้นไม้เงินต้นไม้ทอง ต้นไม้ (โครงสร้างข้อมูล) ต้นไม้สเปลย์ ต้นไม้แดงดำ ต้นไม้ 2–3–4