/* binary search tree */

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

typedef int T;                  /* type of item to be stored */
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

typedef struct Node_ {
    struct Node_ *left;         /* left child */
    struct Node_ *right;        /* right child */
    struct Node_ *parent;       /* parent */
    T data;                     /* data stored in node */
} Node;

Node *root = NULL;               /* root of binary tree */

Node *insertNode(T data) {
    Node *x, *current, *parent;

   /***********************************************
    *  allocate node for data and insert in tree  *
    ***********************************************/

    /* find x's parent */
    current = root;
    parent = 0;
    while (current) {
        if (compEQ(data, current->data)) return (current);
        parent = current;
        current = compLT(data, current->data) ? 
            current->left : current->right;
    }

    /* setup new node */
    if ((x = malloc (sizeof(*x))) == 0) {
        fprintf (stderr, "insufficient memory (insertNode)\n");
        exit(1);
    }
    x->data = data;
    x->parent = parent;
    x->left = NULL;
    x->right = NULL;

    /* insert x in tree */
    if(parent)
        if(compLT(x->data, parent->data))
            parent->left = x;
        else
            parent->right = x;
    else
        root = x;

    return(x);
}

void deleteNode(Node *z) {
    Node *x, *y;

   /*****************************
    *  delete node z from tree  *
    *****************************/

    /* y will be removed from the parent chain */
    if (!z || z == NULL) return;

    /* find tree successor */
    if (z->left == NULL || z->right == NULL)
        y = z;
    else {
        y = z->right;
        while (y->left != NULL) y = y->left;
    }

    /* x is y's only child */
    if (y->left != NULL)
        x = y->left;
    else
        x = y->right;

    /* remove y from the parent chain */
    if (x) x->parent = y->parent;
    if (y->parent)
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    else
        root = x;

    /* y is the node we're removing */
    /* z is the data we're removing */
    /* if z and y are not the same, replace z with y. */
    if (y != z) {
        y->left = z->left;
        if (y->left) y->left->parent = y;
        y->right = z->right;
        if (y->right) y->right->parent = y;
        y->parent = z->parent;
        if (z->parent)
            if (z == z->parent->left)
                z->parent->left = y;
            else
                z->parent->right = y;
        else
            root = y;
        free (z);
    } else {
        free (y);
    }
}

Node *findNode(T data) {

   /*******************************
    *  find node containing data  *
    *******************************/

    Node *current = root;
    while(current != NULL)
        if(compEQ(data, current->data))
            return (current);
        else
            current = compLT(data, current->data) ? 
                current->left : current->right;
    return(0);
}

int main(int argc, char **argv) {
    int i, *a, maxnum, random;

    /* command-line:
     *
     *   bin maxnum random
     *
     *   bin 5000        // 5000 sequential
     *   bin 2000 r      // 2000 random
     *
     */
    maxnum = atoi(argv[1]);
    random = argc > 2;

    if ((a = malloc(maxnum * sizeof(*a))) == 0) {
        fprintf (stderr, "insufficient memory (a)\n");
        exit(1);
    }

    if (random) { /* random */
        /* fill "a" with unique random numbers */
        for (i = 0; i < maxnum; i++) a[i] = rand();
        printf ("ran bt, %d items\n", maxnum);
    } else {
        for (i=0; i<maxnum; i++) a[i] = i;
        printf ("seq bt, %d items\n", maxnum);
    }


    for (i = 0; i < maxnum; i++) {
        insertNode(a[i]);
    }

    for (i = maxnum-1; i >= 0; i--) {
        findNode(a[i]);
    }

    for (i = maxnum-1; i >= 0; i--) {
        deleteNode(findNode(a[i]));
    }
    return 0;
}