Cây đa được định nghĩa là cây có thể có nhiều hơn hai con. Nếu một cây nhiều đường có thể có tối đa m con, thì cây này được gọi là cây nhiều đường bậc m (hoặc cây thứ m).
Giống như với các cây khác đã được nghiên cứu, các nút trong cây m-way sẽ được tạo thành từ m-1 trường khóa và các con trỏ đến con trỏ.
cây multiway thứ tự 5
Để làm cho việc xử lý cây m-way dễ dàng hơn, một số loại ràng buộc hoặc thứ tự sẽ được áp dụng cho các khóa bên trong mỗi nút, dẫn đến cây tìm kiếm nhiều đường có thứ tự m (hoặc cây tìm kiếm m-way). Theo định nghĩa cây tìm kiếm m-way là một cây m-way trong đó điều kiện sau phải được thỏa mãn -
- Mỗi nút được liên kết với m trường con và m-1 trường khóa
- Các khóa trong mỗi nút được sắp xếp theo thứ tự tăng dần.
- Các phím ở con thứ j đầu tiên nhỏ hơn phím thứ j.
- Các phím ở con m-j cuối cùng cao hơn phím thứ j.