Cây (a,b)

Hình ảnh minh hoạ khái niệm cây(a,b)

Trong khoa học máy tính, cây (a,b) (tiếng Anh: (a,b) tree là một loại cây tìm kiếm cân bằng.

Cây (a,b) có tất cả các lá có cùng độ sâu, và tất cả các nút bên trong ngoại trừ gốc nằm giữa con Bản mẫu:Mvar và Bản mẫu:Mvar, trong đó Bản mẫu:Mvar và Bản mẫu:Mvar là các số nguyên thỏa điều kiện Bản mẫu:Math. Gốc, nếu không là lá, có số con nằm giữa 2 và Bản mẫu:Mvar.

Định nghĩa

Giả sử Bản mẫu:Mvar, Bản mẫu:Mvar là các số nguyên dương thỏa điều kiện Bản mẫu:Math. Thì một cây có gốc Bản mẫu:Mvar là cây (a,b) khi:

• Mỗi nút bên trong ngoại trừ gốc có ít nhất Bản mẫu:Mvar và nhiều nhất Bản mẫu:Mvar con.
• Gốc có nhiều nhất Bản mẫu:Mvar con.
• Tất cả các đường dẫn từ gốc đến lá có cùng chiều dài.

Biểu diễn nút bên tron

Every internal node Bản mẫu:Mvar of a (a,b)-tree Bản mẫu:Mvar has the following representation:

• Let ${\rho }_v$ be the number of child nodes of node Bản mẫu:Mvar.
• Let $S_v[1\dots {\rho }_v]$ be pointers to child nodes.
• Let $H_v[1\dots {\rho }_v-1]$ be an array of keys such that $H_v[i]$ equals the largest key in the subtree pointed to by $S_v[i]$.

Xem thêm

• B-tree
• 2-3 tree
• 2-4 tree

Tham khảo

• Bản mẫu:DADS

Bản mẫu:Datastructure-stub