b tree in c

1// Searching a key on a B-tree in C
2
3#include <stdio.h>
4#include <stdlib.h>
5
6#define MAX 3
7#define MIN 2
8
9struct btreeNode
10{
11  int val[MAX + 1], count;
12  struct btreeNode *link[MAX + 1];
13};
14
15struct btreeNode *root;
16
17struct btreeNode *createNode(int val, struct btreeNode *child)
18{
19  struct btreeNode *newNode;
20  newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));
21  newNode->val[1] = val;
22  newNode->count = 1;
23  newNode->link[0] = root;
24  newNode->link[1] = child;
25  return newNode;
26}
27
28void addValToNode(int val, int pos, struct btreeNode *node,
29          struct btreeNode *child)
30{
31  int j = node->count;
32  while (j > pos)
33  {
34    node->val[j + 1] = node->val[j];
35    node->link[j + 1] = node->link[j];
36    j--;
37  }
38  node->val[j + 1] = val;
39  node->link[j + 1] = child;
40  node->count++;
41}
42
43void splitNode(int val, int *pval, int pos, struct btreeNode *node,
44         struct btreeNode *child, struct btreeNode **newNode)
45{
46  int median, j;
47
48  if (pos > MIN)
49    median = MIN + 1;
50  else
51    median = MIN;
52
53  *newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));
54  j = median + 1;
55  while (j <= MAX)
56  {
57    (*newNode)->val[j - median] = node->val[j];
58    (*newNode)->link[j - median] = node->link[j];
59    j++;
60  }
61  node->count = median;
62  (*newNode)->count = MAX - median;
63
64  if (pos <= MIN)
65  {
66    addValToNode(val, pos, node, child);
67  }
68  else
69  {
70    addValToNode(val, pos - median, *newNode, child);
71  }
72  *pval = node->val[node->count];
73  (*newNode)->link[0] = node->link[node->count];
74  node->count--;
75}
76
77int setValueInNode(int val, int *pval,
78           struct btreeNode *node, struct btreeNode **child)
79{
80
81  int pos;
82  if (!node)
83  {
84    *pval = val;
85    *child = NULL;
86    return 1;
87  }
88
89  if (val < node->val[1])
90  {
91    pos = 0;
92  }
93  else
94  {
95    for (pos = node->count;
96       (val < node->val[pos] && pos > 1); pos--)
97      ;
98    if (val == node->val[pos])
99    {
100      printf("Duplicates not allowed\n");
101      return 0;
102    }
103  }
104  if (setValueInNode(val, pval, node->link[pos], child))
105  {
106    if (node->count < MAX)
107    {
108      addValToNode(*pval, pos, node, *child);
109    }
110    else
111    {
112      splitNode(*pval, pval, pos, node, *child, child);
113      return 1;
114    }
115  }
116  return 0;
117}
118
119void insert(int val)
120{
121  int flag, i;
122  struct btreeNode *child;
123
124  flag = setValueInNode(val, &i, root, &child);
125  if (flag)
126    root = createNode(i, child);
127}
128
129void search(int val, int *pos, struct btreeNode *myNode)
130{
131  if (!myNode)
132  {
133    return;
134  }
135
136  if (val < myNode->val[1])
137  {
138    *pos = 0;
139  }
140  else
141  {
142    for (*pos = myNode->count;
143       (val < myNode->val[*pos] && *pos > 1); (*pos)--)
144      ;
145    if (val == myNode->val[*pos])
146    {
147      printf("%d is found", val);
148      return;
149    }
150  }
151  search(val, pos, myNode->link[*pos]);
152
153  return;
154}
155
156void traversal(struct btreeNode *myNode)
157{
158  int i;
159  if (myNode)
160  {
161    for (i = 0; i < myNode->count; i++)
162    {
163      traversal(myNode->link[i]);
164      printf("%d ", myNode->val[i + 1]);
165    }
166    traversal(myNode->link[i]);
167  }
168}
169
170int main()
171{
172  int val, ch;
173
174  insert(8);
175  insert(9);
176  insert(10);
177  insert(11);
178  insert(15);
179  insert(16);
180  insert(17);
181  insert(18);
182  insert(20);
183  insert(23);
184
185  traversal(root);
186
187  printf("\n");
188  search(11, &ch, root);
189}
190