三个年轻人做电影网站800万,wordpress google地图,手表网站官网,南宁网站建设哪家一、B树引入
二叉搜索树、平衡二叉树、红黑树都是动态查找树#xff0c;典型的二叉搜索树结构#xff0c;查找的时间复杂度和树的高度相关O(log2N)。 1#xff09;数据杂乱无章-------线性查找--O#xff08;n#xff09;
2#xff09;数据有序-------二分查找 ---O(lo…一、B树引入
二叉搜索树、平衡二叉树、红黑树都是动态查找树典型的二叉搜索树结构查找的时间复杂度和树的高度相关O(log2N)。 1数据杂乱无章-------线性查找--On
2数据有序-------二分查找 ---O(log 2 n 最差退化成单支树-----线性结构
3二叉搜索树、AVL树、红黑树 --------O(log2 n) 数据一般保存在磁盘上若数据量过大不能全部加载到内存为了访问所有数据使用如下搜索树结构保存数据树的结点中保存权值和磁盘的地址 那如何加速对数据的访问速度呢 提高I/O的时间 降低树的高度--平衡多叉树 二、B树定义 1970年R.Bayer和E.mccreight提出了一种适合外查找的树它是一种平衡的多叉树称为B树。 有些地方写的是B-树注意不要误读成B减树 一棵M阶(M2)的B树是一棵平衡的M路平衡搜索树可以是空树或者满足一下性质 1. 根节点至少有两个孩子 2. 每个非根节点至少有M/2(上取整)个孩子,至多有M个孩子 3. 每个非根节点至少有M/2-1(上取整)个关键字,至多有M-1个关键字并且以升序排列 4. key[i]和key[i1]之间的孩子节点的值介于key[i]、key[i1]之间 一次插入的过程53, 75, 139, 49, 145, 36, 101 #pragma once
#include iostream
#include stdlib.husing namespace std;templateclass K, int M
struct BTreeNode
{typedef BTreeNodeK, M Node;K _keys[M];//多给一个位置是为了先插入方便分裂Node* _sub[M1];Node* _parent;size_t _size;//记录关键字的个数BTreeNode():_parent(NULL),_size(0){for(size_t i 0; i M; i){_keys[i] K();_sub[i] 0;}_sub[M] 0;}
};templateclass K, int M
class BTree
{typedef BTreeNodeK, M Node;
public:BTree():_pRoot(NULL){}void Inorder(){_Inorder(_pRoot);}~BTree(){_Destroy(_pRoot);}bool Insert(const K key){if(NULL _pRoot){_pRoot new Node();_pRoot-_keys[0] key;_pRoot-_size;return true;}pairNode*, size_t temp _Find(key);if(temp.second ! -1){return false;}Node* cur temp.first;Node* sub NULL;K newKey key;while(1){_InsertKey(cur, newKey, sub);if(cur-_size M){return true;}while(cur-_size M){size_t mid cur-_size / 2;Node* NewNode new Node;for(size_t i mid1; i cur-_size; i){int j 0; //新节点的下标NewNode-_keys[j] cur-_keys[i];NewNode-_size;cur-_keys[i] K();//复制之后对应的原位置key置为初始值。j;}int j 0;for(size_t i mid1; i cur-_size1; i){NewNode-_sub[j] cur-_sub[i];if(NewNode-_sub[j])NewNode-_sub[j]-_parent NewNode;j;cur-_sub[i] NULL;}if(cur _pRoot){Node* temp new Node();temp-_keys[0] cur-_keys[mid];cur-_keys[mid] K();cur-_size mid;temp-_size;temp-_sub[0] cur;cur-_parent temp;temp-_sub[1] NewNode;NewNode-_parent temp;_pRoot temp;return true;}newKey cur-_keys[mid];cur-_keys[mid] K();cur-_size mid;sub NewNode;}cur cur-_parent;}}protected:pairNode*, size_t _Find(const K key){Node* cur _pRoot;Node* parent NULL;while(cur){size_t i 0;while(i cur-_size){if(cur-_keys[i] key)i;else if(cur-_keys[i] key)break;elsereturn pairNode*, size_t(cur, i);}parent cur;cur cur-_sub[i];}return pairNode*, size_t(parent, -1);}void _InsertKey(Node* cur,const K Key,Node* sub){int i cur-_size-1;while(i 0){if(cur-_keys[i] Key){//移动关键字位置cur-_keys[i1] cur-_keys[i];//移动子树的位置cur-_sub[i2] cur-_sub[i1];i--;}elsebreak;}cur-_keys[i1] Key;cur-_sub[i2] sub;if(sub)sub-_parent cur;cur-_size;}void _Inorder(Node* _pRoot){if(NULL _pRoot)return;size_t i 0;for(; i _pRoot-_size; i){_Inorder(_pRoot-_sub[i]);cout_pRoot-_keys[i] ;}_Inorder(_pRoot-_sub[i]);}void _Destroy(Node* _pRoot){if(NULL _pRoot)return;size_t i 0;for(; i _pRoot-_size; i){_Destroy(_pRoot-_sub[i]);delete _pRoot-_sub[i];}_Destroy(_pRoot-_sub[i]);delete _pRoot-_sub[i];}private:Node* _pRoot;
};void test()
{BTreeint, 3 bt;int array[] {53, 75, 139, 49, 145, 36, 101};for(int i 0; i sizeof(array)/sizeof(array[0]); i){bt.Insert(array[i]);}bt.Inorder();
}
