Binary Search Tree in C++

bst.cpp

#include <iostream>
#include <functional>
#include <algorithm>
#include <exception>
#include <stdexcept>

template<class T, class Less, class Greater>
class Node{
public:
    explicit Node(Less const& comparer, Greater const& greater);
    Node(Less const& less, Greater const& greater, T const& value);
    Node(Less const& less,  Greater const& greater,Node<T,Less,Greater>* parent, T const& value);
    ~Node();
    
    Node<T,Less,Greater>* left() ;
    Node<T,Less,Greater>* right();
    bool hasChildren() const;
    bool hasBothChildren() const;
    bool hasLeft() const;
    bool hasRight() const;
    bool hasParent() const;
    bool less(Node<T,Less,Greater>* other) const;
    bool less(T const& value) const;
    bool greater(Node<T,Less,Greater>* other) const;
    bool greater(T const& value) const;
    T const& value() const;
    
    void assignValue(T const& value);
    void clearLeft();
    void clearRight();
    void changeLeft(Node<T,Less,Greater>* node);
    void changeRight(Node<T,Less,Greater>* node);
    void changeParent(Node<T,Less,Greater>* node);
    void removeSelfFromParent();
    void removeSelfFromParentAndAssignLeft();
    void removeSelfFromParentAndAssignRight();
    void print(std::ostream& o) const;
    
    
private:
    
    void removeNode(Node<T,Less,Greater>* node);
    
    T value_;
    Less less_;
    Greater greater_;
    Node<T,Less,Greater>* parent_;
    Node<T,Less,Greater>* left_;
    Node<T,Less,Greater>* right_;
};

template<class T, class Less, class Greater>
Node<T,Less,Greater>::Node(Less const& less, Greater const& greater) : less_(less), greater_(greater), parent_(nullptr), left_(nullptr), right_(nullptr){
    
}

template<class T, class Less, class Greater>
Node<T,Less,Greater>::Node(Less const& less, Greater const& greater,T const& value) : less_(less), greater_(greater), value_(value), parent_(nullptr), left_(nullptr), right_(nullptr){
    
}

template<class T, class Less, class Greater>
Node<T,Less,Greater>::Node(Less const& less, Greater const& greater,Node<T,Less,Greater>* parent, T const& value) : less_(less), greater_(greater), value_(value), parent_(parent), left_(nullptr), right_(nullptr){
}

template<class T, class Less, class Greater>
T const& Node<T,Less,Greater>::value() const{
    return value_;
}

template<class T, class Less, class Greater>
Node<T,Less,Greater>* Node<T,Less,Greater>::right(){
    return right_;
}

template<class T, class Less, class Greater>
Node<T,Less,Greater>* Node<T,Less,Greater>::left(){
    return left_;
}

template<class T, class Less, class Greater>
bool Node<T,Less,Greater>::hasChildren() const{
    return hasLeft() || hasRight();
}

template<class T, class Less, class Greater>
bool Node<T,Less,Greater>::hasBothChildren() const{
    return hasLeft() && hasRight();
}

template<class T, class Less, class Greater>
bool Node<T,Less,Greater>::hasLeft() const{
    return left_ != nullptr;
}

template<class T, class Less, class Greater>
bool Node<T,Less,Greater>::hasRight() const{
    return right_ != nullptr;
}

template<class T, class Less, class Greater>
bool Node<T,Less,Greater>::hasParent() const{
    return parent_ != nullptr;
}

template<class T, class Less, class Greater>
bool Node<T,Less,Greater>::less(Node<T,Less,Greater>* other) const{
    return less_(value_, other->value_);
}

template<class T, class Less, class Greater>
bool Node<T,Less,Greater>::less(T const& value) const{
    return less_(value_, value);
}

template<class T, class Less, class Greater>
bool Node<T,Less,Greater>::greater(Node<T,Less,Greater>* other) const{
    return greater_(value_, other->value_);
}

template<class T, class Less, class Greater>
bool Node<T,Less,Greater>::greater(T const& value) const{
    return greater_(value_,value);
}

template<class T, class Less, class Greater>
void Node<T,Less,Greater>::assignValue(const T &value){
    value_ = value;
}

template<class T, class Less, class Greater>
void Node<T,Less,Greater>::changeLeft(Node<T,Less,Greater>* node){
    left_ = node;
    left_->changeParent(this);
}

template<class T, class Less, class Greater>
void Node<T,Less,Greater>::changeRight(Node<T,Less,Greater>* node){
    right_ = node;
    right_->changeParent(this);
}

template<class T, class Less, class Greater>
void Node<T,Less,Greater>::changeParent(Node<T,Less,Greater>* node){
    parent_ = node;
}

template<class T, class Less, class Greater>
void Node<T,Less,Greater>::removeSelfFromParent(){
    parent_->removeNode(this);
}

template<class T, class Less, class Greater>
void Node<T,Less,Greater>::removeSelfFromParentAndAssignLeft(){
    parent_->removeNode(this);
    if(parent_->hasLeft())
        parent_->changeRight(this->left());
    if(parent_->hasRight())
        parent_->changeLeft(this->left());
    this->changeLeft(nullptr);
}

template<class T, class Less, class Greater>
void Node<T,Less,Greater>::removeSelfFromParentAndAssignRight(){
    parent_->removeNode(this);
    if(parent_->hasLeft())
        parent_->changeRight(this->right());
    if(parent_->hasRight())
        parent_->changeLeft(this->right());
    this->changeRight(nullptr);
}

template<class T, class Less, class Greater>
void Node<T,Less,Greater>::print(std::ostream& o) const{
    o << value_ << " ";
}

template<class T, class Less, class Greater>
void Node<T,Less,Greater>::removeNode(Node<T,Less,Greater>* node){
    if(left_ == node){
        clearLeft();
        return;
    }
    
    if(right_ == node){
        clearRight();
        return;
    }
}

template<class T, class Less, class Greater>
void Node<T,Less,Greater>::clearLeft(){
    left_ = nullptr;
}

template<class T, class Less, class Greater>
void Node<T,Less,Greater>::clearRight(){
    right_ = nullptr;
}

template<class T, class Less, class Greater>
Node<T,Less,Greater>::~Node(){
    
    delete left_;
    delete right_;
    std::cout << "Node DTOR: " << value_ << std::endl;
}

template<class T, class L = std::less<T>, class G = std::greater<T>>
class BinaryTree{
    typedef Node<T,L,G> node_t;
public:
    BinaryTree();
    ~BinaryTree();
    void insert(T const& value);
    void print() const;
    bool contains(T const& value) const;
    void remove(T const& value);
    bool empty() const;
    T const& minimum() const;
    T const& maximum() const;
    void removeMinimum();
    void removeMaximum();
private:
    void remove_minimum_implementation(node_t* current);
    void remove_maximum_implementation(node_t* current);
    T const& minimum_implementation(node_t* current) const;
    T const& maximum_implementation(node_t* current) const;
    void print_implementation(node_t* current) const;
    void insert_implementation(node_t* current, T const& value);
    bool contains_implementation(node_t* current, T const& value) const;
    void remove_implementation(node_t* current, T const& value);
    L less_;
    G greater_;
    node_t* root_;
};

template<class T, class L, class G>
BinaryTree<T,L,G>::BinaryTree() : root_(nullptr){

}

template<class T, class L, class G>
BinaryTree<T,L,G>::~BinaryTree(){
    delete root_;
    std::cout << "BST DTOR" << std::endl;
}

template<class T, class L, class G>
bool BinaryTree<T,L,G>::empty() const {
    return root_ != nullptr;
}

template<class T, class L, class G>
void BinaryTree<T,L,G>::removeMinimum() {
    remove_minimum_implementation(root_);
}

template<class T, class L, class G>
void BinaryTree<T,L,G>::remove_minimum_implementation(node_t* current){
    while(current){
        if(!current->hasLeft()){
            current->removeSelfFromParent();
            delete current;
            return;
        }
        current = current->left();
    }
    throw std::runtime_error("Error");
}

template<class T, class L, class G>
void BinaryTree<T,L,G>::removeMaximum() {
    remove_maximim_implementation(root_);
}

template<class T, class L, class G>
void BinaryTree<T,L,G>::remove_maximum_implementation(node_t* current){
    while(current){
        if(!current->hasRight()){
            current->removeSelfFromParent();
            delete current;
            return;
        }
        current = current->right();
    }
    throw std::runtime_error("Error");
}

template<class T, class L, class G>
T const& BinaryTree<T,L,G>::minimum()  const{
    return minimum_implementation(root_);
}

template<class T, class L, class G>
T const& BinaryTree<T,L,G>::minimum_implementation(node_t* current) const{
    while(current){
        if(!current->hasLeft())
            return current->value();
        current = current->left();
    }
    throw std::runtime_error("Error");
}

template<class T, class L, class G>
T const& BinaryTree<T,L,G>::maximum() const{
    return maximum_implementation(root_);
}

template<class T, class L, class G>
T const& BinaryTree<T,L,G>::maximum_implementation(node_t* current) const{
    while(current){
        if(!current->hasRight())
            return current->value();
        current = current->right();
    }
    throw std::runtime_error("Error");
}

template<class T, class L, class G>
void BinaryTree<T,L,G>::remove(T const& value) {
    remove_implementation(root_, value);
}

template<class T, class L, class G>
void BinaryTree<T,L,G>::remove_implementation(node_t* current, T const& value) {
    if(!current) return;
    
    while(current){
        if(current->less(value)){
            current = current->right();
        }else if (current->greater(value)){
            current = current->left();
        }else{
            if(!current->hasChildren()){
                current->removeSelfFromParent();
                delete current;
                return;
            }else if (current->hasBothChildren()){
                
                auto min = minimum_implementation(current->right());
                remove_minimum_implementation(current->right());
                current->assignValue(min);
                
            }else if(current->hasLeft()){
                current->removeSelfFromParentAndAssignLeft();
                delete current;
                return;
            }else if(current->hasRight()){
                current->removeSelfFromParentAndAssignRight();
                delete current;
                return;
            }
        }
    }
}

template<class T, class L, class G>
bool BinaryTree<T,L,G>::contains(T const& value) const{
    return contains_implementation(root_, value);
}

template<class T, class L, class G>
bool BinaryTree<T,L,G>::contains_implementation(node_t* current, T const& value) const{
    if(!current) return false;
    
    while(current){
        if(current->less(value)){
            current = current->right();
        }else if (current->greater(value)){
            current = current->left();
        }else{
            return true;
        }
    }
    
    return false;
}

template<class T, class L, class G>
void BinaryTree<T,L,G>::print() const{
    print_implementation(root_);
    std::cout << std::endl;
}

template<class T, class L, class G>
void BinaryTree<T,L,G>::print_implementation(node_t* current) const{
    
    if(!current){
        return;
    }
    
    print_implementation(current->left());
    print_implementation(current->right());
    
    current->print(std::cout);
}

template<class T, class L, class G>
void BinaryTree<T,L,G>::insert(T const& value){
    insert_implementation(root_, value);
}

template<class T, class L, class G>
void BinaryTree<T,L,G>::insert_implementation(node_t* current, T const& value){
    
    if(!current){
        root_ = new node_t(less_,greater_,value);
        return;
    }
    
    while(current){
        if(current->greater(value)){ // process left subtree
            if(current->hasLeft()){
                current = current->left();
                continue;
            }
            
            current->changeLeft(new node_t(less_,greater_,value));
            break;
            
        }else if(current->less(value)){ // process right subtree
            if(current->hasRight()){
                current = current->right();
                continue;
            }
            
            current->changeRight(new node_t(less_,greater_,value));
            break;
        }else{ // already contained - update
            current->assignValue(value);
            break;
        }
    }
}

int main(int argc, const char * argv[])
{
    using namespace std;
    
    BinaryTree<int> b;
    b.insert(100);
    b.insert(50);
    b.insert(75);
    b.insert(25);
    b.insert(10);
    b.insert(150);
    b.insert(175);
    b.insert(125);
    b.insert(110);
    b.insert(115);
    
    b.print();
    
    cout << "contains 10: " << boolalpha << b.contains(10) << endl;
    cout << "contains 110: " << boolalpha << b.contains(110) << endl;
    cout << "contains 70: " << boolalpha << b.contains(70) << endl;
    cout << "minimum: " << b.minimum() << endl;
    cout << "maximum: " << b.maximum() << endl;
    b.removeMinimum();
    cout << "minimum: " << b.minimum() << endl;
    b.remove(50);
    b.print();
    return 0;
}