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

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

Misc changes.
  • Property svn:eol-style set to CRLF
  • Property svn:keywords set to Author Date Id Revision
File size: 32.3 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 */
288
289void treeInit(TREE **root)
290{
291 *root = LEAF;
292}
293
294/*
295 *@@ treeCompareKeys:
296 * standard comparison func if the TREE.ulKey
297 * field really is a ULONG.
298 */
299
300int TREEENTRY treeCompareKeys(unsigned long ul1, unsigned long ul2)
301{
302 if (ul1 < ul2)
303 return -1;
304 if (ul1 > ul2)
305 return +1;
306 return (0);
307}
308
309/*
310 *@@ rotateLeft:
311 * private function during rebalancing.
312 */
313
314static void rotateLeft(TREE **root,
315 TREE *x)
316{
317 /**************************
318 * rotate node x to left *
319 **************************/
320
321 TREE *y = x->right;
322
323 // establish x->right link
324 x->right = y->left;
325 if (y->left != LEAF)
326 y->left->parent = x;
327
328 // establish y->parent link
329 if (y != LEAF)
330 y->parent = x->parent;
331 if (x->parent)
332 {
333 if (x == x->parent->left)
334 x->parent->left = y;
335 else
336 x->parent->right = y;
337 }
338 else
339 *root = y;
340
341 // link x and y
342 y->left = x;
343 if (x != LEAF)
344 x->parent = y;
345}
346
347/*
348 *@@ rotateRight:
349 * private function during rebalancing.
350 */
351
352static void rotateRight(TREE **root,
353 TREE *x)
354{
355
356 /****************************
357 * rotate node x to right *
358 ****************************/
359
360 TREE *y = x->left;
361
362 // establish x->left link
363 x->left = y->right;
364 if (y->right != LEAF)
365 y->right->parent = x;
366
367 // establish y->parent link
368 if (y != LEAF)
369 y->parent = x->parent;
370 if (x->parent)
371 {
372 if (x == x->parent->right)
373 x->parent->right = y;
374 else
375 x->parent->left = y;
376 }
377 else
378 *root = y;
379
380 // link x and y
381 y->right = x;
382 if (x != LEAF)
383 x->parent = y;
384}
385
386/*
387 *@@ insertFixup:
388 * private function during rebalancing.
389 */
390
391static void insertFixup(TREE **root,
392 TREE *x)
393{
394 /*************************************
395 * maintain Red-Black tree balance *
396 * after inserting node x *
397 *************************************/
398
399 // check Red-Black properties
400 while ( x != *root
401 && x->parent->color == RED
402 )
403 {
404 // we have a violation
405 if (x->parent == x->parent->parent->left)
406 {
407 TREE *y = x->parent->parent->right;
408 if (y->color == RED)
409 {
410 // uncle is RED
411 x->parent->color = BLACK;
412 y->color = BLACK;
413 x->parent->parent->color = RED;
414 x = x->parent->parent;
415 }
416 else
417 {
418 // uncle is BLACK
419 if (x == x->parent->right)
420 {
421 // make x a left child
422 x = x->parent;
423 rotateLeft(root,
424 x);
425 }
426
427 // recolor and rotate
428 x->parent->color = BLACK;
429 x->parent->parent->color = RED;
430 rotateRight(root,
431 x->parent->parent);
432 }
433 }
434 else
435 {
436 // mirror image of above code
437 TREE *y = x->parent->parent->left;
438 if (y->color == RED)
439 {
440 // uncle is RED
441 x->parent->color = BLACK;
442 y->color = BLACK;
443 x->parent->parent->color = RED;
444 x = x->parent->parent;
445 }
446 else
447 {
448 // uncle is BLACK
449 if (x == x->parent->left)
450 {
451 x = x->parent;
452 rotateRight(root,
453 x);
454 }
455 x->parent->color = BLACK;
456 x->parent->parent->color = RED;
457 rotateLeft(root,
458 x->parent->parent);
459 }
460 }
461 }
462 (*root)->color = BLACK;
463}
464
465/*
466 *@@ treeInsert:
467 * inserts a new tree node into the specified
468 * tree, using the specified comparison function
469 * for sorting.
470 *
471 * "x" specifies the new tree node which must
472 * have been allocated by the caller. x->ulKey
473 * must already contain the node's key (data).
474 * This function will then set the parent,
475 * left, right, and color members.
476 *
477 * Returns 0 if no error. Might return
478 * STATUS_DUPLICATE_KEY if a node with the
479 * same ulKey already exists.
480 */
481
482int treeInsert(TREE **root, // in: root of the tree
483 TREE *x, // in: new node to insert
484 FNTREE_COMPARE *pfnCompare) // in: comparison func
485{
486 TREE *current,
487 *parent;
488
489 unsigned long key = x->ulKey;
490
491 // find future parent
492 current = *root;
493 parent = 0;
494
495 while (current != LEAF)
496 {
497 int iResult;
498 if (0 == (iResult = pfnCompare(key, current->ulKey))) // if (compEQ(key, current->key))
499 return STATUS_DUPLICATE_KEY;
500 parent = current;
501 current = (iResult < 0) // compLT(key, current->key)
502 ? current->left
503 : current->right;
504 }
505
506 // set up new node
507 /* if ((x = malloc (sizeof(*x))) == 0)
508 return STATUS_MEM_EXHAUSTED; */
509 x->parent = parent;
510 x->left = LEAF;
511 x->right = LEAF;
512 x->color = RED;
513 // x->key = key;
514 // x->rec = *rec;
515
516 // insert node in tree
517 if (parent)
518 {
519 if (pfnCompare(key, parent->ulKey) < 0) // (compLT(key, parent->key))
520 parent->left = x;
521 else
522 parent->right = x;
523 }
524 else
525 *root = x;
526
527 insertFixup(root,
528 x);
529 // lastFind = NULL;
530
531 return STATUS_OK;
532}
533
534/*
535 *@@ deleteFixup:
536 *
537 */
538
539static void deleteFixup(TREE **root,
540 TREE *tree)
541{
542 TREE *s;
543
544 while ( tree != *root
545 && tree->color == BLACK
546 )
547 {
548 if (tree == tree->parent->left)
549 {
550 s = tree->parent->right;
551 if (s->color == RED)
552 {
553 s->color = BLACK;
554 tree->parent->color = RED;
555 rotateLeft(root, tree->parent);
556 s = tree->parent->right;
557 }
558 if ( (s->left->color == BLACK)
559 && (s->right->color == BLACK)
560 )
561 {
562 s->color = RED;
563 tree = tree->parent;
564 }
565 else
566 {
567 if (s->right->color == BLACK)
568 {
569 s->left->color = BLACK;
570 s->color = RED;
571 rotateRight(root, s);
572 s = tree->parent->right;
573 }
574 s->color = tree->parent->color;
575 tree->parent->color = BLACK;
576 s->right->color = BLACK;
577 rotateLeft(root, tree->parent);
578 tree = *root;
579 }
580 }
581 else
582 {
583 s = tree->parent->left;
584 if (s->color == RED)
585 {
586 s->color = BLACK;
587 tree->parent->color = RED;
588 rotateRight(root, tree->parent);
589 s = tree->parent->left;
590 }
591 if ( (s->right->color == BLACK)
592 && (s->left->color == BLACK)
593 )
594 {
595 s->color = RED;
596 tree = tree->parent;
597 }
598 else
599 {
600 if (s->left->color == BLACK)
601 {
602 s->right->color = BLACK;
603 s->color = RED;
604 rotateLeft(root, s);
605 s = tree->parent->left;
606 }
607 s->color = tree->parent->color;
608 tree->parent->color = BLACK;
609 s->left->color = BLACK;
610 rotateRight (root, tree->parent);
611 tree = *root;
612 }
613 }
614 }
615 tree->color = BLACK;
616
617 /*************************************
618 * maintain Red-Black tree balance *
619 * after deleting node x *
620 *************************************/
621
622 /* while ( x != *root
623 && x->color == BLACK
624 )
625 {
626 if (x == x->parent->left)
627 {
628 TREE *w = x->parent->right;
629 if (w->color == RED)
630 {
631 w->color = BLACK;
632 x->parent->color = RED;
633 rotateLeft(root,
634 x->parent);
635 w = x->parent->right;
636 }
637 if ( w->left->color == BLACK
638 && w->right->color == BLACK
639 )
640 {
641 w->color = RED;
642 x = x->parent;
643 }
644 else
645 {
646 if (w->right->color == BLACK)
647 {
648 w->left->color = BLACK;
649 w->color = RED;
650 rotateRight(root,
651 w);
652 w = x->parent->right;
653 }
654 w->color = x->parent->color;
655 x->parent->color = BLACK;
656 w->right->color = BLACK;
657 rotateLeft(root,
658 x->parent);
659 x = *root;
660 }
661 }
662 else
663 {
664 TREE *w = x->parent->left;
665 if (w->color == RED)
666 {
667 w->color = BLACK;
668 x->parent->color = RED;
669 rotateRight(root,
670 x->parent);
671 w = x->parent->left;
672 }
673 if ( w->right->color == BLACK
674 && w->left->color == BLACK
675 )
676 {
677 w->color = RED;
678 x = x->parent;
679 }
680 else
681 {
682 if (w->left->color == BLACK)
683 {
684 w->right->color = BLACK;
685 w->color = RED;
686 rotateLeft(root,
687 w);
688 w = x->parent->left;
689 }
690 w->color = x->parent->color;
691 x->parent->color = BLACK;
692 w->left->color = BLACK;
693 rotateRight(root,
694 x->parent);
695 x = *root;
696 }
697 }
698 }
699 x->color = BLACK; */
700}
701
702/*
703 *@@ treeDelete:
704 * removes the specified node from the tree.
705 * Does not free() the node though.
706 *
707 * Returns 0 if the node was deleted or
708 * STATUS_INVALID_NODE if not.
709 */
710
711int treeDelete(TREE **root, // in: root of the tree
712 TREE *tree) // in: tree node to delete
713{
714 TREE *y,
715 *d;
716 nodeColor color;
717
718 if ( (!tree)
719 || (tree == LEAF)
720 )
721 return STATUS_INVALID_NODE;
722
723 if ( (tree->left == LEAF)
724 || (tree->right == LEAF)
725 )
726 // d has a TREE_NULL node as a child
727 d = tree;
728 else
729 {
730 // find tree successor with a TREE_NULL node as a child
731 d = tree->right;
732 while (d->left != LEAF)
733 d = d->left;
734 }
735
736 // y is d's only child, if there is one, else TREE_NULL
737 if (d->left != LEAF)
738 y = d->left;
739 else
740 y = d->right;
741
742 // remove d from the parent chain
743 if (y != LEAF)
744 y->parent = d->parent;
745 if (d->parent)
746 {
747 if (d == d->parent->left)
748 d->parent->left = y;
749 else
750 d->parent->right = y;
751 }
752 else
753 *root = y;
754
755 color = d->color;
756
757 if (d != tree)
758 {
759 // move the data from d to tree; we do this by
760 // linking d into the structure in the place of tree
761 d->left = tree->left;
762 d->right = tree->right;
763 d->parent = tree->parent;
764 d->color = tree->color;
765
766 if (d->parent)
767 {
768 if (tree == d->parent->left)
769 d->parent->left = d;
770 else
771 d->parent->right = d;
772 }
773 else
774 *root = d;
775
776 if (d->left != LEAF)
777 d->left->parent = d;
778
779 if (d->right != LEAF)
780 d->right->parent = d;
781 }
782
783 if ( (y != LEAF)
784 && (color == BLACK)
785 )
786 deleteFixup(root,
787 y);
788
789 return (STATUS_OK);
790
791 /* TREE *x,
792 *y; */
793 // *z;
794
795 /*****************************
796 * delete node z from tree *
797 *****************************/
798
799 // find node in tree
800 /* if (lastFind && compEQ(lastFind->key, key))
801 // if we just found node, use pointer
802 z = lastFind;
803 else {
804 z = *root;
805 while(z != LEAF)
806 {
807 int iResult = pfnCompare(key, z->key);
808 if (iResult == 0)
809 // if(compEQ(key, z->key))
810 break;
811 else
812 z = (iResult < 0) // compLT(key, z->key)
813 ? z->left
814 : z->right;
815 }
816 if (z == LEAF)
817 return STATUS_KEY_NOT_FOUND;
818 }
819
820 if ( z->left == LEAF
821 || z->right == LEAF
822 )
823 {
824 // y has a LEAF node as a child
825 y = z;
826 }
827 else
828 {
829 // find tree successor with a LEAF node as a child
830 y = z->right;
831 while (y->left != LEAF)
832 y = y->left;
833 }
834
835 // x is y's only child
836 if (y->left != LEAF)
837 x = y->left;
838 else
839 x = y->right;
840
841 // remove y from the parent chain
842 x->parent = y->parent;
843 if (y->parent)
844 if (y == y->parent->left)
845 y->parent->left = x;
846 else
847 y->parent->right = x;
848 else
849 *root = x;
850
851 // y is about to be deleted...
852
853 if (y != z)
854 {
855 // now, the original code simply copied the data
856 // from y to z... we can't safely do that since
857 // we don't know about the real data in the
858 // caller's TREE structure
859 z->ulKey = y->ulKey;
860 // z->rec = y->rec; // hope this works...
861 // the original implementation used rec
862 // for the node's data
863
864 if (cbStruct > sizeof(TREE))
865 {
866 memcpy(((char*)&z) + sizeof(TREE),
867 ((char*)&y) + sizeof(TREE),
868 cbStruct - sizeof(TREE));
869 }
870 }
871
872 if (y->color == BLACK)
873 deleteFixup(root,
874 x);
875
876 // free(y);
877 // lastFind = NULL;
878
879 return STATUS_OK; */
880}
881
882/*
883 *@@ treeFind:
884 * finds the tree node with the specified key.
885 * Returns NULL if none exists.
886 */
887
888TREE* treeFind(TREE *root, // in: root of the tree
889 unsigned long key, // in: key to find
890 FNTREE_COMPARE *pfnCompare) // in: comparison func
891{
892 /*******************************
893 * find node containing data *
894 *******************************/
895
896 TREE *current = root;
897 while (current != LEAF)
898 {
899 int iResult;
900 if (0 == (iResult = pfnCompare(key, current->ulKey)))
901 return (current);
902 else
903 {
904 current = (iResult < 0) // compLT (key, current->key)
905 ? current->left
906 : current->right;
907 }
908 }
909
910 return 0;
911}
912
913/*
914 *@@ treeFirst:
915 * finds and returns the first node in a (sub-)tree.
916 *
917 * See treeNext for a sample usage for traversing a tree.
918 */
919
920TREE* treeFirst(TREE *r)
921{
922 TREE *p;
923
924 if ( (!r)
925 || (r == LEAF)
926 )
927 return NULL;
928
929 p = r;
930 while (p->left != LEAF)
931 p = p->left;
932
933 return p;
934}
935
936/*
937 *@@ treeLast:
938 * finds and returns the last node in a (sub-)tree.
939 */
940
941TREE* treeLast(TREE *r)
942{
943 TREE *p;
944
945 if ( (!r)
946 || (r == LEAF))
947 return NULL;
948
949 p = r;
950 while (p->right != LEAF)
951 p = p->right;
952
953 return p;
954}
955
956/*
957 *@@ treeNext:
958 * finds and returns the next node in a tree.
959 *
960 * Example for traversing a whole tree:
961 *
962 + TREE *TreeRoot;
963 + ...
964 + TREE* pNode = treeFirst(TreeRoot);
965 + while (pNode)
966 + {
967 + ...
968 + pNode = treeNext(pNode);
969 + }
970 *
971 * This runs through the tree items in sorted order.
972 */
973
974TREE* treeNext(TREE *r)
975{
976 TREE *p,
977 *child;
978
979 if ( (!r)
980 || (r == LEAF)
981 )
982 return NULL;
983
984 p = r;
985 if (p->right != LEAF)
986 return treeFirst (p->right);
987 else
988 {
989 p = r;
990 child = LEAF;
991 while ( (p->parent)
992 && (p->right == child)
993 )
994 {
995 child = p;
996 p = p->parent;
997 }
998 if (p->right != child)
999 return p;
1000 else
1001 return NULL;
1002 }
1003}
1004
1005/*
1006 *@@ treePrev:
1007 * finds and returns the previous node in a tree.
1008 */
1009
1010TREE* treePrev(TREE *r)
1011{
1012 TREE *p,
1013 *child;
1014
1015 if ( (!r)
1016 || (r == LEAF))
1017 return NULL;
1018
1019 p = r;
1020 if (p->left != LEAF)
1021 return treeLast (p->left);
1022 else
1023 {
1024 p = r;
1025 child = LEAF;
1026 while ((p->parent)
1027 && (p->left == child))
1028 {
1029 child = p;
1030 p = p->parent;
1031 }
1032 if (p->left != child)
1033 return p;
1034 else
1035 return NULL;
1036 }
1037}
1038
1039/*
1040 *@@ treeBuildArray:
1041 * builds an array of TREE* pointers containing
1042 * all tree items in sorted order.
1043 *
1044 * This returns a TREE** pointer to the array.
1045 * Each item in the array is a TREE* pointer to
1046 * the respective tree item.
1047 *
1048 * The array has been allocated using malloc()
1049 * and must be free()'d by the caller.
1050 *
1051 * NOTE: This will only work if you maintain a
1052 * tree node count yourself, which you must pass
1053 * in *pulCount on input.
1054 *
1055 * This is most useful if you want to delete an
1056 * entire tree without having to traverse it
1057 * and rebalance the tree on every delete.
1058 *
1059 * Example usage for deletion:
1060 *
1061 + TREE *G_TreeRoot;
1062 + treeInit(&G_TreeRoot);
1063 +
1064 + // add stuff to the tree
1065 + TREE *pNewNode = malloc(...);
1066 + treeInsert(&G_TreeRoot, pNewNode, fnCompare)
1067 +
1068 + // now delete all nodes
1069 + ULONG cItems = ... // insert item count here
1070 + TREE** papNodes = treeBuildArray(G_TreeRoot,
1071 + &cItems);
1072 + if (papNodes)
1073 + {
1074 + ULONG ul;
1075 + for (ul = 0; ul < cItems; ul++)
1076 + {
1077 + TREE *pNodeThis = papNodes[ul];
1078 + free(pNodeThis);
1079 + }
1080 +
1081 + free(papNodes);
1082 + }
1083 +
1084 *
1085 *@@added V0.9.9 (2001-04-05) [umoeller]
1086 */
1087
1088TREE** treeBuildArray(TREE* pRoot,
1089 unsigned long *pulCount) // in: item count, out: array item count
1090{
1091 TREE **papNodes = NULL,
1092 **papThis = NULL;
1093 unsigned long cb = (sizeof(TREE*) * (*pulCount)),
1094 cNodes = 0;
1095
1096 if (cb)
1097 {
1098 papNodes = (TREE**)malloc(cb);
1099 papThis = papNodes;
1100
1101 if (papNodes)
1102 {
1103 TREE *pNode = (TREE*)treeFirst(pRoot);
1104
1105 memset(papNodes, 0, cb);
1106
1107 // copy nodes to array
1108 while ( pNode
1109 && cNodes < (*pulCount) // just to make sure
1110 )
1111 {
1112 *papThis = pNode;
1113 cNodes++;
1114 papThis++;
1115
1116 pNode = (TREE*)treeNext(pNode);
1117 }
1118
1119 // output count
1120 *pulCount = cNodes;
1121 }
1122 }
1123
1124 return (papNodes);
1125}
1126
1127/* void main(int argc, char **argv) {
1128 int maxnum, ct;
1129 recType rec;
1130 keyType key;
1131 statusEnum status;
1132
1133 maxnum = atoi(argv[1]);
1134
1135 printf("maxnum = %d\n", maxnum);
1136 for (ct = maxnum; ct; ct--) {
1137 key = rand() % 9 + 1;
1138 if ((status = find(key, &rec)) == STATUS_OK) {
1139 status = delete(key);
1140 if (status) printf("fail: status = %d\n", status);
1141 } else {
1142 status = insert(key, &rec);
1143 if (status) printf("fail: status = %d\n", status);
1144 }
1145 }
1146} */
Note: See TracBrowser for help on using the repository browser.