tree234.c

   1 /*
   2  * tree234.c: reasonably generic 2-3-4 tree routines. Currently
   3  * supports insert, delete, find and iterate operations.
   4  */
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8
   9 #include "tree234.h"
  10
  11 #define mknew(typ) ( (typ *) malloc (sizeof (typ)) )
  12 #define sfree free
  13
  14 #ifdef TEST
  15 #define LOG(x) (printf x)
  16 #else
  17 #define LOG(x)
  18 #endif
  19
  20 struct tree234_Tag {
  21     node234 *root;
  22     cmpfn234 cmp;
  23 };
  24
  25 struct node234_Tag {
  26     node234 *parent;
  27     node234 *kids[4];
  28     void *elems[3];
  29 };
  30
  31 /*
  32  * Create a 2-3-4 tree.
  33  */
  34 tree234 *newtree234(cmpfn234 cmp) {
  35     tree234 *ret = mknew(tree234);
  36     LOG(("created tree %p\n", ret));
  37     ret->root = NULL;
  38     ret->cmp = cmp;
  39     return ret;
  40 }
  41
  42 /*
  43  * Free a 2-3-4 tree (not including freeing the elements).
  44  */
  45 static void freenode234(node234 *n) {
  46     if (!n)
  47         return;
  48     freenode234(n->kids[0]);
  49     freenode234(n->kids[1]);
  50     freenode234(n->kids[2]);
  51     freenode234(n->kids[3]);
  52     sfree(n);
  53 }
  54 void freetree234(tree234 *t) {
  55     freenode234(t->root);
  56     sfree(t);
  57 }
  58
  59 /*
  60  * Add an element e to a 2-3-4 tree t. Returns e on success, or if
  61  * an existing element compares equal, returns that.
  62  */
  63 void *add234(tree234 *t, void *e) {
  64     node234 *n, **np, *left, *right;
  65     void *orig_e = e;
  66     int c;
  67
  68     LOG(("adding node %p to tree %p\n", e, t));
  69     if (t->root == NULL) {
  70         t->root = mknew(node234);
  71         t->root->elems[1] = t->root->elems[2] = NULL;
  72         t->root->kids[0] = t->root->kids[1] = NULL;
  73         t->root->kids[2] = t->root->kids[3] = NULL;
  74         t->root->parent = NULL;
  75         t->root->elems[0] = e;
  76         LOG(("  created root %p\n", t->root));
  77         return orig_e;
  78     }
  79
  80     np = &t->root;
  81     while (*np) {
  82         n = *np;
  83         LOG(("  node %p: %p [%p] %p [%p] %p [%p] %p\n",
  84              n, n->kids[0], n->elems[0], n->kids[1], n->elems[1],
  85              n->kids[2], n->elems[2], n->kids[3]));
  86         if ((c = t->cmp(e, n->elems[0])) < 0)
  87             np = &n->kids[0];
  88         else if (c == 0)
  89             return n->elems[0];        /* already exists */
  90         else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0)
  91             np = &n->kids[1];
  92         else if (c == 0)
  93             return n->elems[1];        /* already exists */
  94         else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0)
  95             np = &n->kids[2];
  96         else if (c == 0)
  97             return n->elems[2];        /* already exists */
  98         else
  99             np = &n->kids[3];
 100         LOG(("  moving to child %d (%p)\n", np - n->kids, *np));
 101     }
 102
 103     /*
 104      * We need to insert the new element in n at position np.
 105      */
 106     left = NULL;
 107     right = NULL;
 108     while (n) {
 109         LOG(("  at %p: %p [%p] %p [%p] %p [%p] %p\n",
 110              n, n->kids[0], n->elems[0], n->kids[1], n->elems[1],
 111              n->kids[2], n->elems[2], n->kids[3]));
 112         LOG(("  need to insert %p [%p] %p at position %d\n",
 113              left, e, right, np - n->kids));
 114         if (n->elems[1] == NULL) {
 115             /*
 116              * Insert in a 2-node; simple.
 117              */
 118             if (np == &n->kids[0]) {
 119                 LOG(("  inserting on left of 2-node\n"));
 120                 n->kids[2] = n->kids[1];
 121                 n->elems[1] = n->elems[0];
 122                 n->kids[1] = right;
 123                 n->elems[0] = e;
 124                 n->kids[0] = left;
 125             } else { /* np == &n->kids[1] */
 126                 LOG(("  inserting on right of 2-node\n"));
 127                 n->kids[2] = right;
 128                 n->elems[1] = e;
 129                 n->kids[1] = left;
 130             }
 131             if (n->kids[0]) n->kids[0]->parent = n;
 132             if (n->kids[1]) n->kids[1]->parent = n;
 133             if (n->kids[2]) n->kids[2]->parent = n;
 134             LOG(("  done\n"));
 135             break;
 136         } else if (n->elems[2] == NULL) {
 137             /*
 138              * Insert in a 3-node; simple.
 139              */
 140             if (np == &n->kids[0]) {
 141                 LOG(("  inserting on left of 3-node\n"));
 142                 n->kids[3] = n->kids[2];
 143                 n->elems[2] = n->elems[1];
 144                 n->kids[2] = n->kids[1];
 145                 n->elems[1] = n->elems[0];
 146                 n->kids[1] = right;
 147                 n->elems[0] = e;
 148                 n->kids[0] = left;
 149             } else if (np == &n->kids[1]) {
 150                 LOG(("  inserting in middle of 3-node\n"));
 151                 n->kids[3] = n->kids[2];
 152                 n->elems[2] = n->elems[1];
 153                 n->kids[2] = right;
 154                 n->elems[1] = e;
 155                 n->kids[1] = left;
 156             } else { /* np == &n->kids[2] */
 157                 LOG(("  inserting on right of 3-node\n"));
 158                 n->kids[3] = right;
 159                 n->elems[2] = e;
 160                 n->kids[2] = left;
 161             }
 162             if (n->kids[0]) n->kids[0]->parent = n;
 163             if (n->kids[1]) n->kids[1]->parent = n;
 164             if (n->kids[2]) n->kids[2]->parent = n;
 165             if (n->kids[3]) n->kids[3]->parent = n;
 166             LOG(("  done\n"));
 167             break;
 168         } else {
 169             node234 *m = mknew(node234);
 170             m->parent = n->parent;
 171             LOG(("  splitting a 4-node; created new node %p\n", m));
 172             /*
 173              * Insert in a 4-node; split into a 2-node and a
 174              * 3-node, and move focus up a level.
 175              *
 176              * I don't think it matters which way round we put the
 177              * 2 and the 3. For simplicity, we'll put the 3 first
 178              * always.
 179              */
 180             if (np == &n->kids[0]) {
 181                 m->kids[0] = left;
 182                 m->elems[0] = e;
 183                 m->kids[1] = right;
 184                 m->elems[1] = n->elems[0];
 185                 m->kids[2] = n->kids[1];
 186                 e = n->elems[1];
 187                 n->kids[0] = n->kids[2];
 188                 n->elems[0] = n->elems[2];
 189                 n->kids[1] = n->kids[3];
 190             } else if (np == &n->kids[1]) {
 191                 m->kids[0] = n->kids[0];
 192                 m->elems[0] = n->elems[0];
 193                 m->kids[1] = left;
 194                 m->elems[1] = e;
 195                 m->kids[2] = right;
 196                 e = n->elems[1];
 197                 n->kids[0] = n->kids[2];
 198                 n->elems[0] = n->elems[2];
 199                 n->kids[1] = n->kids[3];
 200             } else if (np == &n->kids[2]) {
 201                 m->kids[0] = n->kids[0];
 202                 m->elems[0] = n->elems[0];
 203                 m->kids[1] = n->kids[1];
 204                 m->elems[1] = n->elems[1];
 205                 m->kids[2] = left;
 206                 /* e = e; */
 207                 n->kids[0] = right;
 208                 n->elems[0] = n->elems[2];
 209                 n->kids[1] = n->kids[3];
 210             } else { /* np == &n->kids[3] */
 211                 m->kids[0] = n->kids[0];
 212                 m->elems[0] = n->elems[0];
 213                 m->kids[1] = n->kids[1];
 214                 m->elems[1] = n->elems[1];
 215                 m->kids[2] = n->kids[2];
 216                 n->kids[0] = left;
 217                 n->elems[0] = e;
 218                 n->kids[1] = right;
 219                 e = n->elems[2];
 220             }
 221             m->kids[3] = n->kids[3] = n->kids[2] = NULL;
 222             m->elems[2] = n->elems[2] = n->elems[1] = NULL;
 223             if (m->kids[0]) m->kids[0]->parent = m;
 224             if (m->kids[1]) m->kids[1]->parent = m;
 225             if (m->kids[2]) m->kids[2]->parent = m;
 226             if (n->kids[0]) n->kids[0]->parent = n;
 227             if (n->kids[1]) n->kids[1]->parent = n;
 228             LOG(("  left (%p): %p [%p] %p [%p] %p\n", m,
 229                  m->kids[0], m->elems[0],
 230                  m->kids[1], m->elems[1],
 231                  m->kids[2]));
 232             LOG(("  right (%p): %p [%p] %p\n", n,
 233                  n->kids[0], n->elems[0],
 234                  n->kids[1]));
 235             left = m;
 236             right = n;
 237         }
 238         if (n->parent)
 239             np = (n->parent->kids[0] == n ? &n->parent->kids[0] :
 240                   n->parent->kids[1] == n ? &n->parent->kids[1] :
 241                   n->parent->kids[2] == n ? &n->parent->kids[2] :
 242                   &n->parent->kids[3]);
 243         n = n->parent;
 244     }
 245
 246     /*
 247      * If we've come out of here by `break', n will still be
 248      * non-NULL and we've finished. If we've come here because n is
 249      * NULL, we need to create a new root for the tree because the
 250      * old one has just split into two.
 251      */
 252     if (!n) {
 253         LOG(("  root is overloaded, split into two\n"));
 254         t->root = mknew(node234);
 255         t->root->kids[0] = left;
 256         t->root->elems[0] = e;
 257         t->root->kids[1] = right;
 258         t->root->elems[1] = NULL;
 259         t->root->kids[2] = NULL;
 260         t->root->elems[2] = NULL;
 261         t->root->kids[3] = NULL;
 262         t->root->parent = NULL;
 263         if (t->root->kids[0]) t->root->kids[0]->parent = t->root;
 264         if (t->root->kids[1]) t->root->kids[1]->parent = t->root;
 265         LOG(("  new root is %p [%p] %p\n",
 266              t->root->kids[0], t->root->elems[0], t->root->kids[1]));
 267     }
 268
 269     return orig_e;
 270 }
 271
 272 /*
 273  * Find an element e in a 2-3-4 tree t. Returns NULL if not found.
 274  * e is always passed as the first argument to cmp, so cmp can be
 275  * an asymmetric function if desired. cmp can also be passed as
 276  * NULL, in which case the compare function from the tree proper
 277  * will be used.
 278  */
 279 void *find234(tree234 *t, void *e, cmpfn234 cmp) {
 280     node234 *n;
 281     int c;
 282
 283     if (t->root == NULL)
 284         return NULL;
 285
 286     if (cmp == NULL)
 287         cmp = t->cmp;
 288
 289     n = t->root;
 290     while (n) {
 291         if ( (c = cmp(e, n->elems[0])) < 0)
 292             n = n->kids[0];
 293         else if (c == 0)
 294             return n->elems[0];
 295         else if (n->elems[1] == NULL || (c = cmp(e, n->elems[1])) < 0)
 296             n = n->kids[1];
 297         else if (c == 0)
 298             return n->elems[1];
 299         else if (n->elems[2] == NULL || (c = cmp(e, n->elems[2])) < 0)
 300             n = n->kids[2];
 301         else if (c == 0)
 302             return n->elems[2];
 303         else
 304             n = n->kids[3];
 305     }
 306
 307     /*
 308      * We've found our way to the bottom of the tree and we know
 309      * where we would insert this node if we wanted to. But it
 310      * isn't there.
 311      */
 312     return NULL;
 313 }
 314
 315 /*
 316  * Delete an element e in a 2-3-4 tree. Does not free the element,
 317  * merely removes all links to it from the tree nodes.
 318  */
 319 void del234(tree234 *t, void *e) {
 320     node234 *n;
 321     int ei = -1;
 322
 323     n = t->root;
 324     LOG(("deleting %p from tree %p\n", e, t));
 325     while (1) {
 326         while (n) {
 327             int c;
 328             int ki;
 329             node234 *sub;
 330
 331             LOG(("  node %p: %p [%p] %p [%p] %p [%p] %p\n",
 332                  n, n->kids[0], n->elems[0], n->kids[1], n->elems[1],
 333                  n->kids[2], n->elems[2], n->kids[3]));
 334             if ((c = t->cmp(e, n->elems[0])) < 0) {
 335                 ki = 0;
 336             } else if (c == 0) {
 337                 ei = 0; break;
 338             } else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0) {
 339                 ki = 1;
 340             } else if (c == 0) {
 341                 ei = 1; break;
 342             } else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0) {
 343                 ki = 2;
 344             } else if (c == 0) {
 345                 ei = 2; break;
 346             } else {
 347                 ki = 3;
 348             }
 349             /*
 350              * Recurse down to subtree ki. If it has only one element,
 351              * we have to do some transformation to start with.
 352              */
 353             LOG(("  moving to subtree %d\n", ki));
 354             sub = n->kids[ki];
 355             if (!sub->elems[1]) {
 356                 LOG(("  subtree has only one element!\n", ki));
 357                 if (ki > 0 && n->kids[ki-1]->elems[1]) {
 358                     /*
 359                      * Case 3a, left-handed variant. Child ki has
 360                      * only one element, but child ki-1 has two or
 361                      * more. So we need to move a subtree from ki-1
 362                      * to ki.
 363                      *
 364                      *                . C .                     . B .
 365                      *               /     \     ->            /     \
 366                      * [more] a A b B c   d D e      [more] a A b   c C d D e
 367                      */
 368                     node234 *sib = n->kids[ki-1];
 369                     int lastelem = (sib->elems[2] ? 2 :
 370                                     sib->elems[1] ? 1 : 0);
 371                     sub->kids[2] = sub->kids[1];
 372                     sub->elems[1] = sub->elems[0];
 373                     sub->kids[1] = sub->kids[0];
 374                     sub->elems[0] = n->elems[ki-1];
 375                     sub->kids[0] = sib->kids[lastelem+1];
 376                     n->elems[ki-1] = sib->elems[lastelem];
 377                     sib->kids[lastelem+1] = NULL;
 378                     sib->elems[lastelem] = NULL;
 379                     LOG(("  case 3a left\n"));
 380                 } else if (ki < 3 && n->kids[ki+1] &&
 381                            n->kids[ki+1]->elems[1]) {
 382                     /*
 383                      * Case 3a, right-handed variant. ki has only
 384                      * one element but ki+1 has two or more. Move a
 385                      * subtree from ki+1 to ki.
 386                      *
 387                      *      . B .                             . C .
 388                      *     /     \                ->         /     \
 389                      *  a A b   c C d D e [more]      a A b B c   d D e [more]
 390                      */
 391                     node234 *sib = n->kids[ki+1];
 392                     int j;
 393                     sub->elems[1] = n->elems[ki];
 394                     sub->kids[2] = sib->kids[0];
 395                     n->elems[ki] = sib->elems[0];
 396                     sib->kids[0] = sib->kids[1];
 397                     for (j = 0; j < 2 && sib->elems[j+1]; j++) {
 398                         sib->kids[j+1] = sib->kids[j+2];
 399                         sib->elems[j] = sib->elems[j+1];
 400                     }
 401                     sib->kids[j+1] = NULL;
 402                     sib->elems[j] = NULL;
 403                     LOG(("  case 3a right\n"));
 404                 } else {
 405                     /*
 406                      * Case 3b. ki has only one element, and has no
 407                      * neighbour with more than one. So pick a
 408                      * neighbour and merge it with ki, taking an
 409                      * element down from n to go in the middle.
 410                      *
 411                      *      . B .                .
 412                      *     /     \     ->        |
 413                      *  a A b   c C d      a A b B c C d
 414                      *
 415                      * (Since at all points we have avoided
 416                      * descending to a node with only one element,
 417                      * we can be sure that n is not reduced to
 418                      * nothingness by this move, _unless_ it was
 419                      * the very first node, ie the root of the
 420                      * tree. In that case we remove the now-empty
 421                      * root and replace it with its single large
 422                      * child as shown.)
 423                      */
 424                     node234 *sib;
 425                     int j;
 426
 427                     if (ki > 0)
 428                         ki--;
 429                     sib = n->kids[ki];
 430                     sub = n->kids[ki+1];
 431
 432                     sub->kids[3] = sub->kids[1];
 433                     sub->elems[2] = sub->elems[0];
 434                     sub->kids[2] = sub->kids[0];
 435                     sub->elems[1] = n->elems[ki];
 436                     sub->kids[1] = sib->kids[1];
 437                     sub->elems[0] = sib->elems[0];
 438                     sub->kids[0] = sib->kids[0];
 439
 440                     sfree(sib);
 441
 442                     /*
 443                      * That's built the big node in sub. Now we
 444                      * need to remove the reference to sib in n.
 445                      */
 446                     for (j = ki; j < 3 && n->kids[j+1]; j++) {
 447                         n->kids[j] = n->kids[j+1];
 448                         n->elems[j] = j<2 ? n->elems[j+1] : NULL;
 449                     }
 450                     n->kids[j] = NULL;
 451                     if (j < 3) n->elems[j] = NULL;
 452                     LOG(("  case 3b\n"));
 453
 454                     if (!n->elems[0]) {
 455                         /*
 456                          * The root is empty and needs to be
 457                          * removed.
 458                          */
 459                         LOG(("  shifting root!\n"));
 460                         t->root = sub;
 461                         sub->parent = NULL;
 462                         sfree(n);
 463                     }
 464                 }
 465             }
 466             n = sub;
 467         }
 468         if (ei==-1)
 469             return;                    /* nothing to do; `already removed' */
 470
 471         /*
 472          * Treat special case: this is the one remaining item in
 473          * the tree. n is the tree root (no parent), has one
 474          * element (no elems[1]), and has no kids (no kids[0]).
 475          */
 476         if (!n->parent && !n->elems[1] && !n->kids[0]) {
 477             LOG(("  removed last element in tree\n"));
 478             sfree(n);
 479             t->root = NULL;
 480             return;
 481         }
 482
 483         /*
 484          * Now we have the element we want, as n->elems[ei], and we
 485          * have also arranged for that element not to be the only
 486          * one in its node. So...
 487          */
 488
 489         if (!n->kids[0] && n->elems[1]) {
 490             /*
 491              * Case 1. n is a leaf node with more than one element,
 492              * so it's _really easy_. Just delete the thing and
 493              * we're done.
 494              */
 495             int i;
 496             LOG(("  case 1\n"));
 497             for (i = ei; i < 2 && n->elems[i+1]; i++)
 498                 n->elems[i] = n->elems[i+1];
 499             n->elems[i] = NULL;
 500             return;                    /* finished! */
 501         } else if (n->kids[ei]->elems[1]) {
 502             /*
 503              * Case 2a. n is an internal node, and the root of the
 504              * subtree to the left of e has more than one element.
 505              * So find the predecessor p to e (ie the largest node
 506              * in that subtree), place it where e currently is, and
 507              * then start the deletion process over again on the
 508              * subtree with p as target.
 509              */
 510             node234 *m = n->kids[ei];
 511             void *target;
 512             LOG(("  case 2a\n"));
 513             while (m->kids[0]) {
 514                 m = (m->kids[3] ? m->kids[3] :
 515                      m->kids[2] ? m->kids[2] :
 516                      m->kids[1] ? m->kids[1] : m->kids[0]);
 517             }
 518             target = (m->elems[2] ? m->elems[2] :
 519                       m->elems[1] ? m->elems[1] : m->elems[0]);
 520             n->elems[ei] = target;
 521             n = n->kids[ei];
 522             e = target;
 523         } else if (n->kids[ei+1]->elems[1]) {
 524             /*
 525              * Case 2b, symmetric to 2a but s/left/right/ and
 526              * s/predecessor/successor/. (And s/largest/smallest/).
 527              */
 528             node234 *m = n->kids[ei+1];
 529             void *target;
 530             LOG(("  case 2b\n"));
 531             while (m->kids[0]) {
 532                 m = m->kids[0];
 533             }
 534             target = m->elems[0];
 535             n->elems[ei] = target;
 536             n = n->kids[ei+1];
 537             e = target;
 538         } else {
 539             /*
 540              * Case 2c. n is an internal node, and the subtrees to
 541              * the left and right of e both have only one element.
 542              * So combine the two subnodes into a single big node
 543              * with their own elements on the left and right and e
 544              * in the middle, then restart the deletion process on
 545              * that subtree, with e still as target.
 546              */
 547             node234 *a = n->kids[ei], *b = n->kids[ei+1];
 548             int j;
 549
 550             LOG(("  case 2c\n"));
 551             a->elems[1] = n->elems[ei];
 552             a->kids[2] = b->kids[0];
 553             a->elems[2] = b->elems[0];
 554             a->kids[3] = b->kids[1];
 555             sfree(b);
 556             /*
 557              * That's built the big node in a, and destroyed b. Now
 558              * remove the reference to b (and e) in n.
 559              */
 560             for (j = ei; j < 2 && n->elems[j+1]; j++) {
 561                 n->elems[j] = n->elems[j+1];
 562                 n->kids[j+1] = n->kids[j+2];
 563             }
 564             n->elems[j] = NULL;
 565             n->kids[j+1] = NULL;
 566             /*
 567              * Now go round the deletion process again, with n
 568              * pointing at the new big node and e still the same.
 569              */
 570             n = a;
 571         }
 572     }
 573 }
 574
 575 /*
 576  * Iterate over the elements of a tree234, in order.
 577  */
 578 void *first234(tree234 *t, enum234 *e) {
 579     node234 *n = t->root;
 580     if (!n)
 581         return NULL;
 582     while (n->kids[0])
 583         n = n->kids[0];
 584     e->node = n;
 585     e->posn = 0;
 586     return n->elems[0];
 587 }
 588
 589 void *next234(enum234 *e) {
 590     node234 *n = e->node;
 591     int pos = e->posn;
 592
 593     if (n->kids[pos+1]) {
 594         n = n->kids[pos+1];
 595         while (n->kids[0])
 596             n = n->kids[0];
 597         e->node = n;
 598         e->posn = 0;
 599         return n->elems[0];
 600     }
 601
 602     if (pos < 2 && n->elems[pos+1]) {
 603         e->posn = pos+1;
 604         return n->elems[e->posn];
 605     }
 606
 607     do {
 608         node234 *nn = n->parent;
 609         if (nn == NULL)
 610             return NULL;               /* end of tree */
 611         pos = (nn->kids[0] == n ? 0 :
 612                nn->kids[1] == n ? 1 :
 613                nn->kids[2] == n ? 2 : 3);
 614         n = nn;
 615     } while (pos == 3 || n->kids[pos+1] == NULL);
 616
 617     e->node = n;
 618     e->posn = pos;
 619     return n->elems[pos];
 620 }
 621
 622 #ifdef TEST
 623
 624 int pnode(node234 *n, int level) {
 625     printf("%*s%p\n", level*4, "", n);
 626     if (n->kids[0]) pnode(n->kids[0], level+1);
 627     if (n->elems[0]) printf("%*s\"%s\"\n", level*4+4, "", n->elems[0]);
 628     if (n->kids[1]) pnode(n->kids[1], level+1);
 629     if (n->elems[1]) printf("%*s\"%s\"\n", level*4+4, "", n->elems[1]);
 630     if (n->kids[2]) pnode(n->kids[2], level+1);
 631     if (n->elems[2]) printf("%*s\"%s\"\n", level*4+4, "", n->elems[2]);
 632     if (n->kids[3]) pnode(n->kids[3], level+1);
 633 }
 634 int ptree(tree234 *t) {
 635     if (t->root)
 636         pnode(t->root, 0);
 637     else
 638         printf("empty tree\n");
 639 }
 640
 641 int cmp(void *av, void *bv) {
 642     char *a = (char *)av;
 643     char *b = (char *)bv;
 644     return strcmp(a, b);
 645 }
 646
 647 int main(void) {
 648     tree234 *t = newtree234(cmp);
 649
 650     add234(t, "Richard");
 651     add234(t, "Of");
 652     add234(t, "York");
 653     add234(t, "Gave");
 654     add234(t, "Battle");
 655     add234(t, "In");
 656     add234(t, "Vain");
 657     add234(t, "Rabbits");
 658     add234(t, "On");
 659     add234(t, "Your");
 660     add234(t, "Garden");
 661     add234(t, "Bring");
 662     add234(t, "Invisible");
 663     add234(t, "Vegetables");
 664
 665     ptree(t);
 666     del234(t, find234(t, "Richard", NULL));
 667     ptree(t);
 668     del234(t, find234(t, "Of", NULL));
 669     ptree(t);
 670     del234(t, find234(t, "York", NULL));
 671     ptree(t);
 672     del234(t, find234(t, "Gave", NULL));
 673     ptree(t);
 674     del234(t, find234(t, "Battle", NULL));
 675     ptree(t);
 676     del234(t, find234(t, "In", NULL));
 677     ptree(t);
 678     del234(t, find234(t, "Vain", NULL));
 679     ptree(t);
 680     del234(t, find234(t, "Rabbits", NULL));
 681     ptree(t);
 682     del234(t, find234(t, "On", NULL));
 683     ptree(t);
 684     del234(t, find234(t, "Your", NULL));
 685     ptree(t);
 686     del234(t, find234(t, "Garden", NULL));
 687     ptree(t);
 688     del234(t, find234(t, "Bring", NULL));
 689     ptree(t);
 690     del234(t, find234(t, "Invisible", NULL));
 691     ptree(t);
 692     del234(t, find234(t, "Vegetables", NULL));
 693     ptree(t);
 694 }
 695 #endif