NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/comp/lang/c/11801

Text File | 1992-07-30 | 29.7 KB | 1,060 lines

Newsgroups: comp.lang.c
Path: sparky!uunet!wupost!darwin.sura.net!convex!constellation!munnari.oz.au!bruce.cs.monash.edu.au!monu6!giaeb!s1110238
From: [e-mail] (Lee Hollingworth)
Subject: Re: AVL Source Code
Message-ID: <s1110238.712499844@giaeb>
Keywords: If you asked for AVL code read this!
Sender: [e-mail] (Usenet system)
Organization: Monash University, Melb., Australia.
Date: Thu, 30 Jul 1992 12:37:24 GMT
Lines: 1048

Sorry for using the net to post this but my e-mail responce to a few of
the requests for AVL source bounced.

So if you DO NOT want a copy of AVL tree code press 'n' now...

Lee Hollingworth
[e-mail]


# This is a shell archive.  Remove anything before this line,
# then unpack it by saving it in a file and typing "sh file".
#
# Wrapped by Lee Hollingworth <s1110238@giaeb> on Thu Jul 30 22:17:37 1992
#
# This archive contains:
#    avltree.c    avltree.doc    avltree.h    menu.c
#    mscmake        tccmake        unixmake
#

LANG=""; export LANG
PATH=/bin:/usr/bin:$PATH; export PATH

echo x - avltree.c
cat >avltree.c <<'@EOF'
/*
 * Name:    avltree
 * Purpose: To maintain a balanced binary tree using AVL algorithms
 * Files:   avltree.c  avltree.h
 * Author:  Lee Hollingworth
 * System:  ANSI C comformant
 * Date:    March 4 1992
 */

#include <stdio.h>
#include <stdlib.h>

#include "avltree.h"

/*
 * Name:    rotate_left
 * Purpose: To re-arrange node pointers resulting in a LL rotation
 * Passed:  tree:   address of pointer the rotation root
 * Returns: tree:   pointer to new root node
 */
void rotate_left(trees *tree)
{
    trees left = (*tree)->left;         /* left hand child */

    (*tree)->left = left->right;        /* re-arrange pointers */
    left->right = *tree;
    *tree = left;                   /* change root to top node of rotation */
}

/*
 * Name:    rotate_right
 * Purpose: To re-arrange node pointers resulting in a RR rotation
 * Passed:  tree:   address of pointer to the rotation node
 * Returns: tree:   pointer to new root node
 */
void rotate_right(trees *tree)
{
    trees right = (*tree)->right;       /* right hand child */

    (*tree)->right = right->left;       /* re-arrange pointers */
    right->left = *tree;
    *tree = right;                  /* change root to top node of rotation */
}

/*
 * Name:    rot_left_balance
 * Purpose: Balance the root node and it's right child after a LL rotation
 * Passed:  tree:   pointer to root node of rotation after the rotation has
 *                   taken place
 */
void rot_left_balance(trees tree)
{
    tree->balance = EVEN;
    if ((tree->right->left && tree->right->right) ||
            (!tree->right->left && !tree->right->right)) {
        tree->right->balance = EVEN;
    }
    else {
        tree->right->balance = tree->right->right ? R_HEAVY : L_HEAVY;
    }
}

/*
 * Name:    rot_right_balance
 * Purpose: Balance the root node and it's left child after a RR rotation
 * Passed:  tree:   pointer to root node of rotation after the rotation has
 *                   taken place
 */
void rot_right_balance(trees tree)
{
    tree->balance = EVEN;
    if ((tree->left->left && tree->left->right) ||
            (!tree->left->left && !tree->left->right)) {
        tree->left->balance = EVEN;
    }
    else {
        tree->left->balance = tree->left->right ? R_HEAVY : L_HEAVY;
    }
}

/*
 * Name:    left_balance
 * Purpose: Take care of left rotations, either LL or LR after a node has
 *           been inserted
 * Passed:  tree:   pointer to pointer to root of rotation point which has
 *                   violated the tree balance prior to any rotation taking
 *                   place
 *          key:    the new insertion value
 * Returns: tree:   new root node
 */
void left_balance(trees *tree, keys key)
{
    trees *child = &(*tree)->left;

    if (compare((*tree)->left->key,  key) > 0) {  /* LL rotation */
        rotate_left(tree);
        rot_left_balance(*tree);
    }
    else {                                  /* LR rotation */
        rotate_right(child);
        rot_right_balance(*child);
        rotate_left(tree);
        rot_left_balance(*tree);
    }
}

/*
 * Name:    right_balance
 * Purpose: Take care of right rotations, either RR or RL after a node has
 *           been inserted
 * Passed:  tree:   pointer to pointer to root of rotation point which has
 *                   violated the tree balance prior to any rotation taking
 *                   place
 *          key:    the new insertion value
 * Returns: tree:   new root node
 */
void right_balance(trees *tree, keys key)
{
    trees *child = &(*tree)->right;

    if (compare((*tree)->right->key, key) < 0) {   /* RR rotation */
        rotate_right(tree);
        rot_right_balance(*tree);
    }
    else {                                  /* RL rotation */
        rotate_left(child);
        rot_left_balance(*child);
        rotate_right(tree);
        rot_right_balance(*tree);
    }
}

/*
 * Name:    insert
 * Purpose: To search for and insert if necessary a key in a
 *           binary search tree.
 * Passed:  new_key: the key to be inserted
 *          tree:    the tree
 * Returns: tree:    possibly modified tree containing new_key
 *          TRUE     a new node was added so check the balance
 *          FALSE    balance is okay or node already in tree
 *           (maybe should return something else for duplicate key???)
 */
boolean insert(keys new_key, trees *tree)
{
    int result;

    if (*tree == NULL) {
        /*
         * at leaf, so key was not in the tree and must be added
         */
        *tree = malloc(sizeof(**tree));
        keycpy((*tree)->key, new_key);
        (*tree)->balance = EVEN;
        (*tree)->left = (*tree)->right = NULL;
        return TRUE;
    }
    else if ((result = compare(new_key, (*tree)->key)) < 0) {
        if (insert(new_key, &((*tree)->left))) {
            switch ((*tree)->balance) {
                case EVEN:
                    (*tree)->balance = L_HEAVY;
                    return TRUE;

                case R_HEAVY:
                    (*tree)->balance = EVEN;
                    return FALSE;                   /* tree is balanced */

                case L_HEAVY:
                    left_balance(tree, new_key);
                    return FALSE;                   /* tree is balanced */
            }

        }
        return FALSE;
    }
    else if (result > 0) {
        if (insert(new_key, &((*tree)->right))) {
            switch ((*tree)->balance) {
                case EVEN:
                    (*tree)->balance = R_HEAVY;
                    return TRUE;

                case L_HEAVY:
                    (*tree)->balance = EVEN;
                    return FALSE;                   /* tree is balanced */

                case R_HEAVY:
                    right_balance(tree, new_key);
                    return FALSE;                   /* tree is balanced */
            }
        }
        return FALSE;
    }
    else {
        /*
         * key already in tree so return FALSE
         */
        return FALSE;
    }
}

/*
 * Name:    del_ll
 * Purpose: Balance the tree after a deletion has taken place and a LL
 *           rotation is required
 * Passed:  tree:   pointer to pointer to root rotation node
 * Returns: tree:   pointer to pointer to new root node after rotation
 */
void del_ll(trees *tree)
{
    if ((*tree)->balance == L_HEAVY && (*tree)->left->balance == EVEN) {
        (*tree)->left->balance = R_HEAVY;
    }
    else {
        (*tree)->balance = EVEN;
        (*tree)->left->balance = R_HEAVY;
    }

    rotate_left(tree);
}

/*
 * Name:    del_rr
 * Purpose: Balance the tree after a deletion has taken place and a RR
 *           rotation is required
 * Passed:  tree:   pointer to pointer to root rotation node
 * Returns: tree:   pointer to pointer to new root node after rotation
 */
void del_rr(trees *tree)
{
    if ((*tree)->balance == R_HEAVY && (*tree)->right->balance == EVEN) {
        (*tree)->right->balance = L_HEAVY;
    }
    else {
        (*tree)->balance = EVEN;
        (*tree)->right->balance = L_HEAVY;
    }
    rotate_right(tree);
}

/*
 * Name:    del_lr
 * Purpose: Balance the tree after a deletion has taken place and a LR
 *           rotation is required
 * Passed:  tree:   pointer to pointer to root rotation node
 * Returns: tree:   pointer to pointer to new root node after rotation
 */
void del_lr(trees *tree)
{
    trees *child = &(*tree)->left;

    /*
     * (*tree)->balance == L_HEAVY in all cases
     * (*child)->balance == R_HEAVY in all cases
     */

    switch ((*child)->right->balance) {
        case R_HEAVY:
            (*child)->balance = L_HEAVY;
            (*child)->right->balance = EVEN;        /* new root */
            (*tree)->balance = EVEN;
            break;

        case EVEN:
            (*child)->balance = EVEN;
            (*tree)->balance = EVEN;
            break;

        case L_HEAVY:
            (*child)->balance = EVEN;
            (*tree)->balance = R_HEAVY;
            (*child)->right->balance = EVEN;
            break;
    }

    rotate_right(child);
    rotate_left(tree);
}

/*
 * Name:    del_rl
 * Purpose: Balance the tree after a deletion has taken place and a RL
 *           rotation is required
 * Passed:  tree:   pointer to pointer to root rotation node
 * Returns: tree:   pointer to pointer to new root node after rotation
 */
void del_rl(trees *tree)
{
    trees *child = &(*tree)->right;

    /*
     * (*tree)->balance == R_HEAVY in all cases
     * (*child)->balance == L_HEAVY in all cases
     */

    switch ((*child)->left->balance) {
        case L_HEAVY:
            (*child)->balance = R_HEAVY;
            (*child)->left->balance = EVEN;         /* new root */
            (*tree)->balance = EVEN;
            break;

        case EVEN:
            (*child)->balance = EVEN;
            (*tree)->balance = EVEN;
            break;

        case R_HEAVY:
            (*child)->balance = EVEN;
            (*tree)->balance = L_HEAVY;
            (*child)->left->balance = EVEN;
            break;
    }

    rotate_left(child);
    rotate_right(tree);
}

/*
 * Name:    left_path_balance
 * Purpose: If returning up the left path, check the current nodes balance
 *           and adjust if required
 * Passed:  pointer to pointer to the root node
 * Returns: FALSE no further balancing required above this point
 *          TRUE continue to balance up the tree
 */
boolean left_path_balance(trees *tree)
{
    switch ((*tree)->balance) {
        case EVEN:          /* no further balancing req'd */
            (*tree)->balance = R_HEAVY;
            return FALSE;

        case L_HEAVY:       /* check further up... */
            (*tree)->balance = EVEN;
            break;

        case R_HEAVY:       /* tree is unbalanced rotations req'd */
            /*
             * three possible cases now exist
             * 1. right child is EVEN
             * 2. right child is R_HEAVY
             * 3. right child is L_HEAVY
             * 1 = RR and change balances according to current
             *      balances, tree is now balanced
             * 2 = set both balances to EVEN and RR
             * 3 = RL and change balances according to current
             *      balances
             */
            switch ((*tree)->right->balance) {
                case EVEN:
                    del_rr(tree);
                    return FALSE;

                case R_HEAVY:
                    (*tree)->balance = EVEN;
                    (*tree)->right->balance = EVEN;
                    rotate_right(tree);
                    break;

                case L_HEAVY:
                    del_rl(tree);
                    break;
            }
    }
    return TRUE;
}

/*
 * Name:    right_path_balance
 * Purpose: If returning up the right path, check the current nodes balance
 *           and adjust if required
 * Passed:  pointer to pointer to the root node
 * Returns: FALSE no further balancing required above this point
 *          TRUE continue to balance up the tree
 */
boolean right_path_balance(trees *tree)
{
    switch ((*tree)->balance) {
        case EVEN:      /* no further balancing req'd */
            (*tree)->balance = L_HEAVY;
            return FALSE;

        case R_HEAVY:   /* continue to check on the way up */
            (*tree)->balance = EVEN;
            break;

        case L_HEAVY:
            /*
             * three possible cases now exist
             * 1. left child is EVEN
             * 2. left child is L_HEAVY
             * 3. left child is R_HEAVY
             * 1 = LL and change balances according to current
             *      balances, tree is now balanced
             * 2 = set both balances to EVEN and LL
             * 3 = LR and change balances according to current
             *      balances
             */
            switch ((*tree)->left->balance) {
                case EVEN:
                    del_ll(tree);
                    return FALSE;

                case L_HEAVY:
                    (*tree)->balance = EVEN;
                    (*tree)->left->balance = EVEN;
                    rotate_left(tree);
                    break;

                case R_HEAVY:
                    del_lr(tree);
                    break;
            }
    }
    return TRUE;
}

/*
 * Name:    left_most
 * Purpose: To retrieve the left most descendent of the tree,
 *            and delete this leaf node.
 * Passed:  tree: the tree to be searched
 * Returns: key:     the left most key in this tree
 *          tree:    the tree minus the leftmost node
 *          TRUE until point of balance is reached
 *          FALSE if no deletion or balance acheived
 */
boolean left_most(trees *tree, keys *key)
{
    trees p;               /* node to be disposed of */

    /*
     * first make sure there is something there to find
     */
    if ((*tree) != NULL) {
        /*
         * see if we are already at the bottom of the tree
         */
        if ((*tree)->left == NULL) {
            /*
             * return this left most node, and delete it, tree path is now
             * shorter so return TRUE
             */
            *key = (*tree)->key;
            p = (*tree);
            (*tree) = (*tree)->right;
            free(p);
            return TRUE;
        }
        else {
            /*
             * recurse down the left sub-tree, return of TRUE means a node
             * was removed from the left path so check balance of tree on
             * way up and adjust accordingly
             */
            if (left_most(&((*tree)->left), key)) {
                return left_path_balance(tree);
            }
            return FALSE;
        }
    }
    return FALSE;
}

/*
 * Name:    del_item
 * Purpose: To delete the item in the root of the tree.
 * Passed:  tree:    the tree whose root must be deleted
 * Returns: tree:    the tree with its root deleted
 *          TRUE until point of balance is reached
 *          FALSE if no deletion or balance acheived
 */
boolean del_item(trees *tree)
{
    trees p;                /* node to be disposed of */

    /*
     * first check that there is something to de deleted
     */
    if ((*tree) != NULL) {
        if (((*tree)->left == NULL) && ((*tree)->right == NULL)) {
            /*
             * if tree is a leaf, then it can be deleted easily, path
             *  has been shortened so return TRUE
             */
            free((*tree));
            (*tree) = NULL;
            return TRUE;
        }
        else if ((*tree)->left == NULL) {
            /*
             * if the tree only has a right child, then the root
             *  can be replaced by the right child
             * path has been shortened so return TRUE
             */
            p = (*tree);
            (*tree) = (*tree)->right;
            free(p);
            return TRUE;
        }
        else if ((*tree)->right == NULL) {
            /*
             * if the tree only has a left child, then the root
             *  can be replaced by the left child
             * path has been shortened so return TRUE
             */
            p = (*tree);
            (*tree) = (*tree)->left;
            free(p);
            return TRUE;
        }
        else {
            /*
             * if the tree has two children, then recurse to find
             *  the smallest key larger than the root (i.e. the
             *  left most key to the right of the root)
             * the path from where the replacement node has been
             *  taken is shortened, so the tree must be re-balanced
             *  accordingly
             */
            if (left_most(&((*tree)->right), &(*tree)->key)) {
                return right_path_balance(tree);
            }
            return FALSE;
        }
    }
}

/*
 * Name:    delete
 * Purpose: To delete an item from the tree.
 * Passed:  tree:    the tree to be deleted from
 *          key:     the key value of the item to be deleted
 * Returns: tree:    the tree with the item deleted
 *          TRUE  balancing required
 *          FALSE no further balancing required
 */
boolean delete(trees *tree, keys key)
{
    int result;

    if ((*tree) == NULL) {
        /*
         * key not in tree
         */
        return FALSE;
    }
    else if ((result = compare(key, (*tree)->key)) == 0) {
        /*
         * key found
         */
        return del_item(tree);
    }
    else if (result < 0) {
        /*
         * key could be in left sub-tree
         */
        if (delete(&((*tree)->left), key)) {
            return left_path_balance(tree);
        }
        return FALSE;
    }
    else {
        /*
         * key could be in right sub-tree
         */
        if (delete(&((*tree)->right), key)) {
            return right_path_balance(tree);
        }
        return FALSE;
    }
}

/*
 * Name:    find
 * Purpose: To search for a key in the binary search tree.
 * Passed:  key: the key to be found
 *          tree:    the tree
 * Returns: TRUE     the node was found
 *          FALSE    the node was not found
 */
boolean find(keys key, trees tree)
{
    int result;

    if (tree == NULL) {
        /*
         * at leaf, so key was not in the tree
         */
        return FALSE;
    }
    else if ((result = compare(key, tree->key)) < 0) {
        return (find(key, tree->left));
    }
    else if (result > 0) {
        return (find(key, tree->right));
    }
    else {
        /*
         * key found
         */
        return TRUE;
    }
}
@EOF

chmod 600 avltree.c

echo x - avltree.doc
cat >avltree.doc <<'@EOF'
AVLtree.doc -- AVL tree deletion                            Lee Hollingworth

The deletion of a node from an AVL balanced tree is far more complex than an
insertion, as can easily be confirmed by the way in which any text I could
find "left the implementation as an exercise to the reader"!

The problem of deletion can be reduced to the following steps:

    1. Reduce the problem to the point where the node to be deleted, say
       'p' has at most one child.  This of course was taken care of for
       us with the code supplied by me.  The code supplied uses the
       an in-order traversal to find the successor of p.
       For the rest of this explanation this child will be called 'q'.

    2. Delete the node 'q' from the tree.  As my comments state, it is
       known that 'q' can only have a right child by virtue of the method
       used to find it.  So deletion is a simple matter of linking the
       parent of 'q' to it's right child, which of course could be NULL.
       The height of the path from 'p' to 'q' has  now been reduced by 1,
       and the effects of this change in height must be traced back up the
       path from 'q' to the root of the tree.
       A boolean value of either TRUE or FALSE is used to show if the height
       of the current sub-tree has been shortened.  Using this value and
       the current node's balance and it's child's balance we can take the
       necessary action required in balancing the tree.

    3. Using the initial return value of TRUE, the following steps are
       undertaken, based upon the current value of each node 's' and the
       *return* path traveled to get to 's'.
       By returning FALSE the tree above that point remains unchanged.

    4. i.   The balance factor of 's' is EQUAL.  The balance factor of 's'
            is changed in accordance with whether the left or right path
            was shortened and the boolean value FALSE is passed on up the tree,
            thus terminating the need for any further changes.

       ii.  The balance of 's' is not EQUAL, but the taller sub-tree was
            shortened.  Change the balance of 's' to EQUAL and return TRUE.

       iii. The balance of 's' is not EQUAL, but the shorter sub-tree was
            shortened.
            This is a point in which a leaf in the sub-tree is 2 levels
            taller than it's matching leaf, thus violating AVL balance.
            Now a rotation is required to restore balance, but the rotation
            required depends upon the balance value of 's' and it's child on
            the taller sub-tree 't' (the path not shortened).

            a.  The balance value of 't' is EQUAL.  A single rotation is
                required, with appropriate balance changes (easily said),
                and FALSE is returned up the tree.

            b.  The balance value of 't' is the same as 's'. A single rotation
                is required, set 't' and 's' to EQUAL and return TRUE.

            c.  The balance of 's' and 't' are opposite.  A double rotation,
                first around 't' and then 's' is required, set the balance
                factor of the new root to EQUAL and the other as appropriate
                (very easily said).  Return TRUE.

       As usual the rotations required in 4(iii) depends upon which sub-tree
       was shortened, basically the opposite to an insertion.

The above is basically paraphrased from the book _Data Structures and Program
Design in C_  by Kruse, Leung and Tondo, Prentice Hall page 338.

Unfortunately they do not give a coded example!

The obvious problem with AVL tree node deletion is that of ensuring the correct
balance values is maintained within each node in the path from replacement node
to root.
To assist in this matter I have included a defined constant called SHOW_BALANCE
which if included at compile time will result in each node showing it's balance
value when printed.  This constant can be commented out to produce a normal
printed tree.

@EOF

chmod 600 avltree.doc

echo x - avltree.h
cat >avltree.h <<'@EOF'
/*
 * Name    : avltree
 * Purpose : Header file for avltree.c
 * Author  : Lee Hollingworth
 */

/*
 * macro   : compare
 * purpose : simple compare macro which is implemented here so that if the key
 *           field in the node structure is changed, the only place the code
 *           needs to be changed is here...
 * returns :  0 - a and b are equal
 *            1 - a is greater than b
 *           -1 - b is greater than a
 *
 * note compatible with strcmp
 */
#define compare(a, b)  (a) == (b) ? 0 : (a) > (b) ? 1 : -1

/*
 * macro   : keycpy
 * purpose : copy one key into another
 * note    : can be replaced by any copy function such as strcpy for string
 *           keys
 */
#define keycpy(a, b) a = b

/*
 * datatype: balances
 * purpose : mainatin a balance field in the current node
 */
typedef enum {EVEN, L_HEAVY, R_HEAVY} balances;

/*
 * datatype: boolean
 * purpose : TRUE - FALSE data type
 */
typedef enum {FALSE, TRUE} boolean;

/*
 * datatype: keys
 * purpose : define a key field data type
 */
typedef int keys;

/*
 * datatype: node
 * purpose : tree node structure
 */
typedef struct node {
    keys key;                   /* search key */
    balances balance;           /* level of balance of children */
    struct node *left;          /* left sub-tree */
    struct node *right;         /* right sub-tree */
};

/*
 * datatype: nodes
 * purpose : define node type
 */
typedef struct node *trees;     /* every tree or sub-tree */

/*
 * functions "interfaced" to other source code
 */
boolean  insert(keys new_key,trees *tree);      /* insert new node */
boolean  delete(trees *tree,keys key);          /* delete a node */
boolean  find(keys key, trees tree);            /* find a node */

/*
 * functions "private" to avltree.c
 */
void  rotate_left(trees *tree);
void  rotate_right(trees *tree);
void  rot_left_balance(trees tree);
void  rot_right_balance(trees tree);
void  left_balance(trees *tree, keys key);
void  right_balance(trees *tree, keys key);
void  del_ll(trees *tree);
void  del_rr(trees *tree);
void  del_lr(trees *tree);
void  del_rl(trees *tree);
boolean  left_path_balance(trees *tree);
boolean  right_path_balance(trees *tree);
boolean  left_most(trees *tree, keys *key);
boolean  del_item(trees *tree);
@EOF

chmod 600 avltree.h

echo x - menu.c
cat >menu.c <<'@EOF'
/*
 * Name:    Balanced binary search with AVL balancing
 * Purpose: To insert and delete keys into a binary tree and display the
 *           result using AVL algorithms to maintain a balanced tree.
 * File:    avltree.c
 * Author:  Lee Hollingworth
 * System:  ANSI C comformant
 * Date:    March 4 1992
 */

#include <stdio.h>
#include <stdlib.h>

#include "avltree.h"

/*
 * SHOW_BALANCE allows the tree node balances to be shown for easy viewing
 *  of tree re-balancing after deletions or insertions
 *  to use it just remove comments markers
 */


#define SHOW_BALANCE


typedef enum {ADD, DELETE, FIND, QUIT} options;

/*
 * Name:    print_tree
 * Purpose: To display the entire tree in a reasonable format.
 * Passed:  tree:  the tree to be displayed
 *          level: how far down from the root of the tree we are
 * Output:  visual representation of the tree
 */
void print_tree(trees tree, int level)
{
    int i;

    /*
     * recursion ceases when we reach the bottom of the tree
     */
    if (tree != NULL) {
       /*
        * Still more tree to print, so print the right sub-tree,
        *  then this node, then the left sub-tree.
        * Indentation is proportional to the depth in the tree.
        */
        print_tree(tree->right, level+1);
        for (i=0; i < level; i++)
            printf("       ");
        printf("%d", tree->key);

        #ifdef SHOW_BALANCE
        printf("%c", tree->balance == 0 ? 'E' : tree->balance == 1 ? 'L' : 'R');
        #endif

        printf("\n");
        print_tree(tree->left, level+1);
    }
}

/*
 * Name:    menu
 * Purpose: To display a menu and input the user's selection.
 * Returns: selection
 */
int menu(void)
{
    int c;

    for (;;) {
        printf("Add, Delete, Find or Quit? (a/d/f/q): ");
        while ((c = tolower(getchar())) == '\n')
            ;
        switch (c) {
        case 'a':
            return ADD;
        case 'd':
            return DELETE;
        case 'f':
            return FIND;
        case 'q':
            return QUIT;
        }
    }
}

/*
 * Name:    main
 * Purpose: See comments at start of program.
 */
void main(void)
{
    trees root;                 /* the entire tree */
    keys key;                   /* the key being added */

    root = NULL;   /* start with an empty tree */

    /*
     * Keep on inputting a new key, adding or deleting this key,
     *  and displaying the resultant tree, until the user wants
     *  to stop.
     */
    for (;;) {
        switch (menu()) {
        case ADD:
            printf("Key to add: ");
            scanf("%d", &key);
            insert(key, &root);
            break;
        case DELETE:
            printf("Key to delete: ");
            scanf("%d", &key);
            delete(&root, key);
            break;
        case FIND:
            printf("Key to find: ");
            scanf("%d", &key);
            if (find(key, root)) {
                printf("%d: Key found!\n", key);
            }
            else {
                printf("%d: Key not in tree...\n", key);
            }
            break;
        case QUIT:
            exit(0);
        }
        print_tree(root, 0);
    }
}
@EOF

chmod 600 menu.c


rm -f /tmp/uud$$
(echo "begin 666 /tmp/uud$$\n#;VL*n#6%@x\n \nend" | uudecode) >/dev/null 2>&1
if [ X"`cat /tmp/uud$$ 2>&1`" = Xok ]
then
    unpacker=uudecode
else
    echo Compiling unpacker for non-ascii files
    pwd=`pwd`; cd /tmp
    cat >unpack$$.c <<'EOF'
#include <stdio.h>
#define C (*p++ - ' ' & 077)
main()
{
    int n;
    char buf[128], *p, a,b;

    scanf("begin %o ", &n);
    gets(buf);

    if (freopen(buf, "w", stdout) == NULL) {
        perror(buf);
        exit(1);
    }

    while (gets(p=buf) && (n=C)) {
        while (n>0) {
            a = C;
            if (n-- > 0) putchar(a << 2 | (b=C) >> 4);
            if (n-- > 0) putchar(b << 4 | (a=C) >> 2);
            if (n-- > 0) putchar(a << 6 | C);
        }
    }
    exit(0);
}
EOF
    cc -o unpack$$ unpack$$.c
    rm unpack$$.c
    cd $pwd
    unpacker=/tmp/unpack$$
fi
rm -f /tmp/uud$$

echo x - mscmake '[non-ascii]'
$unpacker <<'@eof'
begin 600 mscmake
M(R!-86ME($%63"Y%6$4@=&\@<G5N(&]N(&UO<W0@24)-(%!#('-Y<W1E;7,NX
M"B,@5&AI<R!F:6QE(&ES(&9O<B!-:6-R;W-O9G0@0R V+C @;W(@475I8VL@X
M0R R+C4Q"B,@268@=7-I;F<@34%+12 H;F]T($Y-04M%*2!C;VUM96YT(&]UX
M="!N97AT(&QI;F4N"D%,3" Z(&%V;"YE>&4*"BYC+F]B:CH*(" @(&-L("]CX
M("]!4R O5S0@+T<R("]*("0\"@IM96YU+F]B:CH@879L=')E92YH(&UE;G4NX
M8PIA=FQT<F5E+F]B:CH@879L=')E92YH(&%V;'1R964N8PH*879L+F5X93H@X
M;65N=2YO8FH@879L=')E92YO8FH*(" @3$E.2R!M96YU(&%V;'1R964L(&%VX
*;"YE>&4["B @('9L                                            X
                                                             X
end
@eof

chmod 600 mscmake

echo x - tccmake
sed 's/^@//' >tccmake <<'@EOF'
#    Turbo C++ Make file for AVL tree program.

#    Implicit rules.

@.c.obj:
    tcc -c $<

#    Targets.

avl.exe:        menu.obj avltree.obj
        tcc -G -O -Z -w -eavl.exe menu.obj avltree.obj

#    Dependencies.

menu.obj:      menu.c avltree.h
avltree.obj:   avltree.c avltree.h
@EOF

chmod 600 tccmake

echo x - unixmake
sed 's/^@//' >unixmake <<'@EOF'
# Make avltree for UNIX [System V] systems

OBJECTS = menu.o avltree.o

# -z - check for dereferencing NULL pointer
CCFLAGS = -O -z +DA1.0

@.c.o:           ; cc $(CCFLAGS) -c -DUNIX $*.c

avltree: $(OBJECTS) ; cc $(CCFLAGS) -o avltree $(OBJECTS) -lcurses

$(OBJECTS):     avltree.h
menu.o:
avltree.o:
@EOF

chmod 644 unixmake

rm -f /tmp/unpack$$
exit 0