a1200   NEWS   APPS   DOCS   ABOUT
Docs » Autodocs » exec.library » AVL_AddNode


       AVL_AddNode -- Add node to the tree (V45)


       result = AVL_AddNode( root, node, func )
D0 A0 A1 A2
struct AVLNode *AVL_FindNextNodeByKey(struct AVLNode **,
struct AVLNode *,


       The function will add the given node to the AVL tree in the correct
position. The correct position is determined by the compare function
which is also passed in and which defines relative value of nodes
by determining their "key" values and comparing them.
Note that the compare function works like strcmp() by returning
<0, 0, >0 results to define a less/equal/greater relationship.
Note that there is no arbitration for access to the tree. You
should use a SignalSemaphore if arbitration is required.


       root  - Address of(!) the root pointer(!) of the AVL tree.
Initially, the root pointer must be set to NULL, which
represents an empty AVL tree.
node - The node to add
func - The compare function to find the right position for
the node in the tree


       If the node could be added, NULL is returned.
If there is already a node in the tree that has the same key, the
pointer to that node be returned and the given node will not be


       There are a few things to remember about AVL trees. First, they
are binary balanced trees. You can expect O(log2(n)) performance
for adding, removing, and searching by key.
Second, the implementation does not care what kind of compare
functions you provide to the AVL functions, i.e., what sort order
you define.
To work with an AVL tree you need two compare functions:
AVLNODECOMP - Determines keys of two nodes and compares them
AVLKEYCOMP - Compares a node's key to a given key
The interpretation of the keys in these two functions must match.
If your compare functions are flawed, the AVL trees will not work.
The implementation does not compare keys or makes any assumption
about them. A key can be anything that fits into a 32 bit value,
even a pointer to the "true" key, whatever it may be.
Remember that each key in a tree must be unique. If you
want to add elements with identical keys, you could use, e.g.,
the memory address of the element as "second level" key to ensure
unique keys for insertion into the tree. In that case, however,
it is obviously not possible to retrieve the node by a single key.
Also, remember that a struct AVLNode can be embedded anywhere
within your element's structure.
The example below illustrates all the points made above. If you
don't need second level keys or embedded struct AVLNode's, you
can simplify things.
Finally, the implementation is not recursive and you don't have
to provide a huge stack even when using AVL functions on
huge trees.


       struct Element
struct Node el_Node; /* Normal maintenance */
UWORD el_pad;
ULONG el_SortKey; /* Bringing order into things ... */
struct AVLNode el_AVLNode; /* Fast access */
ULONG el_Content; /* Magic private content */
LONG ASM AVLNodeComp(REG(a0) struct AVLNode *avlnode1,
REG(a1) struct AVLNode *avlnode2)
struct Element *el1, *el2;
LONG res;
el1 = ElementStart(avlnode1);
el2 = ElementStart(avlnode2);
res = (LONG)(el1->el_SortKey - el2->el_SortKey);
if(res == 0)
// For identical keys, use, e.g., the address as 2nd key
res = (LONG)((ULONG)avlnode1 - (ULONG)avlnode2);
} /* if */
} /* AVLNodeComp */
static LONG ASM AVLKeyComp(REG(a0) struct AVLNode *avlnode,
REG(a1) AVLKey avlkey)
struct Element *el;
LONG res;
el = ElementStart(avlnode);
res = (LONG)(el->el_SortKey - (ULONG)avlkey);
} /* AVLKeyComp */
/* Initially, the tree must be marked as empty! */
avlroot = NULL;
if(AVL_AddNode(&avlroot, &el->el_AVLNode, AVLNodeComp))
// This should not happen because our AVLNodeComp()
// ensures that each node's key is unique by using its address
// If it happens it means that we are trying to readd a
// node that already has been added in this case.
} /* if */



AVL_FindLastNode(), AVL_FindFirstNode(), AVL_RemNodeByKey(), AVL_RemNodeByAddress(), AVL_FindNextNodeByKey(), AVL_FindNextNodeByAddress()


E-mail: Use this if you want a message if you get a response, will not be shown.
Select correct short for:

The Black Lotus



$VER: d0.se 1.14 Copyright © 2011-2020 Tobias Geijersson support at d0 dot se