B Tree - BunksAllowed

BunksAllowed

BunksAllowed is an effort to facilitate Self Learning process through the provision of quality tutorials.

Community

Join WhatsApp Grpup using https://chat.whatsapp.com/EAcqRurEOXb52Ax7Tlmj9I

  • Home
    • demo-image
    Home Data Structures Technology B Tree

    B Tree

    Share This

    In a multi-way search tree, many nodes have a left subtree but no right subtree. Similarly, they have a right subtree but no left subtree. The insertion of the keys into such a tree also increases the height of the tree. 

    As we know access time is totally dependent on the level of the tree so we want to minimize the access time through a balanced tree only. 

    So we have a need to take all the leaf nodes at the same level and non-leaf nodes should not contain the empty subtree. For balancing the tree each node should contain m/2 keys except the root, where m represents m-way search tree. 


    So the B-Tree of order m can be defined as:

    1. Each node has at least m/2 and a maximum of m non-empty children.
    2. All leaf nodes will be at the same level.
    3. All leaf nodes can contain a maximum of m-1 keys.
    4. All non-leaf nodes can contain m-1 keys where m is the number of children for that node.
    5. Keys in the non-leaf node will divide the left and right sub-tree where the value of the left subtree keys will be less and the value of the right subtree keys will be more than the particular key.

    Insertion In B-Tree

    The insertion of a key in a B-Tree requires the first traversal in B-Tree. Through traversal, it will find the key to be inserted is already existing or not. Suppose the key does not exist then through traversal it will reach the leaf node. Now we have two cases for inserting the key.

    1. Node is not full.
    2. Node is already full.

    If the leaf node in which the key is to be inserted is not full, then the insertion is done in the node. A node is said to be full if it contains a maximum of m-1 keys, given the order of the B-Tree to be m. 


    If the node were to be full then insert the key into the existing set of keys in the node, split the node at its median into two nodes at the same level, push the median element up by one level, and rearrange the elements in each level. The following diagrams show how insertion is done in B-Tree of order 5 (i.e. m = 5).

    btree_insertion1
    btree_insertion2
    btree_insertion3

    Deletion In B-Tree

    Deletion also requires traversal in B-Tree. After reaching on particular node two cases may occur:

    1. Node is a leaf node.
    2. Node is non-leaf.

    For the first case suppose the node has more than the minimum number of keys then it can be easily detected. But suppose it has only a minimum number of keys, then first we will see the number of keys in the adjacent node will go to the parent node and the key in the parent node which is partitioning will be combined together in one node. suppose now parent has also less than the minimum number of keys then the same thing will be repeated until it will get the node which has more than the minimum number of keys.


    For the second case, the key will be deleted and its predecessor or successor key will come in its place. Suppose both nodes of the predecessor or successor key have a minimum number of keys then the nodes of the predecessor and the successor keys will be combined. Let's see how the deletion is done in B-Tree in the following figure.


    We have clearly elaborated the deletion mechanism pictorially below.

    btree_del1
    btree_del2

    The source code of insertion and deletion of B-tree is given below,

    Insertion and Deletion operations in B-Tree
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    #include <stdlib.h>
    #include <stdio.h>
    #define M 5 //order of B tree
    struct node{
    int n; /* n < M No. of keys in node will always less than order of B tree */
    int keys[M-1]; /*array of keys*/
    struct node *p[M]; /* (n+1 pointers will be in use) */
    }*root=NULL;
    enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys };
    void insert(int key);
    void display(struct node *root,int);
    void DelNode(int x);
    void search(int x);
    enum KeyStatus ins(struct node *r, int x, int* y, struct node** u);
    int searchPos(int x,int *key_arr, int n);
    enum KeyStatus del(struct node *r, int x);
    int main()
    {
    int key;
    int choice;
    printf("Creation of B tree for order %d\n",M);
    while(1)
    {
    printf("1.Insert\n");
    printf("2.Delete\n");
    printf("3.Search\n");
    printf("4.Display\n");
    printf("5.Quit\n");
    printf("Enter your choice : ");
    scanf("%d", &choice);
    switch(choice)
    {
    case 1:
    printf("Enter the key : ");
    scanf("%d", &key);
    insert(key);
    break;
    case 2:
    printf("Enter the key : ");
    scanf("%d", &key);
    DelNode(key);
    break;
    case 3:
    printf("Enter the key : ");
    scanf("%d", &key);
    search(key);
    break;
    case 4:
    printf("Btree is :\n");
    display(root,0);
    break;
    case 5:
    exit(1);
    default:
    printf("Wrong choice\n");
    break;
    }
    }
    return 0;
    }
    void insert(int key)
    {
    struct node *newnode;
    int upKey;
    enum KeyStatus value;
    value = ins(root, key, &upKey, &newnode);
    if (value == Duplicate)
    printf("Key already available\n");
    if (value == InsertIt)
    {
    struct node *uproot = root;
    root=malloc(sizeof(struct node));
    root->n = 1;
    root->keys[0] = upKey;
    root->p[0] = uproot;
    root->p[1] = newnode;
    }
    }
    enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node **newnode)
    {
    struct node *newPtr, *lastPtr;
    int pos, i, n,splitPos;
    int newKey, lastKey;
    enum KeyStatus value;
    if (ptr == NULL)
    {
    *newnode = NULL;
    *upKey = key;
    return InsertIt;
    }
    n = ptr->n;
    pos = searchPos(key, ptr->keys, n);
    if (pos < n && key == ptr->keys[pos])
    return Duplicate;
    value = ins(ptr->p[pos], key, &newKey, &newPtr);
    if (value != InsertIt)
    return value;
    /*If keys in node is less than M-1 where M is order of B tree*/
    if (n < M - 1)
    {
    pos = searchPos(newKey, ptr->keys, n);
    /*Shifting the key and pointer right for inserting the new key*/
    for (i=n; i>pos; i--)
    {
    ptr->keys[i] = ptr->keys[i-1];
    ptr->p[i+1] = ptr->p[i];
    }
    /*Key is inserted at exact location*/
    ptr->keys[pos] = newKey;
    ptr->p[pos+1] = newPtr;
    ++ptr->n; /*incrementing the number of keys in node*/
    return Success;
    }
    /*If keys in nodes are maximum and position of node to be inserted is last*/
    if (pos == M - 1)
    {
    lastKey = newKey;
    lastPtr = newPtr;
    }
    else /*If keys in node are maximum and position of node to be inserted is not last*/
    {
    lastKey = ptr->keys[M-2];
    lastPtr = ptr->p[M-1];
    for (i=M-2; i>pos; i--)
    {
    ptr->keys[i] = ptr->keys[i-1];
    ptr->p[i+1] = ptr->p[i];
    }
    ptr->keys[pos] = newKey;
    ptr->p[pos+1] = newPtr;
    }
    splitPos = (M - 1)/2;
    (*upKey) = ptr->keys[splitPos];
    (*newnode)=malloc(sizeof(struct node));/*Right node after split*/
    ptr->n = splitPos; /*No. of keys for left splitted node*/
    (*newnode)->n = M-1-splitPos;/*No. of keys for right splitted node*/
    for (i=0; i < (*newnode)->n; i++)
    {
    (*newnode)->p[i] = ptr->p[i + splitPos + 1];
    if(i < (*newnode)->n - 1)
    (*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
    else
    (*newnode)->keys[i] = lastKey;
    }
    (*newnode)->p[(*newnode)->n] = lastPtr;
    return InsertIt;
    }
    void display(struct node *ptr, int blanks)
    {
    if (ptr)
    {
    int i, level = 0;
    printf("\nlevel=%d\n", (blanks+10)/10);
    for(i = 1; i <= blanks; i++)
    printf(" ");
    for (i=0; i < ptr->n; i++)
    printf("%d ",ptr->keys[i]);
    printf("\n");
    for (i=0; i <= ptr->n; i++)
    display(ptr->p[i], blanks+10);
    }
    }
    void search(int key)
    {
    int pos, i, n;
    struct node *ptr = root;
    printf("Search path:\n");
    while (ptr)
    {
    n = ptr->n;
    for (i = 0; i < ptr->n; i++)
    printf(" %d", ptr->keys[i]);
    printf("\n");
    pos = searchPos(key, ptr->keys, n);
    if (pos < n && key == ptr->keys[pos])
    {
    printf("Key %d found in position %d of last dispalyed node\n",key,i);
    return;
    }
    ptr = ptr->p[pos];
    }
    printf("Key %d is not available\n",key);
    }
    int searchPos(int key, int *key_arr, int n)
    {
    int pos=0;
    while (pos < n && key > key_arr[pos])
    pos++;
    return pos;
    }
    void DelNode(int key)
    {
    struct node *uproot;
    enum KeyStatus value;
    value = del(root,key);
    switch (value)
    {
    case SearchFailure:
    printf("Key %d is not available\n",key);
    break;
    case LessKeys:
    uproot = root;
    root = root->p[0];
    free(uproot);
    break;
    }
    }
    enum KeyStatus del(struct node *ptr, int key)
    {
    int pos, i, pivot, n ,min;
    int *key_arr;
    enum KeyStatus value;
    struct node **p,*lptr,*rptr;
    if (ptr == NULL)
    return SearchFailure;
    /*Assigns values of node*/
    n=ptr->n;
    key_arr = ptr->keys;
    p = ptr->p;
    min = (M - 1)/2;/*Minimum number of keys*/
    pos = searchPos(key, key_arr, n);
    if (p[0] == NULL)
    {
    if (pos == n || key < key_arr[pos])
    return SearchFailure;
    /*Shift keys and pointers left*/
    for (i=pos+1; i < n; i++)
    {
    key_arr[i-1] = key_arr[i];
    p[i] = p[i+1];
    }
    return --ptr->n >= (ptr==root ? 1 : min) ? Success : LessKeys;
    }
    if (pos < n && key == key_arr[pos])
    {
    struct node *qp = p[pos], *qp1;
    int nkey;
    while(1)
    {
    nkey = qp->n;
    qp1 = qp->p[nkey];
    if (qp1 == NULL)
    break;
    qp = qp1;
    }
    key_arr[pos] = qp->keys[nkey-1];
    qp->keys[nkey - 1] = key;
    }
    value = del(p[pos], key);
    if (value != LessKeys)
    return value;
    if (pos > 0 && p[pos-1]->n > min)
    {
    pivot = pos - 1; /*pivot for left and right node*/
    lptr = p[pivot];
    rptr = p[pos];
    /*Assigns values for right node*/
    rptr->p[rptr->n + 1] = rptr->p[rptr->n];
    for (i=rptr->n; i>0; i--)
    {
    rptr->keys[i] = rptr->keys[i-1];
    rptr->p[i] = rptr->p[i-1];
    }
    rptr->n++;
    rptr->keys[0] = key_arr[pivot];
    rptr->p[0] = lptr->p[lptr->n];
    key_arr[pivot] = lptr->keys[--lptr->n];
    return Success;
    }
    if (pos < n && p[pos+1]->n > min)
    {
    pivot = pos; /*pivot for left and right node*/
    lptr = p[pivot];
    rptr = p[pivot+1];
    /*Assigns values for left node*/
    lptr->keys[lptr->n] = key_arr[pivot];
    lptr->p[lptr->n + 1] = rptr->p[0];
    key_arr[pivot] = rptr->keys[0];
    lptr->n++;
    rptr->n--;
    for (i=0; i < rptr->n; i++)
    {
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


    Happy Exploring!

    Tags
    Share This
    bunksAllowed

    About BunksAllowed

    By on
    Labels: ,
    Subscribe to: Post Comments (Atom)
    Comment Using!!

    No comments:

    Post a Comment

    Note: Only a member of this blog may post a comment.

    About BunksAllowed