Định nghĩa cây m-ary
Một cây m-ary trong khoa học máy tính là tập hợp các nút thường được biểu diễn phân cấp như sau:
- Cây bắt đầu tại nút gốc (root node).
- Mỗi nút giữ danh sách con trỏ tới các nút con của nó.
- Số nút con nhỏ hơn hoặc bằng m.
Biểu diễn điển hình của cây m-ary dùng mảng m tham chiếu (con trỏ) để lưu trữ các nút con (lưu ý m là giới hạn trên của số con).
Cây tìm kiếm m-way (m-way search tree)
Một cây tìm kiếm m-way:
a. là rỗng hoặc
b. bao gồm một gốc chứa b (1 ≤ b ≤ m) khóa kb, và một tập hợp cây con Ta (a = 0..b), sao cho:
- nếu k là khóa trong T0, thì k ≤ k1
- nếu k là khóa trong Ta (0 < a < b), thì ka ≤ k ≤ ka+1
- nếu k là khóa trong Tb, thì k > kb
- tất cả Ta là cây tìm kiếm m-way không rỗng hoặc tất cả đều rỗng
Hình ảnh cây m-ary
Độ cao và cây B
Độ cao của một cây m-ary hoàn chỉnh với n nút là ceiling(logm n).
Cây B bậc m (B-tree of order m) là một cây m-way mà:
- tất cả lá nằm trên cùng một cấp độ
- tất cả nút trừ gốc và lá có tối thiểu m/2 con và tối đa m con. Gốc có tối thiểu 2 con và tối đa m con.