source: trunk/src/helpers/tree.c@ 113

Last change on this file since 113 was 113, checked in by umoeller, 24 years ago

Misc updates.
  • Property svn:eol-style set to CRLF
  • Property svn:keywords set to Author Date Id Revision
File size: 31.6 KB
Line 
1
2/*
3 *@@sourcefile tree.c:
4 * contains helper functions for maintaining 'Red-Black' balanced
5 * binary trees.
6 *
7 * Usage: All C programs; not OS/2-specific.
8 *
9 * Function prefixes (new with V0.81):
10 * -- tree* tree helper functions
11 *
12 * <B>Introduction</B>
13 *
14 * While linked lists have "next" and "previous" pointers (which
15 * makes them one-dimensional), trees have a two-dimensional layout:
16 * each tree node has one "parent" and two "children" which are
17 * called "left" and "right". The "left" pointer will always lead
18 * to a tree node that is "less than" its parent node, while the
19 * "right" pointer will lead to a node that is "greater than"
20 * its parent. What is considered "less" or "greater" for sorting
21 * is determined by a comparison callback to be supplied by the
22 * tree functions' caller. The "leafs" of the tree will have
23 * null left and right pointers.
24 *
25 * For this, the functions here use the TREE structure. The most
26 * important member here is the "ulKey" field which is used for
27 * sorting (passed to the compare callbacks). Since the tree
28 * functions do no memory allocation, the caller can easily
29 * use an extended TREE structure with additional fields as
30 * long as the first member is the TREE structure. See below.
31 *
32 * Each tree must have a "root" item, from which all other tree
33 * nodes can eventually be reached by following the "left" and
34 * "right" pointers. The root node is the only node whose
35 * parent is null.
36 *
37 * <B>Trees vs. linked lists</B>
38 *
39 * Compared to linked lists (as implemented by linklist.c),
40 * trees allow for much faster searching, since they are
41 * always sorted.
42 *
43 * Take an array of numbers, and assume you'd need to find
44 * the array node with the specified number.
45 *
46 * With a (sorted) linked list, this would look like:
47 *
48 + 4 --> 7 --> 16 --> 20 --> 37 --> 38 --> 43
49 *
50 * Searching for "43" would need 6 iterations.
51 *
52 * With a binary tree, this would instead look like:
53 *
54 + 20
55 + / \
56 + 7 38
57 + / \ / \
58 + 4 16 37 43
59 + / \ / \ / \ / \
60 *
61 * Searching for "43" would need 2 iterations only.
62 *
63 * Assuming a linked list contains N items, then searching a
64 * linked list for an item will take an average of N/2 comparisons
65 * and even N comparisons if the item cannot be found (unless
66 * you keep the list sorted, but linklist.c doesn't do this).
67 *
68 * According to "Algorithms in C", a search in a balanced
69 * "red-black" binary tree takes about lg N comparisons on
70 * average, and insertions take less than one rotation on
71 * average.
72 *
73 * Differences compared to linklist.c:
74 *
75 * -- A tree is always sorted.
76 *
77 * -- Trees are considerably slower when inserting and removing
78 * nodes because the tree has to be rebalanced every time
79 * a node changes. By contrast, trees are much faster finding
80 * nodes because the tree is always sorted.
81 *
82 * -- As opposed to a LISTNODE, the TREE structure (which
83 * represents a tree node) does not contain a data pointer,
84 * as said above. The caller must do all memory management.
85 *
86 * <B>Background</B>
87 *
88 * Now, a "red-black balanced binary tree" means the following:
89 *
90 * -- We have "binary" trees. That is, there are only "left" and
91 * "right" pointers. (Other algorithms allow tree nodes to
92 * have more than two children, but binary trees are usually
93 * more efficient.)
94 *
95 * -- The tree is always "balanced". The tree gets reordered
96 * when items are added/removed to ensure that all paths
97 * through the tree are approximately the same length.
98 * This avoids the "worst case" scenario that some paths
99 * grow terribly long while others remain short ("degenerated"
100 * trees), which can make searching very inefficient:
101 *
102 + 4
103 + / \
104 + 7
105 + / \
106 + 16
107 + / \
108 + 20
109 + / \
110 + 37
111 + / \
112 + 43
113 + / \
114 *
115 * -- Fully balanced trees can be quite expensive because on
116 * every insertion or deletion, the tree nodes must be rotated.
117 * By contrast, "Red-black" binary balanced trees contain
118 * an additional bit in each node which marks the node as
119 * either red or black. This bit is used only for efficient
120 * rebalancing when inserting or deleting nodes.
121 *
122 * I don't fully understand why this works, but if you really
123 * care, this is explained at
124 * "http://www.eli.sdsu.edu/courses/fall96/cs660/notes/redBlack/redBlack.html".
125 *
126 * In other words, as opposed to regular binary trees, RB trees
127 * are not _fully_ balanced, but they are _mostly_ balanced. With
128 * respect to efficiency, RB trees are thus a good compromise:
129 *
130 * -- Completely unbalanced trees are efficient when inserting,
131 * but can have a terrible worst case when searching.
132 *
133 * -- RB trees are still acceptably efficient when inserting
134 * and quite efficient when searching.
135 * A RB tree with n internal nodes has a height of at most
136 * 2lg(n+1). Both average and worst-case search time is O(lg n).
137 *
138 * -- Fully balanced binary trees are inefficient when inserting
139 * but most efficient when searching.
140 *
141 * So as long as you are sure that trees are more efficient
142 * in your situation than a linked list in the first place, use
143 * these RB trees instead of linked lists.
144 *
145 * <B>Using binary trees</B>
146 *
147 * You can use any structure as elements in a tree, provided
148 * that the first member in the structure is a TREE structure
149 * (i.e. it has the left, right, parent, and color members).
150 * Each TREE node has a ulKey field which is used for
151 * comparing tree nodes and thus determines the location of
152 * the node in the tree.
153 *
154 * The tree functions don't care what follows in each TREE
155 * node since they do not manage any memory themselves.
156 * So the implementation here is slightly different from the
157 * linked lists in linklist.c, because the LISTNODE structs
158 * only have pointers to the data. By contrast, the TREE structs
159 * are expected to contain the data themselves.
160 *
161 * Initialize the root of the tree with treeInit(). Then
162 * add nodes to the tree with treeInsert() and remove nodes
163 * with treeDelete(). See below for a sample.
164 *
165 * You can test whether a tree is empty by comparing its
166 * root with LEAF.
167 *
168 * For most tree* functions, you must specify a comparison
169 * function which will always receive two "key" parameters
170 * to compare. This must be declared as
171 +
172 + int TREEENTRY fnCompare(ULONG ul1, ULONG ul2);
173 *
174 * This will receive two TREE.ulKey members (whose meaning
175 * is defined by your implementation) and must return
176 *
177 * -- something < 0: ul1 < ul2
178 * -- 0: ul1 == ul2
179 * -- something > 1: ul1 > ul2
180 *
181 * <B>Example</B>
182 *
183 * A good example where trees are efficient would be the
184 * case where you have "keyword=value" string pairs and
185 * you frequently need to search for "keyword" to find
186 * a "value". So "keyword" would be an ideal candidate for
187 * the TREE.key field.
188 *
189 * You'd then define your own tree nodes like this:
190 *
191 + typedef struct _MYTREENODE
192 + {
193 + TREE Tree; // regular tree node, which has
194 + // the ULONG "key" field; we'd
195 + // use this as a const char*
196 + // pointer to the keyword string
197 + // here come the additional fields
198 + // (whatever you need for your data)
199 + const char *pcszValue;
200 +
201 + } MYTREENODE, *PMYTREENODE;
202 *
203 * Initialize the tree root:
204 *
205 + TREE *root;
206 + treeInit(&root);
207 *
208 * To add a new "keyword=value" pair, do this:
209 *
210 + PMYTREENODE AddNode(TREE **root,
211 + const char *pcszKeyword,
212 + const char *pcszValue)
213 + {
214 + PMYTREENODE p = (PMYTREENODE)malloc(sizeof(MYTREENODE));
215 + p.Tree.ulKey = (ULONG)pcszKeyword;
216 + p.pcszValue = pcszValue;
217 + treeInsert(root, // tree's root
218 + p, // new tree node
219 + fnCompare); // comparison func
220 + return (p);
221 + }
222 *
223 * Your comparison func receives two ulKey values to compare,
224 * which in this case would be the typecast string pointers:
225 *
226 + int TREEENTRY fnCompare(ULONG ul1, ULONG ul2)
227 + {
228 + return (strcmp((const char*)ul1,
229 + (const char*)ul2));
230 + }
231 *
232 * You can then use treeFind to very quickly find a node
233 * with a specified ulKey member.
234 *
235 * This file was new with V0.9.5 (2000-09-29) [umoeller].
236 * With V0.9.13, all the code has been replaced with the public
237 * domain code found at http://epaperpress.com/sortsearch/index.html
238 * ("A compact guide to searching and sorting") by Thomas Niemann.
239 * The old implementation from the Standard Function Library (SFL)
240 * turned out to be buggy for large trees (more than 100 nodes).
241 *
242 *@@added V0.9.5 (2000-09-29) [umoeller]
243 *@@header "helpers\tree.h"
244 */
245
246/*
247 * Original coding by Thomas Niemann, placed in the public domain
248 * (see http://epaperpress.com/sortsearch/index.html).
249 *
250 * This implementation Copyright (C) 2001 Ulrich M”ller.
251 * This file is part of the "XWorkplace helpers" source package.
252 * This is free software; you can redistribute it and/or modify
253 * it under the terms of the GNU General Public License as published
254 * by the Free Software Foundation, in version 2 as it comes in the
255 * "COPYING" file of the XWorkplace main distribution.
256 * This program is distributed in the hope that it will be useful,
257 * but WITHOUT ANY WARRANTY; without even the implied warranty of
258 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
259 * GNU General Public License for more details.
260 */
261
262/*
263 *@@category: Helpers\C helpers\Red-black balanced binary trees
264 * See tree.c.
265 */
266
267#include "setup.h"
268#include "helpers\tree.h"
269
270#define LEAF &sentinel // all leafs are sentinels
271static TREE sentinel = { LEAF, LEAF, 0, BLACK};
272
273/*
274A binary search tree is a red-black tree if:
275
2761. Every node is either red or black.
2772. Every leaf (nil) is black.
2783. If a node is red, then both its children are black.
2794. Every simple path from a node to a descendant leaf contains the same
280 number of black nodes.
281*/
282
283/*
284 *@@ treeInit:
285 * initializes the root of a tree.
286 *
287 *@@changed V0.9.16 (2001-10-19) [umoeller]: added plCount
288 */
289
290void treeInit(TREE **root,
291 PLONG plCount) // out: tree item count, set to 0 (ptr can be NULL)
292{
293 *root = LEAF;
294
295 if (plCount)
296 *plCount = 0; // V0.9.16 (2001-10-19) [umoeller]
297}
298
299/*
300 *@@ treeCompareKeys:
301 * standard comparison func if the TREE.ulKey
302 * field really is a ULONG.
303 */
304
305int TREEENTRY treeCompareKeys(unsigned long ul1, unsigned long ul2)
306{
307 if (ul1 < ul2)
308 return -1;
309 if (ul1 > ul2)
310 return +1;
311 return (0);
312}
313
314/*
315 *@@ treeCompareStrings:
316 * standard comparison func if the TREE.ulKey
317 * field really is a string pointer (PCSZ).
318 *
319 * This runs strcmp internally, but can handle
320 * NULL pointers without crashing.
321 *
322 *@@added V0.9.16 (2001-09-29) [umoeller]
323 */
324
325int TREEENTRY treeCompareStrings(unsigned long ul1, unsigned long ul2)
326{
327 #define p1 (const char*)(ul1)
328 #define p2 (const char*)(ul2)
329
330 if (p1 && p2)
331 {
332 int i = strcmp(p1, p2);
333 if (i < 0) return (-1);
334 if (i > 0) return (+1);
335 }
336 else if (p1)
337 // but p2 is NULL: p1 greater than p2 then
338 return (+1);
339 else if (p2)
340 // but p1 is NULL: p1 less than p2 then
341 return (-1);
342
343 // return 0 if strcmp returned 0 above or both strings are NULL
344 return (0);
345}
346
347/*
348 *@@ rotateLeft:
349 * private function during rebalancing.
350 */
351
352static void rotateLeft(TREE **root,
353 TREE *x)
354{
355 /**************************
356 * rotate node x to left *
357 **************************/
358
359 TREE *y = x->right;
360
361 // establish x->right link
362 x->right = y->left;
363 if (y->left != LEAF)
364 y->left->parent = x;
365
366 // establish y->parent link
367 if (y != LEAF)
368 y->parent = x->parent;
369 if (x->parent)
370 {
371 if (x == x->parent->left)
372 x->parent->left = y;
373 else
374 x->parent->right = y;
375 }
376 else
377 *root = y;
378
379 // link x and y
380 y->left = x;
381 if (x != LEAF)
382 x->parent = y;
383}
384
385/*
386 *@@ rotateRight:
387 * private function during rebalancing.
388 */
389
390static void rotateRight(TREE **root,
391 TREE *x)
392{
393
394 /****************************
395 * rotate node x to right *
396 ****************************/
397
398 TREE *y = x->left;
399
400 // establish x->left link
401 x->left = y->right;
402 if (y->right != LEAF)
403 y->right->parent = x;
404
405 // establish y->parent link
406 if (y != LEAF)
407 y->parent = x->parent;
408 if (x->parent)
409 {
410 if (x == x->parent->right)
411 x->parent->right = y;
412 else
413 x->parent->left = y;
414 }
415 else
416 *root = y;
417
418 // link x and y
419 y->right = x;
420 if (x != LEAF)
421 x->parent = y;
422}
423
424/*
425 *@@ insertFixup:
426 * private function during rebalancing.
427 */
428
429static void insertFixup(TREE **root,
430 TREE *x)
431{
432 /*************************************
433 * maintain Red-Black tree balance *
434 * after inserting node x *
435 *************************************/
436
437 // check Red-Black properties
438 while ( x != *root
439 && x->parent->color == RED
440 )
441 {
442 // we have a violation
443 if (x->parent == x->parent->parent->left)
444 {
445 TREE *y = x->parent->parent->right;
446 if (y->color == RED)
447 {
448 // uncle is RED
449 x->parent->color = BLACK;
450 y->color = BLACK;
451 x->parent->parent->color = RED;
452 x = x->parent->parent;
453 }
454 else
455 {
456 // uncle is BLACK
457 if (x == x->parent->right)
458 {
459 // make x a left child
460 x = x->parent;
461 rotateLeft(root,
462 x);
463 }
464
465 // recolor and rotate
466 x->parent->color = BLACK;
467 x->parent->parent->color = RED;
468 rotateRight(root,
469 x->parent->parent);
470 }
471 }
472 else
473 {
474 // mirror image of above code
475 TREE *y = x->parent->parent->left;
476 if (y->color == RED)
477 {
478 // uncle is RED
479 x->parent->color = BLACK;
480 y->color = BLACK;
481 x->parent->parent->color = RED;
482 x = x->parent->parent;
483 }
484 else
485 {
486 // uncle is BLACK
487 if (x == x->parent->left)
488 {
489 x = x->parent;
490 rotateRight(root,
491 x);
492 }
493 x->parent->color = BLACK;
494 x->parent->parent->color = RED;
495 rotateLeft(root,
496 x->parent->parent);
497 }
498 }
499 }
500 (*root)->color = BLACK;
501}
502
503/*
504 *@@ treeInsert:
505 * inserts a new tree node into the specified
506 * tree, using the specified comparison function
507 * for sorting.
508 *
509 * "x" specifies the new tree node which must
510 * have been allocated by the caller. x->ulKey
511 * must already contain the node's key (data).
512 * This function will then set the parent,
513 * left, right, and color members.
514 *
515 * Returns 0 if no error. Might return
516 * STATUS_DUPLICATE_KEY if a node with the
517 * same ulKey already exists.
518 *
519 *@@changed V0.9.16 (2001-10-19) [umoeller]: added plCount
520 */
521
522int treeInsert(TREE **root, // in: root of the tree
523 PLONG plCount, // in/out: item count (ptr can be NULL)
524 TREE *x, // in: new node to insert
525 FNTREE_COMPARE *pfnCompare) // in: comparison func
526{
527 TREE *current,
528 *parent;
529
530 unsigned long key = x->ulKey;
531
532 // find future parent
533 current = *root;
534 parent = 0;
535
536 while (current != LEAF)
537 {
538 int iResult;
539 if (0 == (iResult = pfnCompare(key, current->ulKey))) // if (compEQ(key, current->key))
540 return STATUS_DUPLICATE_KEY;
541
542 parent = current;
543 current = (iResult < 0) // compLT(key, current->key)
544 ? current->left
545 : current->right;
546 }
547
548 // set up new node
549 /* if ((x = malloc (sizeof(*x))) == 0)
550 return STATUS_MEM_EXHAUSTED; */
551 x->parent = parent;
552 x->left = LEAF;
553 x->right = LEAF;
554 x->color = RED;
555 // x->key = key;
556 // x->rec = *rec;
557
558 // insert node in tree
559 if (parent)
560 {
561 if (pfnCompare(key, parent->ulKey) < 0) // (compLT(key, parent->key))
562 parent->left = x;
563 else
564 parent->right = x;
565 }
566 else
567 *root = x;
568
569 insertFixup(root,
570 x);
571 // lastFind = NULL;
572
573 if (plCount)
574 (*plCount)++; // V0.9.16 (2001-10-19) [umoeller]
575
576 return STATUS_OK;
577}
578
579/*
580 *@@ deleteFixup:
581 *
582 */
583
584static void deleteFixup(TREE **root,
585 TREE *tree)
586{
587 TREE *s;
588
589 while ( tree != *root
590 && tree->color == BLACK
591 )
592 {
593 if (tree == tree->parent->left)
594 {
595 s = tree->parent->right;
596 if (s->color == RED)
597 {
598 s->color = BLACK;
599 tree->parent->color = RED;
600 rotateLeft(root, tree->parent);
601 s = tree->parent->right;
602 }
603 if ( (s->left->color == BLACK)
604 && (s->right->color == BLACK)
605 )
606 {
607 s->color = RED;
608 tree = tree->parent;
609 }
610 else
611 {
612 if (s->right->color == BLACK)
613 {
614 s->left->color = BLACK;
615 s->color = RED;
616 rotateRight(root, s);
617 s = tree->parent->right;
618 }
619 s->color = tree->parent->color;
620 tree->parent->color = BLACK;
621 s->right->color = BLACK;
622 rotateLeft(root, tree->parent);
623 tree = *root;
624 }
625 }
626 else
627 {
628 s = tree->parent->left;
629 if (s->color == RED)
630 {
631 s->color = BLACK;
632 tree->parent->color = RED;
633 rotateRight(root, tree->parent);
634 s = tree->parent->left;
635 }
636 if ( (s->right->color == BLACK)
637 && (s->left->color == BLACK)
638 )
639 {
640 s->color = RED;
641 tree = tree->parent;
642 }
643 else
644 {
645 if (s->left->color == BLACK)
646 {
647 s->right->color = BLACK;
648 s->color = RED;
649 rotateLeft(root, s);
650 s = tree->parent->left;
651 }
652 s->color = tree->parent->color;
653 tree->parent->color = BLACK;
654 s->left->color = BLACK;
655 rotateRight (root, tree->parent);
656 tree = *root;
657 }
658 }
659 }
660 tree->color = BLACK;
661
662 /*************************************
663 * maintain Red-Black tree balance *
664 * after deleting node x *
665 *************************************/
666
667 /* while ( x != *root
668 && x->color == BLACK
669 )
670 {
671 if (x == x->parent->left)
672 {
673 TREE *w = x->parent->right;
674 if (w->color == RED)
675 {
676 w->color = BLACK;
677 x->parent->color = RED;
678 rotateLeft(root,
679 x->parent);
680 w = x->parent->right;
681 }
682 if ( w->left->color == BLACK
683 && w->right->color == BLACK
684 )
685 {
686 w->color = RED;
687 x = x->parent;
688 }
689 else
690 {
691 if (w->right->color == BLACK)
692 {
693 w->left->color = BLACK;
694 w->color = RED;
695 rotateRight(root,
696 w);
697 w = x->parent->right;
698 }
699 w->color = x->parent->color;
700 x->parent->color = BLACK;
701 w->right->color = BLACK;
702 rotateLeft(root,
703 x->parent);
704 x = *root;
705 }
706 }
707 else
708 {
709 TREE *w = x->parent->left;
710 if (w->color == RED)
711 {
712 w->color = BLACK;
713 x->parent->color = RED;
714 rotateRight(root,
715 x->parent);
716 w = x->parent->left;
717 }
718 if ( w->right->color == BLACK
719 && w->left->color == BLACK
720 )
721 {
722 w->color = RED;
723 x = x->parent;
724 }
725 else
726 {
727 if (w->left->color == BLACK)
728 {
729 w->right->color = BLACK;
730 w->color = RED;
731 rotateLeft(root,
732 w);
733 w = x->parent->left;
734 }
735 w->color = x->parent->color;
736 x->parent->color = BLACK;
737 w->left->color = BLACK;
738 rotateRight(root,
739 x->parent);
740 x = *root;
741 }
742 }
743 }
744 x->color = BLACK; */
745}
746
747/*
748 *@@ treeDelete:
749 * removes the specified node from the tree.
750 * Does not free() the node though.
751 *
752 * Returns 0 if the node was deleted or
753 * STATUS_INVALID_NODE if not.
754 *
755 *@@changed V0.9.16 (2001-10-19) [umoeller]: added plCount
756 */
757
758int treeDelete(TREE **root, // in: root of the tree
759 PLONG plCount, // in/out: item count (ptr can be NULL)
760 TREE *tree) // in: tree node to delete
761{
762 TREE *y,
763 *d;
764 nodeColor color;
765
766 if ( (!tree)
767 || (tree == LEAF)
768 )
769 return STATUS_INVALID_NODE;
770
771 if ( (tree->left == LEAF)
772 || (tree->right == LEAF)
773 )
774 // d has a TREE_NULL node as a child
775 d = tree;
776 else
777 {
778 // find tree successor with a TREE_NULL node as a child
779 d = tree->right;
780 while (d->left != LEAF)
781 d = d->left;
782 }
783
784 // y is d's only child, if there is one, else TREE_NULL
785 if (d->left != LEAF)
786 y = d->left;
787 else
788 y = d->right;
789
790 // remove d from the parent chain
791 if (y != LEAF)
792 y->parent = d->parent;
793 if (d->parent)
794 {
795 if (d == d->parent->left)
796 d->parent->left = y;
797 else
798 d->parent->right = y;
799 }
800 else
801 *root = y;
802
803 color = d->color;
804
805 if (d != tree)
806 {
807 // move the data from d to tree; we do this by
808 // linking d into the structure in the place of tree
809 d->left = tree->left;
810 d->right = tree->right;
811 d->parent = tree->parent;
812 d->color = tree->color;
813
814 if (d->parent)
815 {
816 if (tree == d->parent->left)
817 d->parent->left = d;
818 else
819 d->parent->right = d;
820 }
821 else
822 *root = d;
823
824 if (d->left != LEAF)
825 d->left->parent = d;
826
827 if (d->right != LEAF)
828 d->right->parent = d;
829 }
830
831 if ( (y != LEAF)
832 && (color == BLACK)
833 )
834 deleteFixup(root,
835 y);
836
837 if (plCount)
838 (*plCount)--; // V0.9.16 (2001-10-19) [umoeller]
839
840 return (STATUS_OK);
841}
842
843/*
844 *@@ treeFind:
845 * finds the tree node with the specified key.
846 * Returns NULL if none exists.
847 */
848
849TREE* treeFind(TREE *root, // in: root of the tree
850 unsigned long key, // in: key to find
851 FNTREE_COMPARE *pfnCompare) // in: comparison func
852{
853 /*******************************
854 * find node containing data *
855 *******************************/
856
857 TREE *current = root;
858 while (current != LEAF)
859 {
860 int iResult;
861 if (0 == (iResult = pfnCompare(key, current->ulKey)))
862 return (current);
863 else
864 {
865 current = (iResult < 0) // compLT (key, current->key)
866 ? current->left
867 : current->right;
868 }
869 }
870
871 return 0;
872}
873
874/*
875 *@@ treeFirst:
876 * finds and returns the first node in a (sub-)tree.
877 *
878 * See treeNext for a sample usage for traversing a tree.
879 */
880
881TREE* treeFirst(TREE *r)
882{
883 TREE *p;
884
885 if ( (!r)
886 || (r == LEAF)
887 )
888 return NULL;
889
890 p = r;
891 while (p->left != LEAF)
892 p = p->left;
893
894 return p;
895}
896
897/*
898 *@@ treeLast:
899 * finds and returns the last node in a (sub-)tree.
900 */
901
902TREE* treeLast(TREE *r)
903{
904 TREE *p;
905
906 if ( (!r)
907 || (r == LEAF))
908 return NULL;
909
910 p = r;
911 while (p->right != LEAF)
912 p = p->right;
913
914 return p;
915}
916
917/*
918 *@@ treeNext:
919 * finds and returns the next node in a tree.
920 *
921 * Example for traversing a whole tree:
922 *
923 + TREE *TreeRoot;
924 + ...
925 + TREE* pNode = treeFirst(TreeRoot);
926 + while (pNode)
927 + {
928 + ...
929 + pNode = treeNext(pNode);
930 + }
931 *
932 * This runs through the tree items in sorted order.
933 */
934
935TREE* treeNext(TREE *r)
936{
937 TREE *p,
938 *child;
939
940 if ( (!r)
941 || (r == LEAF)
942 )
943 return NULL;
944
945 p = r;
946 if (p->right != LEAF)
947 return treeFirst (p->right);
948 else
949 {
950 p = r;
951 child = LEAF;
952 while ( (p->parent)
953 && (p->right == child)
954 )
955 {
956 child = p;
957 p = p->parent;
958 }
959 if (p->right != child)
960 return p;
961 else
962 return NULL;
963 }
964}
965
966/*
967 *@@ treePrev:
968 * finds and returns the previous node in a tree.
969 */
970
971TREE* treePrev(TREE *r)
972{
973 TREE *p,
974 *child;
975
976 if ( (!r)
977 || (r == LEAF))
978 return NULL;
979
980 p = r;
981 if (p->left != LEAF)
982 return treeLast (p->left);
983 else
984 {
985 p = r;
986 child = LEAF;
987 while ((p->parent)
988 && (p->left == child))
989 {
990 child = p;
991 p = p->parent;
992 }
993 if (p->left != child)
994 return p;
995 else
996 return NULL;
997 }
998}
999
1000/*
1001 *@@ treeBuildArray:
1002 * builds an array of TREE* pointers containing
1003 * all tree items in sorted order.
1004 *
1005 * This returns a TREE** pointer to the array.
1006 * Each item in the array is a TREE* pointer to
1007 * the respective tree item.
1008 *
1009 * The array has been allocated using malloc()
1010 * and must be free()'d by the caller.
1011 *
1012 * NOTE: This will only work if you maintain a
1013 * tree node count yourself, which you must pass
1014 * in *pulCount on input.
1015 *
1016 * This is most useful if you want to delete an
1017 * entire tree without having to traverse it
1018 * and rebalance the tree on every delete.
1019 *
1020 * Example usage for deletion:
1021 *
1022 + TREE *G_TreeRoot;
1023 + treeInit(&G_TreeRoot);
1024 +
1025 + // add stuff to the tree
1026 + TREE *pNewNode = malloc(...);
1027 + treeInsert(&G_TreeRoot, pNewNode, fnCompare)
1028 +
1029 + // now delete all nodes
1030 + ULONG cItems = ... // insert item count here
1031 + TREE** papNodes = treeBuildArray(G_TreeRoot,
1032 + &cItems);
1033 + if (papNodes)
1034 + {
1035 + ULONG ul;
1036 + for (ul = 0; ul < cItems; ul++)
1037 + {
1038 + TREE *pNodeThis = papNodes[ul];
1039 + free(pNodeThis);
1040 + }
1041 +
1042 + free(papNodes);
1043 + }
1044 +
1045 *
1046 *@@added V0.9.9 (2001-04-05) [umoeller]
1047 */
1048
1049TREE** treeBuildArray(TREE* pRoot,
1050 PLONG plCount) // in: item count, out: array item count
1051{
1052 TREE **papNodes = NULL,
1053 **papThis = NULL;
1054 long cb = (sizeof(TREE*) * (*plCount)),
1055 cNodes = 0;
1056
1057 if (cb)
1058 {
1059 papNodes = (TREE**)malloc(cb);
1060 papThis = papNodes;
1061
1062 if (papNodes)
1063 {
1064 TREE *pNode = (TREE*)treeFirst(pRoot);
1065
1066 memset(papNodes, 0, cb);
1067
1068 // copy nodes to array
1069 while ( pNode
1070 && cNodes < (*plCount) // just to make sure
1071 )
1072 {
1073 *papThis = pNode;
1074 cNodes++;
1075 papThis++;
1076
1077 pNode = (TREE*)treeNext(pNode);
1078 }
1079
1080 // output count
1081 *plCount = cNodes;
1082 }
1083 }
1084
1085 return (papNodes);
1086}
1087
1088/* void main(int argc, char **argv) {
1089 int maxnum, ct;
1090 recType rec;
1091 keyType key;
1092 statusEnum status;
1093
1094 maxnum = atoi(argv[1]);
1095
1096 printf("maxnum = %d\n", maxnum);
1097 for (ct = maxnum; ct; ct--) {
1098 key = rand() % 9 + 1;
1099 if ((status = find(key, &rec)) == STATUS_OK) {
1100 status = delete(key);
1101 if (status) printf("fail: status = %d\n", status);
1102 } else {
1103 status = insert(key, &rec);
1104 if (status) printf("fail: status = %d\n", status);
1105 }
1106 }
1107} */
Note: See TracBrowser for help on using the repository browser.