|
+ M] = pNode2->child[i]; } for (int i = index; i < parent->keyNum; i++){//将父节点index以后的关键字以及孩子指针都向前移动一位 parent->key[i] = parent->key[i + 1]; parent->child[i + 1] = parent->child[i + 2]; } parent->keyNum--; delete pNode2; } int BTree::predecessor(BTNode* pNode) { while (!pNode->isLeaf) pNode = pNode->child[pNode->keyNum]; return pNode->key[pNode->keyNum - 1]; } int BTree::successor(BTNode* pNode) { while (!pNode->isLeaf) pNode = pNode->child[0]; return pNode->key[0]; } void BTree::ExchangeLeftNode(BTNode *parent, BTNode* pNode0, BTNode* pNode1, int index) { for (int i = pNode1->keyNum; i > 0; i--) pNode1->key[i] = pNode1->key[i - 1];//pNode1结点所有关键字向后移动一位 pNode1->key[0] = parent->key[index];//第0个关键字来自父节点 pNode1->keyNum++; parent->key[index] = pNode0->key[pNode0->keyNum - 1];//父节点的index处的关键字来自pNode0的最大关键字 if (!pNode0->isLeaf){//如果不是叶子结点， for (int i = pNode1->keyNum; i > 0; i--)//将pNode1的孩子指针都向后移动一位，并将pNode0的最后一个孩子指针赋给它的第一个 pNode1->child[i] = pNode1->child[i - 1]; pNode1->child[0] = pNode0->child[pNode0->keyNum]; } pNode0->keyNum--; } void BTree::ExchangeRightNode(BTNode* parent, BTNode* pNode1, BTNode *pNode2, int index) { pNode1->key[pNode1->keyNum] = parent->key[index]; pNode1->keyNum++; parent->key[index] = pNode2->key[0]; for (int i = 0; i < pNode2->keyNum - 1; i++) pNode2->key[i] = pNode2->key[i + 1]; if (!pNode2->isLeaf){ pNode1->child[pNode1->keyNum] = pNode2->child[0]; for (int i = 0; i < pNode2->keyNum; i++) pNode2->child[i] = pNode2->child[i + 1]; } pNode2->keyNum--; } void BTree::RemoveNonLess(BTNode* pNode, int key) { if (pNode->isLeaf){//到了叶子结点，直接删除 int i = 0; while (i
keyNum&&key>pNode->key[i]) i++; if (i < pNode->keyNum&&key == pNode->key[i]){ while (i < pNode->keyNum - 1){ pNode->key[i] = pNode->key[i + 1]; i++; } pNode->keyNum--; } else { cout << "not found!" << endl; } } else { int i = 0; while (i < pNode->keyNum&&key > pNode->key[i])//找到第一个大于等于key的关键字 i++; if (i < pNode->keyNum&&key == pNode->key[i]){//在结点中找到要删除的关键字 struct BTNode* pNode1 = pNode->child[i]; struct BTNode* pNode2 = pNode->child[i + 1]; if (pNode1->keyNum >= M){//如果关键字左边的孩子结点的关键字数大于等于M int target = predecessor(pNode1);//将其前继结点移到pNode中 pNode->key[i] = target; RemoveNonLess(pNode1, target);//递归删除target } else if (pNode2->keyNum >= M){//右边，同理 int target = successor(pNode2); pNode->key[i] = target; RemoveNonLess(pNode2, target); } else { merge(pNode, pNode1, pNode2, i);//都小于M，合并 RemoveNonLess(pNode1, key); } } else {//不在此结点中 struct BTNode *pNode1 = pNode->child[i]; struct BTNode *pNode0 = NULL; struct BTNode *pNode2 = NULL; if (i>0) pNode0 = pNode->child[i - 1];//左结点 if (i < pNode->keyNum) pNode2 = pNode->child[i + 1];//右结点 if (pNode1->keyNum == M - 1){//如果要删除的孩子结点关键字个数为M-1 if (i > 0 && pNode0->keyNum >= M){//如果左邻结点至少有M个关键字，向其借一个 ExchangeLeftNode(pNode, pNode0, pNode1, i - 1); } else if (i < pNode->keyNum&&pNode2->keyNum >= M){//同理， ExchangeRightNode(pNode, pNode1, pNode2, i); } else if (i>0){//两个相邻结点都只有M-1个关键字，合并 merge(pNode, pNode0, pNode1, i - 1); pNode1 = pNode0; } else{ merge(pNode, pNode1, pNode2, i); } RemoveNonLess(pNode1, key); } else{ RemoveNonLess(pNode1, key); } } } } BTree::BTNode* BTree::search(int key, int &index) { return Search(root, key, index); } void BTree::insert(int key) { struct BTNode* r = root; if (root->keyNum == 2 * M - 1){//根节点特殊处理，如果根节点关键字个数为2*M-1， struct BTNode* pNode = new BTNode();//新建一个结点作为新的根节点，并将现在的根节点作为 root = pNode;//新根节点的孩子结点 pNode->isLeaf = false; pNode->keyNum = 0; pNode->child[0] = r; SplitChild(pNode, 0, r);//孩子结点r有2*M-1个关键字 InsertNonFull(pNode, key); } else InsertN |