✨Cây (a,b)

nhỏ|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 và , trong đó và là các số nguyên thỏa điều kiện . Gốc, nếu không là lá, có số con nằm giữa 2 và .

Định nghĩa

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

• Mỗi nút bên trong ngoại trừ gốc có ít nhất và nhiều nhất con.
• Gốc có nhiều nhất 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 of a (a,b)-tree has the following representation:

• Let $\backslash rho\_v$ be the number of child nodes of node .
• Let $S\_v[1\; \backslash dots\; \backslash rho\_v]$ be pointers to child nodes.
• Let $H\_v[1\; \backslash dots\; \backslash 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]$.