template<class K, size_t M>
struct BTreeNode
{K _keys[M]; // 用于存储关键字的数组，最多容纳 M 个关键字（超额一个，为分裂提供空间）。BTreeNode<K, M>* _subs[M + 1]; // 存储子节点的指针数组，最多 M+1 个子节点。BTreeNode<K, M>* _parent; // 指向父节点的指针。size_t _n; // 当前节点中实际存储的关键字数量。// 构造函数，初始化节点的各个属性。BTreeNode(){for (size_t i = 0; i < M; i++){_keys[i] = K(); // 初始化关键字数组为默认值。_subs[i] = nullptr; // 初始化子节点指针为空。}_subs[M] = nullptr; // 多余的子节点指针初始化为空。_parent = nullptr; // 父节点初始化为空。_n = 0; // 初始关键字数量为 0。}
};
- 作用：定义 B 树节点的结构，包括关键字数组、子节点指针、父节点指针和当前节点的关键字数量。
- 意义：
- 为 B 树的基本操作（插入、删除、查找等）提供节点存储结构。
- 允许节点存储最多 M 个关键字和 M+1 个子节点。
template<class K, size_t M>
class BTree
{typedef BTreeNode<K, M> Node; // 定义一个别名，便于后续引用节点类型。public:pair<Node*, int> Find(const K& key)
{Node* cur = _root; // 从根节点开始查找。Node* parent = nullptr; // 记录当前节点的父节点。while (cur){size_t i = 0;// 在当前节点中逐一比较关键字while (i < cur->_n){if (key < cur->_keys[i]) // 如果目标关键字小于当前关键字，停止查找。{break;}else if (key > cur->_keys[i]) // 如果目标关键字大于当前关键字，继续查找。{i++;}else // 找到目标关键字，返回节点和索引。{return make_pair(cur, i);}}parent = cur; // 更新父节点为当前节点。cur = cur->_subs[i]; // 进入对应的子节点。}return make_pair(parent, -1); // 未找到，返回最近的父节点及无效索引。
}void InsertKey(Node* node, const K& key, Node* child)
{int end = node->_n - 1; // 从节点的最后一个关键字开始比较。while (end >= 0){if (key < node->_keys[end]) // 如果新关键字小于当前关键字，向右移动当前关键字和其右子树。{node->_keys[end + 1] = node->_keys[end];node->_subs[end + 2] = node->_subs[end + 1];end--;}else // 如果新关键字大于等于当前关键字，停止移动。{break;}}node->_keys[end + 1] = key; // 插入新关键字。node->_subs[end + 2] = child; // 插入对应的子节点。if (child){child->_parent = node; // 更新子节点的父节点指针。}node->_n++; // 更新节点的关键字数量。
}bool Insert(const K& key)
{if (_root == nullptr) // 如果树为空，创建根节点并插入关键字。{_root = new Node;_root->_keys[0] = key;_root->_n++;return true;}// key已经存在，不允许插入pair<Node*, int> ret = Find(key);if (ret.second >= 0){return false;}K newKey = key; // 保存当前要插入的关键字。Node* child = nullptr; // 保存分裂后产生的新节点。Node* parent = ret.first; // 从查找到的父节点开始插入。while (1){InsertKey(parent, newKey, child); // 插入关键字到节点。if (parent->_n < M) // 如果节点未满，插入完成。{return true;}else // 如果节点满了，进行分裂。{size_t mid = M / 2; // 找到中间关键字的位置。Node* brother = new Node; // 创建一个新节点作为兄弟节点。size_t j = 0;size_t i = mid + 1;for (; i <= M - 1; i++) // 将中间关键字右边的部分移动到兄弟节点。{brother->_keys[j] = parent->_keys[i];brother->_subs[j] = parent->_subs[i];if (parent->_subs[i]){parent->_subs[i]->_parent = brother;}j++;}brother->_subs[j] = parent->_subs[i]; // 拷贝最后一个右子树。if (parent->_subs[i]){parent->_subs[i]->_parent = brother;}brother->_n = j; // 更新兄弟节点的关键字数量。parent->_n -= (brother->_n + 1); // 更新父节点的关键字数量。K midkey = parent->_keys[mid]; // 提取中间关键字。parent->_keys[mid] = K(); // 清空中间关键字。if (parent->_parent == nullptr) // 如果分裂的是根节点，创建新根节点。{_root = new Node;_root->_keys[0] = midkey;_root->_subs[0] = parent;_root->_subs[1] = brother;_root->_n = 1;parent->_parent = _root;brother->_parent = _root;break;}else // 如果分裂的不是根节点，继续向上插入。{newKey = midkey;child = brother;parent = parent->_parent;}}}return true;
}void _Inorder(Node* root)
{if (root == nullptr){return;}size_t i = 0;for (i = 0; i < root->_n; i++) // 遍历当前节点的关键字和子树。{_Inorder(root->_subs[i]); // 递归遍历左子树。cout << root->_keys[i] << " "; // 打印当前关键字。}_Inorder(root->_subs[i]); // 遍历最后一个右子树。
}
void TestBtree()
{int a[] = {53, 139, 75, 49, 145, 36, 101}; // 要插入的关键字数组。BTree<int, 3> t; // 创建阶数为 3 的 B 树。for (auto e : a){t.Insert(e); // 插入每个关键字。}t.Inorder(); // 打印中序遍历结果。
}
)
)
