| |
0. Preface
I hereby undergraduate sophomore this semester to learn the data structure, our teacher arranged a final assignment to any topic, but I have heard that there has always been a B-tree is a very magical tree, so I chose it, of course, more important reason is because the highest difficulty of the B-tree, I like to do challenging work. At the same time, I listen to my group Friends said he was keen to share what they have learned to think on the blog garden, we have such an article. I hope I can learn at the same time to write the blog more things, but also to help other encountered or will encounter similar problems beginners.
1. For B-tree
B-tree is a tree called a search tree, similar thereto with search binary tree, balanced binary tree, in addition, there are a variety of B tree siblings B + tree, B- tree, B * trees, their common feature is that the laws are in accordance with certain order store. Application of B-tree is very broad, almost by default B-tree index structure of all databases, but also the most widely used index structure. B-tree is a multi-tree, according to the most number of forks can be called M-order B-tree. Introduction to Algorithms based on the narrative, but also by each node B-tree branch to determine a minimum order of B-trees, but the order of the B-tree so it must be even. I personally use a B-tree is determined based on the maximum number of branches of order.
An M-order B-tree or empty tree, or to satisfy the following characteristics M-tree:
(1) Each node in the tree containing up to M sub-trees;
(2) If the root is not a leaf node, then at least two sub-trees;
(3) All non-terminal nodes except the root have at least [m / 2] sub-trees;
(4) Information keynum each non-terminal node contains, ptr [0], key [1], ptr [1], key [2], ptr [2], ...... key [keynum], ptr [keynum ];
Wherein, key for a keyword, and the keyword sorted in ascending order, ptr to point to the sub-tree root node pointer
2. Idea and realization
Interface B is inserted into the main tree (including the empty tree insert an element) and deletions, insertions and deletions will be used inevitable lookup operation, but the main idea is relatively simple to find, mainly using B-tree is a sort the principle of the tree, you can quickly find a location you want to insert or to delete nodes. The key here is to pay attention to where the search results returned include the node, as well as the location of the element, which is to facilitate the next operation is relatively simple.
insert:
Through the B-tree is traversed to identify the node to be inserted and node position, if key values found in the B-tree which already exists, the insertion fails. Otherwise, you can insert. Regardless of whether the upper limit here can be beyond the requirements of M-ary tree, because we will deliberately leave at the time of the definition of a position, you can store the extra element, after insertion, by judging whether the tree cap M-order requirements, and then recursively split operation.
/ ***
* @name Status insertBTree (BTree & T, Record e)
* @description Insert achieve insertion element
* @return Successful return OK, if it exists it returns FALSE, otherwise returns ERROR
* @notice
*** /
Status insertBTree (BTree & T, Record e)
{
BTree p;
int index, temp;
Status find_flag;
if (NULL == T) // consider the B-tree is empty tree case
{
T = (BTree) malloc (BTLEN);
if (NULL == T) return OVERFLOW;
T-> keynum = 1;
T-> parent = NULL;
for (index = 0; index < = m; ++ index)
{
T-> ptr [index] = NULL;
T-> key [index] = 0;
}
T-> key [1] = e.key;
return OK;
}
find_flag = findBTree (T, p, temp, e.key); // looking for the insertion node
if (find_flag == TRUE)
{
return FALSE;
}
if (find_flag == FALSE)
{// First inserted directly anyway
p-> keynum ++;
for (index = p-> keynum; index> temp; - index)
{
p-> key [index] = p-> key [index - 1];
p-> ptr [index] = p-> ptr [index - 1];
}
p-> ptr [temp] = NULL;
p-> key [temp] = e.key;
if (p-> keynum == m) // this case was split
{
splitBTree (p);
}
renewParent (T);
return OK;
}
return ERROR;
}
Split:
Split operation is inserted during the operation one of the most important operations, because this is the deal with "conflict" (ie, nodes in a data element is greater than B-tree rules required by the maximum number) of a generic approach, this approach must to all cases are applicable, but division is a way to solve this problem. Of course, this method is only taking into account the efficiency, no brothers data to judge whether to borrow, but in a different way too much trouble, not discussed here first.
The idea is to split the parent node to vacate a position (including key and ptr) out, and then split the node needs to get inside the middle of the element and move to the middle of the key elements of the father node has been freed up key positions there and then split out the right portion received vacated ptr there. Note that the entire process of the left part and right part of the change in the number of elements to be some useless and empty space. After the split-up may result in a situation in which the father node also may reach the maximum number of split, so check the parent node if you need to split, if necessary, recursion.
/ ***
* @name Status splitBTree (BTree T)
* @description Recursive splitting node operation
* @return Successful return OK, otherwise ERROR
* @notice
*** /
Status splitBTree (BTree T) // this time will be split node exceeds the maximum.
{
BTree t1, t2;
int index, index_1;
if (T-> parent == NULL)
{
t1 = (BTree) malloc (BTLEN);
if (NULL == t1) return OVERFLOW;
t2 = (BTree) malloc (BTLEN);
if (NULL == t2) return OVERFLOW;
t1-> keynum = m / 2;
t2-> keynum = m - (m / 2) - 1;
t1-> parent = T;
t2-> parent = T;
for (index = 0; index < = m; ++ index) // first initialize all
{
t1-> ptr [index] = NULL;
t1-> key [index] = 0;
t2-> ptr [index] = NULL;
t2-> key [index] = 0;
}
for (index = 0; index < = m / 2; ++ index) // initialize t1
{
t1-> ptr [index] = T-> ptr [index];
t1-> key [index] = T-> key [index];
}
t2-> ptr [0] = T-> ptr [(m / 2) + 1];
for (index = (m / 2) + 2; index < = m; ++ index) // initialize t2
{
t2-> ptr [index - ((m / 2) + 1)] = T-> ptr [index];
t2-> key [index - ((m / 2) + 1)] = T-> key [index];
}
T-> keynum = 1;
T-> ptr [0] = t1;
T-> ptr [1] = t2;
T-> key [1] = T-> key [m / 2 + 1];
for (index = 2; index < = m; ++ index) // initialize T
{
T-> ptr [index] = NULL;
T-> key [index] = 0;
}
return OK;
}
delete:
Deletion of elements similar to the B-tree insertion operation, but have to trouble, because in both cases the score processing. (1) finding the existence of this element, but this element is where the leaf node (ie its children is empty), delete them directly after then determine whether the B-tree is less than the minimum required by the rules of the number of sub-tree. If less than, then invoke the merge function. (2) If the finding of the element element is non-leaf node, by looking for smaller than the element largest element (the element certainly is leaf node) to the elements directly assigned to the element you want to delete, and then in the leaf node (1) in operation.
/ ***
* @name Status deleteBTreeRecord (BTree & T, Record e)
* @description Realize delete B-tree elements
* @return Successful return OK, otherwise ERROR
* @notice
*** /
Status deleteBTreeRecord (BTree & T, Record e)
{
BTree p, q;
int num, temp, index;
Status find_flag;
if (T == NULL)
return ERROR;
find_flag = findBTree (T, p, temp, e.key);
if (find_flag == FALSE)
{
return FALSE;
}
if (find_flag == TRUE)
{
// DeleteBTreeBNode (p, temp);
if (p-> ptr [temp] == NULL) // If the node is a leaf, then
{
for (index = temp; index < = p-> keynum; ++ index)
{
p-> key [index] = p-> key [index + 1];
p-> ptr [index] = p-> ptr [index + 1];
}
p-> keynum--;
if (p-> keynum == (m + 1) / 2 - 2)
{
// Call the function by brothers
if (borrowBNode (p) == EMPTY) T = NULL;
else renewParent (T);
}
return OK;
}
else // not a leaf node, then
{
// Iterate
findMax (p-> ptr [temp - 1], q, num); // Returns the q will be a leaf node
p-> key [temp] = q-> key [num];
q-> key [num] = 0;
q-> keynum--;
if (q-> keynum == (m + 1) / 2 - 2)
{
// Call the function by brothers
if (borrowBNode (q) == EMPTY) T = NULL;
else renewParent (T);
}
return OK;
}
return OK;
}
return ERROR;
}
merge:
In this first statement since the beginning of the order consider only the B-tree is four, and later changed to use macros order value of M, there is BUG This code supports only the order of 3 or 4, B = = tree.
Thinking was quite clear, first Xianxiang sibling nodes by element, if the brothers can lend your element, then (after that is borrowed and you will not be less than the least branch), then take the element directly from there the brothers, otherwise, and brothers merge.
In fact, the merger is the case in turn split from the parent node where removed a key element in value between two nodes to be merged between the left portion of the insert at the end, while the right part into the back part of the left, and then his father node element sequentially moved forward. In order to achieve combined operation. After that, his father must also be determined whether the node is less than the minimum number of branches, if also less than his father nodes operate recursively.
/ ***
* @name Status borrowBNode (BTree & T)
* @description Recursive, the brothers borrowed elements, otherwise the brothers merge
* @return Successful return OK, otherwise ERROR
* @notice This should be a single element T junction
*** /
Status borrowBNode (BTree T)
{
int mynum, bronum, index;
BTree b = NULL, f = NULL;
if (T == NULL) return ERROR;
f = T-> parent;
if (f == NULL) // consider the case of parent node does not exist
{
if (T-> keynum == 0)
{
f = T-> ptr [0];
if (f == NULL)
{
free (T);
return EMPTY;
}
for (index = 0; index < = f-> keynum; index ++)
{
T-> key [index] = f-> key [index];
T-> ptr [index] = f-> ptr [index];
}
T-> keynum = f-> keynum;
free (f);
renewParent (T);
}
return OK;
}
mynum = whichSon (T);
if (mynum == 0)
bronum = 1;
else
bronum = mynum - 1;
b = f-> ptr [bronum];
if (b-> keynum == (m + 1) / 2 - 1) // If the brothers can not help you
{
// And then fit this brother
if (bronum < mynum) // if I am not the first
{
b-> keynum ++;
b-> key [b-> keynum] = f-> key [mynum];
b-> ptr [b-> keynum] = T-> ptr [0];
for (index = 1; index < = T-> keynum; index ++)
{
b-> key [index + b-> keynum] = T-> key [index];
b-> ptr [index + b-> keynum] = T-> ptr [index];
b-> keynum ++;
}
free (T);
for (index = mynum; index < = f-> keynum; index ++)
{
f-> key [index] = f-> key [index + 1];
f-> ptr [index] = f-> ptr [index + 1];
}
f-> keynum--;
}
else
{
T-> keynum ++;
T-> key [T-> keynum] = f-> key [bronum];
T-> ptr [T-> keynum] = b-> ptr [0];
for (index = 1; index < = b-> keynum; index ++)
{
T-> key [index + T-> keynum] = b-> key [index];
T-> ptr [index + T-> keynum] = b-> ptr [index];
T-> keynum ++;
}
free (b);
for (index = bronum; index < = f-> keynum; index ++)
{
f-> key [index] = f-> key [index + 1];
f-> ptr [index] = f-> ptr [index + 1];
}
f-> keynum--;
}
renewParent (f);
if (f-> keynum == (m + 1) / 2 - 2)
{
// Call the function by brothers
return borrowBNode (f);
}
}
else // if the brothers can help you
{
if (bronum < mynum) // if I am not the first
{
for (index = 1; index < = T-> keynum; index ++)
{
T-> key [index + 1] = T-> key [index];
T-> ptr [index + 1] = T-> ptr [index];
}
T-> ptr [1] = T-> ptr [0];
T-> key [1] = f-> key [mynum];
T-> ptr [0] = b-> ptr [b-> keynum];
T-> keynum ++;
f-> key [mynum] = b-> key [b-> keynum];
b-> key [b-> keynum] = 0;
b-> ptr [b-> keynum] = NULL;
b-> keynum--;
}
else // if I was the one
{
T-> keynum ++;
T-> key [T-> keynum] = f-> key [1];
T-> ptr [T-> keynum] = b-> ptr [0];
f-> key [1] = b-> key [1];
b-> ptr [0] = b-> ptr [1];
for (index = 1; index < = b-> keynum; index ++)
{
b-> key [index] = b-> key [index + 1];
b-> ptr [index] = b-> ptr [index + 1];
}
b-> keynum--;
}
}
return OK;
}
Traversal, output:
To make it easier to see the B-tree, the code easier to debug, and I also used to write a queue traverse the level, this look like, achieve up quite troublesome. And may also problematic code
/ ***
* @name Status ergodic (BTree T, LinkList L, int newline, int sum)
* @description Print need to use recursive traversal procedures
* @return Successful return OK
* @notice Used herein queue
*** /
Status ergodic (BTree T, LinkList L, int newline, int sum)
{
int index;
BTree p;
if (T! = NULL)
{
printf ( "[");
Enqueue_L (L, T-> ptr [0]);
for (index = 1; index < = T-> keynum; index ++)
{
printf ( "% d", T-> key [index]);
Enqueue_L (L, T-> ptr [index]);
}
sum + = T-> keynum + 1;
printf ( "]");
if (newline == 0)
{
printf ( "\ n");
newline = sum - 1;
sum = 0;
}
else
{
--newline;
}
}
if (IfEmpty (L) == FALSE)
{
Dequeue_L (L, p);
ergodic (p, L, newline, sum);
}
return OK;
}
/ ***
* @name Status print (BTree T)
* @description Traverse the level of output and hierarchical B tree
* @return Successful return OK
* @notice
*** /
Status print (BTree T)
{
LinkList L;
if (T == NULL)
{
printf ( "[] \ n");
return OK;
}
InitQueue_L (L);
ergodic (T, L, 0, 0);
DestroyQueue (L);
return OK;
}
3. Summary
In the current state of knowledge, and finally the B-tree made out, the whole process has not made reference to other people's code, so do not know whether some of their ideas properly, if wrong, forgive me. Throughout the process, the most difficult, the card is the oldest of the merge operation, this code is chaotic dregs, after he had time to improve. Finally, attach the complete code.
#define _CRT_SECURE_NO_WARNINGS
#include < stdio.h>
#include < stdlib.h>
#include < time.h>
#define BTREELENGTH 50
#define BTLEN (sizeof (BTNode))
#define MAXINT 100
typedef enum status
{
TRUE,
FALSE,
OK,
ERROR,
OVERFLOW,
EMPTY
} Status;
typedef int KeyType;
// ********************************** B tree ************ ****************************
Order #define m 3 // B tree, this is set to 4
typedef struct
{
KeyType key;
char data;
} Record;
typedef struct BTNode
{
int keynum; // node in the number of keywords that the size of the junction points
struct BTNode * parent; // point to the parent node
KeyType key [m + 1]; // keyword vector, 0 unimplemented
struct BTNode * ptr [m + 1]; // subtree pointer vector
// Record * recptr [m + 1]; // record pointer vector, 0 unimplemented
// Add here other custom data
Type // B and B-tree node tree;} BTNode, * BTree
typedef struct
{
BTNode * pt; // point to the node found
int i; // 1..m, the node number of keywords
int tag; // 1: Finding Success, 0: lookup fails
} Result; // search results in the B-tree type
// ********************************** B tree ************ ****************************
//**********************************queue************* **************************
typedef struct LNode {
BTree data; // data fields
struct LNode * next; // pointer domain
} LNode, * LinkList;
//**********************************queue************* **************************
/ ***
* @name Status InitQueue_L (LinkList & L)
* @description Initialize queue
* @return Successful return OK, open space failed to return OVERFLOW
* @notice
*** /
Status InitQueue_L (LinkList & L)
{// Initialize a head node containing only a single empty list L
if (NULL == (L = (LNode *) malloc (sizeof (LNode)))) // create a new node
return OVERFLOW;
L-> next = NULL;
return OK;
}
/ ***
* @name LNode * MakeNode_L (BTree e)
* @description Queue node configuration
* @return Returns the node address
* @notice
*** /
LNode * MakeNode_L (BTree e)
{// Single linked list node structure of data fields e
LNode * p;
p = (LNode *) malloc (sizeof (LNode)); // allocate space node
if (p! = NULL)
{
p-> data = e;
p-> next = NULL;
}
return p;
}
/ ***
* @name Status Enqueue_L (LNode * p, BTree e)
* Queue enqueue @description
* @return Successful return OK, otherwise ERROR
* @notice
*** /
Status Enqueue_L (LNode * p, BTree e)
Q {// insert node after node in p
if (NULL == p) return ERROR; // parameter unreasonable
while (p-> next! = NULL)
p = p-> next;
p-> next = MakeNode_L (e); // corresponding to Fig. 4.11 (b) 2, modify the node pointer field p
return OK;
}
/ ***
* @name Status Dequeue_L (LNode * p, BTree & e)
* The team @description queue
* @return Successful return OK, otherwise ERROR
* @notice
*** /
Status Dequeue_L (LNode * p, BTree & e)
{
// Delete p node direct successor node and returns the value of the deleted node parameter e
LNode * q;
if (NULL == p || NULL == p-> next) return ERROR; // remove the unreasonable position
q = p-> next;
p-> next = q-> next; // modify the deleted node pointer field q
e = q-> data;
free (q); // release node q
return OK;
}
/ ***
* @name Void DestroyQueue (LinkList L)
* Destruction @description queue
* @return No return
* @notice
*** /
void DestroyQueue (LinkList L)
{
// Destroy the entire list
LinkList p;
if (L! = NULL)
{
p = L;
L = L-> next;
free (p);
DestroyQueue (L);
}
}
/ ***
* @name Status IfEmpty (LinkList L)
* @description Whether the queue is empty
* @return Null return TRUE, not empty return FALSE, otherwise returns ERROR
* @notice
*** /
Status IfEmpty (LinkList L)
{
if (L == NULL) return ERROR;
if (L-> next == NULL) return TRUE;
return FALSE;
}
/ ***
* @name Status ergodic (BTree T, LinkList L, int newline, int sum)
* @description Print need to use recursive traversal procedures
* @return Successful return OK
* @notice Used herein queue
*** /
Status ergodic (BTree T, LinkList L, int newline, int sum)
{
int index;
BTree p;
if (T! = NULL)
{
printf ( "[");
Enqueue_L (L, T-> ptr [0]);
for (index = 1; index < = T-> keynum; index ++)
{
printf ( "% d", T-> key [index]);
Enqueue_L (L, T-> ptr [index]);
}
sum + = T-> keynum + 1;
printf ( "]");
if (newline == 0)
{
printf ( "\ n");
newline = sum - 1;
sum = 0;
}
else
{
--newline;
}
}
if (IfEmpty (L) == FALSE)
{
Dequeue_L (L, p);
ergodic (p, L, newline, sum);
}
return OK;
}
/ ***
* @name Status print (BTree T)
* @description Traverse the level of output and hierarchical B tree
* @return Successful return OK
* @notice
*** /
Status print (BTree T)
{
LinkList L;
if (T == NULL)
{
printf ( "[] \ n");
return OK;
}
InitQueue_L (L);
ergodic (T, L, 0, 0);
DestroyQueue (L);
return OK;
}
/ ***
* @name Status findMax (BTree T, BTree & p, int ans)
* @description Keywords to find the largest node, T is looking for a tree, p node returned, ans was the first of several
* @return Successful return OK, otherwise ERROR
* @notice
*** /
Status findMax (BTree T, BTree & p, int & ans)
{
if (T == NULL)
return ERROR;
p = T;
while (p-> ptr [p-> keynum]! = NULL)
{
p = p-> ptr [p-> keynum];
}
ans = p-> keynum;
return OK;
}
/ ***
* @name Status findMin (BTree T, BTree & p, int ans)
* @description Keywords to find the smallest node, T is looking for a tree, p node returned, ans was the first of several
* @return Successful return OK, otherwise ERROR
* @notice
*** /
/ ***
* @name Status findBTree (BTree T, BTree & p, int & ans, KeyType k)
* @description Looking, T is looking for a tree, p nodes returned as the first of several elements ans, k is looking for value
* @return Successful return OK, otherwise ERROR
* @notice
*** /
Status findBTree (BTree T, BTree & p, int & ans, KeyType k)
{
BTree q;
int index = 1;
KeyType keynow;
if (T == NULL)
return ERROR;
q = T;
keynow = T-> key [1];
while (q! = NULL) // traverse depth
{
index = 1;
keynow = q-> key [index];
while (index < = q-> keynum) // true value within each node traversal
{
if (k == keynow) // find elements
{
p = q;
ans = index;
return TRUE;
}
if (k> keynow)
{
if (index == q-> keynum)
{
if (q-> ptr [index] == NULL)
{
p = q;
ans = q-> keynum + 1;
return FALSE;
}
q = q-> ptr [index];
break;
}
++ Index;
keynow = q-> key [index];
continue;
}
if (k < keynow)
{
if (q-> ptr [index - 1] == NULL)
{
p = q;
ans = index;
return FALSE;
}
q = q-> ptr [index - 1];
break;
}
}
}
return ERROR;
}
/ ***
* @name Status renewParent (BTree p)
* @description Person who tells the kids father is
* @return Successful return OK, otherwise ERROR
* @notice
*** /
Status renewParent (BTree p)
{
int index;
if (p == NULL) return ERROR;
for (index = 0; index < = p-> keynum; ++ index)
{
if (p-> ptr [index]! = NULL)
{
p-> ptr [index] -> parent = p;
renewParent (p-> ptr [index]);
}
}
return OK;
}
/ ***
* @name Int whichSon (BTree T)
* @description To find the father of several children first
* @return A successful return to the first of several children, otherwise -1
* @notice
*** /
int whichSon (BTree T)
{
int index = -1;
if (T == NULL) return -1;
for (index = 0; index < = T-> parent-> keynum; ++ index) // find the father of several children first
{
if (T-> parent-> ptr [index] == T) return index;
}
return -1;
}
/ ***
* @name Status splitBTree (BTree T)
* @description Recursive splitting node operation
* @return Successful return OK, otherwise ERROR
* @notice
*** /
Status splitBTree (BTree T) // this time will be split node exceeds the maximum.
{
BTree t1, t2;
int index, index_1;
if (T-> parent == NULL)
{
t1 = (BTree) malloc (BTLEN);
if (NULL == t1) return OVERFLOW;
t2 = (BTree) malloc (BTLEN);
if (NULL == t2) return OVERFLOW;
t1-> keynum = m / 2;
t2-> keynum = m - (m / 2) - 1;
t1-> parent = T;
t2-> parent = T;
for (index = 0; index < = m; ++ index) // first initialize all
{
t1-> ptr [index] = NULL;
t1-> key [index] = 0;
t2-> ptr [index] = NULL;
t2-> key [index] = 0;
}
for (index = 0; index < = m / 2; ++ index) // initialize t1
{
t1-> ptr [index] = T-> ptr [index];
t1-> key [index] = T-> key [index];
}
t2-> ptr [0] = T-> ptr [(m / 2) + 1];
for (index = (m / 2) + 2; index < = m; ++ index) // initialize t2
{
t2-> ptr [index - ((m / 2) + 1)] = T-> ptr [index];
t2-> key [index - ((m / 2) + 1)] = T-> key [index];
}
T-> keynum = 1;
T-> ptr [0] = t1;
T-> ptr [1] = t2;
T-> key [1] = T-> key [m / 2 + 1];
for (index = 2; index < = m; ++ index) // initialize T
{
T-> ptr [index] = NULL;
T-> key [index] = 0;
}
return OK;
}
index = whichSon (T);
for (index_1 = T-> parent-> keynum; index_1> index; - index_1) // make his father's position
{
T-> parent-> ptr [index_1 + 1] = T-> parent-> ptr [index_1];
T-> parent-> key [index_1 + 1] = T-> parent-> key [index_1];
}
T-> parent-> keynum ++;
T-> parent-> key [index + 1] = T-> key [m / 2 + 1];
t2 = T-> parent-> ptr [index + 1] = (BTree) malloc (BTLEN);
if (NULL == t2) return OVERFLOW;
for (index = 0; index < = m; ++ index) // first initialize all
{
t2-> ptr [index] = NULL;
t2-> key [index] = 0;
}
t2-> keynum = m - (m / 2) - 1;
t2-> parent = T-> parent;
t2-> ptr [0] = T-> ptr [(m / 2) + 1];
for (index = (m / 2) + 2; index < = m; ++ index) // initialize t2
{
t2-> ptr [index - ((m / 2) + 1)] = T-> ptr [index];
t2-> key [index - ((m / 2) + 1)] = T-> key [index];
}
T-> keynum = m / 2;
for (index = (m / 2) + 1; index < = m; ++ index) // initialize t2
{
T-> ptr [index] = NULL;
T-> key [index] = 0;
}
if (T-> parent-> keynum == m)
{
splitBTree (T-> parent);
}
return OK;
}
/ ***
* @name Status insertBTree (BTree & T, Record e)
* @description Insert achieve insertion element
* @return Successful return OK, if it exists it returns FALSE, otherwise returns ERROR
* @notice
*** /
Status insertBTree (BTree & T, Record e)
{
BTree p;
int index, temp;
Status find_flag;
if (NULL == T)
{
T = (BTree) malloc (BTLEN);
if (NULL == T) return OVERFLOW;
T-> keynum = 1;
T-> parent = NULL;
for (index = 0; index < = m; ++ index)
{
T-> ptr [index] = NULL;
T-> key [index] = 0;
}
T-> key [1] = e.key;
return OK;
}
find_flag = findBTree (T, p, temp, e.key);
if (find_flag == TRUE)
{
return FALSE;
}
if (find_flag == FALSE)
{// First inserted directly anyway
p-> keynum ++;
for (index = p-> keynum; index> temp; - index)
{
p-> key [index] = p-> key [index - 1];
p-> ptr [index] = p-> ptr [index - 1];
}
p-> ptr [temp] = NULL;
p-> key [temp] = e.key;
if (p-> keynum == m) // this case was split
{
splitBTree (p);
}
renewParent (T);
return OK;
}
return ERROR;
}
/ ***
* @name Status borrowBNode (BTree & T)
* @description Recursive, the brothers borrowed elements, otherwise the brothers merge
* @return Successful return OK, otherwise ERROR
* @notice This should be a single element T junction
*** /
Status borrowBNode (BTree T)
{
int mynum, bronum, index;
BTree b = NULL, f = NULL;
if (T == NULL) return ERROR;
f = T-> parent;
if (f == NULL) // consider the case of parent node does not exist
{
if (T-> keynum == 0)
{
f = T-> ptr [0];
if (f == NULL)
{
free (T);
return EMPTY;
}
for (index = 0; index < = f-> keynum; index ++)
{
T-> key [index] = f-> key [index];
T-> ptr [index] = f-> ptr [index];
}
T-> keynum = f-> keynum;
free (f);
renewParent (T);
}
return OK;
}
mynum = whichSon (T);
if (mynum == 0)
bronum = 1;
else
bronum = mynum - 1;
b = f-> ptr [bronum];
if (b-> keynum == (m + 1) / 2 - 1) // If the brothers can not help you
{
// And then fit this brother
if (bronum < mynum) // if I am not the first
{
b-> keynum ++;
b-> key [b-> keynum] = f-> key [mynum];
b-> ptr [b-> keynum] = T-> ptr [0];
for (index = 1; index < = T-> keynum; index ++)
{
b-> key [index + b-> keynum] = T-> key [index];
b-> ptr [index + b-> keynum] = T-> ptr [index];
b-> keynum ++;
}
free (T);
for (index = mynum; index < = f-> keynum; index ++)
{
f-> key [index] = f-> key [index + 1];
f-> ptr [index] = f-> ptr [index + 1];
}
f-> keynum--;
}
else
{
T-> keynum ++;
T-> key [T-> keynum] = f-> key [bronum];
T-> ptr [T-> keynum] = b-> ptr [0];
for (index = 1; index < = b-> keynum; index ++)
{
T-> key [index + T-> keynum] = b-> key [index];
T-> ptr [index + T-> keynum] = b-> ptr [index];
T-> keynum ++;
}
free (b);
for (index = bronum; index < = f-> keynum; index ++)
{
f-> key [index] = f-> key [index + 1];
f-> ptr [index] = f-> ptr [index + 1];
}
f-> keynum--;
}
renewParent (f);
if (f-> keynum == (m + 1) / 2 - 2)
{
// Call the function by brothers
return borrowBNode (f);
}
}
else // if the brothers can help you
{
if (bronum < mynum) // if I am not the first
{
for (index = 1; index < = T-> keynum; index ++)
{
T-> key [index + 1] = T-> key [index];
T-> ptr [index + 1] = T-> ptr [index];
}
T-> ptr [1] = T-> ptr [0];
T-> key [1] = f-> key [mynum];
T-> ptr [0] = b-> ptr [b-> keynum];
T-> keynum ++;
f-> key [mynum] = b-> key [b-> keynum];
b-> key [b-> keynum] = 0;
b-> ptr [b-> keynum] = NULL;
b-> keynum--;
}
else // if I was the one
{
T-> keynum ++;
T-> key [T-> keynum] = f-> key [1];
T-> ptr [T-> keynum] = b-> ptr [0];
f-> key [1] = b-> key [1];
b-> ptr [0] = b-> ptr [1];
for (index = 1; index < = b-> keynum; index ++)
{
b-> key [index] = b-> key [index + 1];
b-> ptr [index] = b-> ptr [index + 1];
}
b-> keynum--;
}
}
return OK;
}
/ ***
* @name Status deleteBTreeRecord (BTree & T, Record e)
* @description Realize delete B-tree elements
* @return Successful return OK, otherwise ERROR
* @notice
*** /
Status deleteBTreeRecord (BTree & T, Record e)
{
BTree p, q;
int num, temp, index;
Status find_flag;
if (T == NULL)
return ERROR;
find_flag = findBTree (T, p, temp, e.key);
if (find_flag == FALSE)
{
return FALSE;
}
if (find_flag == TRUE)
{
// DeleteBTreeBNode (p, temp);
if (p-> ptr [temp] == NULL) // If the node is a leaf, then
{
for (index = temp; index < = p-> keynum; ++ index)
{
p-> key [index] = p-> key [index + 1];
p-> ptr [index] = p-> ptr [index + 1];
}
p-> keynum--;
if (p-> keynum == (m + 1) / 2 - 2)
{
// Call the function by brothers
if (borrowBNode (p) == EMPTY) T = NULL;
else renewParent (T);
}
return OK;
}
else // not a leaf node, then
{
// Iterate
findMax (p-> ptr [temp - 1], q, num); // Returns the q will be a leaf node
p-> key [temp] = q-> key [num];
q-> key [num] = 0;
q-> keynum--;
if (q-> keynum == (m + 1) / 2 - 2)
{
// Call the function by brothers
if (borrowBNode (q) == EMPTY) T = NULL;
else renewParent (T);
}
return OK;
}
return OK;
}
return ERROR;
}
/ ***
* @name Status initBTree (BTree & t)
* @description Initialize an empty B-tree
* @return Successful return OK
* @notice
*** /
Status initBTree (BTree & t)
{
t = NULL;
return OK;
}
/ ***
* @name Status test ()
* @description Data structure for experiments done function test
* @return Successful return OK
* @notice
*** /
Status test ()
{
// Test code
int n, i;
int arr [BTREELENGTH];
BTree a;
Record d;
srand ((unsigned) time (NULL));
n = rand ()% BTREELENGTH;
// Scanf ( "% d", & n); // can be changed to your own input data
printf ( "B tree of order:% d, number of insertions is:% d \ n", m, n);
initBTree (a);
for (i = 0; i < n; i ++)
{
d.key = rand ()% MAXINT;
// Scanf ( "% d", & d.key); // can be changed to your own input data
arr [i] = d.key;
if (insertBTree (a, d) == OK)
printf ( "% d of insertion% d: \ n", i + 1, d.key);
else
printf ( "% d of% d insertion unsuccessful: \ n", i + 1, d.key);
print (a);
}
for (i = 0; i < n; i ++)
{
d.key = arr [i];
if (deleteBTreeRecord (a, d) == OK)
printf ( "% d of time to delete% d: \ n", i + 1, d.key);
else
printf ( "% d of% d times delete unsuccessful: \ n", i + 1, d.key);
print (a);
}
return OK;
}
/ ***
The main function
*** /
int main ()
{
test ();
return 0;
}
BTree |
|
|
|