This module contains a template to build an AVL-tree. More...
Functions | |
| static AVL_NODE | AVL_Search (AVL_NODE root, AVL_KEYT skey, AVL_USER user) |
| Find a key on the tree. | |
| static AVL_NODE | AVL_Insert (AVL_NODE *root, AVL_PATH *path, AVL_NODE node, AVL_KEYT key, AVL_USER user) |
| Inserts a new node with the given key to the tree. | |
| static AVL_NODE | AVL_Delete (AVL_NODE *root, AVL_PATH *path, AVL_KEYT key, AVL_USER user) |
| Deletes the given node from the tree. | |
| static void | AVL_Walk (AVL_NODE root, AVL_PATH *path, AVL_USER user) |
| Initialises a tree walk. | |
| static AVL_NODE | AVL_Step (AVL_PATH *path, AVL_USER user) |
| One step on the tree walk. | |
| static AVL_NODE | AVL_First (AVL_NODE root, AVL_USER user) |
| Returns the node with the smallest key. | |
| static AVL_NODE | AVL_Last (AVL_NODE root, AVL_USER user) |
| Returns the node with the largest key. | |
| static AVL_NODE | AVL_Next (AVL_NODE root, AVL_PATH *path, AVL_KEYT refk, AVL_USER user) |
| Finds the node with smallest key that is larger than the given key. | |
This module contains a template to build an AVL-tree.
The AVL tree is a self-balancing binary search tree, named after Adelson-Velskiy and Landis, the Russian mathematicians who invented it in 1962. It allows you to keep data in a sorted manner. Finding, inserting and deleting a node all take O( log2( N ) ) time even in worst case, therefore the AVL tree is an efficient tool to implement small "databases" in embedded systems.
This implementation is actually a template. It does not assume much about your information and how you store it. In fact, it is not a usable C implementation on its own, you must write small wrapper functions that will be the actual API for the handling of the tree and you need macros or small inline functions to access your chosen data format. However, all the algorithmic working is in the library, so you do not have to know how AVL trees work to use it.
Nodes are ordered by a key. The keys must be unique, the same key can not be on the tree multiple times. The routines will refuse to insert the same key twice.
Apart from this key and your own data, your nodes need to store three more pieces of information that the AVL tree uses.
The first is an integer type that must be wide enough to store the height of the tree.
The other two information fields in your node are references to two other nodes (the subtrees under this node). Note the word 'reference'. Normally these would be pointers. However, the library does not assume that you have a tree that is built from node structures stored in memory. The references can be pointers, but it is not a strict requirement. The importance of this will be explained later.
To use this template you do the following:
misc/avl.h header.misc/avl.hmisc/avl.h.This is what you have to define before you include misc/avl.h:
AVL_NODE.==).AVL_NULL.NULL but if your AVL_NODE is some other type, then you have to find a suitable value of that type which can never be a valid reference to a node.AVL_KEYT.AVL_KEYT objects are just passed around, only one function does really have to know what to do with a key and that function is written by you.AVL_PLEN.AVL_USER.static, possibly inline functions that extract node information.AVL_GET_L(), AVL_GET_R(), AVL_GET_H(). They receive a node reference and return the node's left subtree, right subtree and height, respectively.static, possibly inline functions that set node fields.AVL_SET_L(), AVL_SET_R(), AVL_SET_H(). They receive a node reference and an other parameter. They should set the node's left tree reference, right tree reference and height, respectively, to the operand they receive.static, possibly inline function to compare keys.AVL_CMP() and it receives a node reference and a key reference. It then returns an integer that is positive, negative or zero depending on whether the node's key is, respectively, less than, greater than or equal to the key.The prototype of these functions is the following:
static AVL_NODE AVL_GET_L( AVL_NODE node, AVL_USER user ); static AVL_NODE AVL_GET_R( AVL_NODE node, AVL_USER user ); static unsigned AVL_GET_H( AVL_NODE node, AVL_USER user ); static void AVL_SET_L( AVL_NODE node, AVL_NODE tree, AVL_USER user ); static void AVL_SET_R( AVL_NODE node, AVL_NODE tree, AVL_USER user ); static void AVL_SET_H( AVL_NODE node, unsigned height, AVL_USER user ); static int AVL_CMP( AVL_NODE node, AVL_KEYT refk, AVL_USER user );
If the functions are simple, you should specify them as inline, or, if you prefer macros over inlined functions, you can use those instead of functions.
After definig these, you include misc/avl.h. That file, in turn, defines a type and a bunch of functions. The functions are the basic AVL tree managing functions. You can then use them to implement your own API functions with very little code. Most importantly, it is your responsibility to allocate and prepare new nodes, to handle the information in the node and to deallocate deleted nodes. Furthermore, if you run in a multitasking environment, then the protection from simultaneous access is on your shoulders too.
You also have to provide a workspace for the tree handling routines. That workspace is a structure that has the type of AVL_PATH. Among a couple of other fields it contains an array of AVL_NODE references. The size of the array is the value you defined by the AVL_PLEN macro. The following table shows you the minimum value of AVL_PLEN for a given maximum value of nodes.
The first column contains the maximum number of nodes on your tree, the second column contains the minimum value that you should use when you define AVL_PLEN and the third column is the minimum width, in bits, of the height field in your node (see the examples).
N P W N P W N P W
1 2 1 2,582 16 4 2,178,307 30 5
3 3 2 4,179 17 5 3,524,576 31 5
6 4 2 6,763 18 5 5,702,885 32 5
11 5 3 10,944 19 5 9,227,463 33 6
19 6 3 17,709 20 5 14,930,350 34 6
32 7 3 28,655 21 5 24,157,815 35 6
53 8 3 46,366 22 5 39,088,167 36 6
87 9 4 75,023 23 5 63,245,984 37 6
142 10 4 121,391 24 5 102,334,153 38 6
231 11 4 196,416 25 5 165,580,139 39 6
375 12 4 317,809 26 5 267,914,294 40 6
608 13 4 514,227 27 5 433,494,435 41 6
985 14 4 832,038 28 5 701,408,731 42 6
1,595 15 4 1,346,267 29 5 1,134,903,168 43 6
Now that you defined everything and the library also defined everything, you can write your API functions. These will use the functions provided by the misc/avl.h file. They are formally specified by the function specification section, so that's not repeated here.
A little explanation is in order with regards to that mysticism about references instead of pointers, bit-width of integers and the obscure user parameter of every function. There are several issues that warrant all that magic. Instead of giving you the verbiage about them, you will find some example code below that shows you how to use them. Hopefully these will make it clear why the cruft is there. Note that although the examples seem quite long, most of it is explanatory comments. The actual code you have to write is just a few tens of lines.
/* * This example shows a very simple implementation of an AVL tree. * Simplicity is the key. We assume a proper operating system with * a heap, unlimited memory and we provide minimal functionality. * We use integer keys. */ /****************************************************************************/ /* The following would go into our header file, called tree.h */ /****************************************************************************/ #ifndef _TREE_H #define _TREE_H /* * This is our node structure */ typedef struct s_tree { // AVL tree related data struct s_tree *left; struct s_tree *right; int height; // The integer key int key; // Then all the application dependent information // that is associated with the key. ... } MYDATA; /* * Initialise the tree */ void MyDataInit( void ); /* * Inserts a new key to the tree, returns the pointer to * the new structure that has been created and inserted * onto the three. If the key is already on the tree, then * it returns NULL. */ MYDATA *MyDataInsert( int key ); /* * Finds a node on the tree with the given key. * Returns the node pointer or NULL if the key is not found. */ MYDATA *MyDataFind( int key ); /* * Deletes the given key from the tree. */ void MyDataDelete( int key ); #endif /****************************************************************************/ /* This is the implementation C file */ /****************************************************************************/ #include <malloc.h> // System malloc #include "tree.h" // The include file above /* * What we need from the templates */ #define AVL_USE_DELETE // We will use the node deletion feature /* * Define what the templates need */ typedef MYDATA *AVL_NODE; // Define the node reference type typedef int AVL_KEYT; // Define the key reference type #define AVL_USER int // We won't use it, but must define it anyway #define AVL_PLEN 32 // We're OK up to 5 million nodes #define AVL_NULL NULL // We use pointers, so AVL_NULL is NULL /* * Define the getting functions. We decided to use macros. * We do not use the user parameter but of course it should * be defined as a macro argument. */ #define AVL_GET_L( node, user ) node->left #define AVL_GET_R( node, user ) node->right #define AVL_GET_H( node, user ) node->height /* * Define the setting functions. Again, they are macros. */ #define AVL_SET_L( node, tree, user ) node->left = tree #define AVL_SET_R( node, tree, user ) node->right = tree #define AVL_SET_H( node, newh, user ) node->height = newh /* * Define the comparison function. It is defined as a function. */ static inline int AVL_CMP( AVL_NODE node, AVL_KEYT key, AVL_USER user ) { (void) user; // We don't use it if ( node->key > key ) return +1; if ( node->key < key ) return -1; return 0; } /* * Now that we defined everything, we get the templates */ #include <misc/avl.h> /* * This is where our implementation start. First, we need the root of * the tree and the workspace for the templates. */ static AVL_NODE root; static AVL_PATH work; /* * Tree initialisation */ void MyDataInit( void ) { // All we have to do is to make the root empty root = NULL; } /* * Find a node by a key */ MYDATA *MyDataFind( int key ) { // The functionality is already provided by the template. // All we do is to also pass the tree root and 0 for the // unused user parameter. return AVL_Search( root, key, 0 ); } /* * Insert a new key. We return a pointer to the new node. * We return NULL if the key is already on the tree. */ MYDATA *MyDataInsert( int key ) { MYDATA *node; MYDATA *temp; // Allocate a structure. In real code we'd check the return // value but now we simply assume that malloc() can't fail. node = malloc( sizeof( MYDATA ) ); // Now we insert it to the tree. // We get back AVL_NULL if it went OK. Any other value // indicates that the key is already on the tree. temp = AVL_Insert( &root, // Pointer to the root pointer &work, // Workspace node, // The new node to insert key, // The key for the node 0 ); // Unused user data if ( temp != AVL_NULL ) { // The key is already on the tree // Release the allocated memory and report error free( node ); return NULL; } else { // The insertion was successful. // We have to fill the key field and return the new node. node->key = key; return node; } } /* * Delete a key from the tree. * We release the structure here, assuming that no other user data * fields need freeing (i.e. your node does not countain pointers * to malloc()-ed memory). */ void MyDataDelete( int key ) { MYDATA *node; // The functionality is already provided, we just pass the // additional parameters. node = AVL_Delete( &root, // Pointer to the root pointer &work, // Workspace key, // The key to delete 0 ); // Unused user parameter if ( node ) { // The key was found and the node was removed from // the tree. We just release the associated memory. free( node ); } else { // The key was not found on the tree. We have nothing to do. ; } }
/* * In this example we assume that we have very limited memory. * The example demonstrates a real-life problem which was solved the * way described below. In this example header files and and other * niceties are omitted, only the actual solution is shown. * * The situation: * An application running on an NXP LPC23xx microcontroller. * The chip has 16K general purpose RAM. Furthermore, it has * an Ethernet controller and a USB controller, neither of which * is used by the application. The USB has a private 8K RAM block * which can be used as general memory if the USB is not in use. * The same is true for the Ethernet block, except that it has * 16K RAM. * * The application has to store information about some objects. * The max number of objects is TBD, but it must be at least 1000. * The unique key is 5 bytes. The application related data (on top * of the key) is 16 bytes. * * The "database" is fairly often changed, thus something that is fast * to insert, delete and look up nodes is needed. The AVL tree meets * these requirements. * * However, if the tree needs 2 pointers (4 bytes each) plus 1 byte * height plus 5 bytes key plus 16 bytes application data, then the * data structure is 30 bytes long. That will be rounded up to 32 bytes * by the compiler due to alignment requirements, so it would take 32K * to store the data. That would leave 8K for the rest of the application, * which is a bit tight. Naturally, the 16 bytes data plus the 5 bytes * key can't be saved. However, the 9 bytes AVL administrative info seems * to be a lot (almost 30% of the node size). Every byte saved in a node * is roughly an extra kilobyte for the rest of the code. * * The solution is: * * 1. We realise that since we use pre-allocated memory to store * the nodes, even if we use some malloc()/free() we will allocate * from an array of nodes. * * 2. We also realise that since we use an array, we can split * nodes and store the parts in separate arrays, since the * array index links the node fragments at no extra cost. * * Therefore, we could store the 16 byte application data in one array, * the key and the node administration in an other. The 16 byte data * consumes 16K RAM: a nice fit for the Ethernet RAM. Now if we could * pack the rest (the key and the AVL tree administrative data) into * the USB RAM somehow, that would leave the 16K general purpose RAM * completely free. Since the USB RAM is 8K, we have 8 bytes per node. * The key itself is 5 bytes. Thus, we have 3 bytes to store two node * references and the tree height. Currently we need 9 bytes for that. * So, how do we cram 9 bytes into 3? * * The rest of the solution is: * * 3. The AVL library uses node references and not pointers. We can use * array indices instead of pointers. Using unsigned short indices * decreases our memory consumption from 4+4+1=9 to 2+2+1=5 bytes. * * 4. We only have to store 1000 nodes. A 1000 element array index is * only 10 bits. If we define the max number of nodes to 1023 (thus * exceeding the minimal requirement - payrise in order!), reserving * one value for the NULL reference, we could pack the two references * into 2*10 bits. 20 bits can be stored in 3 bytes, plus the byte for * the height of the subtree: we're down to 4 bytes AVL info per node. * * 5. Consulting the table in the AVL documantation reveals that for a * tree with 1023 nodes the height information can be stored in 4 bits. * Thus, we have two 10-bit references and a 4-bit height. All together * 24 bits, that is, 3 bytes. We managed to fit the key plus the AVL * information into 8 bytes, the problem has been solved. * * Below is the implementation. Note that the data structure stored in * the Ethernet RAM and the associated access functions are not shown. * The example is only about the handling of the key plus AVL info, * stored in the USB RAM. The functions all return an array index, * that can be used to access the data in the Ethernet RAM. */ /* * Define an array of 1024 elements of 8 bytes each that is * in the USB RAM block. We define a pointer to 8 byte objects * and initialise it to the USB RAM's base address. */ static unsigned char (* const array)[ 8 ] = (void *) USB_RAM_ADDRESS; /* * We will store the information in the 8 bytes as follows: * The first 5 (0-4) bytes are the key. Byte 5 will be the lower * 8 bits of the left reference, byte 6 will store the lower 8 bits * of the right reference. The last byte has the height in its top * 4 bits, then the next two bits store the upper two bits of the * left reference while the least significant two bits will hold the * upper two bits of the right reference. We define the node type * and the functions accordingly. */ typedef int AVL_USER; // We don't use it typedef int AVL_NODE; // It is an index, actually typedef char *AVL_KEY; // Pointer to the key #define AVL_PLEN 15 // As per the size table /* * We have to define the AVL_NULL value. When working with arrays, * one would instinctively choose the array size as the NULL value, * since the indices go from 0 to N-1. However, we have memory to * store 1024 elements and we only store 1023 of them. Thus, we can * use 0 as the NULL value and index the array from 1 to 1023. Since * comparison against 0 is usually more efficient than comparison * against an arbitrary number, this choice gives us a slight speed * (and code size) advantage. */ #define AVL_NULL 0 /* * We tell the AVL template that we need deletion */ #define AVL_USE_DELETE /* * GET functions */ static AVL_NODE AVL_GET_L( AVL_NODE node, AVL_USER user ) { // If you use -W -Wall -Werror (as you should!), gcc gives you an // 'unused variable' error for unused parameters. Casting them to // void is using them without generating any code, so gcc is happy // and we're happy too. It also indicates to other people that you // intentionally ignored a function argument. (void) user; // The low 8 bits are in byte 5, the upper 2 bits are bits 3:2 in byte 7 return array[ node ][ 5 ] | ( ( array[ node ][ 7 ] & 0x0c ) << 6 ); } static AVL_NODE AVL_GET_R( AVL_NODE node, AVL_USER user ) { // The low 8 bits are in byte 6, the upper 2 bits are bits 1:0 in byte 7 (void) user; return array[ node ][ 6 ] | ( ( array[ node ][ 7 ] & 0x03 ) << 8 ); } static unsigned AVL_GET_H( AVL_NODE node, AVL_USER user ) { // The height is in bits 7:4 of byte 7 (void) user; return array[ node ][ 7 ] >> 4; } /* * SET functions, the in same fashion as the getters. */ static void AVL_SET_L( AVL_NODE node, AVL_NODE tree, AVL_USER user ) { array[ node ][ 5 ] = tree; array[ node ][ 7 ] &= 0xf3; array[ node ][ 7 ] |= ( tree >> 8 ) << 2; } static void AVL_SET_R( AVL_NODE node, AVL_NODE tree, AVL_USER user ) { array[ node ][ 5 ] = tree; array[ node ][ 7 ] &= 0xfc; array[ node ][ 7 ] |= tree >> 8; } static void AVL_SET_R( AVL_NODE node, unsigned height, AVL_USER user ) { array[ node ][ 7 ] &= 0x0f; array[ node ][ 7 ] |= height << 4; } /* * The comparison function */ static int AVL_CMP( AVL_NODE node, AVL_KEYT refk, AVL_USER user ) { // We have to compare two 5-byte keys. The address of the key of a // node is actually the address of the node itself, since the first 5 // bytes of a node form the key. Furthermore, the memcmp() function // in the C library does what we need, so we have not much to do. return memcmp( array[ node ], refk, 5 ); } /* * Get the template */ #include <misc/avl.h> /* * Define the free node list, the root and the workspace. */ static int free; static int root; static AVL_PATH work; /* * Init * We know that our nodes are on word boundaries, thus it is safe to cast * a node address to a pointer to short. Therefore, we can build a singly * linked list of free nodes. Initially all nodes are free. So, each node * should contain an index 1 more than its own. The last free node, which * has the index of 1023, should contain AVL_NULL, i.e. 0 as its next. * We set the free node index to the first node in the chain, i.e. 1. */ void MyDataInit( void ) { int i; for ( i = 1 ; i < 1023 ; i++ ) *((unsigned short *) array[ node ]) = i + 1; *((unsigned short *) array[ 1023 ]) = AVL_NULL; free = 1; root = AVL_NULL; } /* * Search for a key. * The function returns the index or 0 if the key is not found. */ int MyDataSearch( const char key[ 5 ] ) { // The AVL_Search() function does everything we need. Note that // we have to cast the key to AVL_KEYT. Although AVL_KEYT is // actually char * and the key is a character array, the cast // is needed because with -W -Wall gcc complains about the // const qualifier being omitted when we pass the key. The // explicit cast from const char * to char * keeps gcc happy. return AVL_Search( root, (AVL_KEYT) key, 0 ); } /* * Insert a new node. * We return the index or 0 if the key is already on the tree * and -1 if we ran out of nodes. */ int MyDataInsert( const char key[ 5 ] ) { AVL_NODE node; if ( free == AVL_NULL ) { // No free node, report error return -1; } // Allocate a node node = free; free = *((unsigned short *) array[ node ]); // Attempt insertion if ( AVL_Insert( &root, node, (AVL_KEYT) key, 0 ) != AVL_NULL ) { // The key is already on the tree. Release the node and // report error. Since the node was not changed by the // AVL_Insert routine, it is enough to restore free. free = node; return 0; } // The insertion was successful. Copy the key into the node and // return the index. The address of the key in the node is the // address of the node itself as the first 5 bytes of the node // contain the key. memcpy( array[ node ], key, 5 ); return node; } /* * Delete a key. * If succeeded, then the index is returned. If the key was not on * the tree, 0 is returned. */ int MyDataDelete( const char key[ 5 ] ) { AVL_NODE node; node = AVL_Delete( &root, &work, (AVL_KEYT) key, 0 ); if ( node == AVL_NULL ) { // The key was not on the tree return 0; } // The key was deleted. Put the node back to the // free list and return the index. *((unsigned short *) array[ node ]) = free; free = node; return node; }
/* * In this example we will use the user field. * We build an associative array. It will pair strings and * integers. You can look up a string by the integer and * vice versa. For the sake of simplicity we don't care about * memory now, we assume that we have malloc() and free(). * * We actually build two trees, one for the strings and one for * the integers. They are linked through the common node that * holds the data for both. We will use the user parameter to * distinguish between the two trees. * * We don't detail our own header, it simply contains the prototypes * for the API functions. This is the C implementation file. */ #include "our_API_protos.h" #include <string.h> #include <malloc.h> /* * Define the node type */ typedef struct s_node { struct s_node *int_l; // Integer tree left subtree struct s_node *int_r; // Integer tree right subtree unsigned int_h; // Integer tree height int int_k; // Integer tree key struct s_node *str_l; // String tree left subtree struct s_node *str_r; // String tree right subtree unsigned str_h; // String tree height const char *str_k; // String tree key } *AVL_NODE; /* * The key type is int. When we have to pass the string pointer as * key, it should be cast to an int. If the pointer type is wider * than the int type, you could do it the other way around, define * AVL_KEYT to be a pointer and cast the int to a pointer. */ typedef int AVL_KEYT; /* * The user type will be an int */ typedef int AVL_USER; /* * Since we use pointers, AVL_NULL is NULL */ #define AVL_NULL NULL /* * We don't care about memory, so we just define the workspace size to a * really high value. */ #define AVL_PLEN 64 /* * Now we define the get/set functions and the compare. The user parameter * will be used to distinguish between the integer tree and the string tree. * If the user parameter is 0, then we use the integer tree, if it is not * 0, we use the string tree. We don't declare the functions inline, if * inlining is prudent, then gcc will inline them anyway. */ static AVL_NODE AVL_GET_L( AVL_NODE node, AVL_USER user ) { return user ? node->str_l : node->int_l; } static AVL_NODE AVL_GET_R( AVL_NODE node, AVL_USER user ) { return user ? node->str_r : node->int_r; } static unsigned AVL_GET_H( AVL_NODE node, AVL_USER user ) { return user ? node->str_h : node->int_h; } static void AVL_SET_L( AVL_NODE node, AVL_NODE tree, AVL_USER user ) { if ( user ) node->str_l = tree; else node->int_l = tree; } static void AVL_SET_R( AVL_NODE node, AVL_NODE tree, AVL_USER user ) { if ( user ) node->str_r = tree; else node->int_r = tree; } static void AVL_SET_H( AVL_NODE node, unsigned height, AVL_USER user ) { if ( user ) node->str_h = height; else node->int_h = height; } static int AVL_CMP( AVL_NODE node, AVL_KEYT key, AVL_USER user ) { if ( user ) { return strcmp( node->str_k, (char *) key ); } else { if ( node->int_k < key ) return -1; if ( node->int_k > key ) return +1; return 0; } } /* * Get the template and start the implementation */ #include <misc/avl.h> static AVL_NODE root_int; // Root for the integer tree static AVL_NODE root_str; // Root for the string tree static AVL_PATH work; // Workspace /* * Init */ void AssocInit( void ) { root_int = NULL; root_str = NULL; } /* * Look up a string by the int. * Returns NULL if the key is not found. */ const char *AssocFindByInt( int key ) { AVL_NODE node; // We pass the integer root and the 0 user parameter // will tell the AVL code to use the int_? fields. node = AVL_Search( root_int, key, 0 ); if ( node ) return node->str_k; else return NULL; } /* * Look up an int by a string. * If the string is found, then the int will be copied to the location * pointed by the 'result' pointer and 1 will be returned, if the string * is not found, then 0 is returned and the memory is not modified. */ int AssocFindByString( const char *key, int *result ) { AVL_NODE node; // We pass the string root and the 1 user parameter will // tell the AVL code to use the str_? fields. We have to // cast the char pointer to the key type, which is an int. node = AVL_Search( root_str, (AVL_KEYT) key, 1 ); if ( node ) { *result = node->int_k; return 1; } else return 0; } /* * Inserts a new node * Returns: * 0 if succeeded or the same pair was on the list already * 1 the int is on the tree with a different string * 2 the string is on the tree with a different int * 3 both int and string are on the tree with different pairs */ int AssocRemember( const char *key_str, int key_int ) { AVL_NODE node; AVL_NODE test; // Allocate a new node node = malloc( sizeof( struct s_node ) ); // Try to insert it into the integer tree first if ( test = AVL_Insert( &root_int, &work, node, key_int, 0 ) ) { // This int is already on the tree. We can release the node structure. free( node ); // Let's see if the the node on the tree has the same string key // as the one we wanted to insert would have. if ( ! strcmp( test->str_k, key_str ) ) { // It's the same, so the same pair got registered again, // which is fine. Report success. return 0; } else { // OK, the int is on the tree with a different string. // Our return code depends on whether the string is on // the tree or not if ( AVL_Search( root_str, (AVL_KEYT) key_str, 1 ) ) return 3; else return 1; } } // The int was not on the tree (but is now!). // Try to insert to the string tree. if ( AVL_Insert( &root_str, &work, node, key_str, 1 ) ) { // The string is already on the tree. Remove the new node from // the integer tree, release the memory and report error. AVL_Delete( &root_int, &work, key_int, 0 ); free( node ); return 2; } // Both insertions succeded, put the keys into the node and // report success. node->str_k = malloc( strlen( key_str ) + 1 ); strcpy( node->str_k, key_str ); node_int_k = key_int; return 0 ; } /* * Delete a node. * It receives both an int key and a string key. If the string key is NULL, * then it deletes the node identified by the integer key, if the string * key is not NULL, then it deletes the node by the string and the integer * key will be ignored. If the key is not found, then it does nothing. */ void AssocForget( const char *key_str, int key_int ) { AVL_NODE node; if ( key_str ) node = AVL_Delete( &root_str, &work, (AVL_KEYT) key_str, 1 ); else node = AVL_Delete( &root_int, &work, key_int, 0 ); if ( node ) { if ( key_str ) AVL_Delete( &root_int, &work, node->int_k, 0 ); else AVL_Delete( &root_str, &work, (AVL_KEYT) node->str_k, 1 ); free( node->key_s ); free( node ); } }
| static AVL_NODE AVL_Delete | ( | AVL_NODE * | root, | |
| AVL_PATH * | path, | |||
| AVL_KEYT | key, | |||
| AVL_USER | user | |||
| ) | [static] |
Deletes the given node from the tree.
The function removes a node from the tree and returns its reference. If the node is not on the tree, then AVL_NULL is returned.
| root | Pointer to an AVL_NODE object that contains the reference to the root node of the tree (which should be AVL_NULL if the tree is empty). The object might be modified by this function. | |
| path | Pointer to an AVL_PATH structure. The structure will be used as workspace and can be discarded as soon as this routine returns. | |
| key | The key to be deleted from the tree. | |
| user | The implementation dependent parameter. This argument is not used by the AVL routines themselves, but they are passed to all user defined functions. |
| static AVL_NODE AVL_First | ( | AVL_NODE | root, | |
| AVL_USER | user | |||
| ) | [static] |
Returns the node with the smallest key.
| root | The root of the tree | |
| user | The implementation dependent parameter. This argument is not used by the AVL routines themselves, but they are passed to all user defined functions. |
| static AVL_NODE AVL_Insert | ( | AVL_NODE * | root, | |
| AVL_PATH * | path, | |||
| AVL_NODE | node, | |||
| AVL_KEYT | key, | |||
| AVL_USER | user | |||
| ) | [static] |
Inserts a new node with the given key to the tree.
Returns AVL_NULL if succeeded. If the tree already has a node that has the same key as the one to be inserted, then the tree is not modified and the already existing node is returned. Note that since the function does not know the relationship between AVL_NODE and AVL_KEYT objects, the node's key field will not be set to the key. It is your responsibility. Also note that if you set the node's key to a value other than the key you passed to this function, it is, from the AVL tree handling functions' point of view, equivalent to memory corruption, with the same consequences.
| root | Pointer to an AVL_NODE object that contains the reference to the root node of the tree (which should be AVL_NULL if the tree is empty). The object might be modified by this function. | |
| path | Pointer to an AVL_PATH structure. The structure will be used as workspace and can be discarded as soon as this routine returns. | |
| node | Reference to the new node to insert to the tree. | |
| key | The key for the new node. | |
| user | The implementation dependent parameter. This argument is not used by the AVL routines themselves, but they are passed to all user defined functions. |
| static AVL_NODE AVL_Last | ( | AVL_NODE | root, | |
| AVL_USER | user | |||
| ) | [static] |
Returns the node with the largest key.
| root | The root of the tree | |
| user | The implementation dependent parameter. This argument is not used by the AVL routines themselves, but they are passed to all user defined functions. |
| static AVL_NODE AVL_Next | ( | AVL_NODE | root, | |
| AVL_PATH * | path, | |||
| AVL_KEYT | refk, | |||
| AVL_USER | user | |||
| ) | [static] |
Finds the node with smallest key that is larger than the given key.
This function returns a reference to a node that has the smallest key of all nodes with keys larger than the key passed to the function. If there is no node with a key larger than the given key, the function returns AVL_NULL.
Thus, this function can be used to walk the tree from smallest to largest by the following way:
// This is a function you have yo define. It returns a key of a node. AVL_KEYT GetKeyOfTheNode( AVL_NODE ); // This is the tree-walk routine void Walk( AVL_TREE root, AVL_USER user ) { AVL_NODE node; AVL_PATH work; node = AVL_First( root, user ); while ( node != AVL_NULL ) { DoSomethingWithTheNode( node ); node = AVL_Next( root, &work, GetKeyOfTheNode( node ), user ); } }
Note that this method works even if between successive invocations of the AVL_Next() function the tree gets modified, although if a new node gets inserted that has a key less than the key of the current node, the new node obviously will not be visited. However, the price you pay for this is that every time you call this function, a key search will be performed, at the cost of O(log(N)) steps. Therefore, a full walk will cost you O(N*log(N)) operations. If your tree does not change while you walk through it, you should consider using the AVL_Walk() and AVL_Step() functions, which will take you through the tree in O(N) operations.
| root | The root of the tree. | |
| path | Pointer to an AVL_PATH structure. The structure will be used as workspace and can be discarded as soon as this routine returns. | |
| refk | The reference key | |
| user | The implementation dependent parameter. This argument is not used by the AVL routines themselves, but they are passed to all user defined functions. |
| static AVL_NODE AVL_Search | ( | AVL_NODE | root, | |
| AVL_KEYT | skey, | |||
| AVL_USER | user | |||
| ) | [static] |
Find a key on the tree.
Returns a reference to the node data with the given key or NIL if the key is not found.
| root | The root node of the tree or AVL_NULL if the tree is empty. | |
| skey | The search key | |
| user | The implementation dependent parameter. This argument is not used by the AVL routines themselves, but they are passed to all user defined functions. |
| static AVL_NODE AVL_Step | ( | AVL_PATH * | path, | |
| AVL_USER | user | |||
| ) | [static] |
One step on the tree walk.
Receives an AVL_PATH object that was initially prepared by a call to the AVL_Walk() function. It then returns the node with the smallest key and modifies the AVL_PATH object such that the next invocation of the function will return the node with the second smallest key. That call, in turn, will modify the AVL_PATH object so that the next call returns the third smallest key and so on. Once the node with the largest key is returned, then any further calls to this function will return AVL_NULL.
It is very important that neither the AVL_PATH object nor the tree is modified between the calls. If you can't guarantee that, you should use the AVL_Next() function instead.
This function walks through the tree in O(N) amortised time, that is, one node is accessed on average for each call. However, the access pattern varies, and some calls may not access the tree at all, others might access as many as AVL_PLEN nodes.
| path | An AVL_PATH object that was initialised by a call to AVL_Walk(). | |
| user | The implementation dependent parameter. This argument is not used by the AVL routines themselves, but they are passed to all user defined functions. |
| static void AVL_Walk | ( | AVL_NODE | root, | |
| AVL_PATH * | path, | |||
| AVL_USER | user | |||
| ) | [static] |
Initialises a tree walk.
| root | The root of the tree | |
| path | Pointer to an AVL_PATH structure. The structure will be filled with data that, when passed to the AVL_Step() function, will make that function to return the node with the smallest key. Neither this structure nor the AVL tree itself should be modified between this call and calling AVL_Step() (and any subsequent calls to that function). | |
| user | The implementation dependent parameter. This argument is not used by the AVL routines themselves, but they are passed to all user defined functions. |
1.6.3