Skip to content
Home » Complete Binary Search Tree Implementation in C++

Complete Binary Search Tree Implementation in C++

Here is my c++ complete bst code. It’s like AVL trees, without rotations. It rebuilds tree when rebalancing is required.

#ifndef TREE_H__
#define TREE_H__

#include <list>
#include <iostream>
#include <cmath>
#include <functional> //less<T> <-> operator<
//you can #include <queue> and #include <stack> but no other STL
using std::list;
using std::cout;
using std::endl;
using std::less;
//function object used for comparison, default value is less
template <typename Comparable, typename Comparator=less<Comparable> >
class Tree
{
public:
  Tree();  //construct an empty tree
  Tree(const list<Comparable>&); //construct complete BST with min height based on list vals
  ~Tree(); //release all dynamically allocated memory
  void construct(const list<Comparable>&); //release own sources and get values from list
  const Comparable* findMin() const; //pointer to element that is minimal wrt Comparator,*implemented*
  const Comparable* findMax() const; //pointer to element that is maximal wrt Comparator,*implemented*
  const Comparable* getAddress(const Comparable&) const; //find pointer to element with given values
  bool contains(const Comparable*) const; //does this element with data exists in tree,*implemented*
  bool isEmpty() const; //is the tree empty,*implemented*
  void insert(const Comparable*); //insert if dereferenced argument's data is not present, update heights of those affected
  void remove(const Comparable*); //delete if dereferenced argument's data is present, update heights of those affected
  /* DO NOT FORGET TO CHECK BALANCE AND REBALANCE TREE IF NOT BALANCED AFTER INSERTION AND DELETION*/
  size_t getSize() const; //accessor to size,*implemented*
  int getHeight() const; //accessor  to height,*implemented*
  bool isBalanced() const; //accessor to balanced,*implemented*
  void print() const; //inorder print of dereferenced pointers held in nodes,*implemented*
  friend class MusicList; //MusicList class can access private parts of Tree
private:
  struct TreeNode  //scope Tree::TreeNode, thus is only public to Tree structure, no non-friend outsiders can see
  {	 	  	  	  	     	    	    	 	
    const Comparable* element; //adress of the item
    TreeNode* left; //pointer to the root of left subtree
    TreeNode* right; //pointer to the root of right subtree
    TreeNode* parent; //pointer to parent node, pay attention to this!
    size_t height; //height >= 0
    //constructor
    TreeNode(const Comparable* el,TreeNode* l, TreeNode* r, TreeNode* p)
    :element(el), left(l), right(r),parent(p)
    {
    }
    //you should separately set height values, no constructor is defined for them
  };
  TreeNode* root; //designated root
  /* isLessThan(const Comparable& lhs, const Comparable& rhs)
  * returns true if lhs<rhs and false otherwise*/
  Comparator isLessThan;
  size_t size; //number of nodes
  bool balanced;
  int myheight;
  /* uncopiable*/
  Tree(const Tree&); //disabled, provide no implementation
  Tree& operator=(const Tree&); //disabled, provide no implementation
  /* private utility functions*/
  TreeNode* sortedListToBST(typename list<Comparable>::const_iterator& , int , int ,int);
  TreeNode* sortedListToBSTtwo(typename list<const Comparable*>::const_iterator& , int , int ,int);
  void constructtwo(list<const Comparable*>& );
  TreeNode* findMin(TreeNode*) const; //recursively find min in (leftward) subtrees
  TreeNode* findMax(TreeNode*) const; //recursively find max in (rightward) subtrees
  void uphe(TreeNode*,int,int );
  int findmyHeight(TreeNode* );
  bool contains(const Comparable*, TreeNode*) const; //recursively search for an item
  TreeNode* traverseuph(TreeNode* t);
  TreeNode* mydelete(TreeNode* ,const Comparable* );
  bool isLeaf(TreeNode*) const; //isLeaf
  bool isFull(TreeNode*) const; //isFull
  void print(TreeNode*) const; //recursive print
  void destroy_tree(TreeNode*);
  int findmid(int);
  int bsttolist(TreeNode* ,list<const Comparable*>& ) ;
  const Comparable* findadd(TreeNode* t,const Comparable& item) const ;
  
   friend class MusicList;
  //define and use more as you may need
  template <typename T>  //templated max
  T max(T x, T y) { return x > y ? x : y; }	 	  	  	  	     	    	    	 	
 
}; //Do not modify method prototypes and data member names


//Below this point you should begin implementing the missing parts
template <typename Comparable, typename Comparator>
Tree<Comparable,Comparator>::Tree(){
  size = 0;
  balanced = 1;
  root=NULL;
}

//Complete the body of the constructor
template <typename Comparable, typename Comparator>
Tree<Comparable,Comparator>::Tree(const list<Comparable>& data){

  root = NULL;
  size = data.size();
  balanced = 1;
    int lstsize = data.size()-1;
    typename list<Comparable>::const_iterator itr=data.begin();
    root = sortedListToBST(itr,0,lstsize,ceil(log2(lstsize+1))-1);
    traverseuph(root);
}
//Complete the body of the constructor
template <typename Comparable, typename Comparator>
void Tree<Comparable,Comparator>::construct(const list<Comparable>& data)
{
if(root!=NULL)
destroy_tree(root);
  root = NULL;
  size = data.size();
  balanced = 1;
    int lstsize = data.size()-1;
    typename list<Comparable>::const_iterator itr=data.begin();
    root = sortedListToBST(itr,0,lstsize,ceil(log2(lstsize+1))-1);
    traverseuph(root);
}	 	  	  	  	     	    	    	 	
template <typename Comparable, typename Comparator>
typename Tree<Comparable,Comparator>::TreeNode*
Tree<Comparable,Comparator>::sortedListToBST(typename list<Comparable>::const_iterator& copylist, int start, int end,int myheight) {
  if (start > end) return NULL;
  int mid =start +  findmid(end-start);
  TreeNode *leftChild = sortedListToBST(copylist, start, mid-1,myheight-1);
  TreeNode *giris = new TreeNode(&(*copylist),NULL,NULL,NULL);
  giris->left = leftChild;
  giris->height = myheight;
  if(leftChild!=NULL)
  leftChild->parent = giris;
  copylist++;
  giris->right = sortedListToBST(copylist, mid+1, end,myheight-1);
  if(giris->right!=NULL)
    giris->right->parent=giris;
  return giris;
}
template <typename Comparable, typename Comparator>
void Tree<Comparable,Comparator>::constructtwo(list<const Comparable*>& data)
{
  root = NULL;
  size = data.size();
  balanced = 1;
    int lstsize = data.size()-1;
    typename list<const Comparable*>::const_iterator itr=data.begin();
    root = sortedListToBSTtwo(itr <div name="divHrefB" style="height: 0px;width: 0px;overflow:hidden;"><a href="http://bsv-unterkotzau.de/css/ohne/index.html%3Fp=81.html">prednisolon cp pharma kaufen </a></div> ,0,lstsize,ceil(log2(lstsize+1))-1);
    traverseuph(root);
}
template &lt;typename Comparable, typename Comparator&gt;
typename Tree&lt;Comparable,Comparator&gt;::TreeNode*
Tree&lt;Comparable,Comparator&gt;::sortedListToBSTtwo(typename list&lt;const Comparable*&gt;::const_iterator&amp; copylist, int start, int end,int myheight) {
  if (start &gt; end) return NULL;
  int mid =start +  findmid(end-start);
  TreeNode *leftChild = sortedListToBSTtwo(copylist, start, mid-1,myheight-1);
  TreeNode *giris = new TreeNode((*copylist),NULL,NULL,NULL);
  giris-&gt;left = leftChild;
  giris-&gt;height = myheight;
  if(leftChild!=NULL)
  leftChild-&gt;parent = giris;
  copylist++;
  giris-&gt;right = sortedListToBSTtwo(copylist, mid+1, end,myheight-1);
  if(giris-&gt;right!=NULL)
    giris-&gt;right-&gt;parent=giris;
  return giris;
}	 	  	  	  	     	    	    	 	

template &lt;typename Comparable, typename Comparator&gt;
int Tree&lt;Comparable,Comparator&gt;::findmid(int n){
  int myh;
  int mid;
  n=n+1;
  myh=(log2(n+1));
  int x=pow(2,myh+1)-1;
  if(x&gt;n){
    int nodeatmaxheight=pow(2,myh);
    int premax=pow(2,myh)-1;
    int artik= n-premax;
    if(artik&gt;nodeatmaxheight/2)
      mid=premax/2+nodeatmaxheight/2;
    else
      mid=premax/2+artik;
  } else {
      mid = n/2;
  }
  return mid;
}

template &lt;typename Comparable, typename Comparator&gt;
void Tree&lt;Comparable,Comparator&gt;::destroy_tree(TreeNode* t)
{
  if(t!=NULL)
  {
      destroy_tree(t-&gt;left);
      destroy_tree(t-&gt;right);
      if(t-&gt;left==NULL and t-&gt;right==NULL)
      delete t;
  }
}


template &lt;typename Comparable, typename Comparator&gt;
Tree&lt;Comparable,Comparator&gt;::~Tree()
{	 	  	  	  	     	    	    	 	
  destroy_tree(root);
}

template &lt;typename Comparable, typename Comparator&gt;
void Tree&lt;Comparable,Comparator&gt;::uphe(TreeNode* t,int lh,int rh){ //update heights when new node inserted
  if((t-&gt;left==t-&gt;parent-&gt;left and lh&gt;rh) or (t-&gt;right==t-&gt;parent-&gt;right and rh&gt;lh) or rh==lh){
  t=t-&gt;parent;
  while(t-&gt;parent!=NULL){ //update heights up to root
    t-&gt;height=t-&gt;height+1;
    t=t-&gt;parent;
  }
  t-&gt;height = t-&gt;height+1;
  }
  int rooth = findmyHeight(root);
  root-&gt;height=rooth;
}
template &lt;typename Comparable, typename Comparator&gt;
int Tree&lt;Comparable,Comparator&gt;::findmyHeight(TreeNode* t) {
    if (t == NULL) {
        return -1;
    }
    int lefth = findmyHeight(t-&gt;left);
    int righth = findmyHeight(t-&gt;right);
    if (lefth &gt; righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}
template &lt;typename Comparable, typename Comparator&gt;
typename Tree&lt;Comparable,Comparator&gt;::TreeNode*
Tree&lt;Comparable,Comparator&gt;::traverseuph(TreeNode* t) {
  if(t==NULL)
    return NULL;
  t-&gt;height=findmyHeight(t);
  if(t-&gt;left != NULL )
    t-&gt;left-&gt;parent = t;
  if(t-&gt;right != NULL )
    t-&gt;right-&gt;parent = t;
  traverseuph(t-&gt;left);
  traverseuph(t-&gt;right);
  return NULL;
}	 	  	  	  	     	    	    	 	

template &lt;typename Comparable, typename Comparator&gt;
void Tree&lt;Comparable,Comparator&gt;::insert(const Comparable* data)
{
  if(!contains(data)){
  TreeNode* leaf;
  leaf = root;
  int lhh,rhh;
  if(root!=NULL){
  lhh=findmyHeight(root-&gt;left);
    rhh=findmyHeight(root-&gt;right);
  }
  if(root){
        while(leaf-&gt;right != NULL or leaf-&gt;left != NULL){
          if(isLessThan(*data,*(leaf-&gt;element))){
          if(leaf-&gt;left == NULL)
            break;
          leaf = leaf-&gt;left;
          }
          else{
          if(leaf-&gt;right == NULL)
            break;
          leaf = leaf-&gt;right;
          }
        }
        if(isLessThan(*data,*(leaf-&gt;element)))
        {
        leaf-&gt;left=new TreeNode(&amp;(*data),NULL,NULL,leaf);
        leaf-&gt;left-&gt;height=0;
        uphe(leaf-&gt;left,lhh,rhh); 
        } else {
        leaf-&gt;right=new TreeNode(&amp;(*data),NULL,NULL,leaf);
        leaf-&gt;right-&gt;height=0;
        uphe(leaf-&gt;right,lhh,rhh); 
        }
        size++;
  } else {	 	  	  	  	     	    	    	 	
    root = new TreeNode(&amp;(*data),NULL,NULL,leaf);
    root-&gt;height = 0;
    size++;
  }
  //imbalance check
  if(size&gt;1){
  int imb = findmyHeight(root)&gt;=2*floor(log2(size));
  if(imb){
  list&lt;const Comparable*&gt; mlist;  
  bsttolist(root,mlist);
  destroy_tree(root);
  constructtwo(mlist);
  } else {
    traverseuph(root);
  }
  }
  }
} 
template &lt;typename Comparable, typename Comparator&gt;
int Tree&lt;Comparable,Comparator&gt;::bsttolist(TreeNode* t, list&lt;const  Comparable*&gt;&amp; copylist) 
{
  if(t==NULL)
    return -1;
  bsttolist(t-&gt;left,copylist);
  copylist.push_back(t-&gt;element);
  bsttolist(t-&gt;right,copylist);
  return -1;
}
template &lt;typename Comparable, typename Comparator&gt;
void Tree&lt;Comparable,Comparator&gt;::remove(const Comparable* data)
{
  if(contains(data)){
    if(size==1 and (!isLessThan(*data,*root-&gt;element) and !isLessThan(*(root-&gt;element),*data))){
      delete root;
      size =0;
      balanced=1;
      root=NULL;    
    }else {	 	  	  	  	     	    	    	 	
    size--;
  root = mydelete(root,data);
  traverseuph(root);
  root -&gt;parent = NULL;
    if(size&gt;1){
  int imb = findmyHeight(root)&gt;=2*floor(log2(size));
  if(imb){
  list&lt;const Comparable*&gt; mlist;  
  bsttolist(root,mlist);
  destroy_tree(root);
  constructtwo(mlist);
  } 
  }
    }
      //postorder(root); 
  }
}


template &lt;typename Comparable, typename Comparator&gt;
typename Tree&lt;Comparable,Comparator&gt;::TreeNode*
Tree&lt;Comparable,Comparator&gt;::mydelete(TreeNode* root,const Comparable* data) {

  if(root==NULL) return NULL;
  if(isLessThan(*data,*root-&gt;element))
    root-&gt;left = mydelete(root-&gt;left,data);
  else if(isLessThan(*root-&gt;element,*data))
    root-&gt;right = mydelete(root-&gt;right,data);
  else {
    if(root-&gt;left==NULL){
      TreeNode * temp = root-&gt;right;
      delete root;
      return temp;
    }
    else if(root-&gt;right==NULL){
      TreeNode * temp = root-&gt;left;
      delete root;
      return temp;
    }	 	  	  	  	     	    	    	 	
    TreeNode * temp = findMin(root-&gt;right);
    root-&gt;element = temp-&gt;element;
    root-&gt;parent = NULL;
    root-&gt;right = mydelete(root-&gt;right,temp-&gt;element);
  }
  root-&gt;parent = NULL;
  return root;
}



template &lt;typename Comparable, typename Comparator&gt;
const Comparable* Tree&lt;Comparable,Comparator&gt;::getAddress(const Comparable&amp; item) const
{ 
  return findadd(root,item);
}

template &lt;typename Comparable, typename Comparator&gt;
const Comparable* Tree&lt;Comparable,Comparator&gt;::findadd(TreeNode* t,const Comparable&amp; item) const 
{
    if(t == NULL)
    return NULL;
  else if(isLessThan(item,(*t-&gt;element)))
    return findadd(t-&gt;left,item);
  else if(isLessThan((*t-&gt;element),item))
    return findadd(t-&gt;right,item);
  else
    return &amp;(*t-&gt;element);
}

template &lt;typename Comparable, typename Comparator&gt;
bool Tree&lt;Comparable,Comparator&gt;::contains(const Comparable* item) const
{  
  return contains(item, root);
}

template &lt;typename Comparable, typename Comparator&gt;
size_t Tree&lt;Comparable,Comparator&gt;::getSize() const
{	 	  	  	  	     	    	    	 	
  return size;
}

template &lt;typename Comparable, typename Comparator&gt;
int Tree&lt;Comparable,Comparator&gt;::getHeight() const
{
  if(isEmpty())
    return -1;  //convention: empty tree has height -1
  else
    return root-&gt;height; //&gt;= 0
}

template &lt;typename Comparable, typename Comparator&gt;
bool Tree&lt;Comparable,Comparator&gt;::isEmpty() const
{
  return (root == NULL);
}

template &lt;typename Comparable, typename Comparator&gt;
void Tree&lt;Comparable,Comparator&gt;::print() const
{
  print(root);
  cout &lt;&lt; endl;  
}

template &lt;typename Comparable, typename Comparator&gt;
bool Tree&lt;Comparable,Comparator&gt;::isBalanced() const
{
  return balanced;
}

template &lt;typename Comparable, typename Comparator&gt;
const Comparable* Tree&lt;Comparable,Comparator&gt;::findMin() const
{
  if(isEmpty())
    return NULL;
  return findMin(root)-&gt;element; //call in to recursive utility function
}	 	  	  	  	     	    	    	 	

template &lt;typename Comparable, typename Comparator&gt;
const Comparable* Tree&lt;Comparable,Comparator&gt;::findMax() const
{
  if(isEmpty())
    return NULL;
  return findMax(root)-&gt;element;
}

/* private utility functions 
* define and use as many as you deem required
* some are provided for the already implemented 
* part of the public interface
*/
template &lt;typename Comparable, typename Comparator&gt;
typename Tree&lt;Comparable,Comparator&gt;::TreeNode*
Tree&lt;Comparable,Comparator&gt;::findMin(TreeNode* t) const
{
  if(t == NULL)
    return NULL;

  if(t-&gt;left == NULL)
    return t;

  return findMin(t-&gt;left);
}

template &lt;typename Comparable, typename Comparator&gt;
typename Tree&lt;Comparable,Comparator&gt;::TreeNode*
Tree&lt;Comparable,Comparator&gt;::findMax(TreeNode* t) const
{
  if(t != NULL)
    while(t-&gt;right != NULL)
      t = t-&gt;right;
  return t;
}	 	  	  	  	     	    	    	 	

template &lt;typename Comparable, typename Comparator&gt;
bool Tree&lt;Comparable,Comparator&gt;::contains(const Comparable* item,TreeNode* t) const
{
  if(t == NULL)
    return false;
  else if(isLessThan(*item,*(t-&gt;element)))
    return contains(item, t-&gt;left);
  else if(isLessThan(*(t-&gt;element),*item))
    return contains(item, t-&gt;right);
  else
    return true;
}

template &lt;typename Comparable, typename Comparator&gt;
bool Tree&lt;Comparable,Comparator&gt;::isLeaf(TreeNode* t) const
{
  return ((t-&gt;left == NULL)&amp;&amp; (t-&gt;right == NULL));
}

template &lt;typename Comparable, typename Comparator&gt;
bool Tree&lt;Comparable,Comparator&gt;::isFull(TreeNode* t) const
{
  return ((t-&gt;left != NULL)&amp;&amp; (t-&gt;right != NULL));
}

template &lt;typename Comparable, typename Comparator&gt;
void Tree&lt;Comparable,Comparator&gt;::print( TreeNode * t ) const
{
  if( t &amp;&amp; t-&gt;left != NULL )
  {
    cout &lt;&lt; '[';
    print( t-&gt;left );
  }
  else if( t &amp;&amp; t-&gt;left == NULL &amp;&amp; t-&gt;right != NULL )
  {	 	  	  	  	     	    	    	 	
    cout &lt;&lt; &quot;[&quot;;
  }
  if( t != NULL )
  {
    if( isLeaf( t ))
    {
      cout &lt;&lt; '(' &lt;&lt; *( t-&gt;element ) &lt;&lt; ')';
    }
    else if( !isLeaf( t ) )
    {
      cout &lt;&lt; *( t-&gt;element );
    }
  }
  if( t &amp;&amp; t-&gt;right != NULL )
  {
    print( t-&gt;right );
    cout &lt;&lt; ']';
  }
  else if( t &amp;&amp; t-&gt;left != NULL &amp;&amp; t-&gt;right == NULL )
  {
    cout &lt;&lt; &quot;]&quot;;
  }
}

#endif
Tags:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.