home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume1 / 8707 / 39 / btree.c next >
Encoding:
C/C++ Source or Header  |  1990-07-13  |  14.2 KB  |  829 lines
  1. /***
  2.  
  3. * module name:
  4.     btree.c
  5. * function:
  6.     Provide a library of routines for creating and manipulating
  7.     B-Trees.  The "order" of the B-Tree is controlled by a manifest
  8.     constant.
  9.  
  10.     This module runs stand-alone with a dummy main program
  11.     if the symbol STAND_ALONE is defined.
  12. * interface routines:
  13.     BTREE
  14.     Insert(dtm, tree)    Insert DATUM dtm into B-tree "tree",
  15.                 returning a reference to the updated
  16.                 tree.
  17.     BTREE
  18.     Delete(key, tree)    Remove the entry associated with "key"
  19.                 from the B-Tree.  Returns a reference
  20.                 to the updated tree.
  21.     
  22.     DATUM *
  23.     Search(key, tree)    Look for key "key" in B-tree "tree".
  24.                 Return a reference to the matching
  25.                 DATUM if found, else NULL.
  26.  
  27.     Apply(t, func)        Applies function "func" to every cell
  28.                 in the B-Tree -- uses an inorder
  29.                 traversal.
  30. * libraries used:
  31.     standard
  32. * compile time parameters:
  33.     cc -O -c btree.c
  34. * history:
  35.     Richard Hellier, University of Kent at Canterbury,
  36.     working from "Algorithms+Data Structures = Programs"
  37.     by N.Wirth -- also, "Data Structures and Program Design" by B.Kruse
  38.     Pub. Prentice-Hall.
  39.  
  40.     Modified for use in dynamic memory allocation leak trace tool
  41.     by Mike Schwartz, 3-20-87.  We call mmalloc and ffree instead of
  42.     malloc and free here, since malloc and free call this btree package
  43.     in the dynamic memory allocation leak detection package.
  44.  
  45. ***/
  46.  
  47. #include "btree.h"
  48.  
  49. DATUM    NullDatum = {
  50.     (char *) NULL,
  51. };
  52.  
  53. static BTREE        NewNode;
  54.  
  55. /*
  56. **  ERROR -- Print an error message
  57. **
  58. **    Write the error text to the
  59. **    standard error stream.
  60. **
  61. **    Parameters:
  62. **        fmt       --  Printf-style format string
  63. **        arg[1-3]  --  Arguments as needed.
  64. **
  65. **    Returns:
  66. **        None.
  67. **
  68. */
  69.  
  70. /* ARGSUSED */
  71.  
  72. Error(fmt, arg1, arg2, arg3)
  73. char    *fmt;{
  74.     fprintf(stderr, fmt, arg1, arg2, arg3);
  75. }
  76.  
  77. /*
  78. **  KEYCMP -- Compare two key values
  79. **
  80. **    Like "strcmp" but use key
  81. **    values rather than strings.
  82. **
  83. **    Parameters:
  84. **        key1  --  First key,
  85. **        key2  --  Second key.
  86. **
  87. **    Returns:
  88. **        -1 if key1 < key2;
  89. **        0  if key1 = key2;
  90. **        1  if key1 > key2;
  91. **
  92. */
  93.  
  94. KeyCmp(key1, key2)
  95. KEY    key1,
  96.     key2;{
  97.  
  98.     return key1 < key2 ? -1 : key1 == key2 ? 0 : 1;
  99. }
  100.  
  101. /*
  102. **  SHOWDATUM -- Display a datum
  103. **
  104. **    Atomic routine used to display
  105. **    the contents of a datum.
  106. **
  107. **    Parameters:
  108. **        datum  --  Datum to print.
  109. **
  110. **    Returns:
  111. **        None.
  112. **
  113. */
  114.  
  115. ShowDatum(dtm)
  116. DATUM    dtm;{
  117.     printf("\tkey x%x: callnum %d, size %d\n", dtm.key, dtm.inf.MalCallNum,
  118.         dtm.inf.MalSize);
  119. }
  120.  
  121. /*
  122. **  MKNODE -- Make a new B-tree node
  123. **
  124. **    Allocate storage for a new B-tree node
  125. **    and copy in some pointers.
  126. **
  127. **    Parameters:
  128. **        k1  --  First key value,
  129. **        p0  --  First ptr,
  130. **        p1  --  Second ptr.
  131. **
  132. **    Returns:
  133. **        Reference to the new node.
  134. **
  135. */
  136.  
  137. BTREE
  138. MkNode(dtm, p0, p1)
  139. DATUM    dtm;
  140. BTREE    p0,
  141.     p1;{
  142.     char    *mmalloc();
  143.     BTREE    t;
  144.  
  145.     t = (BTREE) mmalloc(sizeof(NODE));
  146.  
  147.     t -> t_ptr [0] = p0;
  148.     t -> t_ptr [1] = p1;
  149.     t -> t_dat [0] = dtm;
  150.     t -> t_active  = 1;
  151.  
  152.     return t;
  153. }
  154. /*
  155. **  DISPOSE -- Dispose of a tree node
  156. **
  157. **    Return the storage occupied by the
  158. **    tree node to the pool.
  159. **
  160. **    Parameters:
  161. **        t  --  Ptr to the tree node.
  162. **
  163. **    Returns:
  164. **        None.
  165. **
  166. */
  167.  
  168. Dispose(t)
  169. BTREE    t;{
  170.     ffree((char *) t);
  171. }
  172.  
  173. /*
  174. **  INSINNODE -- Add a key to a node
  175. **
  176. **    Add a key value into a
  177. **    B-tree node.  Splitting of
  178. **    nodes is handled elsewhere.
  179. **
  180. **    Parameters:
  181. **        t   --  Ptr to the node,
  182. **        key --  Key value to enter,
  183. **        ptr --  Link to subordinate node.
  184. **
  185. **    Returns:
  186. **        None.
  187. **
  188. */
  189.  
  190. InsInNode(t, d, ptr)
  191. BTREE    t,
  192.     ptr;
  193. DATUM    d;{
  194.     int    i;
  195.  
  196.     for ( i = t -> t_active; i > 0 && KeyCmp(d . key, t -> t_dat [i-1] . key) < 0; i--) {
  197.         t -> t_dat [i]     = t -> t_dat [i - 1];
  198.         t -> t_ptr [i + 1] = t -> t_ptr [i];
  199.     }
  200.  
  201.     t -> t_active++;
  202.     t -> t_dat [i]   = d;
  203.     t -> t_ptr [i+1] = ptr;
  204. }
  205.  
  206. /*
  207. **  INTERNALINSERT -- Key insert routine proper
  208. **
  209. **    The business end of the key insertion
  210. **    routine.
  211. **
  212. **    Parameters:
  213. **        key  --  Key to insert,
  214. **        t    --  Tree to use.
  215. **
  216. **    Returns:
  217. **        Value of the key inserted.
  218. **
  219. */
  220.  
  221. DATUM
  222. InternalInsert(dtm, t)
  223. DATUM    dtm;
  224. BTREE    t;{
  225.     int    i,
  226.         j;
  227.     DATUM    ins;
  228.     BTREE    tmp;
  229.  
  230.     if (t == NULL) {
  231.         NewNode = NULL;
  232.         return dtm;
  233.     } else {
  234.         for (i = 0; i < t -> t_active && KeyCmp(t -> t_dat [i] . key, dtm . key) < 0; ++i)
  235.             ;        /* NULL BODY */
  236.         if (i < t -> t_active && KeyCmp(dtm . key, t -> t_dat [i] . key) == 0)
  237.             fprintf(stderr, "Already had it!\n");
  238.         else {
  239.             ins = InternalInsert(dtm, t -> t_ptr [i]);
  240.  
  241.             if (KeyCmp(ins . key, NullDatum . key) != 0)
  242.                 if (t -> t_active < 2 * M)
  243.                     InsInNode(t, ins, NewNode);
  244.                 else {
  245.                     if (i <= M) {
  246.                         tmp = MkNode(t -> t_dat [2 * M - 1], (BTREE) NULL, t -> t_ptr [2 * M]);
  247.                         t -> t_active--;
  248.                         InsInNode(t, ins, NewNode);
  249.                     } else
  250.                         tmp = MkNode(ins, (BTREE) NULL, NewNode);
  251.                     /*
  252.                      *    Move keys and pointers ...
  253.                      */
  254.  
  255.                     for (j = M + 2; j <= 2 * M; ++j)
  256.                         InsInNode(tmp, t -> t_dat [j-1], t -> t_ptr [j]);
  257.  
  258.                     t -> t_active = M;
  259.                     tmp -> t_ptr [0] = t -> t_ptr [M+1];
  260.                     NewNode = tmp;
  261.  
  262.                     return t -> t_dat [M];
  263.                 }
  264.         }
  265.         return NullDatum;
  266.     }
  267. }
  268. /*
  269. **  INSERT -- Put a key into the B-tree
  270. **
  271. **    Enter the given key into the
  272. **    B-tree.
  273. **
  274. **    Parameters:
  275. **        key  --  Key value to enter.
  276. **
  277. **    Returns:
  278. **        Reference to the new B-tree.
  279. **
  280. */
  281.  
  282. BTREE
  283. Insert(dtm, t)
  284. DATUM    dtm;
  285. BTREE    t;{
  286.     DATUM    ins;
  287.  
  288.     ins = InternalInsert(dtm, t);
  289.  
  290.     /*
  291.      *    Did the root grow ?
  292.      */
  293.  
  294.     return KeyCmp(ins . key, NullDatum . key) != 0 ? MkNode(ins, t, NewNode) : t;
  295. }
  296. /*
  297. **  DELETE -- Remove a key from a B-tree
  298. **
  299. **    Remove the data associated with a
  300. **    given key from a B-tree.
  301. **
  302. **    Parameters:
  303. **        key  --  Key to use,
  304. **        t    --  B-tree to update.
  305. **
  306. **    Returns:
  307. **        Reference to the updated B-tree.
  308. **
  309. **    Notes:
  310. **        Real work is done by RealDelete() q.v.
  311. **
  312. */
  313.  
  314. static int    hadit = FALSE;
  315.  
  316. BTREE
  317. Delete(key, t)
  318. KEY    key;
  319. BTREE    t;{
  320.     BTREE    savet;
  321.  
  322.     RealDelete(key, t);
  323.  
  324.     if (!hadit) {
  325.         Error("No such key\n");
  326.         return NULL;
  327.     } else if (t -> t_active == 0) {    /* Root is now empty */
  328.         savet = t -> t_ptr [0];
  329.         Dispose(t);
  330.         return savet;
  331.     } else
  332.         return t;
  333. }
  334.  
  335. /*
  336. **  SEARCHNODE -- Find a key in a node
  337. **
  338. **    Look for a key in a single B-tree
  339. **    node.
  340. **
  341. **    Parameters:
  342. **        key  --  Key to look for,
  343. **        t    --  Ptr to B-tree node.
  344. **
  345. **    Returns:
  346. **        Index of matching key.
  347. **
  348. */
  349.  
  350. int
  351. SearchNode(key, t)
  352. KEY    key;
  353. BTREE    t;{
  354.     int    i;
  355.  
  356.     if (KeyCmp(key, t -> t_dat [0] . key) < 0) {
  357.         hadit = FALSE;
  358.         return 0;
  359.     } else {
  360.         for (i = t -> t_active; KeyCmp(key, t -> t_dat [i-1] . key) < 0 && i > 1; --i)
  361.             ;        /* NULL BODY */
  362.         hadit = (KeyCmp(key, t -> t_dat [i-1] . key) == 0);
  363.  
  364.         return i;
  365.     }
  366. }
  367. /*
  368. **  REALDELETE -- Remove a key from a tree
  369. **
  370. **    The business end of the Delete() function.
  371. **
  372. **    Parameters:
  373. **        key  --  Key to use,
  374. **        t    --  Tree to update.
  375. **
  376. **    Returns:
  377. **        None.
  378. **
  379. */
  380.  
  381. RealDelete(key, t)
  382. KEY    key;
  383. BTREE    t;{
  384.     int    k;
  385.  
  386.     if (t == NULL)
  387.         hadit = FALSE;
  388.     else {
  389.         k = SearchNode(key, t);
  390.  
  391.         if (hadit) {
  392.             if (t -> t_ptr [k-1] == NULL)        /* A leaf */
  393.                 Remove(t, k);
  394.             else {
  395.                 Succ(t, k);
  396.                 RealDelete(t -> t_dat [k-1] . key, t -> t_ptr [k]);
  397.                 if (!hadit)
  398.                     Error("Hmm ???");
  399.             }
  400.         } else {
  401.             RealDelete(key, t -> t_ptr [k]);
  402.  
  403.             if (t -> t_ptr [k] != NULL && t -> t_ptr [k] -> t_active < M)
  404.                 Restore(t, k);
  405.         }
  406.     }
  407. }
  408.  
  409. /*
  410. **  REMOVE -- Remove a single datum
  411. **
  412. **    Remove a datum from a B-tree node
  413. **    by shuffling down the pointers and
  414. **    data above it.
  415. **
  416. **    Parameters:
  417. **        t   --  Ptr to the B-tree node,
  418. **        pos --  Index of the key to be removed.
  419. **
  420. **    Returns:
  421. **        None.
  422. **
  423. */
  424.  
  425. Remove(t, pos)
  426. BTREE    t;
  427. int    pos;{
  428.     int    i;
  429.  
  430.     for (i = pos + 1; i <= t -> t_active; ++i) {
  431.         t -> t_dat [i-2] = t -> t_dat [i-1];
  432.         t -> t_ptr [i-1] = t -> t_ptr [i];
  433.     }
  434.     t -> t_active--;
  435. }
  436.  
  437. /*
  438. **  SUCC -- Replace a key by its successor
  439. **
  440. **    Using the natural ordering, replace
  441. **    a key with its successor.
  442. **
  443. **    Parameters:
  444. **        t   --  Ptr to a B-tree node,
  445. **        pos --  Index of the key to be succ'ed.
  446. **
  447. **    Returns:
  448. **        None.
  449. **
  450. **    Notes:
  451. **        This routine relies on the fact
  452. **        that if the key to be deleted is
  453. **        not in a leaf node, then its
  454. **        immediate successor will be.
  455. */
  456.  
  457. Succ(t, pos)
  458. BTREE    t;
  459. int    pos;{
  460.     BTREE    tsucc;
  461.  
  462.     /*
  463.      *    Using the branch *above* the key
  464.      *    chain down to leftmost node below
  465.      *    it.
  466.      */
  467.  
  468.     for (tsucc = t -> t_ptr [pos]; tsucc -> t_ptr [0] != NULL; tsucc = tsucc -> t_ptr [0])
  469.         ;        /* NULL BODY */
  470.  
  471.     t -> t_dat [pos-1] = tsucc -> t_dat [0];
  472. }
  473. /*
  474. **  RESTORE -- Restore balance to a B-tree
  475. **
  476. **    After removing an item from a B-tree
  477. **    we must restore the balance.
  478. **
  479. **    Parameters:
  480. **        t   --  Ptr to the B-tree node,
  481. **        pos --  Index of the out-of-balance point.
  482. **
  483. **    Returns:
  484. **        None.
  485. **
  486. */
  487.  
  488. Restore(t, pos)
  489. BTREE    t;
  490. int    pos;{
  491.     if (pos > 0) {
  492.         if (t -> t_ptr [pos - 1] -> t_active > M)
  493.             MoveRight(t, pos);
  494.         else
  495.             Combine(t, pos);
  496.     } else {
  497.         if (t -> t_ptr [1] -> t_active > M)
  498.             MoveLeft(t, 1);
  499.         else
  500.             Combine(t, 1);
  501.     }
  502. }
  503.  
  504. /*
  505. **  MOVERIGHT -- Shuffle keys up
  506. **
  507. **    Make room for a key in a B-tree
  508. **    node.
  509. **
  510. **    Parameters:
  511. **        t   --  Ptr to the B-tree node,
  512. **        pos --  Index of the first key
  513. **            to be moved.
  514. **
  515. **    Returns:
  516. **        None.
  517. **
  518. */
  519.  
  520. MoveRight(t, pos)
  521. BTREE    t;
  522. int    pos;{
  523.     int    i;
  524.     BTREE    tpos;
  525.  
  526.     tpos = t -> t_ptr [pos];
  527.  
  528.     for (i = tpos -> t_active; i >= 1; i--) {
  529.         tpos -> t_dat [i]   = tpos -> t_dat [i-1];
  530.         tpos -> t_ptr [i+1] = tpos -> t_ptr [i];
  531.     }
  532.  
  533.     tpos -> t_ptr [1] = tpos -> t_ptr [0];
  534.     tpos -> t_active++;
  535.     tpos -> t_dat [0] = t -> t_dat [pos-1];
  536.  
  537.     tpos = t -> t_ptr [pos-1];
  538.  
  539.     t -> t_dat [pos-1]            = tpos -> t_dat [tpos -> t_active-1];
  540.     t -> t_ptr [pos] -> t_ptr [0] = tpos -> t_ptr [tpos -> t_active];
  541.     tpos -> t_active--;
  542. }
  543. /*
  544. **  MOVELEFT -- Shuffle keys down
  545. **
  546. **    Shuffle keys down after a removal
  547. **    from a B-tree node.
  548. **
  549. **    Parameters:
  550. **        t   --  Ptr to the B-tree node,
  551. **        pos --  Index of the first key
  552. **            to be moved.
  553. **
  554. **    Returns:
  555. **        None.
  556. **
  557. */
  558.  
  559. MoveLeft(t, pos)
  560. BTREE    t;
  561. int    pos;{
  562.     int    i;
  563.     BTREE    tpos;
  564.  
  565.     tpos = t -> t_ptr [pos-1];
  566.  
  567.     tpos -> t_active++;
  568.     tpos -> t_dat [tpos -> t_active-1] = t -> t_dat [pos-1];
  569.     tpos -> t_ptr [tpos -> t_active]   = t -> t_ptr [pos] -> t_ptr [0];
  570.  
  571.     tpos = t -> t_ptr [pos];
  572.  
  573.     t -> t_dat [pos-1]  = tpos -> t_dat [0];
  574.     tpos -> t_ptr [0]   = tpos -> t_ptr [1];
  575.     tpos -> t_active--;
  576.  
  577.     for (i = 1; i <= tpos -> t_active; ++i) {
  578.         tpos -> t_dat [i-1] = tpos -> t_dat [i];
  579.         tpos -> t_ptr [i]   = tpos -> t_ptr [i+1];
  580.     }
  581. }
  582. /*
  583. **  COMBINE -- Combine two nodes.
  584. **
  585. **    Coalesce two nodes of a
  586. **    B-tree when they have too few nodes.
  587. **
  588. **    Parameters:
  589. **        t   --  Ptr to B-tree node,
  590. **        pos --  Index of the split point.
  591. **
  592. **    Returns:
  593. **        None.
  594. **
  595. */
  596.  
  597. Combine(t, k)
  598. BTREE    t;
  599. int    k;{
  600.     int    i;
  601.     BTREE    p,
  602.         q;
  603.  
  604.     p = t -> t_ptr [k-1];
  605.     q = t -> t_ptr [k];
  606.  
  607.     p -> t_active++;
  608.     p -> t_dat [p -> t_active-1] = t -> t_dat [k-1];
  609.     p -> t_ptr [p -> t_active]   = q -> t_ptr [0];
  610.  
  611.     for (i = 1; i <= q -> t_active; ++i) {
  612.         p -> t_active++;
  613.         p -> t_dat [p -> t_active-1] = q -> t_dat [i-1];
  614.         p -> t_ptr [p -> t_active]   = q -> t_ptr [i];
  615.     }
  616.  
  617.     for (i = k; i <= t -> t_active - 1; ++i) {
  618.         t -> t_dat [i-1] = t -> t_dat [i];
  619.         t -> t_ptr [i]   = t -> t_ptr [i+1];
  620.     }
  621.     t -> t_active--;
  622.  
  623.     Dispose(q);
  624. }
  625.  
  626. /*
  627. **  SEARCH -- Fetch a key from a tree
  628. **
  629. **    Look for a key in a tree.
  630. **
  631. **    Parameters:
  632. **        key  --  Key value to look for,
  633. **        t    --  Tree to look in.
  634. **
  635. **    Returns:
  636. **        None.
  637. **
  638. */
  639.  
  640. DATUM *
  641. Search(key, t)
  642. KEY    key;
  643. BTREE    t;{
  644.     int    i;
  645.  
  646.     while (t != NULL) {
  647.         for (i = 0; i < t -> t_active && KeyCmp(t -> t_dat [i] . key, key) < 0; ++i)
  648.             ;        /* NULL BODY */
  649.  
  650.         if (i < t -> t_active && KeyCmp(key, t -> t_dat [i] . key) == 0) {
  651.             /* FOUND IT */
  652.             return &t -> t_dat [i];
  653.         }
  654.         t = t -> t_ptr [i];
  655.     }
  656.     return NULL;
  657. }
  658. /*
  659. **  SHOWTREE -- Display a tree
  660. **
  661. **    Print the contents of
  662. **    a tree, showing the level
  663. **    of each node.
  664. **
  665. **    Parameters:
  666. **        t     --  Tree to print,
  667. **        level --  Depth in tree.
  668. **
  669. **    Returns:
  670. **        None.
  671. **
  672. */
  673.  
  674. ShowTree(t, level)
  675. BTREE    t;
  676. int    level;{
  677.     int    i;
  678.  
  679.     if (t != NULL) {
  680.         for (i = 0; i < level; ++i)
  681.             putchar(' ');
  682.         for (i = 0; i < t -> t_active; ++i)
  683.             ShowDatum(t -> t_dat [i]);
  684.         putchar('\n');
  685.         for (i = 0; i <= t -> t_active; ++i)
  686.             ShowTree(t -> t_ptr [i], 1 + level);
  687.     }
  688. }
  689.  
  690. /*
  691. **  APPLY -- Apply a function to a b-tree
  692. **
  693. **    Traverse a B-tree, applying the function
  694. **    to each key we find.
  695. **
  696. **    Parameters:
  697. **        t    --  The tree to display,
  698. **        func --  The function to apply.
  699. **
  700. **    Returns:
  701. **        None.
  702. **
  703. */
  704.  
  705. Apply(t, func)
  706. BTREE    t;
  707. int    (*func)();{
  708.     int    i;
  709.  
  710.     if (t != NULL) {
  711.         for (i = 0; i < t -> t_active; ++i) {
  712.             Apply(t -> t_ptr [i], func);
  713.             (*func) (t -> t_dat [i]);
  714.         }
  715.         Apply(t -> t_ptr [t -> t_active], func);
  716.     }
  717. }
  718. #ifdef STAND_ALONE
  719. main(){
  720.     BTREE    t,
  721.         oldt;
  722.     DATUM    d,
  723.         *dp;
  724.     KEY    k;
  725.     char    buf [BUFSIZ];
  726.  
  727.     t = NULL;
  728.  
  729.     printf("Command: "); fflush(stdout);
  730.     while (fgets(buf, sizeof buf, stdin) != NULL) {
  731.         buf [strlen(buf) - 1] = '\0';
  732.  
  733.         /*
  734.          *    Get the command
  735.          */
  736.  
  737.         switch (buf [0]) {
  738.             default:        /* Error case */
  739.                 fprintf(stderr, "I, D, L, P or S please!\n");
  740.                 break;
  741.  
  742.             case '0':
  743.             case '1':
  744.             case '2':
  745.             case '3':
  746.             case '4':
  747.             case '5':
  748.             case '6':
  749.             case '7':
  750.             case '8':
  751.             case '9':
  752.                 sscanf(buf, "%d", &d . key);
  753.                 t = Insert(d, t);
  754.                 break;
  755.  
  756.             case 'S':        /* Set up default tree */
  757.                 t = NULL;
  758.                 d . key = 20;
  759.                 t = Insert(d, t);
  760.                 d . key = 10;
  761.                 t = Insert(d, t);
  762.                 d . key = 15;
  763.                 t = Insert(d, t);
  764.                 d . key = 30;
  765.                 t = Insert(d, t);
  766.                 d . key = 40;
  767.                 t = Insert(d, t);
  768.                 d . key = 7;
  769.                 t = Insert(d, t);
  770.                 d . key = 18;
  771.                 t = Insert(d, t);
  772.                 d . key = 22;
  773.                 t = Insert(d, t);
  774.                 d . key = 26;
  775.                 t = Insert(d, t);
  776.                 d . key = 5;
  777.                 t = Insert(d, t);
  778.                 d . key = 35;
  779.                 t = Insert(d, t);
  780.                 d . key = 13;
  781.                 t = Insert(d, t);
  782.                 d . key = 27;
  783.                 t = Insert(d, t);
  784.                 d . key = 32;
  785.                 t = Insert(d, t);
  786.                 d . key = 42;
  787.                 t = Insert(d, t);
  788.                 d . key = 46;
  789.                 t = Insert(d, t);
  790.                 d . key = 24;
  791.                 t = Insert(d, t);
  792.                 d . key = 45;
  793.                 t = Insert(d, t);
  794.                 d . key = 25;
  795.                 t = Insert(d, t);
  796.                 ShowTree(t, 0);
  797.                 break;
  798.  
  799.             case 'I':        /* Insert a key */
  800.                 sscanf(buf+1, "%d", &d . key);
  801.                 t = Insert(d, t);
  802.                 break;
  803.  
  804.             case 'D':        /* Delete a key */
  805.                 sscanf(buf+1, "%d", &d . key);
  806.                 oldt = t;
  807.                 t = Delete(d . key, t);
  808.                 if (t == NULL)
  809.                     t = oldt;
  810.                 break;
  811.  
  812.             case 'L':        /* Lookup a key */
  813.                 sscanf(buf+1, "%d", &d . key);
  814.                 dp = Search(d . key, t);
  815.                 printf("%s\n",
  816.                     dp != NULL ? "Found it" : "No such key");
  817.                 break;
  818.  
  819.             case 'P':        /* Show the tree */
  820.                 ShowTree(t, 0);
  821.                 break;
  822.         }
  823.         printf("Command: "); fflush(stdout);
  824.     }
  825.     Apply(t, ShowDatum);
  826.     exit(0);
  827. }
  828. #endif STAND_ALONE
  829.