1 /* indent -blC -bli0 -npcs -ncs -i4 -bad -bap avl.c */
3 Copyright (c) 2008, The AROS Development Team. All rights reserved.
5 #Description: @AROS.Exec.AVL@
7 <chapter title="Exec AVL Trees">
9 <p>FIXME explain it</p>
15 #include <proto/exec.h>
18 /* don't think this works inside exec.library */
24 /* internal functions */
25 /* Re-Links the parent of subroot, properly handling the root-node.
26 The old parent is supplied in parent */
28 link_parent(struct AVLNode
**root
, const struct AVLNode
*scan
,
29 struct AVLNode
*subroot
, struct AVLNode
*parent
)
36 subroot
->avl_parent
= NULL
;
41 dir
= parent
->avl_link
[1] == scan
;
42 parent
->avl_link
[dir
] = subroot
;
43 subroot
->avl_parent
= parent
;
49 /* Perform a single rotation about next in the given direction.
50 Note that this will be inlined with hard-coded dirs */
51 static inline struct AVLNode
*
52 rotate_single(struct AVLNode
*scan
, struct AVLNode
*next
, const int dir
)
54 struct AVLNode
*subroot
= next
;
55 const int other
= dir
== 0;
57 D(printf("single %s about %p\n", dir
== 0 ? "left" : "right", subroot
));
59 scan
->avl_link
[other
] = next
->avl_link
[dir
];
60 if (next
->avl_link
[dir
] != NULL
)
61 next
->avl_link
[dir
]->avl_parent
= scan
;
62 next
->avl_link
[dir
] = scan
;
63 scan
->avl_parent
= next
;
68 /* Peform a double rotation about scan and then next in a given direction
69 Note that this will be in-lined with hard-coded dirs */
70 static inline struct AVLNode
*
71 rotate_double(struct AVLNode
*scan
, struct AVLNode
*next
, const int dir
)
73 struct AVLNode
*subroot
= next
->avl_link
[dir
];
74 const int other
= dir
== 0;
76 D(printf("double %s about %p\n", dir
== 0 ? "left" : "right", subroot
));
78 next
->avl_link
[dir
] = subroot
->avl_link
[other
];
79 if (subroot
->avl_link
[other
] != NULL
)
80 subroot
->avl_link
[other
]->avl_parent
= next
;
81 subroot
->avl_link
[other
] = next
;
82 scan
->avl_link
[other
] = subroot
->avl_link
[dir
];
83 if (subroot
->avl_link
[dir
] != NULL
)
84 subroot
->avl_link
[dir
]->avl_parent
= scan
;
85 subroot
->avl_link
[dir
] = scan
;
87 next
->avl_parent
= subroot
;
88 scan
->avl_parent
= subroot
;
93 /*#AROS_LH********************************************************************
97 AROS_LH3I(struct AVLNode
*, AVL_AddNode
,
99 AROS_LHA(struct AVLNode
**, root
, A0
),
100 AROS_LHA(struct AVLNode
*, node
, A1
),
101 AROS_LHA(AVLNODECOMP
, func
, A2
),
103 struct ExecBase
*, SysBase
, 142, Exec
)
105 Add a new node to an AVL tree.
108 Root - The root node of the tree to which the new node will be added.
109 Initially and if the tree is empty, this will be NULL.
111 Node - The new node to add. Any key information must alread be
114 Func - A key comparison function. It will be passed 2 nodes,
115 node1 and node2 to compare and must return <0, 0 or >0 to
116 reflect node1 < node2, node1 == node, or node1 > node2
120 NULL if the node was added to the tree, or a pointer to a node with the
121 same key which already exists in the tree.
124 AVL trees are balanced binary search trees. This implementation is
125 based on embedding the struct AVLNode within your own data object
126 and providing custom comparison functions wherever they are needed.
128 Two comparison functions are needed for different cases. It is entirely
129 up to the application as to how it interprets the nodes and compares
132 AVLNODECOMP is used to compare the keys of two nodes.
134 typedef LONG *AVLNODECOMP(const struct AVLNode *avlnode1,
135 const struct AVLNode *avlnode2);
138 AVLKEYCOMP is used to compare a key to a node.
140 typedef LONG *AVLKEYCOMP(const struct AVLNode *avlnode,
144 These functions must return the same sense for the same key values.
146 <0 if key of avlnode1 < key of avlnode2
147 if key of avlnode < key
148 0 if key of avlnode1 == key of avlnode2
149 if key of avlnode == key
150 >0 if key of avlnode1 > key of avlnode2
151 if key of avlnode < key
153 Since this function returns the existing node if the keys match,
154 this function can be used to efficiently add items to the tree or
155 update existing items without requiring additional lookups.
158 This is a fragment which counts the occurances of every word in a file.
159 Also note that this example embeds the struct AVLNode data at
160 the start of the structure, so simple casts suffice for translating
161 AVLNode to ExampleNode addresses.
169 static LONG ExampleNodeComp(const struct AVLNode *a1, const struct AVLNode *a2)
171 const struct ExampleNode *e1 = (const struct ExampleNode *)a1;
172 const struct ExampleNode *e2 = (const struct ExampleNode *)e2;
174 return strcmp(a1->key, a2->key);
177 static LONG ExampleKeyComp(const struct AVLNode *a1, AVLKey key)
179 const struct ExampleNode *e1 = (const struct ExampleNode *)a1;
182 return strcmp(a1->key, skey);
185 void CountWords(wordfile)
187 struct ExampleNode *node;
188 struct AVLNode *root = NULL, *check;
190 node = AllocMem(sizeof(struct ExampleNode), 0);
193 while (node->key = read_word(wordfile)) {
194 check = AVL_AddNode(&root, &node->avl, ExampleNodecomp);
197 struct ExampleNode *work = (struct ExampleNode *)check;
202 node = AllocMem(sizeof(struct ExampleNode), 0);
206 FreeMem(node, sizeof(struct ExampleNode));
212 AVL_FindNode(), AVL_FindNextNodeByKey(), AVL_FindPrevNodeByKey(),
213 AVL_RemNodeByAddress(), AVL_RemNodeByKey()
216 ******************************************************************************/
221 struct AVLNode
*next
= *root
;
222 struct AVLNode
*scan
;
223 struct AVLNode
*child
;
225 /* Simple case - empty tree */
229 node
->avl_link
[0] = node
->avl_link
[1] = node
->avl_parent
= NULL
;
230 node
->avl_balance
= 0;
234 /* find insertion point */
240 cmp
= func(scan
, node
);
242 return (struct AVLNode
*)scan
;
245 next
= scan
->avl_link
[dir
];
247 while (next
!= NULL
);
250 node
->avl_parent
= scan
;
251 scan
->avl_link
[dir
] = node
;
252 node
->avl_link
[0] = node
->avl_link
[1] = NULL
;
253 node
->avl_balance
= 0;
255 /* update balance factors */
258 LONG bal
= (dir
* 2 - 1) + scan
->avl_balance
;
259 struct AVLNode
*parent
;
260 struct AVLNode
*subroot
;
265 scan
->avl_balance
= bal
;
269 parent
= scan
->avl_parent
;
270 next
= scan
->avl_link
[1];
272 switch (next
->avl_balance
)
275 subroot
= rotate_double(scan
, next
, LEFT
);
277 if (subroot
->avl_balance
== 1)
279 scan
->avl_balance
= -1;
280 next
->avl_balance
= 0;
282 else if (subroot
->avl_balance
== -1)
284 scan
->avl_balance
= 0;
285 next
->avl_balance
= 1;
289 scan
->avl_balance
= next
->avl_balance
= 0;
292 subroot
->avl_balance
= 0;
295 subroot
= rotate_single(scan
, next
, LEFT
);
297 scan
->avl_balance
= next
->avl_balance
= 0;
301 link_parent(root
, scan
, subroot
, parent
);
305 parent
= scan
->avl_parent
;
306 next
= scan
->avl_link
[0];
308 switch (next
->avl_balance
)
311 subroot
= rotate_double(scan
, next
, RIGHT
);
313 if (subroot
->avl_balance
== -1)
315 scan
->avl_balance
= 1;
316 next
->avl_balance
= 0;
318 else if (subroot
->avl_balance
== 1)
320 scan
->avl_balance
= 0;
321 next
->avl_balance
= -1;
325 scan
->avl_balance
= next
->avl_balance
= 0;
328 subroot
->avl_balance
= 0;
331 subroot
= rotate_single(scan
, next
, RIGHT
);
333 scan
->avl_balance
= next
->avl_balance
= 0;
337 link_parent(root
, scan
, subroot
, parent
);
341 scan
->avl_balance
= bal
;
344 scan
= scan
->avl_parent
;
348 dir
= scan
->avl_link
[1] == child
;
358 /*#AROS_LH********************************************************************
362 AROS_LH2I(struct AVLNode
*, AVL_RemNodeByAddress
,
364 AROS_LHA(struct AVLNode
**, Root
, A0
),
365 AROS_LHA(struct AVLNode
*, Node
, A1
),
367 struct ExecBase
*, SysBase
, 143, Exec
)
369 Remove a given node from the tree.
372 Root - A pointer to a pointer to the root node of the tree.
374 Node - A struct AVLNode to remove. The node must be present
381 Removing a node may require multiple rebalancing steps
382 in the tree. Each step however runs in constant time
383 and no more than 1.44log(n) steps will be required.
386 See AVL_NextNodeByAddress(), AVL_PrevNodeByAddress()
391 AVL_AddNode(), AVL_FindNode(), AVL_NextNodeByAddress(),
392 AVL_PrevNodeByAddress()
395 ******************************************************************************/
399 struct AVLNode
*scan
;
400 struct AVLNode
*node
= (struct AVLNode
*)Node
;
401 struct AVLNode
**root
= (struct AVLNode
**)Root
;
404 if (node
->avl_link
[0] == NULL
)
406 if (node
->avl_link
[1] == NULL
)
408 if (node
->avl_parent
== NULL
)
410 /* removed last node */
417 scan
= node
->avl_parent
;
418 dir
= scan
->avl_link
[1] == node
;
419 scan
->avl_link
[dir
] = NULL
;
420 D(printf("removed leaf dir = %d\n", dir
));
425 if (node
->avl_parent
== NULL
)
427 /* removed root left-leaf node */
428 *root
= node
->avl_link
[1];
429 node
->avl_link
[1]->avl_parent
= NULL
;
434 /* removed a left-leaf */
435 scan
= node
->avl_parent
;
436 dir
= scan
->avl_link
[1] == node
;
437 scan
->avl_link
[dir
] = node
->avl_link
[1];
438 node
->avl_link
[1]->avl_parent
= scan
;
439 D(printf("removed left leaf dir =%d\n", dir
));
445 if (node
->avl_link
[1] == NULL
)
447 if (node
->avl_parent
== NULL
)
449 /* removed root right-leaf node */
450 *root
= node
->avl_link
[0];
451 node
->avl_link
[0]->avl_parent
= NULL
;
456 /* removed a right-leaf */
457 scan
= node
->avl_parent
;
458 dir
= scan
->avl_link
[1] == node
;
459 scan
->avl_link
[dir
] = node
->avl_link
[0];
460 node
->avl_link
[0]->avl_parent
= scan
;
461 D(printf("removed right leaf dir=%d\n", dir
));
466 /* removing a non-leaf node - swap it with a leaf node and 'remove' that instead */
467 struct AVLNode
*toremove
= (struct AVLNode
*)AVL_FindPrevNodeByAddress(Node
); // do we do prev/next based on balance factor? */
469 D(printf("removing non-leaf key ... %p\n", toremove
));
471 /* remove the leaf node */
472 scan
= toremove
->avl_parent
;
476 /* special case - immediate child of what we're removing */
477 toremove
->avl_link
[1] = node
->avl_link
[1];
478 if (node
->avl_link
[1] != NULL
)
479 node
->avl_link
[1]->avl_parent
= toremove
;
482 D(printf(" removed immediate child\n"));
486 dir
= toremove
->avl_parent
->avl_link
[1] == toremove
;
487 toremove
->avl_parent
->avl_link
[dir
] = toremove
->avl_link
[0];
488 if (toremove
->avl_link
[0] != NULL
)
489 toremove
->avl_link
[0]->avl_parent
= toremove
->avl_parent
;
491 /* swap it with the removed node */
492 toremove
->avl_link
[0] = node
->avl_link
[0];
493 if (node
->avl_link
[0] != NULL
)
494 node
->avl_link
[0]->avl_parent
= toremove
;
495 toremove
->avl_link
[1] = node
->avl_link
[1];
496 if (node
->avl_link
[1] != NULL
)
497 node
->avl_link
[1]->avl_parent
= toremove
;
498 D(printf(" removed distant child\n"));
500 toremove
->avl_balance
= node
->avl_balance
;
501 toremove
->avl_parent
= node
->avl_parent
;
502 if (node
->avl_parent
== NULL
)
505 node
->avl_parent
->avl_link
[node
->avl_parent
->avl_link
[1] ==
508 D(printf("removed key, tree is now:\n"));
509 D(dumptree(*root
, 0));
513 /* rebalance from 'scan' up */
516 int bal
= scan
->avl_balance
- (dir
* 2 - 1);
517 struct AVLNode
*next
;
518 struct AVLNode
*parent
;
519 struct AVLNode
*subroot
;
524 scan
->avl_balance
= bal
;
526 parent
= scan
->avl_parent
;
530 dir
= parent
->avl_link
[1] == scan
;
536 scan
->avl_balance
= bal
;
540 parent
= scan
->avl_parent
;
541 next
= scan
->avl_link
[1];
543 switch (next
->avl_balance
)
546 subroot
= rotate_single(scan
, next
, LEFT
);
547 scan
->avl_balance
= 1;
548 next
->avl_balance
= -1;
550 link_parent(root
, scan
, subroot
, parent
);
553 subroot
= rotate_single(scan
, next
, LEFT
);
554 scan
->avl_balance
= 0;
555 next
->avl_balance
= 0;
559 subroot
= rotate_double(scan
, next
, LEFT
);
561 if (subroot
->avl_balance
== 1)
563 scan
->avl_balance
= -1;
564 next
->avl_balance
= 0;
566 else if (subroot
->avl_balance
== -1)
568 scan
->avl_balance
= 0;
569 next
->avl_balance
= 1;
573 scan
->avl_balance
= 0;
574 next
->avl_balance
= 0;
577 subroot
->avl_balance
= 0;
582 dir
= link_parent(root
, scan
, subroot
, parent
);
590 parent
= scan
->avl_parent
;
591 next
= scan
->avl_link
[0];
593 switch (next
->avl_balance
)
596 subroot
= rotate_single(scan
, next
, RIGHT
);
597 scan
->avl_balance
= -1;
598 next
->avl_balance
= 1;
600 link_parent(root
, scan
, subroot
, parent
);
603 subroot
= rotate_single(scan
, next
, RIGHT
);
604 scan
->avl_balance
= next
->avl_balance
= 0;
608 subroot
= rotate_double(scan
, next
, RIGHT
);
610 if (subroot
->avl_balance
== -1)
612 scan
->avl_balance
= 1;
613 next
->avl_balance
= 0;
615 else if (subroot
->avl_balance
== 1)
617 scan
->avl_balance
= 0;
618 next
->avl_balance
= -1;
622 scan
->avl_balance
= 0;
623 next
->avl_balance
= 0;
626 subroot
->avl_balance
= 0;
631 dir
= link_parent(root
, scan
, subroot
, parent
);
641 } /* AVL_RemNodeByAddress */
643 /*#AROS_LH********************************************************************
647 AROS_LH3I(struct AVLNode
*, AVL_RemNodeByKey
,
649 AROS_LHA(struct AVLNode
**, root
, A0
),
650 AROS_LHA(AVLKey
, key
, A1
), AROS_LHA(AVLKEYCOMP
, func
, A2
),
652 struct ExecBase
*, SysBase
, 144, Exec
)
654 Looks up a node in the tree by key, and removes it if it
658 Root - A pointer to a pointer to the root node of the AVL tree.
660 key - The key to search for.
662 func - An AVLKEYCOMP function used to compare the key and nodes
666 If the key was present in the tree, then a pointer to the node
667 for that key. Otherwise NULL if no such key existed in the
671 See AVL_RemNodeByAddress().
678 AVL_AddNode(), AVL_RemNodeByAddress()
681 ******************************************************************************/
685 struct AVLNode
*node
;
687 node
= AVL_FindNode(*root
, key
, func
);
690 node
= AVL_RemNodeByAddress(root
, node
);
695 } /* AVL_RemNodeByKey */
697 /*#AROS_LH********************************************************************
701 AROS_LH3I(struct AVLNode
*, AVL_FindNode
,
703 AROS_LHA(const struct AVLNode
*, Root
, A0
),
704 AROS_LHA(AVLKey
, key
, A1
), AROS_LHA(AVLKEYCOMP
, func
, A2
),
706 struct ExecBase
*, SysBase
, 145, Exec
)
708 Find an entry in the AVL tree by key.
711 Root - The root of the AVL tree.
713 key - The key to search.
715 func - The AVLKEYCOMP key comparision function for this tree.
718 A pointer to the node matching key if it exists in the
719 tree, or NULL if no such node exists.
724 node = (struct ExampleNode *)AVL_FindNode(root, "aros", ExampleKeyComp);
726 printf(" `%s' occurs %d times\n", node->key, node->count);
731 AVL_AddNode(), AVL_RemNodeByAddress(), AVL_FindNextNodeByAddress(),
732 AVL_FindPrevNodeByAddress()
735 ******************************************************************************/
739 struct AVLNode
*node
= (struct AVLNode
*)Root
;
742 while (node
!= NULL
&& (cmp
= func((struct AVLNode
*)node
, key
)) != 0)
744 node
= node
->avl_link
[cmp
< 0];
747 return (struct AVLNode
*)node
;
752 /*#AROS_LH********************************************************************
756 AROS_LH1I(struct AVLNode
*, AVL_FindPrevNodeByAddress
,
758 AROS_LHA(const struct AVLNode
*, Node
, A0
),
760 struct ExecBase
*, SysBase
, 146, Exec
)
762 Perform an inverse-order traversal to the previous node in the tree.
765 Node - The current node. The node must be present in the tree.
768 The next-least node in the tree, or NULL if Node was already
769 the lowest valued node in the tree.
772 This implementation uses a parent pointer to avoid needing
773 a stack or state to track it's current position in the tree.
775 Although this operation is typically O(1), in the worst case it
776 iterate the full depth of the tree - approximately 1.44Log(N).
779 ... inverse-order traversal of all nodes
780 node = (struct ExampleNode *)AVL_FindLastNode(root);
782 printf(" %s\n", node->key);
783 node = (struct ExampleNode *)AVL_FindPrevNodeByAddress(node);
786 ... inverse-order traversal of all nodes - with safe deletion
787 node = (struct ExampleNode *)AVL_FindLastNode(root);
788 prev = (struct ExampleNode *)AVL_FindPrevNodeByAddress(node);
790 printf(" %s\n", node->key);
792 if (DELETE_NODE(node))
793 AVL_RemNodeByAddress(&root, node);
796 prev = (struct ExampleNode *)AVL_FindPrevNodeByAddress(node);
802 AVL_AddNode(), AVL_RemNodeByAddress(), AVL_FindLastNode()
805 ******************************************************************************/
809 const struct AVLNode
*node
= (const struct AVLNode
*)Node
;
810 const struct AVLNode
*prev
;
812 prev
= node
->avl_link
[0];
818 prev
= prev
->avl_link
[1];
827 node
= node
->avl_parent
;
829 while (node
!= NULL
&& node
->avl_link
[1] != prev
);
832 return (struct AVLNode
*)node
;
835 } /* AVL_FindPrevNodeByAddress */
837 /*#AROS_LH********************************************************************
841 AROS_LH3I(struct AVLNode
*, AVL_FindPrevNodeByKey
,
843 AROS_LHA(const struct AVLNode
*, root
, A0
),
844 AROS_LHA(AVLKey
, key
, A1
), AROS_LHA(AVLKEYCOMP
, func
, A2
),
846 struct ExecBase
*, SysBase
, 147, Exec
)
848 Find the node matching the key, or if such a node does not exist,
849 then the node with the next-lowest value.
852 Root - The root of the AVL tree.
854 key - The key to search.
856 func - The AVLKEYCOMP key comparision function for this tree.
859 A pointer to the struct AVLNode which matches this key, or
860 if that key is not present in the tree, the next lowest node.
861 Or NULL if key is lower than the key of any node in the tree.
864 This is only O(1.44log(n)) in the worst case.
871 AVL_AddNode(), AVL_FindNextNodeByAddress(), AVL_FindLastNode()
874 ******************************************************************************/
878 struct AVLNode
*node
= (struct AVLNode
*)root
;
879 struct AVLNode
*lesser
= NULL
;
882 while (node
!= NULL
&& (cmp
= func((struct AVLNode
*)node
, key
)) != 0)
886 node
= node
->avl_link
[cmp
< 0];
889 return (struct AVLNode
*)(node
!= NULL
? node
: lesser
);
892 } /* AVL_FindPrevNodeByKey */
894 /*#AROS_LH********************************************************************
898 AROS_LH1I(struct AVLNode
*, AVL_FindNextNodeByAddress
,
900 AROS_LHA(const struct AVLNode
*, Node
, A0
),
902 struct ExecBase
*, SysBase
, 148, Exec
)
904 Perform an in-order traversal to the next node in the tree.
907 Node - The current node. The node must be present in the tree.
910 The next-greatest node in the tree, or NULL if Node was already
911 the highest valued node in the tree.
914 This implementation uses a parent pointer to avoid needing
915 a stack or state to track it's current position in the tree.
917 Although this operation is typically O(1), in the worst case it
918 iterate the full depth of the tree - approximately 1.44Log(N).
921 ... in-order traversal of all nodes
922 node = (struct ExampleNode *)AVL_FindFirstNode(root);
924 printf(" %s\n", node->key);
925 node = (struct ExampleNode *)AVL_FindNextNodeByAddress(node);
928 ... in-order traversal of all nodes - with safe deletion
929 node = (struct ExampleNode *)AVL_FindFirstNode(root);
930 next = (struct ExampleNode *)AVL_FindNextNodeByAddress(node);
932 printf(" %s\n", node->key);
934 if (DELETE_NODE(node))
935 AVL_RemNodeByAddress(&root, node);
938 next = (struct ExampleNode *)AVL_FindNextNodeByAddress(node);
944 AVL_AddNode(), AVL_RemNodeByAddress(), AVL_FindFirstNode()
947 ******************************************************************************/
951 const struct AVLNode
*node
= (const struct AVLNode
*)Node
;
952 const struct AVLNode
*next
;
954 next
= node
->avl_link
[1];
960 next
= node
->avl_link
[0];
962 while (next
!= NULL
);
969 node
= node
->avl_parent
;
971 while (node
!= NULL
&& node
->avl_link
[1] == next
);
974 return (struct AVLNode
*)node
;
977 } /* AVL_FindNextNodeByAddress */
979 /*#AROS_LH********************************************************************
983 AROS_LH3I(struct AVLNode
*, AVL_FindNextNodeByKey
,
985 AROS_LHA(const struct AVLNode
*, Root
, A0
),
986 AROS_LHA(AVLKey
, key
, A1
), AROS_LHA(AVLKEYCOMP
, func
, A2
),
988 struct ExecBase
*, SysBase
, 149, Exec
)
990 Find the node matching the key, or if such a node does not exist,
991 then the node with the next-highest value.
994 Root - The root of the AVL tree.
996 key - The key to search.
998 func - The AVLKEYCOMP key comparision function for this tree.
1001 A pointer to the struct AVLNode which matches this key, or
1002 if that key is not present in the tree, the next highest node.
1003 Or NULL if key is higher than the key of any node in the tree.
1006 This is only O(1.44log(n)) in the worst case.
1013 AVL_AddNode(), AVL_FindNextNodeByAddress(), AVL_FindLastNode()
1016 ******************************************************************************/
1020 struct AVLNode
*node
= (struct AVLNode
*)Root
;
1021 struct AVLNode
*greater
= NULL
;
1024 while (node
!= NULL
&& (cmp
= func((struct AVLNode
*)node
, key
)) != 0)
1028 node
= node
->avl_link
[cmp
< 0];
1031 return (struct AVLNode
*)(node
!= NULL
? node
: greater
);
1034 } /* AVL_FindNextNodeByKey */
1036 /*#AROS_LH********************************************************************
1040 AROS_LH1I(struct AVLNode
*, AVL_FindFirstNode
,
1042 AROS_LHA(const struct AVLNode
*, Root
, A0
),
1044 struct ExecBase
*, SysBase
, 150, Exec
)
1046 Find the smallest node in an AVL tree.
1049 Root - The root node of the AVL tree.
1052 NULL if the tree is empty (i.e. Root is NULL), or the node
1053 which contains the least value in the tree as determined by
1054 the comparision function used to add the node.
1057 AVL trees are balanced but not minimal. This operation
1058 must iterate the full depth of the tree on one side -
1059 approximately 1.44Log(N).
1062 See AVL_FindNextNodeByAddress()
1067 AVL_AddNode(), AVL_FindNextNodeByAddress()
1070 ******************************************************************************/
1074 struct AVLNode
*node
= (struct AVLNode
*)Root
;
1077 while (node
->avl_link
[0] != NULL
)
1078 node
= node
->avl_link
[0];
1080 return (struct AVLNode
*)node
;
1083 } /* AVL_FindFirstNode */
1085 /*#AROS_LH********************************************************************
1089 AROS_LH1I(struct AVLNode
*, AVL_FindLastNode
,
1091 AROS_LHA(const struct AVLNode
*, Root
, A0
),
1093 struct ExecBase
*, SysBase
, 151, Exec
)
1095 Find the largest node in an AVL tree.
1098 Root - The root node of the AVL tree.
1101 NULL if the tree is empty (i.e. Root is NULL), or the node
1102 which contains the greatest value in the tree as determined by
1103 the comparision function used to add the node.
1106 AVL trees are balanced but not minimal. This operation
1107 must iterate the full depth of the tree on one side -
1108 approximately 1.44Log(N).
1111 See AVL_FindPrevNodeByAddress()
1116 AVL_AddNode(), AVL_FindPrevNodeByAddress()
1119 ******************************************************************************/
1123 struct AVLNode
*node
= (struct AVLNode
*)Root
;
1126 while (node
->avl_link
[1] != NULL
)
1127 node
= node
->avl_link
[1];
1129 return (struct AVLNode
*)node
;
1132 } /* AVL_FindLastNode */