B-樹
一棵m階的B-樹，或?yàn)榭諛浔古眩驗(yàn)闈M足下列特性的m叉樹：
(1) 樹中每個(gè)結(jié)點(diǎn)至多有m棵孩子結(jié)點(diǎn)（即至多有m-1個(gè)關(guān)鍵字）倡勇。
(2) 若根節(jié)點(diǎn)不是葉子結(jié)點(diǎn)，至少有兩棵子樹嘉涌。
(3) 除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有[m/2]棵子樹妻熊。
(4) 所有葉子結(jié)點(diǎn)都在同一層上，即B樹是所有結(jié)點(diǎn)的平衡因子均等于0的多路查找樹仑最。
(5) 所有非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù)（n,A0,K1,A1,K2,A2,...Kn,An）扔役。
#define MAXM 10
typedef int KeyType;
const int m = 5;
int min = 2;
typedef struct BTNode
{
int keynum;
KeyType keys[MAXM];
struct BTNode *parent;
struct BTNode *child[MAXM];
void (*insertKey)(struct BTNode *node,KeyType k);
void (*removeKey)(struct BTNode *node,KeyType k);
int (*childrenCount)(struct BTNode *node);
struct BTNode * (* addChild)(struct BTNode *node, struct BTNode *child);
struct BTNode * (* insertChild)(struct BTNode *node, struct BTNode *child, int pos);
bool (*removeChild)(struct BTNode *node, struct BTNode *child);
int (*indexOf)(struct BTNode *mySelf, struct BTNode *node);
}BTNode;
void insertKey(BTNode *node,KeyType k);
void removeKey(BTNode *node,KeyType k);
int getChildrenCount(BTNode *node);
BTNode* addChild(BTNode *node, BTNode *child);
BTNode * insertChild(BTNode *node, BTNode *child, int pos);
bool removeChild(BTNode *node, BTNode *child);
int indexOf(BTNode *mySelf,BTNode *node);
int binarySearch(BTNode *root,KeyType key);
void initBTNode(BTNode *node)
{
node->keynum = 0;
for(int i = 0; i < MAXM; i++)
{
node->keys[i] = -1;
}
node->insertKey = insertKey;
node->removeKey = removeKey;
node->parent = NULL;
for(int i = 0; i < MAXM; i++)
{
node->child[i] = NULL;
}
node->childrenCount = getChildrenCount;
node->addChild = addChild;
node->removeChild = removeChild;
node->indexOf = indexOf;
}
void insertKey(BTNode *node,KeyType k)
{
if(node->keynum == 0)
{
node->keys[0] = k;
return;
}
int left = 0, right = node->keynum - 1, mid = (left + right) / 2;
while (left <= right) {
mid = (left + right) / 2;
if(k < node->keys[mid])
right = mid - 1;
else if (k > node->keys[mid])
left = mid + 1;
}
int insertPos = k < node->keys[mid] ? mid : mid + 1;
for (int i = node->keynum - 1; i >= insertPos; i--) {
node->keys[i + 1] = node->keys[i];
}
node->keys[insertPos] = k;
node->keynum++;
}
void removeKey(BTNode *node,KeyType k)
{
int keyIndex = binarySearch(node, k);
for (int j = keyIndex; j < node->keynum; j++) {
node->keys[j] = node->keys[j+1];
}
node->keys[node->keynum - 1] = -1;
node->keynum--;
}
int getChildrenCount(BTNode *node)
{
int i = 0;
for(;i < MAXM; i++)
{
if(node->child[i] == NULL)
break;
}
return i;
}
BTNode* addChild(BTNode *node, BTNode *child)
{
int i = 0;
for(;i < MAXM; i++)
{
if(node->child[i] == NULL)
break;
}
node->child[i] = child;
return node;
}
BTNode* insertChild(BTNode *node, BTNode *child, int pos)
{
for (int i = node->keynum - 1; i >= pos; i--) {
node->child[i + 1] = node->child[i];
}
node->child[pos] = child;
return node;
}
bool removeChild(BTNode *node, BTNode *child)
{
int i = 0;
for (; i<node->keynum + 1; i++) {
if(child == node->child[i])
break;
}
if(i == node->keynum + 1)
return false;
for (int j = i; j < node->keynum; j++) {
node->child[j] = node->child[j+1];
}
node->child[node->keynum] = NULL;
return true;
}
int indexOf(BTNode *mySelf,BTNode *node)
{
int i = 0, count = mySelf->childrenCount(mySelf);
for (; i < count; i++) {
if(mySelf->child[i] == node)
break;
}
i = i == count ? -1 : i;
return i;
}
1. 查找
int binarySearch(BTNode *root,KeyType key)
{
int left = 0, right = root->keynum - 1, mid = (left + right) / 2;
while (left <= right) {
mid = (left + right)/2;
if(key < root->keys[mid])
right = mid - 1;
else if (key > root->keys[mid])
left = mid + 1;
else
break;
}
mid = (left <= right) ? mid : -mid;
return mid;
}
BTNode* searchNode(BTNode *root,KeyType key)
{
if(root == NULL)
return NULL;
int index = binarySearch(root,key);
if(index > 0){
return root;
}else{
return searchNode(root->child[-index-1], key);
}
}
2. 插入
對(duì)于新元素的插入，都是發(fā)生在葉子節(jié)點(diǎn)上的警医。所有的插入操作都是從根節(jié)點(diǎn)開始亿胸，搜索這棵樹坯钦，并找到該元素應(yīng)該被插入的節(jié)點(diǎn)。將新元素插入到該節(jié)點(diǎn)需要如下步驟：
- 如果該節(jié)點(diǎn)上的元素?cái)?shù)未滿侈玄，則將新元素插入到該節(jié)點(diǎn)婉刀，并保持節(jié)點(diǎn)中元素的順序。
- 如果該節(jié)點(diǎn)上的元素已滿序仙，則需要將該節(jié)點(diǎn)平均地分裂成兩個(gè)節(jié)點(diǎn)：
?? 從該節(jié)點(diǎn)中的元素和新元素先出一個(gè)中位數(shù)
?? 小于中位數(shù)的元素放到左邊節(jié)點(diǎn)突颊，大于中位數(shù)的元素放到右邊節(jié)點(diǎn)，中位數(shù)做為分隔值潘悼。
?? 分隔值被插入到父節(jié)點(diǎn)中（增加了樹的高度）律秃，這可能會(huì)導(dǎo)致父節(jié)點(diǎn)的分裂，分裂父節(jié)點(diǎn)時(shí)又可能會(huì)使它的父節(jié)點(diǎn)分裂治唤，以此類推棒动。如果分裂一直上升到根節(jié)點(diǎn)，那么就創(chuàng)建一個(gè)新的根節(jié)點(diǎn)肝劲，它有一個(gè)分隔值和兩個(gè)子節(jié)點(diǎn)迁客。（這就是根節(jié)點(diǎn)并不像內(nèi)部節(jié)點(diǎn)一樣有最少子節(jié)點(diǎn)數(shù)量限制的原因）
下圖是一個(gè)5階B樹，我們通過順序插入1到17辞槐，來觀察節(jié)點(diǎn)的分裂過程掷漱。
void insertNodeKey(BTNode *node,KeyType key);
void insert(BTNode **root,KeyType key)
{
if(*root == NULL){
BTNode *node = (BTNode *)malloc(sizeof(BTNode));
initBTNode(node);
node->insertKey(node,key);
*root = node;
return;
}
insertNodeKey(*root, key);
}
void addKeys(BTNode *node,BTNode *fromNode,int begin, int end)
{
for (int i = begin; i < end; i++) {
node->keys[i - begin] = fromNode->keys[i];
}
node->keynum = end - begin;
}
void addChildren(BTNode *node,BTNode *fromNode,int begin, int end)
{
for (int i = begin; i < end; i++) {
node->child[i-begin] = fromNode->child[i];
fromNode->child[i]->parent = node;
}
}
void split(BTNode *node)
{
int mid = node->keynum/2;
//分離值
KeyType sepKey = node->keys[mid];
//分離后的左節(jié)點(diǎn)
BTNode *leftNode = (BTNode *)malloc(sizeof(BTNode));
initBTNode(leftNode);
//添加key
addKeys(leftNode, node, 0, mid);
BTNode *rightNode = (BTNode *)malloc(sizeof(BTNode));
initBTNode(rightNode);
addKeys(rightNode, node, mid + 1, node->keynum);
//分離子結(jié)點(diǎn)
if(node->childrenCount(node) > 0)
{
addChildren(leftNode, node, 0, mid);
addChildren(rightNode, node, mid + 1, node->keynum);
}
//當(dāng)前節(jié)點(diǎn)為根結(jié)點(diǎn)
BTNode *parent = node->parent;
if(parent == NULL){
BTNode *newRoot = (BTNode *)malloc(sizeof(BTNode));
newRoot->insertKey(newRoot,sepKey);
leftNode->parent = newRoot;
rightNode->parent = newRoot;
newRoot->addChild(newRoot,leftNode)->addChild(newRoot,rightNode);
}else{
parent->insertKey(parent,sepKey);
leftNode->parent = parent;
rightNode->parent = parent;
int pos = binarySearch(parent, sepKey);
parent->removeChild(parent,node);
parent->insertChild(parent,leftNode,pos)->insertChild(parent,rightNode,pos+1);
if(parent->keynum > m - 1)
split(parent);
}
}
void insertNodeKey(BTNode *node,KeyType key)
{
//當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)
if(node->childrenCount == 0)
{
//如果當(dāng)前結(jié)點(diǎn)key未滿，直接添加
if(node->keynum < m - 1)
{
node->insertKey(node,key);
return;
}
// 如果key已滿榄檬，分裂結(jié)點(diǎn)
node->insertKey(node,key);
split(node);
return;
}
//當(dāng)前節(jié)點(diǎn)為內(nèi)部節(jié)點(diǎn)的時(shí)候卜范，需要查找相應(yīng)的子結(jié)點(diǎn)，直到找到相應(yīng)的葉子結(jié)點(diǎn)時(shí)鹿榜，才插入
int index = binarySearch(node, key);
if(index < 0)
insertNodeKey(node->child[-index-1],key);
}
3. 刪除
B樹的刪除就復(fù)雜了許多海雪，可分為下面幾種情況：
- 刪除葉子結(jié)點(diǎn)的元素：
(1) 搜索要?jiǎng)h除的元素
(2) 如果它在葉子節(jié)點(diǎn)上，直接將其刪除
(3) 如果刪除后產(chǎn)生了下溢出（鍵數(shù)小于最小值 [m/2]-1）舱殿，則向其兄弟節(jié)點(diǎn)借元素奥裸。如果兄弟結(jié)點(diǎn)借，即將其父節(jié)點(diǎn)元素下移至當(dāng)前節(jié)點(diǎn)沪袭，將兄弟節(jié)點(diǎn)中元素上移至父節(jié)點(diǎn)（若是左節(jié)點(diǎn)湾宙，上移最大元素；若是右節(jié)點(diǎn)冈绊，上移最小元素）
(4) 若兄弟節(jié)點(diǎn)也達(dá)到下限侠鳄，即不借，則合并兄弟節(jié)點(diǎn)與分割鍵(父結(jié)點(diǎn)分割鍵下移到當(dāng)前結(jié)點(diǎn)刪除的位置死宣，然后和兄弟結(jié)點(diǎn)合并)伟恶。
下圖是一個(gè)5階B樹，我們通過刪除15毅该、14博秫、17潦牛、5四個(gè)鍵，來觀察刪除過程（基本涵蓋所有情況）挡育。
- 刪除內(nèi)部結(jié)點(diǎn)：
內(nèi)部節(jié)點(diǎn)中元素為其左右子節(jié)點(diǎn)的分割值,需要從左子樹中找最大的key或右子樹中找最小的key來代替被刪除的key元素罢绽。從而轉(zhuǎn)化為刪除葉子結(jié)點(diǎn)上的元素
下面以3階的B-樹刪除內(nèi)部結(jié)點(diǎn)為例進(jìn)行演示：
void afterDeleteHandle(BTNode **root,BTNode *node,int deleteIndex);
void merge(BTNode **root,BTNode *node, BTNode *brotherNode, int parentKeyIndex);
void leftRotate(BTNode *node, int nodeIndex, BTNode *rightNode);
void rightRotate(BTNode *node, int nodeIndex, BTNode *leftNode);
BTNode* findLeftChildMaxKeyNode(BTNode *node,int index)
{
BTNode *maxNode = node->child[index];
BTNode *lastNode = maxNode;
int maxIndex = -1;
while (lastNode) {
maxIndex = maxNode->childrenCount(maxNode) - 1;
lastNode = maxNode->child[maxIndex];
if(lastNode)
maxNode = lastNode;
}
return maxNode;
}
BTNode* findRightChildMinKeyNode(BTNode *node,int index)
{
BTNode *minNode = node->child[index + 1];
BTNode *firstNode = minNode;
while (firstNode) {
firstNode = minNode->child[0];
if(firstNode)
minNode = firstNode;
}
return minNode;
}
void delete(BTNode **root,KeyType key)
{
BTNode *node = searchNode(*root, key);
if(!node)
return;
//刪除節(jié)點(diǎn)
int keyIndex = binarySearch(node, key);
node->removeKey(node, key);
if(node->keynum < min){
afterDeleteHandle(root,node, keyIndex);
}
}
void afterDeleteHandle(BTNode **root,BTNode *node,int deleteIndex)
{
//如果是內(nèi)部結(jié)點(diǎn) 轉(zhuǎn)化為刪除葉子結(jié)點(diǎn)
//要么向左子樹中最大的葉子結(jié)點(diǎn)的最大key借
//要么向右子樹中最小的葉子結(jié)點(diǎn)的最小key借
if(node->childrenCount > 0 && deleteIndex > 0){
BTNode *leftChildMaxNode = findLeftChildMaxKeyNode(node, deleteIndex);
if(leftChildMaxNode){
int maxIndex = leftChildMaxNode->keynum - 1;
KeyType maxKey = leftChildMaxNode->keys[maxIndex];
node->insertKey(node,maxKey);
leftChildMaxNode->removeKey(leftChildMaxNode,maxKey);
if(leftChildMaxNode->keynum < min){
afterDeleteHandle(root, leftChildMaxNode, maxIndex);
}
}else{
BTNode *rightChildMinNode = findRightChildMinKeyNode(node, deleteIndex);
KeyType minKey = rightChildMinNode->keys[0];
node->insertKey(node,minKey);
rightChildMinNode->removeKey(rightChildMinNode,minKey);
if(rightChildMinNode->keynum < min){
afterDeleteHandle(root, rightChildMinNode, 0);
}
}
}
//刪除葉子結(jié)點(diǎn) 或繼續(xù)向兄弟結(jié)點(diǎn)借
BTNode *parentNode = node->parent;
//當(dāng)前結(jié)點(diǎn)在父結(jié)點(diǎn)中的位置
int nodeIndex = parentNode->indexOf(parentNode,node);
//左兄弟結(jié)點(diǎn)
BTNode *leftNode = nodeIndex > 0 ? parentNode->child[nodeIndex-1] : NULL;
//右兄弟節(jié)點(diǎn)
BTNode *rightNode = nodeIndex == parentNode->childrenCount(parentNode) - 1 ? NULL : parentNode->child[nodeIndex + 1];
int leftKeyCount = leftNode == NULL ? 0 : leftNode->keynum;
int rightKeyCount = rightNode == NULL ? 0 : rightNode->keynum;
int maxCount = MAX(leftKeyCount, rightKeyCount);
// 左右兄弟節(jié)點(diǎn)元素?cái)?shù)均達(dá)到限定值，合并
if(maxCount <= min){
if(leftNode){
//與左兄弟節(jié)點(diǎn)合并
merge(root,node, leftNode, nodeIndex - 1);
}else if (rightNode){
//與右兄弟節(jié)點(diǎn)合并
merge(root,node, rightNode, nodeIndex);
}
return;
}
//向最富裕的兄弟結(jié)點(diǎn)借
if(maxCount == leftKeyCount){
//向左節(jié)點(diǎn)借-> 右旋
rightRotate(node, nodeIndex, leftNode);
}else{
//向右節(jié)點(diǎn)借-> 左旋
leftRotate(node, nodeIndex, rightNode);
}
}
void merge(BTNode **root,BTNode *node, BTNode *brotherNode, int parentKeyIndex)
{
BTNode *parentNode = node->parent;
BTNode *newNode = (BTNode *)malloc(sizeof(BTNode));
initBTNode(newNode);
KeyType parentKey = parentNode->keys[parentKeyIndex];
addKeys(newNode, node, 0, node->keynum);
addKeys(newNode, brotherNode, 0, brotherNode->keynum);
newNode->insertKey(newNode,parentKey);//向父結(jié)點(diǎn)借
addChildren(newNode, node, 0, node->childrenCount(node));
addChildren(newNode, brotherNode, 0, brotherNode->childrenCount(brotherNode));
parentNode->removeKey(parentNode,parentKey);
parentNode->removeChild(parentNode,node);
parentNode->removeChild(parentNode,brotherNode);
parentNode->addChild(parentNode,newNode);
newNode->parent = parentNode;
//合并之后静盅，若父結(jié)點(diǎn)的元素小于限定數(shù) 繼續(xù)調(diào)整
if(parentNode == *root && parentNode->keynum == 0)
{
*root = newNode;
free(parentNode);
return;
}
if(parentNode->keynum < min){
afterDeleteHandle(root, parentNode, -1);
}
}
/**
* 左旋轉(zhuǎn)
* （1）將父節(jié)點(diǎn)的中間值元素刪除，并添加到當(dāng)前節(jié)點(diǎn)中
* （2）將右兄弟節(jié)點(diǎn)中最小元素刪除寝殴，并添加到父節(jié)點(diǎn)中
*
* @param node 當(dāng)前節(jié)點(diǎn)
* @param nodeIndex 中間值索引
* @param rightNode 右節(jié)點(diǎn)
*/
void leftRotate(BTNode *node, int nodeIndex, BTNode *rightNode)
{
BTNode *parentNode = node->parent;
KeyType key = parentNode->keys[nodeIndex];
parentNode->removeKey(parentNode,key);
node->insertKey(node,key);
KeyType rightKey = rightNode->keys[0];
parentNode->insertKey(parentNode,rightKey);
rightNode->removeKey(rightNode,rightKey);
BTNode *rightFirstChild = rightNode->child[0];
rightNode->removeChild(rightNode,rightFirstChild);
node->addChild(node,rightFirstChild);
}
/**
* 右旋轉(zhuǎn)
* （1）將父節(jié)點(diǎn)的中間值元素刪除蒿叠，并添加到當(dāng)前節(jié)點(diǎn)中
* （2）將左兄弟節(jié)點(diǎn)中最大元素刪除，并添加到父節(jié)點(diǎn)中
*
* @param node 當(dāng)前節(jié)點(diǎn)
* @param nodeIndex 中間值索引
* @param leftNode 左節(jié)點(diǎn)
*/
void rightRotate(BTNode *node, int nodeIndex, BTNode *leftNode)
{
BTNode *parentNode = node->parent;
KeyType key = parentNode->keys[nodeIndex - 1];
parentNode->removeKey(parentNode,key);
node->insertKey(node,key);
KeyType leftKey = leftNode->keys[leftNode->keynum - 1];
parentNode->insertKey(parentNode,leftKey);
leftNode->removeKey(leftNode,leftKey);
int leftLast = leftNode->childrenCount(leftNode) - 1;
BTNode *leftLastChild = leftNode->child[leftLast];
leftNode->removeChild(leftNode,leftLastChild);
node->addChild(node,leftLastChild);
}
