資料結構（C++）[B樹（B-樹）插入與中序周遊，效率分析]、B+樹、B*樹、B樹系列應用
文章目錄
- 1. B樹
-
- B樹的插入與删除流程
- 2. B+樹（MySQL）
- 3. B+樹與B樹對比
- 4. C++實作B樹插入，中序周遊
1. B樹
B樹類似于二叉排序樹，B樹可以了解為多叉排序樹。
B樹和二叉排序樹相類似，查找效率取決于樹的高度。
因為二搜尋樹每個節點隻能存一個資料。而B樹每一個節點可以儲存多個值（這些值在這個節點内部按照順序排序）。
是以一般情況下，B樹的高度小于搜尋二叉樹，效率高。
注意：如果B樹的每個節點隻儲存一個資料，B樹就退化為搜尋二叉樹
- 是以為了避免這種情況，規定除了根節點外，任意m叉樹中每一個節點規定至少有[m/2]向上取整，個分叉，至少含有[m/2]-1個資料。
- 多叉樹在插入後，高度退化為線性查找，是以規定m叉樹任意一個節點的高度相同。
B樹的定義：
B樹，又稱多路平衡查找樹，B樹中所有結點的孩子個數的最大值稱為B樹的階，通常用m表示。一棵m階B樹或為空樹，或為滿足如下特性的m叉樹：
- 樹中每個結點至多有m棵子樹，即至多含有m-1個關鍵字。
- 若根結點不是終端結點，則至少有兩棵子樹（絕對平衡）。
- 除根結點外的所有非葉結點至少有「m/2]棵子樹，即至少含有[m/2]-1個關鍵字。
- 所有的葉結點都出現在同一層次上，并且不帶資訊（可以視為外部結點或類似于折半查找判定樹的查找失敗結點，實際上這些結點不存在，指向這些結點的指針為空)
- 每個非葉結點的結構為：（n，A0，K1，A1，K2，A2，… ，Kn，An）其中，Ki(1≤i≤n)為關鍵字，且Ki<Ki+1(1≤i≤n-1)。Ai(0≤i≤n)為指向子樹根結點的指針。且Ai所指子樹所有結點中的關鍵字均小于Ki+1。n為結點中關鍵字的個數，滿足ceil(m/2)-1≤n≤m-1。（關鍵字按照升序排列，同時保證A0<K1<A1<K2<A2）(多叉搜尋樹)
需要注意的是計算B樹的高度不包括失敗節點層
含有n個關鍵字的m階B樹
最小高度：
每一個節點填滿關鍵字，每一個節點放m-1個關鍵字
n≤(m-1)(1+m+m^2+...+m^(h-1))，最小高度為logm(n+1)
最大高度：
每一個節點儲存最小關鍵字（分叉數最小），根節點最小有2個分叉，其他節點最小有m/2個分叉
第一層最少有1個節點，第二次有兩個，第三次有2(m/2)，第四層有2(m/2)*(m/2)...第n層2(m/2)^(h-2)
第n+1層是失敗節點，最少有2(m/2)^(h-1)個節點。而n個關鍵字的B樹一定有n+1個葉節點，失敗節點
是以n+1≥2(m/2)^(h-1)，求解h即可得出最大高度。
B樹的插入與删除流程
B樹的插入：
連續插入key，在插入key後，若導緻原結點關鍵字數超過上限。則從中間位置_([m/2])将其中的關鍵字分為兩部分。
左部分包含的關鍵字放在原結點中，右部分包含的關鍵字放到新結點中，中間位置[m/2]的結點插入原結點的父結點
eg：三階B樹插入關鍵字（53, 139, 75, 49, 145, 36, 50, 47, 101）
節點最多儲存2個關鍵字，最少儲存1個關鍵字。根節點單獨看
- 根節點最多可以儲存2個關鍵字，為了簡化插入操作，開辟三個關鍵字大小，當插入後發現已經滿了時再進行分裂。同時多開辟一個空間也有助于在插入時進行排序。
資料結構-考研難點代碼突破（C++實作樹型查找 - B樹插入與周遊，B+樹基本概念）1. B樹2. B+樹（MySQL）3. B+樹與B樹對比4. C++實作B樹插入，中序周遊 - 如果節點滿了，分裂右邊一半關鍵字個數的一般給兄弟節點。提取中位數給父親，沒有父親就建立新的根節點
資料結構-考研難點代碼突破（C++實作樹型查找 - B樹插入與周遊，B+樹基本概念）1. B樹2. B+樹（MySQL）3. B+樹與B樹對比4. C++實作B樹插入，中序周遊 - 繼續插入49等後續關鍵字。 此時節點又滿了，需要進行分裂。
資料結構-考研難點代碼突破（C++實作樹型查找 - B樹插入與周遊，B+樹基本概念）1. B樹2. B+樹（MySQL）3. B+樹與B樹對比4. C++實作B樹插入，中序周遊 資料結構-考研難點代碼突破（C++實作樹型查找 - B樹插入與周遊，B+樹基本概念）1. B樹2. B+樹（MySQL）3. B+樹與B樹對比4. C++實作B樹插入，中序周遊 - 繼續插入50和47這兩個關鍵字。
資料結構-考研難點代碼突破（C++實作樹型查找 - B樹插入與周遊，B+樹基本概念）1. B樹2. B+樹（MySQL）3. B+樹與B樹對比4. C++實作B樹插入，中序周遊 - 最後插入101，導緻葉子節點滿，需要進行分裂
資料結構-考研難點代碼突破（C++實作樹型查找 - B樹插入與周遊，B+樹基本概念）1. B樹2. B+樹（MySQL）3. B+樹與B樹對比4. C++實作B樹插入，中序周遊
這次分裂會導緻兩次連續分裂
第一次分裂導緻根節點滿
繼續分裂根節點，産生新的根節點
插入完畢
特點
- B樹天然平衡，B樹是先橫向擴充，再豎直生長。是以B樹天然平衡
- 新插入的節點一定在葉子插入，葉子節點沒有孩子，不影響關鍵字和孩子的關系
- 葉子節點滿了，分裂出一個兄弟，提取中位數，向父親插入一個值和孩子
- 根節點分裂會增加一層
- 對于B樹的每一個節點，這個節點的孩子個數比關鍵字個數多一個。
B樹的删除：
- 若被删除關鍵字在終端節點，則直接删除該關鍵字（要注意節點關鍵字個數是否低于下限[m/2] -1)
-
若被删除關鍵字在非終端節點，則用直接前驅或直接後繼來替代被删除的關鍵字。這樣就轉化為對終端節點的删除了。
直接前驅：目前關鍵字左側指針所指子樹中“最右下”的元素
特别注意：如果删除終端節點到下線，這是需要進行分類處理
- 這個節點的兄弟節點可以借出一個元素時：
資料結構-考研難點代碼突破（C++實作樹型查找 - B樹插入與周遊，B+樹基本概念）1. B樹2. B+樹（MySQL）3. B+樹與B樹對比4. C++實作B樹插入，中序周遊 資料結構-考研難點代碼突破（C++實作樹型查找 - B樹插入與周遊，B+樹基本概念）1. B樹2. B+樹（MySQL）3. B+樹與B樹對比4. C++實作B樹插入，中序周遊 - 兄弟節點不夠借用：這個節點和兄弟節點進行合并
資料結構-考研難點代碼突破（C++實作樹型查找 - B樹插入與周遊，B+樹基本概念）1. B樹2. B+樹（MySQL）3. B+樹與B樹對比4. C++實作B樹插入，中序周遊
2. B+樹（MySQL）
類似于分塊查找，一棵m階的B+樹需滿足下列條件:
- 每個分支結點最多有m棵子樹（孩子結點)。
-
根結點不是葉子節點時至少有兩棵子樹，其他每個分支結點至少有[m/2]棵子樹。
B+樹綠色的節點稱為葉子節點。藍色節點(分支節點)又稱為"索引"
- 結點的子樹個數與關鍵字個數相等（B樹節點兩個分支，說明這個節點有三個關鍵字）
- 所有葉結點包含全部關鍵字及指向相應記錄的指針，葉結點中将關鍵字按大小順序排列，并且相鄰葉結點按大小順序互相連結起來。
- 分支節點隻包括子節點關鍵字的最大值和指向子節點的指針。
3. B+樹與B樹對比
- m階B+樹節點n個分叉對應n個關鍵字，m階B樹節點n個分叉對應n-1個關鍵字
-
m階B樹節點關鍵字個數範圍[(m/2)-1，m-1]（根節點[1，m-1]）
m階B+樹節點關鍵字個數範圍[m/2，m]（根節點[1，m]）
-
B+樹中，葉節點包含全部關鍵字，非葉節點出現的關鍵字也會在葉子節點出現。
B樹中，各個節點的關鍵字不會重複。
-
B+樹中，葉結點包含資訊，所有非葉結點僅起索引作用，非葉結點中的每個索引項隻含有對應子樹的最大關鍵字和指向該子樹的指針，不含有該關鍵字對應記錄的存儲位址。（查找元素需要一直找到葉節點）
B樹的結點中都包含了關鍵字對應的記錄的存儲位址（如果中間節點找到了關鍵字元素，可以直接找到儲存位址，無需到葉子節點上）
4. C++實作B樹插入，中序周遊
#include <iostream>
#include <vector>
// order階B樹，節點最多order-1個元素，但是需要開辟order大小的空間,因為我是先插入後在判斷擴容的
template <class ValueType, size_t order>
struct TreeNode
{
std::vector<ValueType> _value; // 存放節點值
std::vector<TreeNode<ValueType, order> *> _subs; // 存放節點的子樹,空間大小為order+1
TreeNode<ValueType, order> *_parent; // 父指針
size_t _size; // 記錄實際存儲關鍵字個數
TreeNode()
{
_value.resize(order);
_subs.resize(order + 1);
for (size_t i = 0; i < order; i++)
{
_value[i] = ValueType();
_subs[i] = nullptr;
}
_subs[order] = nullptr;
_parent = nullptr;
_size = 0;
}
};
template <class ValueType, size_t order>
class BTree
{
typedef TreeNode<ValueType, order> TreeNode;
private:
TreeNode *_root = nullptr;
public:
BTree(const std::vector<ValueType> &vet)
{
for (auto &val : vet)
{
insert(val);
}
}
BTree() = default;
bool insert(const ValueType &value)
{
if (_root == nullptr)
{
_root = new TreeNode;
_root->_value[0] = value;
_root->_size += 1;
return true;
}
else
{
// 找要插入的位置
std::pair<TreeNode *, int> ret = _findPos(value);
if (ret.second >= 0)
{
// 不允許備援
return false;
}
TreeNode *cur = ret.first; // 要插入的節點
int insert_value = value;
TreeNode *child = nullptr;
while (true)
{
_insert(cur, insert_value, child);
if (cur->_size == order)
{
// 節點放滿了需要分裂
int mid = order / 2;
TreeNode *node = new TreeNode; // node存放[mid+1,order-1]的資料
size_t pos = 0;
for (size_t i = mid + 1; i < order; i++)
{
node->_value[pos] = cur->_value[i];
node->_subs[pos] = cur->_subs[i];
// 更新父節點
if (cur->_subs[i] != nullptr)
{
cur->_subs[i]->_parent = node;
}
pos += 1;
// 将cur移出的位置清空
cur->_value[i] = ValueType();
cur->_subs[i] = nullptr;
}
// node節點中，新插入的值的孩子節點指針沒處理
node->_subs[order] = cur->_subs[order];
if (cur->_subs[order] != nullptr)
{
// 更新父節點
cur->_subs[order]->_parent = node;
}
cur->_subs[order] = nullptr;
node->_size = pos;
cur->_size -= pos + 1; // cur還提取了一個值作為這兩個節點父親,下面的代碼會操作
ValueType midValue = cur->_value[mid];
cur->_value[mid] = ValueType();
if (cur->_parent == nullptr)
{
// 新建立父節點，這個節點是cur和node的父親
_root = new TreeNode;
_root->_value[0] = midValue;
_root->_subs[0] = cur;
_root->_subs[1] = node;
_root->_size = 1;
cur->_parent = _root;
node->_parent = _root;
break;
}
// 轉劃為向cur->_parent這個位置插入midValue問題，可以通過while循環解決
insert_value = midValue;
child = node;
cur = cur->_parent;
}
else
{
// 節點沒有插滿，插入結束
return true;
}
}
}
return true;
}
// 删除指定元素
void erase(const ValueType &value)
{
std::pair<TreeNode *, int> ret = _findPos(value);
if (ret.second == -1)
{
// 沒有找到删除的元素
return;
}
else
{
TreeNode *del = ret.first;
if (!_isLeave(del))
{
// 如果删除的節點不是終端節點，轉化為終端節點後在删除
TreeNode *prev = del->_subs[ret.second]; // 找直接前繼節點(左子樹的最右節點)
while (prev->_subs[ret.second + 1] != nullptr)
{
prev = prev->_subs[ret.second + 1];
}
// 交換節點，轉化為删除終端節點
ValueType delValue = del->_value[ret.second];
del->_value[ret.second] = prev->_value[prev->_size - 1];
prev->_value[prev->_size - 1] = delValue;
erase(delValue);
}
else
{
// 是終端節點，找其兄弟節點
/**
* @brief 考研對B樹的代碼不怎麼考核，而删除的代碼比較複雜，需要找這要删除這個節點的兄弟節點
* 出于時間考慮，這裡先空開。
* 我認為删除節點操作需要找到删除節點的B樹節點指針才行，這樣才能準确的找到删除節點的兄弟B樹節點的位置
*/
}
}
}
void disPlayInorder()
{
_disPlay(_root);
}
private:
bool _isLeave(TreeNode *node)
{
bool ret = true;
for (int i = 0; i < node->_size; i++)
{
if (node->_subs[i] != nullptr)
{
ret = false;
break;
}
}
return ret && node->_subs[node->_size] == nullptr;
}
void _disPlay(TreeNode *node)
{
if (node == nullptr)
return;
for (size_t i = 0; i < node->_size; i++)
{
_disPlay(node->_subs[i]);
std::cout << node->_value[i] << " ";
}
// 最後剩餘右子樹
_disPlay(node->_subs[node->_size]);
}
void _insert(TreeNode *node, int value, TreeNode *child)
{
// 在數組中找value插入的位置，需要移動數組
int endPos = node->_size - 1;
while (endPos >= 0)
{
if (value < node->_value[endPos])
{
// 挪動資料
node->_value[endPos + 1] = node->_value[endPos];
node->_subs[endPos + 2] = node->_subs[endPos + 1];
endPos -= 1;
}
else
{
break;
}
}
// endPos位置是第一個值小于value的位置,value要插入到其後邊
node->_value[endPos + 1] = value;
node->_subs[endPos + 2] = child;
if (child != nullptr)
{
child->_parent = node;
}
node->_size += 1;
}
// 查找要插入的葉子節點以及數組下标
std::pair<TreeNode *, int> _findPos(const ValueType &value)
{
TreeNode *par = nullptr;
TreeNode *cur = _root;
while (cur != nullptr)
{
int pos = 0; // 先從數組下标為0處開始
while (pos < cur->_size)
{
if (value < cur->_value[pos])
{
//_value[pos]左子樹
break;
}
else if (value > cur->_value[pos])
{
pos += 1;
}
else
{
return std::make_pair(cur, pos);
}
}
par = cur;
cur = cur->_subs[pos];
}
return std::make_pair(par, -1);
}
};
#include "BTree.h"
using namespace std;
int main(int argc, char const *argv[])
{
vector<int> ret = {2, 4, 1, 5, 7, 6, 0, 9, 3, 8};
BTree<int, 5> tree(ret); // 5階B樹
tree.disPlayInorder();
// tree.erase(6);
return 0;
}
代碼倉庫