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 <typename Comparable, typename Comparator> typename Tree<Comparable,Comparator>::TreeNode* Tree<Comparable,Comparator>::sortedListToBSTtwo(typename list<const Comparable*>::const_iterator& copylist, int start, int end,int myheight) { if (start > 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->left = leftChild; giris->height = myheight; if(leftChild!=NULL) leftChild->parent = giris; copylist++; giris->right = sortedListToBSTtwo(copylist, mid+1, end,myheight-1); if(giris->right!=NULL) giris->right->parent=giris; return giris; } template <typename Comparable, typename Comparator> int Tree<Comparable,Comparator>::findmid(int n){ int myh; int mid; n=n+1; myh=(log2(n+1)); int x=pow(2,myh+1)-1; if(x>n){ int nodeatmaxheight=pow(2,myh); int premax=pow(2,myh)-1; int artik= n-premax; if(artik>nodeatmaxheight/2) mid=premax/2+nodeatmaxheight/2; else mid=premax/2+artik; } else { mid = n/2; } return mid; } template <typename Comparable, typename Comparator> void Tree<Comparable,Comparator>::destroy_tree(TreeNode* t) { if(t!=NULL) { destroy_tree(t->left); destroy_tree(t->right); if(t->left==NULL and t->right==NULL) delete t; } } template <typename Comparable, typename Comparator> Tree<Comparable,Comparator>::~Tree() { destroy_tree(root); } template <typename Comparable, typename Comparator> void Tree<Comparable,Comparator>::uphe(TreeNode* t,int lh,int rh){ //update heights when new node inserted if((t->left==t->parent->left and lh>rh) or (t->right==t->parent->right and rh>lh) or rh==lh){ t=t->parent; while(t->parent!=NULL){ //update heights up to root t->height=t->height+1; t=t->parent; } t->height = t->height+1; } int rooth = findmyHeight(root); root->height=rooth; } template <typename Comparable, typename Comparator> int Tree<Comparable,Comparator>::findmyHeight(TreeNode* t) { if (t == NULL) { return -1; } int lefth = findmyHeight(t->left); int righth = findmyHeight(t->right); if (lefth > righth) { return lefth + 1; } else { return righth + 1; } } template <typename Comparable, typename Comparator> typename Tree<Comparable,Comparator>::TreeNode* Tree<Comparable,Comparator>::traverseuph(TreeNode* t) { if(t==NULL) return NULL; t->height=findmyHeight(t); if(t->left != NULL ) t->left->parent = t; if(t->right != NULL ) t->right->parent = t; traverseuph(t->left); traverseuph(t->right); return NULL; } template <typename Comparable, typename Comparator> void Tree<Comparable,Comparator>::insert(const Comparable* data) { if(!contains(data)){ TreeNode* leaf; leaf = root; int lhh,rhh; if(root!=NULL){ lhh=findmyHeight(root->left); rhh=findmyHeight(root->right); } if(root){ while(leaf->right != NULL or leaf->left != NULL){ if(isLessThan(*data,*(leaf->element))){ if(leaf->left == NULL) break; leaf = leaf->left; } else{ if(leaf->right == NULL) break; leaf = leaf->right; } } if(isLessThan(*data,*(leaf->element))) { leaf->left=new TreeNode(&(*data),NULL,NULL,leaf); leaf->left->height=0; uphe(leaf->left,lhh,rhh); } else { leaf->right=new TreeNode(&(*data),NULL,NULL,leaf); leaf->right->height=0; uphe(leaf->right,lhh,rhh); } size++; } else { root = new TreeNode(&(*data),NULL,NULL,leaf); root->height = 0; size++; } //imbalance check if(size>1){ int imb = findmyHeight(root)>=2*floor(log2(size)); if(imb){ list<const Comparable*> mlist; bsttolist(root,mlist); destroy_tree(root); constructtwo(mlist); } else { traverseuph(root); } } } } template <typename Comparable, typename Comparator> int Tree<Comparable,Comparator>::bsttolist(TreeNode* t, list<const Comparable*>& copylist) { if(t==NULL) return -1; bsttolist(t->left,copylist); copylist.push_back(t->element); bsttolist(t->right,copylist); return -1; } template <typename Comparable, typename Comparator> void Tree<Comparable,Comparator>::remove(const Comparable* data) { if(contains(data)){ if(size==1 and (!isLessThan(*data,*root->element) and !isLessThan(*(root->element),*data))){ delete root; size =0; balanced=1; root=NULL; }else { size--; root = mydelete(root,data); traverseuph(root); root ->parent = NULL; if(size>1){ int imb = findmyHeight(root)>=2*floor(log2(size)); if(imb){ list<const Comparable*> mlist; bsttolist(root,mlist); destroy_tree(root); constructtwo(mlist); } } } //postorder(root); } } template <typename Comparable, typename Comparator> typename Tree<Comparable,Comparator>::TreeNode* Tree<Comparable,Comparator>::mydelete(TreeNode* root,const Comparable* data) { if(root==NULL) return NULL; if(isLessThan(*data,*root->element)) root->left = mydelete(root->left,data); else if(isLessThan(*root->element,*data)) root->right = mydelete(root->right,data); else { if(root->left==NULL){ TreeNode * temp = root->right; delete root; return temp; } else if(root->right==NULL){ TreeNode * temp = root->left; delete root; return temp; } TreeNode * temp = findMin(root->right); root->element = temp->element; root->parent = NULL; root->right = mydelete(root->right,temp->element); } root->parent = NULL; return root; } template <typename Comparable, typename Comparator> const Comparable* Tree<Comparable,Comparator>::getAddress(const Comparable& item) const { return findadd(root,item); } template <typename Comparable, typename Comparator> const Comparable* Tree<Comparable,Comparator>::findadd(TreeNode* t,const Comparable& item) const { if(t == NULL) return NULL; else if(isLessThan(item,(*t->element))) return findadd(t->left,item); else if(isLessThan((*t->element),item)) return findadd(t->right,item); else return &(*t->element); } template <typename Comparable, typename Comparator> bool Tree<Comparable,Comparator>::contains(const Comparable* item) const { return contains(item, root); } template <typename Comparable, typename Comparator> size_t Tree<Comparable,Comparator>::getSize() const { return size; } template <typename Comparable, typename Comparator> int Tree<Comparable,Comparator>::getHeight() const { if(isEmpty()) return -1; //convention: empty tree has height -1 else return root->height; //>= 0 } template <typename Comparable, typename Comparator> bool Tree<Comparable,Comparator>::isEmpty() const { return (root == NULL); } template <typename Comparable, typename Comparator> void Tree<Comparable,Comparator>::print() const { print(root); cout << endl; } template <typename Comparable, typename Comparator> bool Tree<Comparable,Comparator>::isBalanced() const { return balanced; } template <typename Comparable, typename Comparator> const Comparable* Tree<Comparable,Comparator>::findMin() const { if(isEmpty()) return NULL; return findMin(root)->element; //call in to recursive utility function } template <typename Comparable, typename Comparator> const Comparable* Tree<Comparable,Comparator>::findMax() const { if(isEmpty()) return NULL; return findMax(root)->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 <typename Comparable, typename Comparator> typename Tree<Comparable,Comparator>::TreeNode* Tree<Comparable,Comparator>::findMin(TreeNode* t) const { if(t == NULL) return NULL; if(t->left == NULL) return t; return findMin(t->left); } template <typename Comparable, typename Comparator> typename Tree<Comparable,Comparator>::TreeNode* Tree<Comparable,Comparator>::findMax(TreeNode* t) const { if(t != NULL) while(t->right != NULL) t = t->right; return t; } template <typename Comparable, typename Comparator> bool Tree<Comparable,Comparator>::contains(const Comparable* item,TreeNode* t) const { if(t == NULL) return false; else if(isLessThan(*item,*(t->element))) return contains(item, t->left); else if(isLessThan(*(t->element),*item)) return contains(item, t->right); else return true; } template <typename Comparable, typename Comparator> bool Tree<Comparable,Comparator>::isLeaf(TreeNode* t) const { return ((t->left == NULL)&& (t->right == NULL)); } template <typename Comparable, typename Comparator> bool Tree<Comparable,Comparator>::isFull(TreeNode* t) const { return ((t->left != NULL)&& (t->right != NULL)); } template <typename Comparable, typename Comparator> void Tree<Comparable,Comparator>::print( TreeNode * t ) const { if( t && t->left != NULL ) { cout << '['; print( t->left ); } else if( t && t->left == NULL && t->right != NULL ) { cout << "["; } if( t != NULL ) { if( isLeaf( t )) { cout << '(' << *( t->element ) << ')'; } else if( !isLeaf( t ) ) { cout << *( t->element ); } } if( t && t->right != NULL ) { print( t->right ); cout << ']'; } else if( t && t->left != NULL && t->right == NULL ) { cout << "]"; } } #endif