m-ary tree

ต้นไม้ m-ary ในวิทยาการคอมพิวเตอร์ถูกกำหนดให้เป็นชุดของโหนดที่ปกติจะแสดงตามลำดับชั้นในลักษณะต่อไปนี้

• ต้นไม้เริ่มต้นที่โหนดราก
• แต่ละโหนดของแผนผังจะเก็บรักษารายการตัวชี้ไปยังโหนดย่อย
• จำนวนโหนดย่อยน้อยกว่าหรือเท่ากับ m.

การแทนค่าโดยทั่วไปของ m-ary tree จะใช้อาร์เรย์ของการอ้างอิง m (หรือพอยน์เตอร์) เพื่อเก็บลูก (โปรดทราบว่า m เป็นขอบเขตบนของจำนวนลูก)

ต้นไม้ค้นหา m-way

ก. ว่างเปล่าหรือ

ข. ประกอบด้วยรูทที่มีคีย์ b (1<=b

• ถ้า k เป็นคีย์ใน T0 แล้ว k <=k1
• ถ้า k เป็นคีย์ใน Ta (0
• ถ้า k เป็นคีย์ใน Tb แล้ว k> kb และ
• Ta ทั้งหมดเป็นต้นไม้ค้นหา m-way ที่ไม่ว่างเปล่า หรือ Ta ทั้งหมดว่างเปล่า

รูปภาพของ m-ary ต้นไม้

ความสูงของต้นไม้ m-ary ที่สมบูรณ์ที่เกี่ยวข้องกับ n โหนดคือเพดาน(log_m น)

B-tree of order m คือต้นไม้ m-way ซึ่ง

ก. ใบทั้งหมดควรอยู่ในระดับเดียวกันและ

ข. โหนดทั้งหมดยกเว้นรากและใบมีลูกขั้นต่ำ m/2 และลูก สูงสุด m รูทมีลูกขั้นต่ำ 2 ลูกและลูกสูงสุด m