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