CIS 250 - Binary search tree deletion

CIS 250 - Templated binary search tree implementation

Objectives

implement node insertion in a binary search tree
implement searching for a node in a binary search tree
implement node deletion in a binary search tree
implement displaying a binary search tree (especially inorder)
make the class generic using templating

Binary Search Tree - rewritten Spring 2012

/*
   bintree.h
   CIS 250
   4/11/12
   Dave Klick

Templated binary search tree implementation
*/

#ifndef __BINTREE_H__
#define __BINTREE_H__

#include <iostream>
using std::ostream;
using std::cout;

template<typename T>
struct Node {
public:
    // If allowing duplicate values by keeping a count in the node,
    // you will need to add an integer count variable to the node.
    // You will also need to add methods to increment and decrement
    // the count. The insertion operator overload should also be
    // modified to display the count.
    T data;
    Node* left;
    Node* right;
    Node() { left = right = NULL; }
    Node(const T thingie) { left = right = NULL; data = thingie; }
    T getData() const { return data; }
    friend ostream& operator<<(ostream& strm, const Node<T>& node) {
        return strm << node.data;
    }
};

template<typename T>
class bintree {
private:
    Node<T>* root;
    void inOrder(const Node<T>* p) const;
    void preOrder(const Node<T>* p) const;
    void postOrder(const Node<T>* p) const;
    void deleteTree(Node<T>*);
public:
    bintree() { root = NULL; }
    ~bintree();
    bool deleteNode(const T&);
    bool insert(const T&);
    bool find(const T&) const;
    void inOrder() const { inOrder(root); }
    void preOrder() const { preOrder(root); }
    void postOrder() const { postOrder(root); }
};

template<typename T>
void bintree<T>::deleteTree(Node<T>* p) {
    if (p != NULL) {
        if (p->left) deleteTree(p->left);
        if (p->right) deleteTree(p->right);
        delete p;
    }
}

template<typename T>
void bintree<T>::inOrder(const Node<T>* p) const {
    if (p != NULL) {
        inOrder(p->left);
        cout << *p << '\n';
        inOrder(p->right);
    }
}

template<typename T>
void bintree<T>::preOrder(const Node<T>* p) const {
    if (p != NULL) {
        cout << *p << '\n';
        preOrder(p->left);
        preOrder(p->right);
    }
}

template<typename T>
void bintree<T>::postOrder(const Node<T>* p) const {
    if (p != NULL) {
        postOrder(p->left);
        postOrder(p->right);
        cout << *p << '\n';
    }
}

template<typename T>
bintree<T>::~bintree() { 
    deleteTree(root); root = NULL;
}

template<typename T>
bool bintree<T>::deleteNode(const T& data) {
    Node<T> *parent, *delNode, *succ, *parentSucc;
    bool isLeftChild = true;
    if (root == NULL) return false;

// find node to be deleted
    parent = NULL;
    delNode =  root;
    while (data != delNode->data) {
        parent = delNode;
        if (data < delNode->data) {
            if (delNode->left == NULL) return false;
            delNode = delNode->left;
            isLeftChild = true;
        } else {
            if (delNode->right == NULL) return false;
            delNode = delNode->right;
            isLeftChild = false;
        }
    }
    
    // If a count is being stored in the node for duplicates,
    // then you would check that count here and decrement that
    // count and return true if it is greater than 1. Otherwise,
    // you would continue on with the code below.
    
    if (delNode->left == NULL && delNode->right == NULL) {
        // do delete for node with no children
        if (delNode == root) root = NULL;
        else if (isLeftChild) parent->left = NULL;
        else parent->right = NULL;
    } else if (delNode->right == NULL || delNode->left == NULL) {
        // do delete for node with one child
        succ = delNode->right == NULL ? delNode->left : delNode->right;
        if (delNode == root) root = succ;
        else if (isLeftChild) parent->left = succ;
        else parent->right = succ;
    } else {
        // do delete for node with two children
        parentSucc = delNode;
        succ = delNode->right; // once to right
        while (succ->left != NULL) { // left as far as possible
            parentSucc = succ;
            succ = succ->left;
        }
        if (delNode == root) root = succ;
        else if (isLeftChild) parent->left = succ;
        else parent->right = succ;
        if (parentSucc != delNode) parentSucc->left = succ->right;
        succ->left = delNode->left;
        if (delNode->right != succ) succ->right = delNode->right;
    }

delete delNode;
    return true;
}

template<typename T>
bool bintree<T>::insert(const T& data) {
    Node<T> *newNode, *prev, *curr;
    newNode = new Node<T>(data);
    if (root == NULL) root = newNode;
    else {
        curr = root;
        while (curr != NULL) {
            prev = curr;
            // If duplicates are being allowed, then you have two
            // options for changing the code below. If the duplicates
            // are stored as unique nodes, then you can add the new
            // node as either a predecessor or successor by eliminating
            // the equality test and adding equality to either of the
            // other two tests.
            // If the duplicates are stored by increasing a count
            // stored in the node, then the action taken on equality
            // should be to increase that count and return true. If
            // this is the case, then don't forget to release
            // the newNode you created (or choose to only create it
            // if it is needed).
            if (data == curr->data) { delete newNode; return false; }
            else if (data < curr->data) curr = curr->left;
            else curr = curr->right;
        }
        if (data < prev->data) prev->left = newNode;
        else prev->right = newNode;
    }
    return true;
}

template<typename T>
bool bintree<T>::find(const T& data) const {
    Node<T> *curr;
    bool found = false;

if (root != NULL) {
        curr = root;
        while (curr != NULL && !found) {
            if (data == curr->data) found = true;
            else if (data < curr->data) curr = curr->left;
            else curr = curr->right;
        }
    }

return found;
}

#endif

Test Program

#include "bintree.h"
#include <iostream>
using std::cout;

const int SIZE = 1000;

int find(int val, int ar[], int sz) {
   for (int pos=0; pos<sz; pos++) {
      if (ar[pos] == val) return pos;
   }
   return -1;
}

int main(int argc, char* argv[]) {
   srand(time(NULL));
   int nums[SIZE];
   int n;
   int insertErrors = 0;
   int deleteErrors = 0;
   int numints = 0;

bintree<int> t;
   while (numints < SIZE) {
      n = rand() % (SIZE << 1);
      cout << "Trying to insert " << n;
      int pos = find(n, nums, numints);
      bool ok = t.insert(n);
      if (pos==-1) {
         nums[numints++] = n;
         if (!ok) {
            cout << " tree insert failed\n";
            insertErrors++;
         } else {
            cout << " success on both - good\n";
         }
      } else {
         if (ok) {
            cout << " tree inserted duplicate\n";
            insertErrors++;
         } else {
            cout << " both inserts failed - good\n";
         }
      }
   }
   cout << "Insert errors: " << insertErrors << '\n';

for (int i=0; i<(SIZE << 1); i++) {
      n = rand() % (SIZE << 1);
      cout << "Trying to delete " << n;
      int pos = find(n, nums, numints);
      if (pos != -1) {
         nums[pos] = nums[numints-1];
         numints--;
      }
      bool ok = t.deleteNode(n);
      if (pos==-1) {
         if (!ok) {
            cout << " failed on both - good\n";
         } else {
            cout << " tree deleted missing item\n";
            deleteErrors++;
         }
      } else {
         if (ok) {
            cout << " both deletes worked\n";
         } else {
            cout << " tree failed to delete\n";
            deleteErrors++;
         }
      }
   }
   cout << "Delete errors: " << deleteErrors << '\n';
   cout << "Insert errors: " << insertErrors << '\n';
   return 0;
}