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  be the number of child nodes of node .
 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
B-tree
2-3 tree
2-4 tree

Tham khảo


Thể loại:Cây tìm kiếm