Search Tree

bst_tree.hpp

#include <iostream>
#include <stack>
template<typename KeyType, typename Comparator = std::less<KeyType> >
class binary_search_tree{

protected:
    Comparator isLessThan;
    class  bst_node{
    public:
        KeyType key;
        int num_child;
        bst_node * left,* right;

        bst_node * getNext();
        bst_node(KeyType key):key(key),num_child(1),
            left(NULL), right(NULL){}
    };

    bst_node * root;

public:
    class iterator{
        friend class binary_search_tree;
    private:
        bst_node * current;
    public:
        iterator(bst_node * root):current(root){}

        bool operator==(const iterator & rhs) const{
            return this->current == rhs.current;
        }

        bool operator != (const iterator & rhs) const {
            return !(*this == rhs);
        }

        iterator operator++ (int){
            iterator tmp(*this);
            bst_node * nxt = this->current->getNext();
            this->current = nxt; // current iterator point to next
            return tmp; // return old;
        }

        const KeyType & operator*(){ return current->key;}
    };
    binary_search_tree():root(NULL){}
    virtual ~binary_search_tree();

    iterator begin(){
        bst_node * temp = root;
        while (temp != NULL && temp->left != NULL)
        {
                temp = temp->left;
        }
        return iterator(temp);
    }
    iterator end(){return iterator(NULL);}

    std::pair<iterator, iterator> find(KeyType key);
    virtual iterator insert(KeyType key);
protected:
    iterator __insert(bst_node* key, std::stack<bst_node*> & parents);
};


template <typename KeyType, typename Comparator>
std::ostream & operator << (std::ostream & out,
                                binary_search_tree<KeyType, Comparator> & bstTree){
    typename binary_search_tree<KeyType, Comparator>::iterator it = bstTree.begin();
    out << "{";
    if (it != bstTree.end()){
        out << *it;
        it++;
    }
    for (; it != bstTree.end();it++){
            out<< ", "<< *it;
    }
    out << "}";
    return out;
}

template <typename KeyType, typename Comparator>
typename binary_search_tree<KeyType, Comparator>::bst_node *
        binary_search_tree<KeyType, Comparator>::bst_node::getNext()
{
    bst_node * temp = this->right;
    if (temp == NULL)
        return NULL;
    if (right->num_child > this->num_child)
        return right;		//Threaded link

    //getSuccesor on bottom
    while (temp->left != NULL && temp->num_child > temp->left->num_child)
    {
        temp = temp->left;
    }
    return temp;
}

template <typename KeyType, typename Comparator>
binary_search_tree<KeyType, Comparator>::~binary_search_tree()
{
    for (binary_search_tree::iterator it = begin(); it != end();){
        binary_search_tree::iterator tmp = it++;
        delete tmp.current;
    }
}




//return the parent and node containing the key if present
template <typename KeyType, typename Comparator>
std::pair<
typename binary_search_tree<KeyType, Comparator>::iterator,
typename binary_search_tree<KeyType, Comparator>::iterator
          >
    binary_search_tree<KeyType, Comparator>::find(KeyType node)
{
    bst_node *node_ptr = root, *parent_ptr = root;
    std::stack<bst_node*> nodes;
    while (node_ptr != NULL && node != node_ptr->key)
    {
        nodes.push(node_ptr);
        if (isLessThan(node , node_ptr->key))
        {
            parent_ptr = node_ptr;
            node_ptr = node_ptr->left;

            if (node_ptr != NULL &&
                node_ptr->num_child > parent_ptr->num_child)				//Extra op
                break;
        }
        else
        {
            parent_ptr = node_ptr;
            node_ptr = node_ptr->right;

            if (node_ptr != NULL &&
                node_ptr->num_child > parent_ptr->num_child)				//Extra op
                break;
        }
    }
    return std::make_pair(iterator(parent_ptr),iterator(node_ptr));
}

template <typename KeyType, typename Comparator>
        typename binary_search_tree<KeyType, Comparator>::iterator
binary_search_tree<KeyType, Comparator>::insert(KeyType node){
    std::stack<bst_node*> parents;
    bst_node* newNode = new bst_node(node);
    iterator it = __insert(newNode, parents);
    if (it.current != NULL){
        while (!parents.empty())
        {
            parents.top()->num_child++;
            // Logn extra updates to maintain size of subtrees
            parents.pop();
        }
        return it;
    }
    //duplicate node cannot be inserted so deleting it
    delete newNode;
    return it;
}

template <typename KeyType, typename Comparator>
        typename binary_search_tree<KeyType, Comparator>::iterator
binary_search_tree<KeyType, Comparator>::__insert(bst_node* node,
                                                  std::stack<bst_node*> & nodes ){
    bst_node *node_ptr = root, *parent_ptr = root;
    while (node_ptr != NULL && node->key != node_ptr->key)
    {
        nodes.push(node_ptr);
        if (isLessThan(node->key, node_ptr->key))
        {
            parent_ptr = node_ptr;
            node_ptr = node_ptr->left;
            if (node_ptr != NULL &&
                    node_ptr->num_child > parent_ptr->num_child)				//Extra op
                break;
        } else {
            parent_ptr = node_ptr;
            node_ptr = node_ptr->right;
            if (node_ptr != NULL &&
                    node_ptr->num_child > parent_ptr->num_child)				//Extra op
                break;
        }
    }
    if (node_ptr != NULL)
    {
        if (node_ptr->key != node->key)
        {
            if (isLessThan(node->key, parent_ptr->key))
            {
                parent_ptr->left = node;
                parent_ptr->left->right = parent_ptr;
                parent_ptr->left->left = node_ptr;
            } else {
                parent_ptr->right = node;
                parent_ptr->right->left = parent_ptr;
                parent_ptr->right->right = node_ptr;
            }
            return iterator(node);
        }
        //else block is required for duplicate handling
        return iterator(NULL);
   } else { // Not found the node with given key
        if (parent_ptr != NULL)  // You have inserted either the least or largest key
        {
            if (node->key < parent_ptr->key)
            {
               parent_ptr->left = node;
               parent_ptr->left->right = parent_ptr;
            } else {
               parent_ptr->right = node;
               parent_ptr->right->left = parent_ptr;
            }
        } else {	 // Add a root Node
           root = node;
        }
    }
    return iterator(node);
}