BinarySearchTree.h

Go to the documentation of this file.

//
//  Created by Matthias Thöny on 1/11/12.
//  Copyright (c) 2012 University of Zuerich. All rights reserved.
//
#ifndef VMML_BinarySearchTree_h
#define VMML_BinarySearchTree_h

#include "Bintree.h"
#include "BinarySearchTreeNode.h"

namespace geData {
    template <class T>
    class BinarySearchTree : public Bintree<T>
    {
    public:
        //constructors and destructor
        BinarySearchTree(): Bintree<T>() {}
        BinarySearchTree(T data):Bintree<T>(new BinarySearchTreeNode<T>(data)){}
        ~BinarySearchTree() { }
        
        //search
        BinarySearchTreeNode<T>* search(T data)
        {
            return 0L;
        }
        
        //insert in a BST
        bool insert(T data)
        {
            if(this->root != 0L)
            {
                return this->root->insert(data);
            }else{
                this->root = new BinarySearchTreeNode<T>(data);
                return true;
            }
            return false;
        }
        
        bool remove(T _data){
            if(this->root != 0L)
            {
                if(this->root->getData() == _data)
                {
                    BinarySearchTreeNode<T>* nodeToDelete = dynamic_cast<BinarySearchTreeNode<T>*>(this->root);
                    if(nodeToDelete->getLeft() == 0L && nodeToDelete->getRight() == 0L)
                    {
                        // case 1: node to delete has no children
                    }else{
                        // case 2: node to delete has one child
                        if(nodeToDelete->getLeft() == 0L)
                        {
                            this->root = nodeToDelete->getRight();
                        }else if ( nodeToDelete->getRight() == 0L){
                            this->root = nodeToDelete->getLeft();
                        }else{
                            // case 3: node to delete is internal node
                            this->root = dynamic_cast<BinarySearchTreeNode<T>*>(nodeToDelete->getRight()->searchLeftElement());
                            if(this->root != nodeToDelete->getRight())
                            {
                                this->root->getParent()->setLeft(0L);
                                // falls es ein teilbaum ist der raufgenommen wird, muss am ende noch der
                                // erste teilbaum hinugefuegt werden
                                if(this->root->getRight() != 0L){
                                    BinarySearchTreeNode<T>* newRight = dynamic_cast<BinarySearchTreeNode<T>*>(this->root->searchRightElement());
                                    newRight->setRight(nodeToDelete->getRight());
                                }
                            }
                            
                            BinarySearchTreeNode<T>* newLeft = dynamic_cast<BinarySearchTreeNode<T>*>(nodeToDelete->getLeft());
                            this->root->setLeft(newLeft);
                        }
                        this->root->setParent(0L);
                    }
                    nodeToDelete->setLeft(0L);
                    nodeToDelete->setRight(0L);
                    delete nodeToDelete;
                }else{
                    return this->root->remove(_data); 
                }
            }else{ // no tree exists
                return true;
            }
            return false;
            
        }
        
    };
}
#endif