B tree

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

T is a B tree has the following properties of the root tree (with root for root):

Each node has 1 X domain:

(a)num,The current number of keywords in storage node x, keyword to non descending stored, so key[i]<=key[i+1]<=...key[n],

(b)isleaf,Is a boolvalue, if x is a leaf node, isleaf=true.

(c)Each node includes num+ 1 point to their children the pointer p[0], p[1],...... P[num]. If x leaves, p=NULL

(d)Each node includes the num keyword key[0], key[1],...... Key[num-1]. The key[i] keyword to the range of keys stored in the subtree of the separated: k1<=key[1]<=k2<=key[2]...

2 each leaf node have the same depth.

3 each node contains keywords with lower and upper bounds. These bounds can use fixed integer M> is called a B tree to represent the minimum degree; =2. A number of each non root node of the N must meet M-1<=n<=2M-1. The root node includes at least one keyword. If a node is full, it is 2M-1 key words.

A B tree can be expressed as follows:


like B tree and the tree of the place;Is that, every N node of the B tree height is O (LGN), but may be smaller than the height of a red black tree, because its branches more! Because in the disk storage, often need to read the data, so the choice of a large branching factor, can greatly reduce the height of the tree, and disk access times. This may be more abstract, the following are examples: below is a branching factor of 1001, height of 2 B tree, we can see that it can store more than 1000000000 words; however, because the root node can be lasting retained in the memory, so need to find a key to need only two disk access. If using two binary tree storage of words, the depth of the tree will be very large, so look for in a leaf node is the keyword will need a lot of disk reads! Suppose that there are n nodes, so the height of two binary tree h<=lg (n+ 1), and B tree for h<=log ((n+ 1) /2) /log (M), where M is the minimum degree.


Various operations on B tree:

1 Search

Search the B-tree and find two tree like, is at the branch of judging and choosing the correct subtree, then the recursive call. Search process time complex read implementation for Mlgn/lgM specific procedures are as follows:

/**********************************************************\
Function: the node where the search keywords
Input: the root of the tree, the keyword
Keywords: where the output node
\**********************************************************/
BtreeNode *BtreeSearch(BtreeNode *TestNode,int keyword)
{
	int i=0;
	while(i<TestNode->num&&keyword>TestNode->key[i])
		i=i+1;
	if(i<=TestNode->num&&keyword==TestNode->key[i])
		return TestNode;
	if(TestNode->isleaf)
	{
		printf("Not founded!\n");
		return NULL;
	}
	else
	{
		return BtreeSearch(TestNode->p[i],keyword);
	}
}

2 create an empty B tree


/**********************************************************\
Function: create a node
Input: no
Output: the new node
\**********************************************************/
BtreeNode * BtreeCreate()
{
	BtreeNode *node=(BtreeNode *)malloc(sizeof(BtreeNode));
	if(NULL==node)
		return NULL;
	node->isleaf=true;
	node->num=0;
	for(int i=0;i<2*M;i++)
		node->p[i]=NULL;
	for(int i=0;i<2*M-1;i++)
		node->key[i]=0;
	return node;
}

The 3 insertion


Insert the B into the two fork tree tree than the much more complex, Because the inserted two fork tree is to insert the new node, and insert the B tree is the key is inserted into the existing node, and the node may already be full node (mentioned earlier), nature will destroy the B tree. It cannot be inserted into a full node key. According to the B tree rule, Each node of the key number in [M-1, 2M-1], So when keyword (insert the key) to be added to a leaf when, If the leaf node has a 2M-1 keyword, Definitions and addition of keyword would be in violation of B tree, Then you need to split the leaf node, The leaves in the middle of the node is bounded, Divided into two M-1 contains a key node, At the same time, the intermediate node to the parent node of the leaves, If you make a number of key parent nodes than 2M-1, Will continue to split, Until the root node, The root node split will make the tree heightening one layer.

In order to solve the above problems, we need to continue to go back, this is obviously more complex, we can save: We did not wait to find whether you really need to split a full node to insert operation. On the contrary, when along the tree search down to insert a key position, can divide each full node encountered along the way. After doing this, when to split a full node, can guarantee the parents not full node.

The following graphic full node splitting process:


We also consider the special case: When splitting a full root, need to let the root becomes a new empty the children of the root node, then it can be decomposition process of the above decomposition. The height of the tree increases 1, division is the only way to tree! The operation is as follows:


In summary, the insertion process is implemented as follows:


//////////////////////////////Insert part///////////////////////////////////////////
/**********************************************************\
Function: node splitting, to prevent the property in violation of the B tree
Input: the parent node father, node child, K said the boy child nodes of the parent node
Output: no
\**********************************************************/
void BtreeSplitChild(BtreeNode *father,BtreeNode *child,int k)
{
	BtreeNode *newchild=(BtreeNode *)malloc(sizeof(BtreeNode));
	newchild->isleaf=child->isleaf;//Newchild is the right node child, namely child divided into child and newchild
	newchild->num=M-1;
	for(int i=0;i<M-1;i++)
		newchild->key[i]=child->key[i+M];
	if(!child->isleaf)//When the child is not a leaf, but also the pointer is assigned to newchild
	{
		for(int j=0;j<M;j++)
			newchild->p[j]=child->p[j+M];
	}

	child->num=M-1;//The number of child was changed from 2M-1 to M-1

	for(int i=father->num-1;i>=k+1;i--)//Change the parent node content
		father->p[i+1]=father->p[i];
	father->p[k+1]=newchild;
	for(int j=father->num-1;j>=k;j--)
		father->key[j+1]=father->key[j];
	father->key[k]=child->key[M-1];//Ascension will intermediate node child to the parent node
	father->num=father->num+1;


}

/**********************************************************\
Function: X node is not full cases, insert the keyword
Input: the root of the B tree, insert the key word
Output: no
\**********************************************************/
void BtreeInsertNotFull(BtreeNode *x,int keyword)
{
	int i=x->num;
	if(x->isleaf)//When x leaves, keyword inserted into the node
	{
		while(i>=1&&keyword<x->key[i-1])
		{
			x->key[i]=x->key[i-1];
			i=i-1;
		}	
		x->key[i]=keyword;
		x->num=x->num+1;
	}
	else//When the X is not a leaf node to be inserted, find keyword and insert
	{
		while(i>=1&&keyword<x->key[i-1])
		{
			i=i-1;
		}
	
		if(x->p[i]->num==2*M-1)//When a node for the full node, need to split
		{
			BtreeSplitChild(x,x->p[i],i);
			if(keyword>x->key[i])
				i=i+1;
			
		}
		BtreeInsertNotFull(x->p[i],keyword);
	}
}

/**********************************************************\
Function: insert the key value
Input: the root of the B tree, keyword
Output: the root of the B tree
\**********************************************************/
BtreeNode * BtreeInsert(BtreeNode *TestNode,int keyword)
{
	if(TestNode->num==2*M-1)//When the root node is full, only increase the height of the situation
	{
		BtreeNode *newroot=(BtreeNode *)malloc(sizeof(BtreeNode));
		newroot->isleaf=false;//New root
		newroot->num=0;
		newroot->p[0]=TestNode;
		BtreeSplitChild(newroot,TestNode,0);
		BtreeInsertNotFull(newroot,keyword);
		return newroot;
	}
	else
	{
		BtreeInsertNotFull(TestNode,keyword);
		return TestNode;
	}

}

4 deletion


Delete the B tree is more complex than the insert operation, only need to consider three cases operation to insert, and delete operations need to be considered by many, as follows:


And insert like B tree, according to the rules, a number of key between each node in the [M-1, 2M-1], when keyword (insert the key) to be removed from a leaf when, If the leaf node only has the M-1 keyword, then delete the definition of keyword would be in violation of B tree, When the need for consolidation of the leaf node. T in the above is what I call the M minimum degree. The specific procedures to achieve the following:


///////////////////////////Delete part//////////////////////////////////////////
/**********************************************************\
Function: with left and right child nodes
Input: root, left and right child node, the left node is the parent node of the POS node
Output: no
\**********************************************************/
void BtreeMergeChild(BtreeNode *root, int pos, BtreeNode *y, BtreeNode *z)
{
    // In the Z will be copied to the Y in the latter part of the node
    y->num = 2 * M - 1;
    for(int i = M; i <2 * M - 1; i++) 
	{
        y->key[i] = z->key[i-M];
    }
    y->key[M-1] = root->key[pos]; // Root-> key[pos] decreased as the middle node y
    
    
    if(false == z->isleaf)// If Z is a non leaf node, need to copy to the child node pointer p
	{
        for(int i = M; i <2 * M; i++) 
		{
            y->p[i] = z->p[i-M];
        }
    }
     
      
    for(int j = pos + 1; j <root->num; j++) // root->key[pos]Down to y, key and P in root update
	{
        root->key[j-1] = root->key[j];
        root->p[j] = root->p[j+1];
    }

    root->num -= 1;
    free(z);
}
  
/**********************************************************\
Function: remove the keyword keyword
Input: the root of the tree, the keyword
Output: the root of the tree
\**********************************************************/
BtreeNode *BtreeDelete(BtreeNode *root, int keyword)
{
    
    // Only can reduce tree height.
    if(1 == root->num) // When the root is a keyword, two children
	{
        BtreeNode *y = root->p[0];
        BtreeNode *z = root->p[1];
        if(NULL != y && NULL != z &&M - 1 == y->num && M - 1 == z->num)//A number of key two children are M-1, and two children with root
		{
            BtreeMergeChild(root, 0, y, z);
            free(root);//Note that the release of space
            BtreeDeleteNotFull(y, keyword);
            return y;
        }
		else 
		{
            BtreeDeleteNotFull(root, keyword);
            return root;
        }
    } 
	else 
	{
        BtreeDeleteNotFull(root, keyword);    
        return root;
    }
}

/**********************************************************\
Function: remove the root keyword has at least one M keyword
Input: the root of the tree, the keyword
Output: no
\**********************************************************/
void BtreeDeleteNotFull(BtreeNode *root, int keyword)
{
    if(true == root->isleaf) // If you delete directly in the leaf nodes,, 1
	{ 
        int i = 0;
        while(i <root->num && keyword > root->key[i]) i++;
        if(keyword == root->key[i])
		{
            for(int j = i + 1; j <2 * M - 1; j++) 
			{
                root->key[j-1] = root->key[j];
            }
            root->num -= 1;
        } 
		else 
		{
            printf("keyword not found\n");
        }
    }
	else 
	{  // In the branch
        int i = 0;
        BtreeNode *y = NULL, *z = NULL;
        while(i <root->num && keyword > root->key[i]) i++; 
        if(i <root->num && keyword == root->key[i]) 
		{ // If you find a keyword in the branch node
            y = root->p[i];
            z = root->p[i+1];
            if(y->num > M - 1) 
			{  
		      // If the left branch keyword more than M-1, then find the right node pre left branch, replace the keyword
                // And in the left branch of recursive delete prev, 2A
                int pre = BtreeSearchPrevious(y);
                root->key[i] = pre;
                BtreeDeleteNotFull(y, pre);//The recursive process
            } 
			else if(z->num > M - 1)
			{
                // If the right branching keyword more than M-1, next left most node is to find the right branch, replace the keyword
                // And in the right branch of a recursive delete next, 2b
                int next = BtreeSearchNext(z);
                root->key[i] = next;
                BtreeDeleteNotFull(z, next);
            }
			else // Two branches of number of nodes for M-1, then merge to y, and in the Y recursive delete keyword, 2C
			{
                
                BtreeMergeChild(root, i, y, z);
                BtreeDelete(y, keyword);
            }
        }
		else// The branch does not, in the branch node in the case of
		{   
            y = root->p[i];
            if(i <root->num) 
			{
                z = root->p[i+1];//Y right brother
            }
            BtreeNode *p = NULL;//Initialization
            if(i > 0)
			{
                p = root->p[i-1];//Y left the brothers
            }

            if(y->num == M - 1)
			{
                if(i > 0 && p->num > M - 1) 
				{
                    // The number left sibling node key is greater than M-1, 3A
                    BtreeChangeToRchild(root, i-1, p, y); 
                } 
				else if(i <root->num && z->num > M - 1) 
				{
                    // Right sibling node key number is greater than M-1, 3A
                    BtreeChangeToLchild(root, i, y, z); 
                }
				else if(i > 0) 
				{   
                    BtreeMergeChild(root, i-1, p, y);  //About the brother nodes are not greater than M-1, 3b
                    y = p;
                } 
				else //No left sibling situation
				{
                    BtreeMergeChild(root, i, y, z); 
                }
                BtreeDeleteNotFull(y, keyword);
            }
			else 
			{
                BtreeDeleteNotFull(y, keyword);
            }
        }

    }
}

/**********************************************************\
Function: to find the root for maximum keyword root
Input: the root of the tree
Keywords: maximum output
\**********************************************************/ 
int BtreeSearchPrevious(BtreeNode *root)
{
    BtreeNode *y = root;
    while(false == y->isleaf)
	{
        y = y->p[y->num];
    }
    return y->key[y->num-1];
}

/**********************************************************\
Function: to find the minimum in root keyword root
Input: the root of the tree
Keywords: minimum output
\**********************************************************/
int BtreeSearchNext(BtreeNode *root)  
{
    BtreeNode *z = root;
    while(false == z->isleaf)
	{
        z = z->p[0];
    }
    return z->key[0];
}


/**********************************************************\
Function: Z node, root-> to y; key[pos] down to Z, will rise to root maximum keyword y POS
Input: root, left and right child node, the left node is the parent node of the POS node
Output: no
\**********************************************************/
void BtreeChangeToRchild(BtreeNode *root, int pos, BtreeNode *y, BtreeNode *z)
{
    z->num += 1;
    for(int i = z->num -1; i > 0; i--) 
	{
        z->key[i] = z->key[i-1];
    }
    z->key[0]= root->key[pos];
    root->key[pos] = y->key[y->num-1];

    if(false == z->isleaf)
	{
        for(int i = z->num; i > 0; i--) 
		{
            z->p[i] = z->p[i-1];
        }
        z->p[0] = y->p[y->num];
    }

    y->num -= 1; 
}

 
/**********************************************************\
Function: y to borrow node, root-> key[pos] down to y, will rise to root minimum key from Z POS
Input: root, left and right child node, the left node is the parent node of the POS node
Output: no
\**********************************************************/
void BtreeChangeToLchild(BtreeNode *root, int pos, BtreeNode *y, BtreeNode *z)
{
    y->num += 1;
    y->key[y->num-1] = root->key[pos];
    root->key[pos] = z->key[0];

    for(int j = 1; j <z->num; j++)
	{
        z->key[j-1] = z->key[j];
    }

    if(false == z->isleaf) 
	{
        y->p[y->num] = z->p[0];
        for(int j = 1; j <= z->num; j++) 
		{
            z->p[j-1] = z->p[j];
        }
    } 

    z->num -= 1;
}

The following image shows the B tree with specific examples of the operation:

Assume that the initial B tree as follows:


After a series of insert operation:



In the procedure for convenient, the key by the letters into digital, A, B, C...... Y, Z corresponding to 1, 2, 3...25, 26.

After the insert operation, then on a series of deletion:




The complete example of the program are as follows:


#include<stdio.h>
#include<stdlib.h>

#define M 3

//The node structure
typedef struct BtreeNode
{
	int num;
	struct BtreeNode *p[2*M];
	int key[2*M-1];
	bool isleaf; 
}BtreeNode;

BtreeNode * BtreeCreate();
void BtreeSplitChild(BtreeNode *father,BtreeNode *child,int k);
void BtreeInsertNotFull(BtreeNode *x,int keyword);
BtreeNode * BtreeInsert(BtreeNode *TestNode,int keyword);
BtreeNode *BtreeSearch(BtreeNode *TestNode,int keyword);

//////
void BtreeMergeChild(BtreeNode *root, int pos, BtreeNode *y, BtreeNode *z);
BtreeNode *BtreeDelete(BtreeNode *root, int keyword);
void BtreeDeleteNotFull(BtreeNode *root, int keyword);
int BtreeSearchPrevious(BtreeNode *root);
int BtreeSearchNext(BtreeNode *root);
void BtreeChangeToRchild(BtreeNode *root, int pos, BtreeNode *y, BtreeNode *z);
void BtreeChangeToLchild(BtreeNode *root, int pos, BtreeNode *y, BtreeNode *z);

/**********************************************************\
Function: create a node
Input: no
Output: the new node
\**********************************************************/
BtreeNode * BtreeCreate()
{
	BtreeNode *node=(BtreeNode *)malloc(sizeof(BtreeNode));
	if(NULL==node)
		return NULL;
	node->isleaf=true;
	node->num=0;
	for(int i=0;i<2*M;i++)
		node->p[i]=NULL;
	for(int i=0;i<2*M-1;i++)
		node->key[i]=0;
	return node;
}
//////////////////////////////Insert part///////////////////////////////////////////
/**********************************************************\
Function: node splitting, to prevent the property in violation of the B tree
Input: the parent node father, node child, K said the boy child nodes of the parent node
Output: no
\**********************************************************/
void BtreeSplitChild(BtreeNode *father,BtreeNode *child,int k)
{
	BtreeNode *newchild=(BtreeNode *)malloc(sizeof(BtreeNode));
	newchild->isleaf=child->isleaf;//Newchild is the right node child, namely child divided into child and newchild
	newchild->num=M-1;
	for(int i=0;i<M-1;i++)
		newchild->key[i]=child->key[i+M];
	if(!child->isleaf)//When the child is not a leaf, but also the pointer is assigned to newchild
	{
		for(int j=0;j<M;j++)
			newchild->p[j]=child->p[j+M];
	}

	child->num=M-1;//The number of child was changed from 2M-1 to M-1
	
	for(int i=father->num;i>=k+1;i--)//Change the parent node content
	{
		father->p[i+1]=father->p[i];
	}
	father->p[k+1]=newchild;
	for(int j=father->num-1;j>=k;j--)
		father->key[j+1]=father->key[j];
	father->key[k]=child->key[M-1];//Ascension will intermediate node child to the parent node
	father->num=father->num+1;


}

/**********************************************************\
Function: X node is not full cases, insert the keyword
Input: the root of the B tree, insert the key word
Output: no
\**********************************************************/
void BtreeInsertNotFull(BtreeNode *x,int keyword)
{
	int i=x->num;
	if(x->isleaf)//When x leaves, keyword inserted into the node
	{
		while(i>=1&&keyword<x->key[i-1])
		{
			x->key[i]=x->key[i-1];
			i=i-1;
		}	
		x->key[i]=keyword;
		x->num=x->num+1;
	}
	else//When the X is not a leaf node to be inserted, find keyword and insert
	{
		i=x->num;
		while(i>=1&&keyword<x->key[i-1])
		{
			i=i-1;
		}
	
		if(x->p[i]->num==2*M-1)//When a node for the full node, need to split
		{
			BtreeSplitChild(x,x->p[i],i);
			if(keyword>x->key[i])
				i=i+1;
			
		}
		BtreeInsertNotFull(x->p[i],keyword);
	}
}

/**********************************************************\
Function: insert the key value
Input: the root of the B tree, keyword
Output: the root of the B tree
\**********************************************************/
BtreeNode * BtreeInsert(BtreeNode *TestNode,int keyword)
{
	if(TestNode->num==2*M-1)//When the root node is full, only increase the height of the situation
	{
		
		BtreeNode *newroot=(BtreeNode *)malloc(sizeof(BtreeNode));
		newroot->isleaf=false;//New root
		newroot->num=0;
		newroot->p[0]=TestNode;
		BtreeSplitChild(newroot,TestNode,0);
		BtreeInsertNotFull(newroot,keyword);
		return newroot;
	}
	else
	{
		
		BtreeInsertNotFull(TestNode,keyword);
		return TestNode;
	}

}

/**********************************************************\
Function: the node where the search keywords
Input: the root of the tree, the keyword
Keywords: where the output node
\**********************************************************/
BtreeNode *BtreeSearch(BtreeNode *TestNode,int keyword)
{
	int i=0;
	while(i<TestNode->num&&keyword>TestNode->key[i])
		i=i+1;
	if(i<=TestNode->num&&keyword==TestNode->key[i])
		return TestNode;
	if(TestNode->isleaf)
	{
		printf("Not founded!\n");
		return NULL;
	}
	else
	{
		return BtreeSearch(TestNode->p[i],keyword);
	}
}




///////////////////////////Delete part//////////////////////////////////////////
/**********************************************************\
Function: with left and right child nodes
Input: root, left and right child node, the left node is the parent node of the POS node
Output: no
\**********************************************************/
void BtreeMergeChild(BtreeNode *root, int pos, BtreeNode *y, BtreeNode *z)
{
    // In the Z will be copied to the Y in the latter part of the node
    y->num = 2 * M - 1;
    for(int i = M; i <2 * M - 1; i++) 
	{
        y->key[i] = z->key[i-M];
    }
    y->key[M-1] = root->key[pos]; // Root-> key[pos] decreased as the middle node y
    
    
    if(false == z->isleaf)// If Z is a non leaf node, need to copy to the child node pointer p
	{
        for(int i = M; i <2 * M; i++) 
		{
            y->p[i] = z->p[i-M];
        }
    }
     
      
    for(int j = pos + 1; j <root->num; j++) // root->key[pos]Down to y, key and P in root update
	{
        root->key[j-1] = root->key[j];
        root->p[j] = root->p[j+1];
    }

    root->num -= 1;
    free(z);
}
  
/**********************************************************\
Function: remove the keyword keyword
Input: the root of the tree, the keyword
Output: the root of the tree
\**********************************************************/
BtreeNode *BtreeDelete(BtreeNode *root, int keyword)
{
    
    // Only can reduce tree height.
    if(1 == root->num) // When the root is a keyword, two children
	{
        BtreeNode *y = root->p[0];
        BtreeNode *z = root->p[1];
        if(NULL != y && NULL != z &&M - 1 == y->num && M - 1 == z->num)//A number of key two children are M-1, and two children with root
		{
            BtreeMergeChild(root, 0, y, z);
            free(root);//Note that the release of space
            BtreeDeleteNotFull(y, keyword);
            return y;
        }
		else 
		{
            BtreeDeleteNotFull(root, keyword);
            return root;
        }
    } 
	else 
	{
        BtreeDeleteNotFull(root, keyword);    
        return root;
    }
}

/**********************************************************\
Function: remove the root keyword has at least one M keyword
Input: the root of the tree, the keyword
Output: no
\**********************************************************/
void BtreeDeleteNotFull(BtreeNode *root, int keyword)
{
    if(true == root->isleaf) // If you delete directly in the leaf nodes,, 1
	{ 
        int i = 0;
        while(i <root->num && keyword > root->key[i]) i++;
        if(keyword == root->key[i])
		{
            for(int j = i + 1; j <2 * M - 1; j++) 
			{
                root->key[j-1] = root->key[j];
            }
            root->num -= 1;
        } 
		else 
		{
            printf("keyword not found\n");
        }
    }
	else 
	{  // In the branch
        int i = 0;
        BtreeNode *y = NULL, *z = NULL;
        while(i <root->num && keyword > root->key[i]) i++; 
        if(i <root->num && keyword == root->key[i]) 
		{ // If you find a keyword in the branch node
            y = root->p[i];
            z = root->p[i+1];
            if(y->num > M - 1) 
			{  
		      // If the left branch keyword more than M-1, then find the right node pre left branch, replace the keyword
                // And in the left branch of recursive delete prev, 2A
                int pre = BtreeSearchPrevious(y);
                root->key[i] = pre;
                BtreeDeleteNotFull(y, pre);//The recursive process
            } 
			else if(z->num > M - 1)
			{
                // If the right branching keyword more than M-1, next left most node is to find the right branch, replace the keyword
                // And in the right branch of a recursive delete next, 2b
                int next = BtreeSearchNext(z);
                root->key[i] = next;
                BtreeDeleteNotFull(z, next);
            }
			else // Two branches of number of nodes for M-1, then merge to y, and in the Y recursive delete keyword, 2C
			{
                
                BtreeMergeChild(root, i, y, z);
                BtreeDelete(y, keyword);
            }
        }
		else// The branch does not, in the branch node in the case of
		{   
            y = root->p[i];
            if(i <root->num) 
			{
                z = root->p[i+1];//Y right brother
            }
            BtreeNode *p = NULL;//Initialization
            if(i > 0)
			{
                p = root->p[i-1];//Y left the brothers
            }

            if(y->num == M - 1)
			{
                if(i > 0 && p->num > M - 1) 
				{
                    // The number left sibling node key is greater than M-1, 3A
                    BtreeChangeToRchild(root, i-1, p, y); 
                } 
				else if(i <root->num && z->num > M - 1) 
				{
                    // Right sibling node key number is greater than M-1, 3A
                    BtreeChangeToLchild(root, i, y, z); 
                }
				else if(i > 0) 
				{   
                    BtreeMergeChild(root, i-1, p, y);  //About the brother nodes are not greater than M-1, 3b
                    y = p;
                } 
				else //No left sibling situation
				{
                    BtreeMergeChild(root, i, y, z); 
                }
                BtreeDeleteNotFull(y, keyword);
            }
			else 
			{
                BtreeDeleteNotFull(y, keyword);
            }
        }

    }
}

/**********************************************************\
Function: to find the root for maximum keyword root
Input: the root of the tree
Keywords: maximum output
\**********************************************************/ 
int BtreeSearchPrevious(BtreeNode *root)
{
    BtreeNode *y = root;
    while(false == y->isleaf)
	{
        y = y->p[y->num];
    }
    return y->key[y->num-1];
}

/**********************************************************\
Function: to find the minimum in root keyword root
Input: the root of the tree
Keywords: minimum output
\**********************************************************/
int BtreeSearchNext(BtreeNode *root)  
{
    BtreeNode *z = root;
    while(false == z->isleaf)
	{
        z = z->p[0];
    }
    return z->key[0];
}


/**********************************************************\
Function: Z node, root-> to y; key[pos] down to Z, will rise to root maximum keyword y POS
Input: root, left and right child node, the left node is the parent node of the POS node
Output: no
\**********************************************************/
void BtreeChangeToRchild(BtreeNode *root, int pos, BtreeNode *y, BtreeNode *z)
{
    z->num += 1;
    for(int i = z->num -1; i > 0; i--) 
	{
        z->key[i] = z->key[i-1];
    }
    z->key[0]= root->key[pos];
    root->key[pos] = y->key[y->num-1];

    if(false == z->isleaf)
	{
        for(int i = z->num; i > 0; i--) 
		{
            z->p[i] = z->p[i-1];
        }
        z->p[0] = y->p[y->num];
    }

    y->num -= 1; 
}

 
/**********************************************************\
Function: y to borrow node, root-> key[pos] down to y, will rise to root minimum key from Z POS
Input: root, left and right child node, the left node is the parent node of the POS node
Output: no
\**********************************************************/
void BtreeChangeToLchild(BtreeNode *root, int pos, BtreeNode *y, BtreeNode *z)
{
    y->num += 1;
    y->key[y->num-1] = root->key[pos];
    root->key[pos] = z->key[0];

    for(int j = 1; j <z->num; j++)
	{
        z->key[j-1] = z->key[j];
    }

    if(false == z->isleaf) 
	{
        y->p[y->num] = z->p[0];
        for(int j = 1; j <= z->num; j++) 
		{
            z->p[j-1] = z->p[j];
        }
    } 

    z->num -= 1;
}


//According to the level of traversing the B tree
void Print(BtreeNode *root)
{	
	int front,rear;
	int num=0;
	int num1=0;
	int flag=0;
	BtreeNode *queue[100];
	BtreeNode *s;
	if(root!=NULL)
	{
		rear=1;
		front=0;
		queue[rear]=root;
		while(front<rear)
		{
			front++;
		
			s=queue[front];

			if(!s->isleaf)
			{
				for(int j=0;j<=s->num;j++)
				{
					if(s->p[j]!=NULL)
					{
						rear++;
						queue[rear]=s->p[j];
						
					}
				}
			}
			
		}
			for(int k=1;k<=rear;k++)//The output is simple and easy to read
			{	
				for(int i=0;i<queue[k]->num;i++)
					printf("%d ",queue[k]->key[i]);
				printf("| ");			
				if(k>num)
				{
					
					while(flag<k)
					{
					num=num+queue[flag+1]->num+1;
					flag++;
					}
				printf("\n");
				flag=k;
				}
				
			}
			
			
		
	}
}


////////////////////////////////////////////////////////////////////////////
void main()
{
/**************************Initialization**************************/
	BtreeNode *TestNode=BtreeCreate();
	BtreeNode *Node1=BtreeCreate();
	BtreeNode *Node2=BtreeCreate();
	BtreeNode *Node3=BtreeCreate();
	BtreeNode *Node4=BtreeCreate();
	BtreeNode *Node5=BtreeCreate();
	BtreeNode *root=BtreeCreate();

	BtreeNode *SearchNode=BtreeCreate();
	TestNode->isleaf=false;
	TestNode->num=4;
	TestNode->key[0]=7;
	TestNode->key[1]=13;
	TestNode->key[2]=16;
	TestNode->key[3]=24;
	TestNode->p[0]=Node1;
	TestNode->p[1]=Node2;
	TestNode->p[2]=Node3;
	TestNode->p[3]=Node4;
	TestNode->p[4]=Node5;

	Node1->isleaf=true;
	Node1->num=4;
	Node1->key[0]=1;
	Node1->key[1]=3;
	Node1->key[2]=4;
	Node1->key[3]=5;

	Node2->isleaf=true;
	Node2->num=2;
	Node2->key[0]=10;
	Node2->key[1]=11;


	Node3->isleaf=true;
	Node3->num=2;
	Node3->key[0]=14;
	Node3->key[1]=15;


	Node4->isleaf=true;
	Node4->num=5;
	Node4->key[0]=18;
	Node4->key[1]=19;
	Node4->key[2]=20;
	Node4->key[3]=21;
	Node4->key[4]=22;


	Node5->isleaf=true;
	Node5->num=2;
	Node5->key[0]=25;
	Node5->key[1]=26;
	root=TestNode;
/*******************************Initialization is finished***********************/
	printf("The original B tree: \n");
	Print(root);
	root=BtreeInsert(root,2);
	printf("\The N keyword is inserted after 2 B tree: \n");
	Print(root);
	root=BtreeInsert(root,17);
	printf("\The N keyword is inserted after 17 B tree: \n");
	Print(root);
	root=BtreeInsert(root,12);
	printf("\The N keyword is inserted after 12 B tree: \n");
	Print(root);
	root=BtreeInsert(root,6);
	printf("\The N keyword is inserted after 6 B tree: \n");
	Print(root);
	printf("\n\n");
	//The delete operation
    root=BtreeDelete(root,6);
	printf("\Delete n key for 6 B tree: \n");
	Print(root);

	root=BtreeDelete(root,13);
	printf("\Delete n key for 13 B tree: \n");
	Print(root);

	root=BtreeDelete(root,7);
	printf("\Delete n key for 7 B tree: \n");
	Print(root);

	root=BtreeDelete(root,4);
	printf("\Delete n key for 4 B tree: \n");
	Print(root);


    root=BtreeDelete(root,2);
	printf("\Delete n key for 2 B tree: \n");
	Print(root);
	
}

The results are as follows (| procedures used to separate different node words, shown in a hierarchical tree traversal, can be seen from the above results and insert and delete the graphic process of the sameļ¼):



Note: if the program is in error, is probably the version of the development platform using different, please click on the link below: explanation



Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Tiffany at December 06, 2013 - 8:53 PM