Cây nhị thức (Binomial Tree) là gì?
Cây nhị thức là cấu trúc dữ liệu cây có thứ tự. B₀ chỉ gồm 1 nút. Bₖ gồm 2 cây Bₖ₋₁ liên kết: gốc của một cây là con trái nhất của gốc cây kia. Cây nhị thức dùng trong phân tích tài sản/chứng khoán, nút đại diện giá trị nội tại.
Đống nhị thức (Binomial Heap) là gì?
Đống nhị thức là tập hợp các cây nhị thức thỏa mãn:
- Mỗi cây nhị thức trong đống đều có thứ tự heap (khóa nút ≥ khóa cha).
- Tối đa 1 cây nhị thức có gốc với bậc (degree) cho trước.
Biểu diễn bộ nhớ của nút Binomial Heap
Mỗi nút có 5 trường:
- Parent Pointer: địa chỉ nút cha.
- Key: dữ liệu/khóa của nút.
- Degree: bậc/cấp độ của nút.
- Left Child Pointer: địa chỉ con trái nhất.
- Sibling Pointer: địa chỉ anh em ngay sau (con phải của cha cùng cấp).
Các ví dụ minh họa
1. Nút đơn lẻ
2. Nút cha và con
3. Các nút anh em
Lưu ý: Hình ảnh minh họa cấu trúc con trỏ trong bộ nhớ.