// Tree.h Stan Eisenstat (04/01/16) // // Specification of the interface for a Tree ADT that stores unique (Key,Attr) // pairs in a binary search tree ordered by Key. #include typedef struct tree *Tree; // External definition of Tree typedef int Key, Attr; // Datatypes for Key and Attr // Search for Key K in Tree T. If found, then put corresponding Attr in *A // and return TRUE, else return FALSE. bool 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/01/16) // // A rough, incomplete, and untested implementation of the Tree ADT. #include #include #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. bool search (Tree t, Key k, Attr *a) { #ifdef RECURSIVE // Recursive version if (t) { if (k < t->key) return search (t->left, k, a); // Search in left subtree else if (t->key < k) return search (t->right, k, a); // Search in right subtree else { *a = t->attr; // Found return true; } } #else // Iterative version 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 } // 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; // Modified tree 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 }