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

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

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