dw怎样做网站链接,精准营销系统,做网站小程序的客户是怎么找的,宁波seo哪家好数据结构 —— B树 B树B树的插入操作分裂孩子分裂父亲分裂 我们之前学过了各种各样的树#xff0c;二叉树#xff0c;搜索二叉树#xff0c;平衡二叉树#xff0c;红黑树等等等等#xff0c;其中平衡二叉树和红黑树都是控制树的高度来控制查找次数。
但是#xff0c;这都… 数据结构 —— B树 B树B树的插入操作分裂孩子分裂父亲分裂 我们之前学过了各种各样的树二叉树搜索二叉树平衡二叉树红黑树等等等等其中平衡二叉树和红黑树都是控制树的高度来控制查找次数。
但是这都基于内存能放的下 平衡二叉树和红黑树等数据结构确实是为了在内存中高效处理动态数据集而设计的。它们的主要目标是在各种操作如查找、插入和删除中保持对数时间复杂度O(log n)其中n是树中节点的数量。这意味着随着数据集的增长操作时间不会线性增长而是以较慢的速度增长保持较高的性能。 在设计上平衡二叉树和红黑树假设整个数据集能够被加载到内存中这是因为这些树的算法和操作需要频繁地遍历树的不同部分。磁盘I/O操作比内存访问要慢得多因此如果数据集太大而不能完全装入内存使用这些数据结构将大大降低效率。 但是直接在磁盘上实现平衡二叉树或红黑树通常不是最有效的方法因为磁盘访问的成本高而这类树的许多操作涉及多次磁盘读写。因此对于大规模数据集更常见的做法是使用专门针对磁盘访问优化的数据结构如B树或B树它们在设计上考虑了磁盘I/O的特性可以更有效地处理大量数据。
B树
1970年R.Bayer和E.mccreight提出了一种适合外查找的树它是一种平衡的多叉树称为B树(后面有一个B的改进版本B树然后有些地方的B树写的的是B-树注意不要误读成B减树)。一棵m阶(m2)的B树是一棵平衡的M路平衡搜索树可以是空树或者满足一下性质 根节点至少有两个孩子每个分支节点都包含k-1个关键字和k个孩子其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数每个叶子节点都包含k-1个关键字其中 ceil(m/2) ≤ k ≤ m所有的叶子节点都在同一层每个节点中的关键字从小到大排列节点当中k-1个元素正好是k个孩子包含的元素的值域划分每个结点的结构为nA0K1A1K2A2… KnAn其中Ki(1≤i≤n)为关键字且KiKi1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki1。n为结点中关键字的个数满足ceil(m/2)-1≤n≤m-1。 说白了我们以前的树中一个结点包含的数据量只能有一个 B树的基本思想就是一个结点可以携带多个数据 但是每个结点也有自己的要求一个结点要包括数据和孩子
假设我们是一棵3阶的B树规定每个结点的孩子最多有3个而数据个数比孩子个数小1
但是我们数据个数为偶数的话后面的分裂操作不好操作所以我们会多开一个数据空间但是不会装入任何数据同时会增加一个孩子
B树的插入操作
我们这里以3阶的B树为例
int a[] {53, 139, 75, 49, 145, 36, 101} //构建b树下面我们要插入75 这个时候数据个数已经超过了两个需要进行分裂
分裂
这个时候75被提出来 接下来我们插入49145
孩子分裂
接着我们插入36 父亲分裂
我们这样一直插入插入到139 B树的插入过程是反人类的是先有孩子再有父亲其中孩子会分裂父亲也会分裂
我们来看看代码大家能看懂多少看多少
#pragma once
#include iostream
using namespace std;// B-树节点模板定义
templateclass K, size_t M
struct BTreeNode
{// 键数组存储节点的关键字K _keys[M];// 子节点数组存储指向子节点的指针BTreeNodeK, M* _Children[M 1];// 指向父节点的指针BTreeNodeK, M* _Parent;// 节点中的实际关键字数量size_t _n;// 构造函数初始化节点BTreeNode(){// 初始化所有键为空for (int i 0; i M; i){_keys[i] K();_Children[i] nullptr;}// 初始化最后一个子节点指针为空_Children[M] nullptr;_Parent nullptr;_n 0; // 节点中实际关键字数量为0}
};// B-树模板类定义
templateclass K, size_t M
class BTree
{typedef BTreeNodeK, 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-_Children[i];}// 没有找到键返回父节点和-1return 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-_Children[end 2] node-_Children[end 1];end--;}else{break;}}// 插入新的键和子节点node-_keys[end 1] key;node-_Children[end 2] child;node-_n;}// 插入键的主函数bool Insert(const K key){if (_root nullptr){// 如果树为空创建根节点并插入键_root new _Node();_root-_keys[0] key;_root-_n;return true;}pair_Node*, int ret Find(key);if (ret.second 0){// 键已存在返回falsereturn false;}_Node* parent ret.first;K newkey key;_Node* child nullptr;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-_Children[j] parent-_Children[i];if (parent-_Children[i]){parent-_Children[i]-_Parent brother; //父节点分裂分裂出了父亲的brother}j;parent-_keys[i] K();}// 处理新节点的最后一个右孩子节点brother-_Children[j] parent-_Children[i];if (parent-_Children[i]){parent-_Children[i]-_Parent brother;}brother-_n j;parent-_n - j 1;// 将父节点的中间键提升到新节点newkey parent-_keys[mid];child brother;if (parent-_Parent nullptr){// 如果父节点是根节点则创建新的根节点_root new _Node();_root-_keys[0] parent-_keys[mid];_root-_Children[0] parent;_root-_Children[1] brother;_root-_n 1;parent-_keys[mid] K();parent-_Parent _root;brother-_Parent _root;break;}else{// 继续向父节点的父节点插入分裂后的节点newkey parent-_keys[mid];parent-_keys[mid] K();child brother;parent parent-_Parent;}}}return true;}// 中序遍历树的函数void InOrder(){_InOrder(_root);}// 递归实现的中序遍历void _InOrder(_Node* pRoot){if (nullptr pRoot)return;for (size_t i 0; i pRoot-_n; i){_InOrder(pRoot-_Children[i]);cout pRoot-_keys[i] ;}_InOrder(pRoot-_Children[pRoot-_n]);}private:// 树的根节点_Node* _root nullptr;
};// 测试函数
void Test()
{int a[] { 53, 139, 75, 49, 145, 36, 101, 34, 1, 9, 41 };BTreeint, 3 t;for (auto e : a){t.Insert(e);}t.InOrder();
}
我们可以测试如果打印的顺序是升序说明我们代码的逻辑没问题 写代码要注意几点 插入新结点有可能改变父子关系是第一个数据的孩子插入后有可能会变成第二个数据的孩子。分裂结点也有可能改变父子关系变成父亲兄弟的孩子
