ต้นไม้หลายทาง

ต้นไม้หลายทางถูกกำหนดให้เป็นต้นไม้ที่สามารถมีลูกได้มากกว่าสองคน หากต้นไม้หลายทางสามารถมีลูกได้สูงสุด m ต้นไม้นี้จะถูกเรียกว่าต้นไม้หลายทางที่มีลำดับ m (หรือต้นไม้ทาง m)

เช่นเดียวกับต้นไม้อื่นๆ ที่ได้รับการศึกษา โหนดในทรี m-way จะประกอบด้วยฟิลด์คีย์ m-1 และตัวชี้ไปยังลูก

ต้นไม้ลำดับที่ 5

เพื่อให้การประมวลผลทรี m-way ง่ายขึ้น ข้อจำกัดหรือลำดับบางประเภทจะถูกกำหนดบนคีย์ภายในแต่ละโหนด ส่งผลให้ทรีการค้นหาแบบหลายทางของคำสั่ง m (หรือ m-way search tree) ตามคำจำกัดความ m-way search tree คือ m-way tree ซึ่งควรจะเป็นไปตามเงื่อนไขต่อไปนี้ -

• แต่ละโหนดเชื่อมโยงกับ m ลูกและ m-1 คีย์ฟิลด์
• คีย์ในแต่ละโหนดจะเรียงลำดับจากน้อยไปมาก
• คีย์ใน j ลูกแรกน้อยกว่าคีย์ j-th
• คีย์ในลูก m-j สุดท้ายจะสูงกว่าคีย์ j-th