Một cây FP (FP-tree) là một biểu diễn chắc chắn (compact representation) của dữ liệu đầu vào. Nó được xây dựng bằng cách đọc tập dữ liệu một giao dịch (transaction) tại một thời điểm và ánh xạ mỗi giao dịch lên một tuyến đường (path) trong cây FP. Một số giao dịch có thể có nhiều mặt hàng (items) chung, tuyến đường của chúng có thể chồng chéo (overlap).
Càng nhiều tuyến đường chồng chéo với nhau, càng nhiều nén có thể thực hiện sử dụng kiến trúc cây FP. Nếu kích thước cây FP đủ để vừa vặn vào bộ nhớ chính (main memory), điều này sẽ cho phép chúng ta trích xuất các tập mục thường xuyên (frequent itemsets) trực tiếp từ kiến trúc trong bộ nhớ thay vì tạo các lần lặp qua dữ liệu lưu trên đĩa.
Mỗi nút trong cây bao gồm nhãn của một mặt hàng cùng với một bộ đếm (counter) hiển thị số lượng giao dịch được ánh xạ lên tuyến đường cho trước. Ban đầu, cây FP chỉ bao gồm nút gốc (root node) được xác định bởi ký hiệu null.
Cây FP được mở rộng theo các phương pháp sau:
Tập dữ liệu được tìm kiếm một lần để quyết định số đếm hỗ trợ (support count) của mỗi mặt hàng. Mặt hàng không thường xuyên (Infrequent items) bị loại bỏ, trong khi các mặt hàng thường xuyên được giữ lại theo thứ tự giảm dần của số đếm hỗ trợ.
Thuật toán tạo một lần lặp thứ hai qua dữ liệu để tạo cây FP. Sau khi xem xét giao dịch đầu tiên, {a, b}, các nút được gán nhãn a và b được tạo. Một tuyến đường được hình thành từ null→a→b để mã hóa giao dịch. Mỗi nút dọc theo tuyến đường có số đếm tần suất bằng 1.
Sau khi xem xét giao dịch thứ hai, {b, c, d}, một tập mới các nút được tạo cho mặt hàng b, c, và d. Một tuyến đường sau đó được hình thành để xác định giao dịch bằng cách liên kết các nút null→b→c→d.
Mỗi nút dọc theo tuyến đường này cũng có số đếm tần suất bằng một. Mặc dù hai giao dịch đầu tiên có một mặt hàng chung, là b, tuyến đường của chúng là rời rạc (disjoint) vì các giao dịch không chia sẻ tiền tố chung (common prefix).
Giao dịch thứ ba, {a, c, d, e}, chia sẻ một mặt hàng tiền tố chung (là a) với giao dịch đầu tiên. Theo đó, tuyến đường cho giao dịch thứ ba, null→a→c→d→e, chồng chéo với tuyến đường cho giao dịch đầu tiên, null→a→b. Do tuyến đường chồng chéo, số đếm tần suất cho nút a được tăng lên hai, trong khi số đếm tần suất cho các nút mới tạo c, d, và e bằng một.
Giai đoạn này tiếp tục cho đến khi mỗi giao dịch đã được ánh xạ lên một trong các tuyến đường cho trước trong cây FP. Kích thước của một cây FP nhỏ hơn kích thước dữ liệu không nén vì nhiều giao dịch trong thông tin giỏ hàng (market basket) chia sẻ nhiều mặt hàng chung.