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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/%282%2C_4%29-baum.svg/220px-%282%2C_4%29-baum.svg.png)
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 a và b, trong đó a và b là các số nguyên thỏa điều kiện 2 ≤ a ≤ (b+1)/2. Gốc, nếu không là lá, có số con nằm giữa 2 và b.
Định nghĩa
sửaGiả sử a, b là các số nguyên dương thỏa điều kiện 2 ≤ a ≤ (b+1)/2. Thì một cây có gốc T là cây (a,b) khi:
- Mỗi nút bên trong ngoại trừ gốc có ít nhất a và nhiều nhất b con.
- Gốc có nhiều nhất b 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
sửaEvery internal node v of a (a,b)-tree T has the following representation:
- Let be the number of child nodes of node v.
- Let be pointers to child nodes.
- Let be an array of keys such that equals the largest key in the subtree pointed to by .
Xem thêm
sửaTham khảo
sửa