BinarySearchTreeNode.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_BinarySearchTreeNode_h
#define VMML_BinarySearchTreeNode_h

#include "BintreeNode.h"
#include <iostream>

namespace geData {
    template <class T>
    class BinarySearchTreeNode : public BintreeNode<T>
    {
    public:
        //constructors and destructor
        BinarySearchTreeNode(T _data): BintreeNode<T>(_data) {}
        
        bool insert(T data)
        {
            if(this->data == 0L)
            {
                this->setData(data);
                return 1;
            }else{
                if(data < this->data)
                {
                    if(this->left == 0L)
                    {
                        this->left = new BinarySearchTreeNode<T>(data);
                        this->left->setParent(this);
                        return 1;
                    }else{
                        return this->left->insert(data);
                    }
                }else{ // data >= this->data
                    if(this->right == 0L)
                    {
                        this->right = new BinarySearchTreeNode<T>(data);
                        this->right->setParent(this);
                        return 1;
                    }else{
                        return this->right->insert(data);
                    }
                }
            }
        }
        
        bool remove(T data)
        {
            if(this->data == 0L)
            {   // data not in tree
                std::cout << "data not in tree" << std::endl;
            }else if(this->data == data)
            {
                return 1;
            }else{
                if(data < this->data)
                {
                    if(this->left->remove(data))
                    {
                        BinarySearchTreeNode<T>* nodeToDelete = dynamic_cast<BinarySearchTreeNode<T>*>(this->getLeft());
                        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->left = nodeToDelete->getRight();
                            }else if ( nodeToDelete->getRight() == 0L){
                                this->left = nodeToDelete->getLeft();
                            }else{
                                // case 3: node to delete is internal node
                                this->left = dynamic_cast<BinarySearchTreeNode<T>*>(nodeToDelete->getRight()->searchLeftElement());
                                if(this->left != nodeToDelete->getRight())
                                {
                                    this->left->getParent()->setLeft(0L);
                                    // falls es ein teilbaum ist der raufgenommen wird, muss am ende noch der
                                    // erste teilbaum hinugefuegt werden
                                    if(this->left->getRight() != 0L){
                                        BinarySearchTreeNode<T>* newRight = dynamic_cast<BinarySearchTreeNode<T>*>(this->left->searchRightElement());
                                        newRight->setRight(nodeToDelete->getRight());
                                    }
                                }
                                this->left->setLeft(nodeToDelete->getLeft());
                                
                            }
                            this->left->setParent(this);
                        }
                        nodeToDelete->setLeft(0L);
                        nodeToDelete->setRight(0L);
                        delete nodeToDelete;
                    }
                }else{
                    if(this->right->remove(data))
                    {
                        BinarySearchTreeNode<T>* nodeToDelete = dynamic_cast<BinarySearchTreeNode<T>*>(this->getRight());
                        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->right = nodeToDelete->getRight();
                            }else if ( nodeToDelete->getRight() == 0L){
                                this->right = nodeToDelete->getLeft();
                            }else{
                                // case 3: node to delete is internal node
                                this->right = dynamic_cast<BinarySearchTreeNode<T>*>(nodeToDelete->getRight()->searchLeftElement());
                                if(this->right != nodeToDelete->getRight())
                                {
                                    this->right->getParent()->setLeft(0L);
                                    // falls es ein teilbaum ist der raufgenommen wird, muss am ende noch der
                                    // erste teilbaum hinugefuegt werden
                                    if(this->right->getRight() != 0L){
                                        BinarySearchTreeNode<T>* newRight = dynamic_cast<BinarySearchTreeNode<T>*>(this->right->searchRightElement());
                                        newRight->setRight(nodeToDelete->getRight());
                                    }
                                }
                                this->right->setLeft(nodeToDelete->getLeft());
                            }
                            this->right->setParent(this);
                        }
                        nodeToDelete->setLeft(0L);
                        nodeToDelete->setRight(0L);
                        delete nodeToDelete;
                    }
                }
            }
            return 0;
        }
        
        virtual void printValue(){
            //T::print_value();
            std::cout << this->data <<  " ";
            std::cout << &this->data << std::endl;
        }
        
        //comparison operators
        virtual bool operator<(const BinarySearchTreeNode<T>& node) const {
            return this->data < node.getData();
        }
        
        virtual bool operator>(const BinarySearchTreeNode<T>& node) const {
            return this->data > node.getData();
        }
        
        virtual bool operator==(const BinarySearchTreeNode<T>& node) const {
            return this->data == node.getData();
        }
        
        //set and get left and right branches
        BinarySearchTreeNode<T>* getLeft() {
            return dynamic_cast<BinarySearchTreeNode<T>*>(this->left);
        }
        BinarySearchTreeNode<T>* getRight() {
            return dynamic_cast<BinarySearchTreeNode<T>*>(this->right);
        }
        
        void setLeft(BinarySearchTreeNode<T>* node){
            if(node != 0L){
                node->setParent(this);
                this->left = node;
            }else{
                this->left = 0L;
            }
        }
        
        void setRight(BinarySearchTreeNode<T> * node){
            if(node != 0L){
                node->setParent(this);
                this->right = node;
            }else{
                this->right = 0L;
            }
        }
    };
}
#endif