B-tree

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// B-Tree节点
class BTreeNode {
public:
    vector<int> keys;  // 存储不同数值
    vector<BTreeNode*> children;  // 存储指向相应数值的孩子的指针
    bool isLeaf;  // 是否为叶子节点

    BTreeNode(bool leaf) : isLeaf(leaf) {}

    // 查找某个键值的下标
    int findKey(int k) {
        int idx = 0;
        while (idx < keys.size() && keys[idx] < k)
            idx++;
        return idx;
    }
};

// B-Tree类
class BTree {
private:
    BTreeNode* root;
    int t;  // B树的最小度数（人为规定）

public:
    // 构造函数
    BTree(int t) : t(t) {
        root = new BTreeNode(true);
    }

    // 插入一个键
    void insert(int k) {
        if (root->keys.size() == 2 * t - 1) {
            // 根节点满了，需要分裂
            BTreeNode* newRoot = new BTreeNode(false);
            newRoot->children.push_back(root);
            splitChild(newRoot, 0);
            root = newRoot;
        }
        insertNonFull(root, k);
    }

    // 查找键值
    bool search(int k) {
        return searchHelper(root, k);
    }

    // 打印树结构（用于调试）
    void printTree() {
        printTreeHelper(root, 0);
    }

private:
    // 插入到非满节点
    void insertNonFull(BTreeNode* node, int k) {
        int idx = node->findKey(k);
        if (node->isLeaf) {
            node->keys.insert(node->keys.begin() + idx, k);
        } else {
            if (node->children[idx]->keys.size() == 2 * t - 1) {
                splitChild(node, idx);
                if (k > node->keys[idx]) {
                    idx++;
                }
            }
            insertNonFull(node->children[idx], k);//递归直到到达叶子节点层，插入，如果满了则分裂
        }
    }

    // 分裂子节点
    void splitChild(BTreeNode* parent, int idx) {
        BTreeNode* fullChild = parent->children[idx];
        BTreeNode* newChild = new BTreeNode(fullChild->isLeaf);

        // 将fullChild的后半部分移动到newChild
        parent->keys.insert(parent->keys.begin() + idx, fullChild->keys[t - 1]);
        parent->children.insert(parent->children.begin() + idx + 1, newChild);

        newChild->keys.assign(fullChild->keys.begin() + t, fullChild->keys.end());
        fullChild->keys.resize(t - 1);

        if (!fullChild->isLeaf) {
            newChild->children.assign(fullChild->children.begin() + t, fullChild->children.end());
            fullChild->children.resize(t);
        }
    }

    // 查找树中是否存在某个键
    bool searchHelper(BTreeNode* node, int k) {
        int idx = node->findKey(k);
        if (idx < node->keys.size() && node->keys[idx] == k) {
            return true;
        } else if (node->isLeaf) {
            return false;
        } else {
            return searchHelper(node->children[idx], k);
        }
    }

    // 打印树（递归方式）
    void printTreeHelper(BTreeNode* node, int level) {
        cout << string(level, ' ') << "[";
        for (size_t i = 0; i < node->keys.size(); i++) {
            cout << node->keys[i] << " ";
        }
        cout << "]" << endl;
        if (!node->isLeaf) {
            for (size_t i = 0; i < node->children.size(); i++) {
                printTreeHelper(node->children[i], level + 1);
            }
        }
    }
};

// 测试B-树实现
int main() {
    BTree btree(3);  // 创建一个最小度数为3的B树

    // 插入一些数据
    btree.insert(10);
    btree.insert(20);
    btree.insert(5);
    btree.insert(6);
    btree.insert(12);
    btree.insert(30);
    btree.insert(7);
    btree.insert(17);

    // 打印树结构
    cout << "B-Tree structure:" << endl;
    btree.printTree();

    // 查找数据
    int key = 12;
    if (btree.search(key)) {
        cout << "Key " << key << " found in the tree." << endl;
    } else {
        cout << "Key " << key << " not found in the tree." << endl;
    }

    return 0;
}