网站编辑做seo好做吗,顺德网站建设,一六八互联网站建设,网络营销软文范例一、常见的搜索结构
1、顺序查找 时间复杂度#xff1a;O(N)
2、二分查找 时间复杂度#xff1a;O(logN) 要求#xff1a;#xff08;1#xff09;有序 #xff08;2#xff09;支持下标的随机访问
3、二叉搜索树#xff08;BS树#xff09; 时间复杂…
一、常见的搜索结构
1、顺序查找 时间复杂度O(N)
2、二分查找 时间复杂度O(logN) 要求1有序 2支持下标的随机访问
3、二叉搜索树BS树 时间复杂度O(logN)——O(N) 若接近有序的数据插入到BS中会导致退化成单支树时间复杂度退化为O(N)
4、平衡搜索树 AVL树和RB树 时间复杂度O(logN) 在BS的基础上通过一些规则加以限制通过旋转来限制高度,维持logN的时间复杂度
5、哈希 时间复杂度O(1) 底层是散列表要注意解决哈希冲突。综合效率优于平衡搜索树 以上结构适合用于数据量相对不是很大能够一次性存放在内存中内查找进行数据查找的场景。如果数据量很大比如有100G数据无法一次放进内存中那就只能放在磁盘上了如果放在磁盘上有需要搜索某些数据那么如果处理呢那么我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中那么要访问数据时先取这个地址去磁盘访问数据。B树系列 解决外查找的问题 根据上面的分析我们知道B树系列是为了解决外查找的问题而生的但是你可能会有这样的疑惑虽然高度下降了但是由于我的一个节点存储这多个关键字信息那么我即使找到这个节点不也是要遍历关键字信息效率真的能提高么 答在磁盘中的搜索来说定位的效率低但是如果准确定位到了节点后面效率就会很高顺序遍历节点中的关键字这个跟磁盘的底层结构有关具体可以参照下面的文献去理解。 二、B树的概念 1970年R.Bayer和E.mccreight提出了一种适合外查找的树它是一种平衡的多叉树称为B树(后面有一个B的改进版本B树、B*树然后有些地方的B树写的的是B-树注意不要误读成B减树)。一棵m阶(m2)的B树是一棵平衡的M路平衡搜索树可以是空树或者满足一下性质
1根节点至少有两个孩子
2每个分支节点都包含k-1个关键字和k个孩子其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数
3每个叶子节点都包含k-1个关键字其中 ceil(m/2) ≤ k ≤ m 4所有的叶子节点都在同一层
5每个节点中的关键字从小到大排列节点当中k-1个元素正好是k个孩子包含的元素的值域划 分 6每个结点的结构为nA0K1A1K2A2… KnAn其中Ki(1≤i≤n)为关键 字且KiKi1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki1。 7实际中M通常会设计得比较大比如1024
以上规则可能还有点抽象我们通过分析B树的插入来剖析具体的过程
三、B树的插入过程分析 为了简单起见假设M 3. 即三叉树每个节点中存储两个数据两个数据可以将区间分割成三个部分因此节点应该有三个孩子为了后续实现简单期间节点的结构如下
注意孩子比关键字多一个并且为了防止越界的问题我们多开一个空间 用序列{53, 139, 75, 49, 145, 36, 50,47,101}构建B树的过程如下
1插入53
2插入139 3插入75
4进行分裂 这里可以解释为什么ceil(m/2) ≤ k ≤ M
假设M是偶数 比如是10 那么后面5个给兄弟中位数给父亲自己还剩下4个兄弟会多一个
假设M是奇数 比如是11 那么后面5个给兄弟中位数给父亲自己还剩下5个正好一样多
5插入49 分析以下当B树有多个叶子节点的时候如何去选取我们要插入的叶子节点。
答B树的逻辑是 左-根-左-根-左-根……-右我们先忽略掉后面这个右子树把它抽象成一个节点对应一个左子树在拓展兄弟的时候是向右拓展的所以我们找的是要左小的找。 举个例子49比75小那么必然在75左孩子那边此时可以直接往下走但是如果139比75大那么此时不能直接到下一层而是先往后找直到找到一个比自己大的节点如果后面没有就是当前节点的左孩子去找。
6插入145 7插入36 8进行分裂 9插入50 10插入47 11插入101 12继续分裂 13二次分裂 四、B树简单模拟实现
4.1 B树的节点设计
templateclass K,size_t M
struct BTreeNode
{BTreeNode(){for (size_t i 0; i M; i){_keys[i] K(); //K的默认构造_subs[i] nullptr;}_subs[M] nullptr;_parent nullptr;_n 0;}//关键字永远比孩子少一个 为了方便插入我们多开一个空间 预防边界情况K _keys[M]; //M-1个关键字BTreeNodeK, M* _subs[M 1];// 孩子的集合 M个孩子BTreeNodeK, M* _parent;//父亲节点 方便插入的时候向上回溯size_t _n; //实际存了多少节点
};
templateclass K, size_t M
class BTree
{typedef BTreeNodeK, M Node;
public:private:Node* _rootnullptr;
};
1、K代表K类型一般是表示地址当然也可以是KV模型
2、M表示这是M路多叉树
3、_subs表示孩子节点的集合_keys表示关键字的集合为了防止边界情况的判断统一多开一个空间。
4、_n表示一共个有效的关键字
5、_parent是父亲节点维护父亲的原因是我们需要向上传中位数如果不维护一个父亲节点会比较难实现但是增加了一个指针同时也要十分注意去维护这个指针容易忽略。
4.2 B树的查找 在B树不允许键值冗余的情况下如果我们想插入一个节点那么我们要保证B树没有该节点因此我们在实现插入之前先实现一个查找的函数
pairNode*, int Find(const K key) //查找这个节点以及对应关键字的下标
{Node* cur _root;Node* parent nullptr;//如果没找到 把父亲节点带回来while (cur) //因为i每次都要重头开始算{size_t i 0; while (i cur-_n){if (key cur-_keys[i]) break; //keys[i]的左孩子根他的下标是相等的else if (key cur-_keys[i]) i; //左才会往下跳 比右小ielse return make_pair(cur, i);}//但是有可能走到空都不会结束 找不到就往自己的孩子去跳parent cur;cur cur-_subs[i];}return make_pair(parent, -1);
}
1、返回值pairNode*,int 前一个返回对应的节点后一个表示对应节点中的下标。
2、parent指针的意义因为我们在插入之前必须要调用这个查找函数并且必须插入到相应的叶子节点中去。那么我们可以顺便通过这个返回值返回我们要插入的叶子节点。这样在insert函数中接受find函数的返回值的时就可以直接拿到待插入的叶子节点。
3、因为拓展都是往右拓展的所以我们必须要确保比key当前元素小我们才能跳到下一层去找他的左孩子并且每次都要从第一个位置开始找如果比当前元素大的话那么先往后找而不是直接往该节点的右孩子找
4.3 插入key的过程 我们多开一块空间的目的先进行无脑插入然后再去检查该节点是否满了如果满了再进行分裂调整但是我们有些时候可能不光要插入key还要插入新增的节点。
//每次循环往cur插入newkey和child
void InsertKey(Node* node, const K key, Node* child)
{int end node-_n - 1;while (end 0) //如果我比你小你就往后挪 类似插入排序逻辑{if (key node-_keys[end]) //挪动key 还要挪动右孩子{node-_keys[end 1] node-_keys[end];node-_subs[end 2] node-_subs[end1];--end;}else break; //找到了就放}node-_keys[end 1] key;node-_subs[end 2] child;if (child) child-_parent node; // 一定要记得反向链接维护parent指针node-_n;
}
1、只有多次分裂的时候才会出现需要链接新增的节点如果只有一次分裂的话child就是nullptr所以在反向链接的时候要注意
2、在插入关键字的时候我们按照插入排序的逻辑从后开始往前找不断将比自己大的元素往后挪挪动的时候要别忘了把他的右子树也跟着往后挪动。
3、end必须设置成int而不能是size_t因为是从后往前找的所以end是有可能会出现负数的。
4.4 B树的插入整体实现
bool Insert(const K key)
{if (_root nullptr) //如果我为空 那我就让自己成为新的根{_root new Node;_root-_keys[0] key;_root-_n; return true;}//如果不为空 开始执行插入逻辑pairNode*, int ret Find(key);if (ret.second0) return false;//如果没有找到find顺便带回了要插入的叶子节点Node* cur ret.first;//每次循环往cur插入newkey和childK newKey key;Node* child nullptr;while (1){InsertKey(cur, newKey, child);//情况1 没满 直接结束if (cur-_n M) return true;Node* brother new Node;//分裂一半[mid1,M-1]给兄弟 找到中间那个值size_t mid M / 2;size_t i mid 1;size_t j 0;for (; i M; i, j){//拷贝key和key的左孩子brother-_keys[j] cur-_keys[i]; brother-_subs[j] cur-_subs[i]; //节点也拷过去//与父亲建立连接if (cur-_subs[i]) cur-_subs[i]-_parent brother;//清理一下方便观察cur-_keys[i] K();cur-_subs[i] nullptr;}// 还有最后一个右孩子拷过去brother-_subs[j] cur-_subs[i];if (cur-_subs[i]) cur-_subs[i]-_parent brother; //孩子如果不是空 那么父亲就得更新一下cur-_subs[i] nullptr;brother-_n j;cur-_n - (brother-_n 1);//因为还要把中位数往上放K midKey cur-_keys[mid];cur-_keys[mid] K();//方便观察//转化成往cur的parent去插入 cur-[mid]和 brother// 说明刚刚分裂是根节点if (cur-_parent nullptr){_root new Node; //最坏情况 我的父亲是空那就造一个新的根出来_root-_keys[0] midKey;_root-_subs[0] cur;_root-_subs[1] brother;_root-_n 1;//链接起来cur-_parent _root;brother-_parent _root;break;}else //如果父亲不是空还可以向上调整{// 转换成往parent-parent 去插入parent-[mid] 和 brothernewKey midKey;child brother;cur cur-_parent;}}return true;
}
1、如果什么也没有那么自己就成为新的树。
2、通过find函数去找B树中是否存在这个关键字如果存在就结束不存在那就把返回的pair中的first待插入的叶子节点提取出来。
3、因为有可能会涉及到多次分裂所以我们要将插入的函数写在循环里面通过cur、newkey、child来帮助我们迭代 然后每次插入之后就去判断是否还要进行分裂。如果没满就结束如果满了就分裂。
4、分裂一半的key和节点要注意节点的反向链接给自己的兄弟然后清理一下数据方便我们调试观察最后有一个右孩子还得再拷贝一次。
5、传中位数的时候如果cur没有父亲那么就直接造一个父亲出来。如果cur有父亲就更新一下cur、newkey、child继续往上迭代去走。将问题转化成往父亲节点插入中位数和一个brother节点。
4.5 B树的中序遍历验证 他的整体逻辑是左、根、左、根、左、根……右 所以我们可以将前两个过程抽出来然后最后再单独处理右。走一个中序遍历的逻辑实现有序。 void _InOrder(Node* cur){if (cur nullptr) return;// 左 根 左 根 ... 右size_t i 0;for (; i cur-_n; i){_InOrder(cur-_subs[i]); // 左子树cout cur-_keys[i] ; // 根}_InOrder(cur-_subs[i]); // 最后的那个右子树}void InOrder(){_InOrder(_root);} 附上测试用例
void testBtree()
{BTreeint, 3 t;int a[] { 53, 139, 75, 49, 145, 36, 101 };for (auto e : a) t.Insert(e);t.InOrder();
} 4.6 整体的代码
#pragma once
#includeiostream
using namespace std;//K表示存的地址 M表示最多有几个分支
templateclass K,size_t M
struct BTreeNode
{BTreeNode(){for (size_t i 0; i M; i){_keys[i] K(); //K的默认构造_subs[i] nullptr;}_subs[M] nullptr;_parent nullptr;_n 0;}//关键字永远比孩子少一个 为了方便插入我们多开一个空间 预防边界情况K _keys[M]; //M-1个关键字BTreeNodeK, M* _subs[M 1];// 孩子的集合 M个孩子BTreeNodeK, M* _parent;//父亲节点 方便插入的时候向上回溯size_t _n; //实际存了多少节点
};templateclass K, size_t M
class BTree
{typedef BTreeNodeK, M Node;
public:pairNode*, int Find(const K key) //查找这个节点以及对应关键字的下标{Node* cur _root;Node* parent nullptr;//如果没找到 把父亲节点带回来while (cur) //因为i每次都要重头开始算{size_t i 0; while (i cur-_n){if (key cur-_keys[i]) break; //keys[i]的左孩子根他的下标是相等的else if (key cur-_keys[i]) i; //左才会往下跳 比右小ielse return make_pair(cur, i);}//但是有可能走到空都不会结束 找不到就往自己的孩子去跳parent cur;cur cur-_subs[i];}return make_pair(parent, -1);}//每次循环往cur插入newkey和childvoid InsertKey(Node* node, const K key, Node* child){int end node-_n - 1;while (end 0) //如果我比你小你就往后挪 类似插入排序{if (key node-_keys[end]) //挪动key 还要挪动右孩子{node-_keys[end 1] node-_keys[end];node-_subs[end 2] node-_subs[end1];--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;}//如果不为空 开始执行插入逻辑pairNode*, int ret Find(key);if (ret.second0) return false;//如果没有找到find顺便带回了要插入的叶子节点Node* cur ret.first;//每次循环往cur插入newkey和childK newKey key;Node* child nullptr;while (1){InsertKey(cur, newKey, child);//情况1 没满 直接结束if (cur-_n M) return true;Node* brother new Node;//分裂一半[mid1,M-1]给兄弟 找到中间那个值size_t mid M / 2;size_t i mid 1;size_t j 0;for (; i M; i, j){//拷贝key和key的左孩子brother-_keys[j] cur-_keys[i]; brother-_subs[j] cur-_subs[i]; //节点也拷过去//与父亲建立连接if (cur-_subs[i]) cur-_subs[i]-_parent brother;//清理一下方便观察cur-_keys[i] K();cur-_subs[i] nullptr;}// 还有最后一个右孩子拷过去brother-_subs[j] cur-_subs[i];if (cur-_subs[i]) cur-_subs[i]-_parent brother; //孩子如果不是空 那么父亲就得更新一下cur-_subs[i] nullptr;brother-_n j;cur-_n - (brother-_n 1);//因为还要把中位数往上放K midKey cur-_keys[mid];cur-_keys[mid] K();//方便观察//转化成往cur的parent去插入 cur-[mid]和 brother// 说明刚刚分裂是根节点if (cur-_parent nullptr){_root new Node; //最坏情况 我的父亲是空那就造一个新的根出来_root-_keys[0] midKey;_root-_subs[0] cur;_root-_subs[1] brother;_root-_n 1;//链接起来cur-_parent _root;brother-_parent _root;break;}else //如果父亲不是空还可以向上调整{// 转换成往parent-parent 去插入parent-[mid] 和 brothernewKey midKey;child brother;cur cur-_parent;}}return true;}void _InOrder(Node* cur){if (cur nullptr) return;// 左 根 左 根 ... 右size_t i 0;for (; i cur-_n; i){_InOrder(cur-_subs[i]); // 左子树cout cur-_keys[i] ; // 根}_InOrder(cur-_subs[i]); // 最后的那个右子树}void InOrder(){_InOrder(_root);}private:Node* _rootnullptr;
};void testBtree()
{BTreeint, 3 t;int a[] { 53, 139, 75, 49, 145, 36, 101 };for (auto e : a) t.Insert(e);t.InOrder();
} 4.7 B树的性能分析 对于一棵节点为N度为M的B-树查找和插入需要$log{M-1}N$~$log{M/2}N$次比较这个很好证明对于度为M的B-树每一个节点的子节点个数为M/2 ~(M-1)之间因此树的高度应该在要 $log{M-1}N$和$log{M/2}N$之间在定位到该节点后再采用二分查找的方式可以很快的定位 到该元素。 B-树的效率是很高的对于N 62*1000000000个节点如果度M为1024则$log_{M/2}N$ 4即在620亿个元素中如果这棵树的度为1024则需要小于4次即可定位到该节点然后利用二分查找可以快速定位到该元素大大减少了读取磁盘的次数。
4.8 B树的删除过程分析 1、删除36 2、删除40 3、删49 4、删150 5、删160 五、B树系列
5.1 B树 B树是B树的变形是在B树基础上优化的多路平衡搜索树B树的规则跟B树基本类似但是又在B树的基础上做了以下几点改进优化
1分支节点的子树指针与关键字个数相同相当于去掉了左边的子树相比B树取消了孩子和关键字的包含关系而是一一对应 2分支节点的子树指针p[i]指向关键字值大小在[k[i]k[i1])区间之间和B树一致 3 所有叶子节点增加一个链接指针链接在一起这样就可以直接找到叶子节点不一定需要从根去找了 4所有关键字及其映射数据都在叶子节点出现1、分支节点和叶子节点有重复的值分支节点存的是叶子节点的索引-key.2、父亲中存的是孩子节点中的最小值做索引
和B树规则区别总结
1、简化B树孩子比关键字多一个的规则变成了相等一一对应。
2、而key value都存在叶子节点上一方面是节省空间一方面是方便遍历查找所有值
B树的特性1. 所有关键字都出现在叶子节点的链表中且链表中的节点都是有序的。 2. 不可能在分支节点中命中因为只存k而没有存kv。 3. 分支节点相当于是叶子节点的索引叶子节点才是存储数据的数据层 5.2 B树的插入过程分析 用序列{53, 139, 75, 49, 145, 36, 50,47,101}构建B树的过程如下
1、插入53 2、插入139 3、插入75 4、插入49 5、分裂 6、插入145 7、插入36 8、插入50 9、分裂 10、插入47 11、插入101 12、分裂 13、二次分裂 和B树插入的区别
1、一开始创建的是两层一层做根一层做分支
2、父亲节点存的是孩子节点中的最小值做索引如果最小值更新了那么往上的索引值都要全部更新
3、孩子不再是比key多一个包含关系而是和key相等一一对应关系
4、分裂的时候不再是把中位数往上拿而是把分裂出来的兄弟节点的最小值往上拿
5.3 B*树
B*树是B树的变形在B树的非根和非叶子节点再增加指向兄弟节点的指针。为什么B*树的非叶子节点需要指向兄弟节点的指针呢而B树不需要呢 究竟想达到什么目的
B树的分裂 当一个结点满时分配一个新的结点并将原结点中1/2的数据复制到新结点最后在父结点中增加新结点的指针B树的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向兄弟的指针。
B*树的分裂 当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父结点增加新结点的指针。所以B*树的关键字和孩子数量-[2/3M——M] 所以B*树分配新结点的概率比B树要低空间使用率更高
5.3 B树系列总结
B树有序数组平衡多叉树 B树有序数组链表平衡多叉树 B*树一棵更丰满的空间利用率更高的B树。
