Chương trình C++ triển khai cây B (B Tree)

Cây B (B-tree) là sự khái quát hóa của cây tìm kiếm nhị phân ở chỗ một nút có thể có hơn hai nút con. Về cơ bản là một cấu trúc dữ liệu cây tự cân bằng (self-balancing) duy trì dữ liệu đã sắp xếp và cho phép truy cập tuần tự, tìm kiếm, chèn và xóa trong thời gian logarit.

Dưới đây là chương trình C++ triển khai cây B bậc 6.

Thuật toán

Bắt đầu
  Hàm insert() để chèn nút vào cây:
    Khởi tạo x là root.
    Nếu x là lá và có chỗ cho thêm info thì chèn a vào x.
    Ngược lại nếu x không phải lá, làm:
      Tìm nút con của x sẽ được duyệt tiếp.
      Nếu nút con không đầy, thay đổi x trỏ đến nút con đó.
      Nếu nút con đầy, tách nó và thay đổi x trỏ đến một trong hai phần của nút con. Nếu a nhỏ hơn
      khóa giữa trong nút con, đặt x là phần đầu của nút con. Ngược lại là phần thứ hai.
      Khi tách nút con, di chuyển một khóa từ nút con đến cha x.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

struct BTree {
    int *d;
    BTree **child_ptr;
    bool l;
    int n;
}*r = NULL, *np = NULL, *x = NULL;

BTree* init() {
    int i;
    np = new BTree;
    np->d = new int[6];
    np->child_ptr = new BTree*[7];
    np->l = true;
    np->n = 0;
    for (i = 0; i < 7; i++) {
        np->child_ptr[i] = NULL;
    }
    return np;
}

void traverse(BTree *p) {
    cout << endl;
    int i;
    for (i = 0; i < p->n; i++) {
        if (p->l == false) {
            traverse(p->child_ptr[i]);
        }
        cout << " " << p->d[i];
    }
    if (p->l == false) {
        traverse(p->child_ptr[i]);
    }
    cout << endl;
}

void sort(int *p, int n) {
    int i, j, t;
    for (i = 0; i < n; i++) {
        for (j = i; j <= n; j++) {
            if (p[i] > p[j]) {
                t = p[i];
                p[i] = p[j];
                p[j] = t;
            }
        }
    }
}

int split_child(BTree *x, int i) {
    int j, mid;
    BTree *np1, *np3, *y;
    np3 = init();
    np3->l = true;
    if (i == -1) {
        mid = x->d[2];
        x->d[2] = 0;
        x->n--;
        np1 = init();
        np1->l = false;
        x->l = true;
        for (j = 3; j < 6; j++) {
            np3->d[j - 3] = x->d[j];
            np3->child_ptr[j - 3] = x->child_ptr[j];
            np3->n++;
            x->d[j] = 0;
            x->n--;
        }
        for (j = 0; j < 6; j++) {
            x->child_ptr[j] = NULL;
        }
        np1->d[0] = mid;
        np1->child_ptr[np1->n] = x;
        np1->child_ptr[np1->n + 1] = np3;
        np1->n++;
        r = np1;
    } else {
        y = x->child_ptr[i];
        mid = y->d[2];
        y->d[2] = 0;
        y->n--;
        for (j = 3; j < 6; j++) {
            np3->d[j - 3] = y->d[j];
            np3->n++;
            y->d[j] = 0;
            y->n--;
        }
        x->child_ptr[i + 1] = y;
        x->child_ptr[i + 1] = np3;
    }
    return mid;
}

void insert(int a) {
    int i, t;
    x = r;
    if (x == NULL) {
        r = init();
        x = r;
    } else {
        if (x->l == true && x->n == 6) {
            t = split_child(x, -1);
            x = r;
            for (i = 0; i < (x->n); i++) {
                if ((a > x->d[i]) && (a < x->d[i + 1])) {
                    i++;
                    break;
                } else if (a < x->d[0]) {
                    break;
                } else {
                    continue;
                }
            }
            x = x->child_ptr[i];
        } else {
            while (x->l == false) {
                for (i = 0; i < (x->n); i++) {
                    if ((a > x->d[i]) && (a < x->d[i + 1])) {
                        i++;
                        break;
                    } else if (a < x->d[0]) {
                        break;
                    } else {
                        continue;
                    }
                }
                if ((x->child_ptr[i])->n == 6) {
                    t = split_child(x, i);
                    x->d[x->n] = t;
                    x->n++;
                    continue;
                } else {
                    x = x->child_ptr[i];
                }
            }
        }
    }
    x->d[x->n] = a;
    sort(x->d, x->n);
    x->n++;
}

int main() {
    int i, n, t;
    cout << "Nhập số phần tử cần chèn:\n";
    cin >> n;
    for(i = 0; i < n; i++) {
        cout << "Nhập phần tử:\n";
        cin >> t;
        insert(t);
    }
    cout << "Duyệt cây B đã xây dựng:\n";
    traverse(r);
    return 0;
}

Kết quả đầu ra

Nhập số phần tử cần chèn: 7
Nhập phần tử: 10
Nhập phần tử: 20
Nhập phần tử: 30
Nhập phần tử: 40
Nhập phần tử: 50
Nhập phần tử: 60
Nhập phần tử: 70
Duyệt cây B đã xây dựng:
10 20 30 40 50 60 70