#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#define M 2
#define MM 4
#define NIL (-1L)
struct node { int cnt, key[MM]; long ptr[MM+1]; };
typedef struct node NODE;
NODE rootnode;
long start[2], root = NIL, freelist = NIL;
FILE *fptree;
/************ declaración de funciones ***************/
void search (int x);
int binsearch (int x, int *a, int n);
void found (long t, int i);
void notfound (int x);
void insert (int x);
int ins (int x, long t, int *y, long *u);
long getnode ();
void freenode (long t);
void readnode (long t, NODE *pnode);
void writenode (long t, NODE *pnode);
void rdstart ();
void wrstart ();
void error (char *str);
void borrar (int x);
int del (int x, long t);
/*****************************************************/
int main ()
{ int x;
char ch, inpfilnam[30], treefilnam[30];
FILE *fpinp;
printf ("Enter name of (binary) file for the B-tree; ");
scanf ("%s", treefilnam);
fptree = fopen (treefilnam, "rb+"); /* rb+ and wb+ */
if (fptree == NULL) /* are system */
{ fptree = fopen (treefilnam, "wb+"); /* dependent */
wrstart ();
} else rdstart ();
printf ("Enter name of (ASCII) input file (or NONE) : ");
scanf ("%s", inpfilnam);
fpinp = fopen (inpfilnam, "r");
if (fpinp != NULL)
{ while (fscanf (fpinp, "%d", &x) > 0) insert (x);
fclose (fpinp);
}
while (1)
{ printf (
"\nDelete (D), Insert (I), Search (S) or Quit (Q): ");
do
{ ch = getchar (); ch = toupper (ch);
} while (ch != 'D' && ch != 'I' &&
ch != 'S' && ch != 'Q');
if (ch == 'Q') break;
printf ("Enter an integer: "); scanf ("%d", &x);
switch (ch)
{ case 'D': borrar (x); break;
case 'I': insert (x); break;
case 'S': search (x); break;
}
}
wrstart ();
fclose (fptree);
return EXIT_SUCCESS;
}
void search (int x)
{ int i, j, *k, n;
NODE nod;
long t = root;
printf ("Trace:\n");
while (t != NIL)
{ readnode (t, &nod);
k = nod.key; n = nod.cnt;
for (j = 0; j < n; j++) printf ("%d", k[j]);
printf ("\n");
i = binsearch (x, k, n);
if (i < n && x == k[i]) { found (t, i); return; }
t = nod.ptr[i];
}
notfound (x);
}
int binsearch (int x, int *a, int n)
/* Search array a[0], a[1], ..., a[n-1] for x */
/* Returned value: 0 if x <= a[0], n if x > a[n-1],*/
/* or r, where a[r-1] < x <= a[r] */
{ int i, left, right;
if (x <= a[0]) return 0;
if (x > a[n-1]) return n;
left = 0; right = n-1;
while (right - left > 1)
{ i = right + left >> 1;
if (x <= a[i]) right = i; else left = i;
}
return right;
}
void found (long t, int i)
{ NODE nod;
printf ("Found in position %d ", i);
printf ("of node with contents: ");
readnode (t, &nod);
for (i = 0; i < nod.cnt; i++) printf (" %d", nod.key[i]);
printf ("\n");
}
void notfound (int x)
{ printf ("Item %d not found\n", x);
}
void insert (int x)
/* Driver function for node insertion, called only in the
main program. Most of the work is delegated to 'ins'
*/
{ long tnew, u, getnode ();
int xnew, code;
code = ins (x, root, &xnew, &tnew);
if (code == 2) printf ("Duplicate key %d ignored\n", x);
if (code) return;
u = getnode ();
rootnode.cnt = 1; rootnode.key[0] = xnew;
rootnode.ptr[0] = root; rootnode.ptr[1] = tnew;
root = u;
writenode (u, &rootnode);
}
int ins (int x, long t, int *y, long *u)
/* Insert x in B-tree with root t. If not completely
successful, the integer *y and the pointer *u
remain to be inserted.
Returned value:
0 if insertion not completely successful.
1 if insertion successful.
2 if x is already present in B-tree.
*/
{ long tnew, getnode (), p_final, *p;
int i, j, xnew, k_final, *n, *k, code;
NODE nod, newnod;
/* Examine whether t is a pointer field in a leaf:
*/
if (t == NIL) { *u = NIL; *y = x; return 0; }
readnode (t, &nod);
n = &nod.cnt; k = nod.key; p = nod.ptr;
/* Select pointer p[i] and try to insert x in
the subtree of which p[i] is the root;
*/
i = binsearch (x, k, *n);
if (i < *n && x == k[i]) return 2; /* Duplicate key */
code = ins (x, p[i], &xnew, &tnew);
if (code) return code;
/* Insertion in subtree did not completely succed;
try to insert xnew and tnew in the current node:
*/
if (*n < MM)
{ i = binsearch (xnew, k, *n);
for (j = *n; j > i; j--)
{ k[j] = k[j-1]; p[j+1] = p[j];
}
k[i] = xnew; p[i+1] = tnew; ++*n;
writenode (t, &nod); return 1;
}
/* The current node was already full, so split it. Pass
item k[M] in the middle of the augmented sequence
back through parameter y, so that it can move
upward in the tree. Also, pass a pointer to the newly
created node back through u. Return 0, to report
that insertion was not completed:
*/
if (i == MM) { k_final = xnew; p_final = tnew; } else
{ k_final = k[MM-1]; p_final = p[MM];
for (j = MM-1; j > i; j--)
{ k[j] = k[j-1]; p[j+1] = p[j];
}
k[i] = xnew; p[i+1] = tnew;
}
*y = k[M]; *n = M;
*u = getnode (); newnod.cnt = M;
for (j = 0; j < M-1; j++)
{ newnod.key[j] = k[j+M+1]; newnod.ptr[j] = p[j+M+1];
}
newnod.ptr[M-1] = p[MM]; newnod.key[M-1] = k_final;
newnod.ptr[M] = p_final;
writenode (t, &nod); writenode (*u, &newnod); return 0;
}
long getnode ()
{ long t;
NODE nod;
if (freelist == NIL)
{ if (fseek (fptree, 0L, 2)) error ("fseek in getnode");
t = ftell (fptree);
writenode (t, &nod); /* Reserve space on disk */
} else
{ t = freelist;
readnode (t, &nod); /* To update freelist */
freelist = nod.ptr[0];
}
return t;
}
void freenode (long t)
{ NODE nod;
readnode (t, &nod);
nod.ptr[0] = freelist;
freelist = t;
writenode (t, &nod);
}
void readnode (long t, NODE *pnode)
{ if (t == root) { *pnode = rootnode; return; }
if (fseek (fptree, t, 0)) error ("fseek in readnode");
if (fread (pnode, sizeof (NODE), 1, fptree) == 0)
error ("fread in readnode");
}
void writenode (long t, NODE *pnode)
{ if (t == root) rootnode = *pnode;
if (fseek (fptree, t, 0)) error ("fseek in writenode");
if (fwrite (pnode, sizeof (NODE), 1, fptree) == 0)
error ("fwrite in writenode");
}
void rdstart ()
{ if (fseek (fptree, 0L, 0)) error ("fseek in rdstart");
if (fread (start, sizeof (long), 2, fptree) == 0)
error ("fread in rdstart");
readnode (start[0], &rootnode);
root = start[0]; freelist = start[1];
}
void wrstart ()
{ start[0] = root; start[1] = freelist;
if (fseek (fptree, 0L, 0)) error ("fseek in wrstart");
if (fwrite (start, sizeof (long), 2, fptree) == 0)
error ("fwrite in wrstart");
if (root != NIL) writenode (root, &rootnode);
}
void error (char *str)
{ printf ("\nError: %s\n", str);
exit (EXIT_FAILURE);
}
void borrar (int x)
/* Driver function for node deletion called only in the
main program. Most of the work is delegated to "del".
*/
{ int code;
long newroot;
code = del (x, root);
if (code == 2) printf ("%d not found\n", x);
if (code) return;
/* 0 = underflow; 1 = success; 2 = key not found */
/* If underflow, decrease the height of the three: */
newroot = rootnode.ptr[0]; freenode (root);
if (newroot != NIL) readnode (newroot, &rootnode);
root = newroot;
}
int del (int x, long t)
/* Delete item x in B-tree with root t.
Returned value:
0 = underflow, 1 = success, 2 = not found
*/
{ int i, j, *k, *n, *item, code,
*nleft, *nright, *lkey, *rkey, borrowleft, nq, *addr;
long *p, left, right, *lptr, *rptr, q, q1;
NODE nod, nod1, nod2;
if (t == NIL) return 2;
readnode (t, &nod);
n = &nod.cnt; k = nod.key; p = nod.ptr;
i = binsearch (x, k, *n);
if (p[0] == NIL) /* *t is a leaf */
{ if (i == *n || x < k[i]) return 2;
/* x is now equal to k[i], located in a leaf: */
for (j = i+1; j < *n; j++)
{ k[j-1] = k[j]; p[j] = p[j+1];
}
--*n;
writenode (t, &nod);
return *n >= (t == root ? 1 : M);
}
/* *t is an interior node (not a leaf): */
item = k+i; left = p[i]; readnode (left, &nod1);
nleft = &nod1.cnt;
if (i < *n && x == *item)
{ /* x found in interior node. */
/* Go to left child *p[i] and then follow a path */
/* all the way to a leaf, using rightmost branches */
q = p[i]; readnode (q, &nod1); nq = nod1.cnt;
while (q1 = nod1.ptr[nq], q1 != NIL)
{ q = q1; readnode (q, &nod1); nq = nod1.cnt;
}
/* Exchange k[i] with the rightmost item in
that leaf:
*/
addr = nod1.key + nq - 1;
*item = *addr; *addr = x;
writenode (t, &nod); writenode (q, &nod1);
}
/* Delete x in subtree with root p[i] */
code = del (x, left);
if (code) return code;
/* Underflow: borrow, and, if necessary, merge */
borrowleft = i == *n;
if (borrowleft) /* p[i] is rightmost pointer in *p */
{ item = k+i-1; left = p[i-1]; right = p[i];
readnode (left, &nod1);
nleft = &nod1.cnt;
} else right = p[i+1];
readnode (left, &nod1);
readnode (right, &nod2);
nright = &nod2.cnt;
lkey = nod1.key; rkey = nod2.key;
lptr = nod1.ptr; rptr = nod2.ptr;
if (borrowleft) /* This is an exception */
{ rptr[*nright + 1] = rptr[*nright];
for (j = *nright; j > 0; j--)
{ rkey[j] = rkey[j-1];
rptr[j] = rptr[j-1];
}
++*nright;
rkey[0] = *item; rptr[0] = lptr[*nleft];
*item = lkey[*nleft - 1];
if (--*nleft >= M)
{ writenode (t, &nod); writenode (left, &nod1);
writenode (right, &nod2);
return 1;
}
} else
if (*nright > M) /* Borrow from right sibling: */
{ lkey[M-1] = *item; lptr[M] = rptr[0]; *item = rkey[0];
++*nleft; --*nright;
for (j = 0; j < *nright; j++)
{ rptr[j] = rptr[j+1]; rkey[j] = rkey[j+1];
}
rptr[*nright] = rptr[*nright + 1];
writenode (t, &nod); writenode (left, &nod1);
writenode (right, &nod2);
return 1;
}
/* Merge */
lkey[M-1] = *item; lptr[M] = rptr[0];
for (j = 0; j < M; j++)
{ lkey[M+j] = rkey[j]; lptr[M+j+1] = rptr[j+1];
}
*nleft = MM;
freenode (right);
for (j = i+1; j < *n; j++) { k[j-1] = k[j]; p[j] = p[j+1]; }
--*n;
writenode (t, &nod);
writenode (left, &nod1);
return *n <= (t == root ? 1 : M);
}