Introduction

An AVL tree can be converted to a "LAT" which is a linked-list-AVL-tree. In this transient form the tree is not a valid AVL tree; this form is used in the Merge operation, and can be created to speed in-order input of large trees. The details of LAT format are not public.

Configuration

AE_ELEMENT

a typedef for the type to be stored in the tree

nilAE

a nil pointer to an AE_ELEMENT entry (for "not found")

AECmp(pAEGiven)

a function to compare a given AE_ELEMENT to the "current" one during an insert/search

AEPrint(pAEOut)

a function to output an AE_ELEMENT for debugging

AEInit(pAENew)

a function to init any new AE_ELEMENT nodes built

AEMerge(pAELeft, pAERight)

a function called to select between two AE_ELEMENT during a merge should return an int to select a merge action

• < 0 to take the left argument next in the list
• == 0 to call AESame on the right argument (& free it)
• > 0 to take the right argument next in the list

AESame(pAESame)

a function to prepare an element from the right list during an AVMerge for "deletion" After this call, AVMerge will free the memory and skip this element.

AEFree(pAEFree)

a function to prepare the selected AE_ELEMENT for deallocation by a call to AVFree (AVFree will call free for you)

AEDelete(pAEDel)

a function to prepare the selected AE_ELEMENT for deallocation by a call to AVDelete (AVDelete will call free for you)

AENotfound()

a function to call when an AVDelete fails

Squeak(pchErr)

as always is a routine to process errors (as yyerror() does for lex(1)). Called from "AVVerifiy" only (currently).

The elements above should be declared in a configuration.h file and included before "avl.h" in any file that makes use of the AVL code {see "avltest.h"}.

Provides

AVL *pAVRoot;

AVL *sbpAVList[MAXTABLE];

A nil AVL tree is provided as "nilAV", so

AVL *pAVRoot = nilAV;

A function "AVInit" can be passed a pointer to an AVL pointer to make this assignment (for compatibility with other MICE routines requiring Init functions). Example:

AVInit(& pAVRoot);

Inserting/Searching in a tree is accomplished by

1. notify "AECmp" what the current key is {how this is done is not AVLs concern},
2. call "AVInsert(& pAVRoot, 1)" if new data is to added to the tree; else "AVInsert(& pAVRoot, 0)" for just search.
3. use "AVpAEInsert", the inserted element

The function "AEInit" will be called to initialize any new nodes in the tree (if the record already exists "AEInit" is not called); AVpAEInsert is set to the located data (in either case). "AVInsert" returns non-zero if the tree grew. Example:

pKECmp = gets(sbKey);
(void) AVInsert(& pAVFile1, 0);
AEReport(AVpAEInsert);
...

Deleting from the tree is just as easy :-)

1. notify "AECmp" what element we are deleting
2. call "AVDelete(& pAVRoot)"
3. "AENotfound" will be called if no such key can be found
4. "AEDelete" will be called if the key is found
5. AVDelete will free the memory for you

pKECmp = "zap_me";
AVDelete(& pAVRoot);

To scan every node in the tree in order the user can call "AVScan". This function will call a user supplied function on every AE_ELEMENT in tree, or stop when any user function returns non-zero. "AVScan" returns either zero for "not found" or the non-zero return code from some (user) call. Example:

(void) AVScan(pAVRoot, puts)

To reclaim the memory used by a tree (and destroy the tree) the user may call "AVFree" which will recursively delete all nodes in the tree. "AEFree" is called to prepare each AE_ELEMENT node for being free-d. Example:

 AVFree(pAVRoot);
pAVRoot = nilAV;

The typedef "AVCARDINAL" is used to declare counts of AVL nodes. It is always unsigned, but may be size adjusted for different applications or for machine speed optimization. AVCARDINAL is returned by "AVCount", and is used in the arguments of "AVConstruct" and "AVMerge".

The "AVCount" function returns the number of elements in an AVL tree; this is most useful before a call to "AVConstruct", and even works if the tree is currently "LAT". This is the only AVL routine other than "AVConstruct" that is guaranteed not to drop core if this is true! Example:

printf("%d", AVCount(pAVTemp));

The user should use "AVBegin", "AVEnd", "AVStep" to build an AVL tree from any pre-sorted input source. "AVBegin" will return non-zero if any pending in-order input is happening {bug}. "AVStep" will return an AE_ELEMENT pointer to the next node in the tree, the user should fill in the key info. "AVEnd" returns the root of the tree and closes the LAT insertion.
Example:

register AE_ELEMENT *pAE;
(void) AVBegin();
while (NULL != gets(sbBuf)) {
	pAE = AVStep();
	MyInit(pAE, sbBuf);
}
pAVRoot = AVEnd();

For some cases, it is easy to build a 100% efficient AVL tree from a sorted LAT list; "AVConstruct" does the dirty work of doing this. The user usually will use "AVBegin", "AVEnd", "AVStep" to do this. "AVConstruct" is passed a LAT list of AVL nodes, a count of the nodes it is to build a balanced tree from (type AVCARDINAL), and an address to hang the new tree from. It returns the the node remaining on the LAT list (or nilAV). [Some randomness is used to reduce any chance of a deliberate worst-case tree construction :-)]
Example:

(void) AVConstruct(pAVLat, iCount, & pAVRoot)

The function "AVLat" efficiently turns the bushy AVL tree in a linked-list. In this form "AVConstruct" can be called to build a perfect tree. The user will (almost) never call this routine, the only time it is suggested is when the tree to be re-constructed is going to be searched many, many times without changing.
Example:

AVCARDINAL n;

n = AVCount(pAVRoot);
(void) AVLat(pAVRoot, & pAVTemp);
(void) AVConstruct(pAVTemp, n, & pAVRoot);

To merge two AVL trees into one (destroying both subtrees) we use "AVMerge". See "AEMerge" above. AEMerge-s third parameter is a pointer to an AVCARDINAL. It is used to record the number of elements in the resulting tree, if it is (AVCARDINAL *)0 it will be ignored. The first two arguments are the component trees (note that the first one has "precedence" over the second by MICE convention). The function "AESame" should be defined to handle return codes of 0 from "AEMerge".
Example:

/* merge pAV_A, pAV_B */
pAV_A = AVMerge(pAV_A, pAV_B, & iCountA)
pAV_B = nilAV;
iCountB = 0;

If the user believes that the AVL routines have produced an invalid tree "AVVerify" may be called to confirm or deny it. "AVVerify" returns the maximum depth of the tree. If an error is found in the tree "Squeak" will be called with a (char *) to indicate the error:

	AVVerify(pAVRoot);

For better debugging an AVL tree may be displayed via "AVPrint"; "AEPrint" is called to output each nodes name. "-", "/", and "\" are used to display balance factors. "~" is used to display an empty (sub)tree.
Example:

	AVPrint(pAV);
	putchar('\n');

	k=0\(e=1-(c=6,i=3),s=5-(n=4\(~,o=7),v=2/(t=8,~)))

C Identifiers

AVL

A typedef to declare AVL trees as AVL *pAVRoot;.

void

AVInit(ppAV)

Make an AVL tree empty.

AVL **

AVConstruct(pAVLat, iCount, ppAVRoot)

Build an AVL tree from the LAT structure.

AVCARDINAL

AVCount(pAV)

Return the number of elements in an AVL tree.

int

AVDelete(ppAVRoot)

Delete a node from an AVL tree.

int AVFree(pAVRoot)

Delete every node in a tree.

int

AVInsert(ppAVRoot)

Add a new element to an AVL tree.

AVL **

AVLat(pAVCur, ppAVRet)

Squish an AVL tree to a LAT list.

AVL *

AVMerge(pAVOne, pAVTwo, pi)

Merge two AVL trees (destroy both component trees in the process).

int

AVPrint(pAV)

Terse description of the AVL tree to stdout.

int

AVScan(pAVRoot, pFunc)

Visit every node in an AVL tree in-order.

int

AVBegin()

Begin construction of an AVL tree from a sorted list.

AVL *

AVEnd()

End sorted list construction.

AE_ELEMENT *

AVStep()

Move to next element in sorted list insertion.

int

AVVerify(pAVRoot)

Verify that the tree is an AVL tree and return depth.

To Do List

See also

$Id: avl.html,v 6.9 2012/08/30 14:53:51 ksb Exp $