// Tree.h                                           Stan Eisenstat (04/02/2009)

   Specification of interface for Tree ADT, which stores (Key,Attr) pairs
   in a binary search tree ordered by Key.  Only one pair with a given Key
   field can be stored.

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

// External definition of Tree
typedef struct tree *Tree;

// Datatypes for Key, Attr, and Status
typedef int Key, Attr;

// Search for Key K in Tree T.  If found, then put corresponding Attr in *A
// and return TRUE, else return FALSE.
Status search (Tree t, Key k, Attr *a);

// Insert pair (K,A) into Tree T if no pair with Key K is already present;
// otherwise replace Attr field corresponding to Key K by A.  Return pointer
// to updated Tree.
Tree insert (Tree t, Key k, Attr a);

// Delete pair with Key K from Tree T.  Return pointer to updated tree.
Tree delete (Tree t, Key k);

//***************************************************************************

// Tree.c                                           Stan Eisenstat (04/02/2009)
//
// A rough, incomplete, and untested implementation of the Tree ADT.

#include "Tree.h"

struct tree {               // Internal definition of the Tree ADT
    Key key;                //  Each node contains a (Key, Attr) pair
    Attr attr;
    Tree left, right;       //  Each node has a left and a right subtree
};

// Search for Key K in Tree T.  If found, then put corresponding Attr in *A
// and return TRUE, else return FALSE.
Status search (Tree t, Key k, Attr *a)          // Recursive version
{
#ifdef RECURSIVE
    if (t) {
	if (k < t->key)
	    return searchR (t->left, k, a);     // Search in left subtree
	else if (t->key < k)
	    return searchR (t->right, k, a);    // Search in right subtree
	else
	    *a = t->attr;                       // Found
	    return true;
    }
#else
    while (t) {
	if (k < t->key)
	    t = t->left;                        // Move to left subtree
	else if (t->key < k)
	    t = t->right;                       // Move to right subtree
	else {
	    *a = t->attr;                       // Found
	    return true;
	}
    }
#endif
    return false;                             // Not found
}

// Return a one-node tree containing the pair (K,A)
static Tree makenode (Key k, Attr a);

// Insert pair (K,A) into Tree T if no pair with Key K is already present;
// otherwise replace Attr field corresponding to Key K by A.  Return pointer
// to updated Tree.
Tree insert (Tree t, Key k, Attr a)
{
    if (t) {
	if (k < t->key)
	    t->left = insert (t->left, k, a);   // Insert in left subtree
	else if (t->key < k)
	    t->right = insert (t->right, k, a); // Insert in right subtree
	else
	    t->attr = a;                        // Replace existing attribute
	return (t);                             // Return modified tree
    }
    return makenode (k, a);                     // Create single-node tree
}

// Delete node with largest key in nonempty Tree T and set *P to that node.
// Return pointer to updated tree.
static Tree deleteLargest (Tree t, Tree *p)
{
    if (t->right == NULL) {                     // No right child =>
	*p = t;                                 //   Root is largest
	return t->left;
    } else {
	t->right = deleteLargest (t->right, p); // Largest in right child
	return t;
    }
}

// Delete root of Tree T.  Return pointer to updated tree.
static Tree deleteRoot (Tree t)
{
    Tree p;

    if (t->left == NULL)                        // Case 1: No left child
	p = t->right;                           //   Promote right child
    else if (t->right == NULL)                  // Case 2: No right child
	p = t->left;                            //   Promote left child
    else {                                      // Case 3: Two children
	t->left = deleteLargest (t->left, &p);  //   Delete predecessor
	p->left = t->left;                      //   and make it new root
	p->right = t->right;
    }
    free(t);                                    // Free tree node deleted
    return p;                                   // Return modified tree
}

// Delete pair with Key K from Tree T.  Return pointer to updated tree.
Tree delete (Tree t, Key k)
{
    if (t) {
	if (k < t->key)
	    t->left = delete (t->left, k);      // Delete from left subtree
	else if (t->key < k)
	    t->right = delete (t->right, k);    // Delete from right subtree
	else
	    t = deleteRoot (t);                 // Delete key at root
    }
    return (t);                                 // Return modified tree
}
							   // CS 223-04/02/09