We need at least 3 items to build the essential triangles that make up an AVL tree, and some data to store and search on.

How to politely say the basic data structure is wrong for any AVL tree? Each node of an AVL tree needs at least 5 items. 1. the data or a pointer to the data. the data MUST include a key. 2. a pointer to the the left child node. 3. a pointer to the right child node 4. a pointer to the PARENT node, which is missing 5. one or more items to enforce the balance of the tree. One could store these extra item(s) separately. As a side note, one could use an index into an array rather than a C style pointer. In any case, the code is a cascade miss design with error(s) in each function.

No doubt it compiles (?under which OS and compiler?). To debug and test, you will want to write one or a series of tree display sub programs. I'm currently building a general purpose 32/64 bit Intel AVL tree. I'm at about 2000 lines and not done [ verbose is my nickname ]. It is intended for symbol tables for a compiler. I did some web searches for code: found a lot of broken examples. Search on an AVL tree should be about m*O( lg N). Insert about m*O( 2 * lg N) because of retrace. Delete and other operations such as bulk load not needed for my intended use.