BinsrySearchTree.cpp

/*
 *  File:    BinarySearchTree.cpp
 *  Prj:    Dictonary
 *
 *  Created by Will Mernagh on April 21.
 *  Copyright 2007. All rights reserved.
 *
 */
#include <iostream>
#include "nodes.h"
#include "BinarySearchTree.h"
using namespace std;

/*
 * Constructor
 */
BST::BST()
{
    setRoot(NULL);
}

/*
 * Returns the root
 */
TreeNode * BST::getRoot(){
    return root;
}

/*
 * Set the root
 */
void BST::setRoot(TreeNode *rootin){
    root = rootin;
}

/* 
 * Inserts the node into the tree
 *
 * @param    TreeNode    The Node to add to the tree
 * @return    False        if already in the tree
 */
bool BST::insert(TreeNode *tnode)
{
    TreeNode *search, *position;
    search = getRoot();

    /* If empty tree */
    if(search == NULL){

        setRoot(tnode);
        getRoot()->setLeft(NULL);
        getRoot()->setRight(NULL);
        getRoot()->setParent(NULL);
        return true;

    }

    /* if word already in the tree */
    if(find(tnode->word)){
        return false;
    }

    position = search;

    while(position != NULL){

        search = position;

        if(tnode->word > search->word){
            position = search->getRight();
        }else if (tnode->word  < search->word){
            position = search->getLeft();
        }else{
            return false; //match
        }
    }

    if(tnode->word > search->word){

        search->setRight(tnode);
        tnode->setParent(search);
        tnode->setLeft(NULL);
        tnode->setRight(NULL);


    }else if (tnode->word  < search->word){

        search->setLeft(tnode);
        tnode->setParent(search);
        tnode->setLeft(NULL);
        tnode->setRight(NULL);

    }    
    return true;

}

/* 
 * Inserts the string into the tree. 
 *
 * @param    String        The string to add to the tree
 * @return    False        if already in the tree
 */
bool BST::insert(string word)
{
    TreeNode *tnode = new TreeNode;
    tnode->word = word;
    if(BST::insert(tnode)){
        return true;
    }else{
        delete tnode;
        return false;
    }
}

/* 
 * Search for a string and return true if in tree
 *
 * @param    String        The string to search for
 * @return    True        if string in the tree
 */
bool BST::find(string word)
{
    TreeNode *search;

    search = getRoot();

    while(search != NULL){
        
        if(word > search->word){
    
            search = search->getRight();
    
        }else if (word  < search->word){
    
            search = search->getLeft();
    
        }else{
    
            return true; //match
    
        }
    }

    return false;
}

/* 
 * Search for a node and return true if in tree
 *
 * @param    String    The string encapsulated in node to search for
 * @return        True    if string in the tree
 */
TreeNode * BST::findNode(string word)
{
    TreeNode *search;

    search = getRoot();

    while(search != NULL){

        if(word > search->word){
    
            search = search->getRight();
    
        }else if (word  < search->word){
    
            search = search->getLeft();
    
        }else{
    
            return search; //match
    
        }
    }

    return NULL;
}

/* 
 * Search for the successor of a string and return it if in tree
 *
 * @param    String        The string whose successor to search for
 * @return    TreeNode    if string in the tree else return null
 */
TreeNode * BST::successor(string word)
{
    TreeNode *wordNode;
    TreeNode *search;

    wordNode = findNode(word);

    if(wordNode == NULL){
        return NULL;
    }

    if((wordNode->getRight()==NULL)&&(wordNode->getParent()==NULL)){

        return NULL; //no successor

    }else if(wordNode->getRight() != NULL) {//search down

        search = wordNode->getRight();

        while(search->getLeft() != NULL){
    
            search = search->getLeft();
    
        }

        return search;

    }else if(wordNode->getParent()->word > wordNode->word){
        return wordNode->getParent();
    }else{

        //Search up

        search = wordNode;

        while((search->getParent() != NULL) && 
                (search->getParent()->word < wordNode->word)){
    
            search = search->getParent();
    
        }

        return search->getParent();


    }
    return NULL;
}

/* 
 * Display the items in a tree in order
 *
 * @param    TreeNode    The next node to recurse on
 */
void BST::recurseDisplay(TreeNode *node)
{
    if(node != NULL){

        recurseDisplay(node->getLeft());
        cout<<node->word<<"";

        if(node->getParent() != NULL){
    
            cout << "(" << node->getParent()->word<<")\n";

        }else{

            cout<<"\n";

        }

        recurseDisplay(node->getRight());

    }
}

/* 
 * Display the items in a tree in order
 *
 */
void BST::display()
{
    recurseDisplay(getRoot());
}

/* Delete a word from the tree
 * 
 * @param    string    The string to delete
 * @return    bool    False if it does not exist in tree
 */
bool BST::del(string word)
{
    TreeNode *todel, *scsr;
    string scsrWord;
    todel = findNode(word);


        /* does not exist */
    if(todel == NULL){
        return false;
    }

    if(todel == getRoot()){

        scsr = successor(word);

        if((scsr == NULL)&&(todel->getLeft() == NULL)){

            delete(todel);
            setRoot(NULL);
            return true;
    
        }else if(scsr == NULL){
    
            setRoot(todel->getLeft());
            todel->getLeft()->setParent(NULL);
            delete(todel);
            return true;
    
        }else{
    
            scsrWord = scsr->word;
            del(scsrWord);
            todel->word = scsrWord;
            return true;
    
        }
    }else if((todel->getLeft() == NULL)&&(todel->getRight() == NULL)){

        if((todel->getParent()->getLeft() != NULL) && 
            (todel->getParent()->getLeft()->word == todel->word)){
    
            todel->getParent()->setLeft(NULL);
    
        }else{
    
            todel->getParent()->setRight(NULL);
    
        }

        delete todel;
        return true;

    }else if(todel->getLeft() == NULL){

        if((todel->getParent()->getLeft() != NULL) && 
            (todel->getParent()->getLeft()->word == todel->word)){
    
            todel->getParent()->setLeft(todel->getRight());
            todel->getRight()->setParent(todel->getParent());
    
        }else{

            todel->getParent()->setRight(todel->getRight());
            todel->getRight()->setParent(todel->getParent());
    
        }

        delete todel;
        return true;

    }else if(todel->getRight() == NULL){ 

        if((todel->getParent()->getLeft() != NULL) && 
            (todel->getParent()->getLeft()->word == todel->word)){

            todel->getParent()->setLeft(todel->getLeft());
            todel->getLeft()->setParent(todel->getParent());

        }else{

            todel->getParent()->setRight(todel->getLeft());
            todel->getLeft()->setParent(todel->getParent());
        }

        delete todel;
        return true;

    }else{

        scsr = successor(word);
        scsrWord = scsr->word;
        del(scsr->word);
        todel->word = scsrWord;

        return true;
    }

    return false;
}

/* Destructor
 */
BST::~BST(){
    while(getRoot() != NULL){
        del(getRoot()->word);
    }
}