Sắp xếp bằng cây B-Tree trong C++

B-Tree là cây n-ary, mỗi nút chứa tối đa 5 khóa. Chèn các phần tử vào B-Tree, sau đó duyệt in-order (traverse) để lấy dãy đã sắp xếp.

Ý tưởng

1. Tạo nút gốc, chèn lần lượt các giá trị.
2. Nếu nút đầy (5 khóa), tách nút (split) tạo cấp mới.
3. Dùng bubble sort trong nút (vì số phần tử nhỏ).
4. Duyệt cây: đệ quy con trái, in khóa, đệ quy con phải.

Cấu trúc nút

struct BTreeNode {
    int* data;           // mảng 5 khóa
    BTreeNode** child;   // mảng 6 con trỏ
    bool leaf;
    int n;               // số khóa hiện tại
};

Hàm chính

• insert(a): chèn giá trị, tách nút nếu cần.
• split_child(x, i): tách nút x tại vị trí con i.
• traverse(p): duyệt in-order.

Kết quả mẫu

Nhập 8 phần tử: 54 23 98 52 10 23 47 84
Duyệt cây: 10 23 23 47 52 54 84 98