I have implemented a dictionary with an AVL tree, and here is the code and I need help improving it.
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <string>
#include <vector>
#include <list>
using namespace std;
class NoSuchKeyExeption {};
template<typename k, typename t>
class dictionary
{
private:
struct element
{
k key;
t data;
unsigned height;
unsigned level;
element* left;
element* right;
};
element* root;
unsigned size;
bool pinsert(element* ptr, const k &key, const t &data,element* parent);
bool pinsert_pseudo(element* ptr, element* toadd, element* parent);
element* pcopy(const element* ptr);
void pinsert_rec(const element* ptr);
void clear(element* ptr);
bool pexists(element* ptr, const k& key)const;
ostream & printos(ostream & os,element* ptr)const;
ostream & printosdes(ostream & os,element* ptr)const;
unsigned pheight(const element* ptr)const;
void calclvls(element* ptr, unsigned lvl, vector<element*> &storage, unsigned & maxlvl)const;
element* find(const k &key, element* ptr, element*& parent)const;
void find(element* ptr, vector<k> &keys)const;
void find(const t &data, element* ptr, vector<k> &keys)const;
void find(element* ptr, list<k> &keys)const;
void find(const t &data, element* ptr, list<k> &keys)const;
element* findrep(element* ptr, bool dir, element*& parent)const;
element* balance(element* ptr);
void premove(const element* ptr);
bool premove(const k &key, element* ptr, element* parent);
bool comparator(const element* ptr)const;
inline void newheight(element* ptr);
public:
dictionary();
dictionary(const dictionary<k,t> & copy);
~dictionary();
dictionary<k,t> & operator=(const dictionary<k,t> & copy);
template<typename u, typename i>
friend dictionary<u,i> operator+(const dictionary<u,i> & add1, const dictionary<u,i> & add2);
template<typename u, typename i>
friend dictionary<u,i> operator-(const dictionary<u,i> & subtract1, const dictionary<u,i> & subtract2);
dictionary<k,t> & operator+=(const dictionary<k,t> & add)
{
*this=*this+add;
return *this;
};
dictionary<k,t> & operator-=(const dictionary<k,t> & subtract)
{
*this=*this-subtract;
return *this;
};
void clear();
t& getData(const k& key)const;
vector<k> vgetKeys()const;
vector<k> vgetKeys(const t& data)const;
list<k> lgetKeys()const;
list<k> lgetKeys(const t& data)const;
unsigned int getSize()
{
return size;
};
bool empty()const
{
if(!root)
return true;
else
return false;
};
bool insert(const k &key, const t &data);
bool remove(const k &key);
inline bool exists(const k &key)const;
bool changeKey(const k &keyfrom,const k &keyto);
void printTree()const;
template<typename u, typename i>
friend bool operator==(const dictionary<u,i> & check1,const dictionary<u,i> & check2);
template<typename u, typename i>
friend bool operator!=(const dictionary<u,i> & check1,const dictionary<u,i> & check2);
template<typename u, typename i>
friend ostream & operator<< (ostream & os, const dictionary<u,i> & toprint);
void printDescend(ostream & os)const;
};
//MAI JEWELRY
template<typename k, typename t>
bool dictionary<k,t>::pinsert(element* ptr, const k &key, const t &data,element* parent)
{
if(root==nullptr)
{
element* temp = new element;
temp->key=key;
temp->data=data;
temp->height=1;
temp->left=nullptr;
temp->right=nullptr;
root=temp;
size=1;
return true;
}
if(ptr->key<key)
{
if(ptr->right==nullptr)
{
element * temp=new element;
temp->key=key;
temp->data=data;
temp->height=1;
temp->left=nullptr;
temp->right=nullptr;
ptr->right=temp;
size++;
newheight(ptr);
return true;
}
if(pinsert(ptr->right,key,data,ptr))
{
newheight(ptr);
if(parent)
{
if(parent->right==ptr)
parent->right=balance(ptr);
else
parent->left=balance(ptr);
}
else
root=balance(ptr);
return true;
}
else
return false;
}
else if(key<ptr->key)
{
if(ptr->left==nullptr)
{
element * temp=new element;
temp->key=key;
temp->data=data;
temp->height=1;
temp->left=nullptr;
temp->right=nullptr;
ptr->left=temp;
size++;
newheight(ptr);
return true;
}
if(pinsert(ptr->left,key,data,ptr))
{
newheight(ptr);
if(parent)
{
if(parent->right==ptr)
parent->right=balance(ptr);
else
parent->left=balance(ptr);
}
else
root=balance(ptr);
return true;
}
else
return false;
}
return false;
}
template<typename k, typename t>
bool dictionary<k,t>::pinsert_pseudo(element* ptr, element* toadd, element* parent)
{
if(root==nullptr)
{
toadd->left=nullptr;
toadd->right=nullptr;
toadd->height=1;
root=toadd;
size++;
return true;
}
if(ptr->key<toadd->key)
{
if(ptr->right==nullptr)
{
toadd->height=1;
toadd->left=nullptr;
toadd->right=nullptr;
ptr->right=toadd;
size++;
newheight(ptr);
//balance(root);
return true;
}
if(pinsert_pseudo(ptr->right,toadd,ptr))
{
newheight(ptr);
if(parent)
if(parent->right==ptr)
parent->right=balance(ptr);
else
parent->left=balance(ptr);
else
root=balance(ptr);
return true;
}
else
return false;
}
else if(toadd->key<ptr->key)
{
if(ptr->left==nullptr)
{
toadd->height=1;
toadd->left=nullptr;
toadd->right=nullptr;
ptr->left=toadd;
size++;
newheight(ptr);
//balance(root);
return true;
}
if(pinsert_pseudo(ptr->left,toadd,ptr))
{
newheight(ptr);
if(parent)
if(parent->right==ptr)
parent->right=balance(ptr);
else
parent->left=balance(ptr);
else
root=balance(ptr);
return true;
}
else
return false;
}
}
template<typename k, typename t>
typename dictionary<k,t>::element* dictionary<k,t>::pcopy(const element* ptr)
{
if(ptr==nullptr)
return nullptr;
element * temp=new element;
temp->key=ptr->key;
temp->data=ptr->data;
temp->height=ptr->height;
temp->left=pcopy(ptr->left);
temp->right=pcopy(ptr->right);
size++;
return temp;
}
template<typename k, typename t>
void dictionary<k,t>::pinsert_rec(const element* ptr)
{
if(ptr==nullptr)
return;
if(!pexists(root,ptr->key))
pinsert(root,ptr->key,ptr->data,nullptr);
pinsert_rec(ptr->left);
pinsert_rec(ptr->right);
}
template<typename k, typename t>
void dictionary<k,t>::clear(element* ptr)
{
if(ptr==nullptr)
return;
clear(ptr->left);
clear(ptr->right);
delete ptr;
ptr=nullptr;
}
template<typename k, typename t>
bool dictionary<k,t>::pexists(element* ptr, const k& key)const
{
if(ptr==nullptr)
return false;
if(ptr->key==key)
return true;
if(pexists(ptr->left,key)||pexists(ptr->right,key))
return true;
return false;
}
template<typename k, typename t>
ostream & dictionary<k,t>::printos(ostream & os,element* ptr)const
{
if(ptr==nullptr)
return os;
printos(os,ptr->left);
os<<"Key:"<<endl<<ptr->key<<endl<<"Data:"<<endl<<ptr->data<<endl;
printos(os,ptr->right);
return os;
}
template<typename k, typename t>
ostream & dictionary<k,t>::printosdes(ostream & os,element* ptr)const
{
if(ptr==nullptr)
return os;
printosdes(os,ptr->right);
os<<"Key:"<<endl<<ptr->key<<endl<<"Data:"<<endl<<ptr->data<<endl;
printosdes(os,ptr->left);
return os;
}
template<typename k, typename t>
unsigned dictionary<k,t>::pheight(const element* ptr)const
{
if(ptr==nullptr)
return 0;
unsigned l=pheight(ptr->left);
unsigned r=pheight(ptr->right);
if(l>r)
return l+1;
else
return r+1;
}
template<typename k, typename t>
void dictionary<k,t>::calclvls(element* ptr, unsigned lvl, vector<element*> &storage, unsigned & maxlvl)const
{
if(ptr==nullptr)
return;
ptr->level=++lvl;
storage.push_back(ptr);
if(maxlvl<lvl)
maxlvl=lvl;
calclvls(ptr->left,lvl,storage,maxlvl);
calclvls(ptr->right,lvl,storage,maxlvl);
}
template<typename k, typename t>
typename dictionary<k,t>::element* dictionary<k,t>::find(const k &key,element* ptr,element*& parent)const
{
if(ptr==nullptr)
return nullptr;
if(ptr->key==key)
return ptr;
parent=ptr;
element* lrptr=find(key,ptr->left,parent);
if(lrptr==nullptr)
{
parent=ptr;
lrptr=find(key,ptr->right,parent);
}
return lrptr;
}
template<typename k, typename t>
void dictionary<k,t>::find(element* ptr, vector<k> &keys)const
{
if(ptr==nullptr)
return;
keys.push_back(ptr->key);
find(ptr->left,keys);
find(ptr->right,keys);
}
template<typename k, typename t>
void dictionary<k,t>::find(const t &data, element* ptr, vector<k> &keys)const
{
if(ptr==nullptr)
return;
if(ptr->data==data)
keys.push_back(ptr->key);
find(data,ptr->left,keys);
find(data,ptr->right,keys);
}
template<typename k, typename t>
void dictionary<k,t>::find(element* ptr, list<k> &keys)const
{
if(ptr==nullptr)
return;
keys.push_back(ptr->key);
find(ptr->left,keys);
find(ptr->right,keys);
}
template<typename k, typename t>
void dictionary<k,t>::find(const t &data, element* ptr, list<k> &keys)const
{
if(ptr==nullptr)
return;
if(ptr->data==data)
keys.push_back(ptr->key);
find(data,ptr->left,keys);
find(data,ptr->right,keys);
}
template<typename k, typename t>
typename dictionary<k,t>::element* dictionary<k,t>::findrep(element* ptr,bool dir,element*& parent)const
{
if(dir)
{
if(ptr->right==nullptr)
return ptr;
else
{
parent=ptr;
return findrep(ptr->right,true,parent);
}
}
else
{
if(ptr->left==nullptr)
return ptr;
else
{
parent=ptr;
return findrep(ptr->left,false,parent);
}
}
}
template<typename k, typename t>
typename dictionary<k,t>::element* dictionary<k,t>::balance(element* ptr)
{
if(ptr==nullptr)
return nullptr;
int l=0;
int r=0;
if(ptr->left)
l=ptr->left->height;
if(ptr->right)
r=ptr->right->height;
int balfac=l-r;
if(balfac<=1&&balfac>=-1)
return ptr;
element* swapper;
if(balfac>1)
{
swapper=ptr->left;
if(ptr->left->right)
{
ptr->left=swapper->right;
swapper->right=swapper->right->left;
ptr->left->left=swapper;
newheight(swapper);
newheight(ptr->left);
newheight(ptr);
swapper=ptr->left;
}
ptr->left=swapper->right;
swapper->right=ptr;
newheight(ptr);
newheight(swapper);
if(root==ptr)
root=swapper;
return swapper;
}
else
{
swapper=ptr->right;
if(ptr->right->left)
{
ptr->right=swapper->left;
swapper->left=swapper->left->right;
ptr->right->right=swapper;
newheight(swapper);
newheight(ptr->right);
newheight(ptr);
swapper=ptr->right;
}
ptr->right=swapper->left;
swapper->left=ptr;
newheight(ptr);
newheight(swapper);
if(root==ptr)
root=swapper;
return swapper;
}
}
template<typename k, typename t>
void dictionary<k,t>::premove(const element* ptr)
{
if(ptr==nullptr)
return;
remove(ptr->key);
premove(ptr->right);
premove(ptr->left);
}
template<typename k, typename t>
bool dictionary<k,t>::premove(const k &key, element* remptr, element* parent)
{
if(remptr==nullptr)
return false;
if(remptr->key!=key)
{
if(key<remptr->key)
{
if(premove(key,remptr->left,remptr))
{
newheight(remptr);
if(parent)
if(parent->right==remptr)
parent->right=balance(remptr);
else
parent->left=balance(remptr);
else
balance(remptr);
return true;
}
return false;
}
else
{
if(premove(key,remptr->right,remptr))
{
newheight(remptr);
if(parent)
if(parent->right==remptr)
parent->right=balance(remptr);
else
parent->left=balance(remptr);
else
balance(remptr);
return true;
}
return false;
}
}
if(remptr->right==nullptr&&remptr->left==nullptr)
{
if(parent)
{
if(parent->right==remptr)
parent->right=nullptr;
else
parent->left=nullptr;
}
else
root=nullptr;
delete remptr;
size--;
return true;
}
if(remptr->right==nullptr||remptr->left==nullptr)
{
if(parent)
{
if(parent->right==remptr)
{
if(remptr->right==nullptr)
parent->right=remptr->left;
else
parent->right=remptr->right;
}
else
{
if(remptr->right==nullptr)
parent->left=remptr->left;
else
parent->left=remptr->right;
}
}
else
{
if(remptr->right==nullptr)
root=remptr->left;
else
root=remptr->right;
}
delete remptr;
size--;
return true;
}
element* repparent=nullptr;
element* repptr=findrep(remptr->right,false,repparent);
if(parent)
{
if(parent->right==remptr)
parent->right=repptr;
else
parent->left=repptr;
}
else
root=repptr;
repptr->left=remptr->left;
if(remptr->right!=repptr)
{
repparent->left=repptr->right;
repptr->right=remptr->right;
}
delete remptr;
size--;
return true;
}
template<typename k, typename t>
bool dictionary<k,t>::comparator(const element* ptr)const
{
if(ptr==nullptr&&root==nullptr)
return true;
if(ptr==nullptr)
return true;
if(!pexists(root,ptr->key))
return false;
if(comparator(ptr->left)&&comparator(ptr->right))
return true;
return false;
}
template<typename k, typename t>
void dictionary<k,t>::newheight(element* ptr)
{
if(ptr->right||ptr->left)
{
if(ptr->right&&ptr->left)
ptr->height=ptr->right->height>ptr->left->height?ptr->right->height+1:ptr->left->height+1;
else if(ptr->right)
ptr->height=ptr->right->height+1;
else
ptr->height=ptr->left->height+1;
}
else
ptr->height=1;
}
//MAI PUBLICS
template<typename k, typename t>
dictionary<k,t>::dictionary()
{
root=nullptr;
size=0;
}
template<typename k, typename t>
dictionary<k,t>::dictionary(const dictionary<k,t> & copy)
{
size=0;
root=pcopy(copy.root);
}
template<typename k, typename t>
dictionary<k,t>::~dictionary()
{
clear(root);
size=0;
}
template<typename k, typename t>
dictionary<k,t> & dictionary<k,t>::operator=(const dictionary<k,t> & copy)
{
if(this==©)
return *this;
clear(root);
size=0;
root=pcopy(copy.root);
}
template<typename k, typename t>
dictionary<k,t> operator+(const dictionary<k,t> & add1, const dictionary<k,t> & add2)
{
dictionary<k,t> temp;
temp.root = temp.pcopy(add1.root);
temp.pinsert_rec(add2.root);
return temp;
}
template<typename k, typename t>
dictionary<k,t> operator-(const dictionary<k,t> & subtract1, const dictionary<k,t> & subtract2)
{
dictionary<k,t> temp;
temp.root = temp.pcopy(subtract1.root);
temp.premove(subtract2.root);
return temp;
}
template<typename k, typename t>
void dictionary<k,t>::clear()
{
clear(root);
size=0;
root=nullptr;
}
template<typename k, typename t>
t& dictionary<k,t>::getData(const k& key)const
{
element *ptr,*parent;
ptr=find(key,root,parent);
if(ptr==nullptr)
throw NoSuchKeyExeption();
return ptr->data;
}
template<typename k, typename t>
vector<k> dictionary<k,t>::vgetKeys()const
{
vector<k> keys;
find(root,keys);
return keys;
}
template<typename k, typename t>
vector<k> dictionary<k,t>::vgetKeys(const t& data)const
{
vector<k> keys;
find(data,root,keys);
return keys;
}
template<typename k, typename t>
list<k> dictionary<k,t>::lgetKeys()const
{
list<k> keys;
find(root,keys);
return keys;
}
template<typename k, typename t>
list<k> dictionary<k,t>::lgetKeys(const t& data)const
{
list<k> keys;
find(data,root,keys);
return keys;
}
template<typename k, typename t>
bool dictionary<k,t>::insert(const k &key, const t &data)
{
if(pexists(root,key))
return false;
return pinsert(root,key,data,nullptr);
}
template<typename k, typename t>
bool dictionary<k,t>::remove(const k &key)
{
return premove(key,root,nullptr);
}
template<typename k, typename t>
bool dictionary<k,t>::exists(const k &key)const
{
return pexists(root,key);
}
template<typename k, typename t>
bool dictionary<k,t>::changeKey(const k &keyfrom,const k &keyto)
{
if(pexists(root,keyto))
return false;
element* remptr;
element* parent=nullptr;
remptr = find(keyfrom,root,parent);
//copypasta from remove method
{
if(remptr==nullptr)
return false;
else if(remptr->right==nullptr&&remptr->left==nullptr)
{
if(parent)
{
if(parent->right==remptr)
parent->right=nullptr;
else
parent->left=nullptr;
}
else
root=nullptr;
size--;
balance(root);
}
else if(remptr->right==nullptr||remptr->left==nullptr)
{
if(parent)
{
if(parent->right==remptr)
{
if(remptr->right==nullptr)
parent->right=remptr->left;
else
parent->right=remptr->right;
}
else
{
if(remptr->right==nullptr)
parent->left=remptr->left;
else
parent->left=remptr->right;
}
}
else
{
if(remptr->right==nullptr)
root=remptr->left;
else
root=remptr->right;
}
size--;
balance(root);
}
else
{
element* repparent=nullptr;
element* repptr=findrep(remptr->right,false,repparent);
if(parent)
{
if(parent->right==remptr)
parent->right=repptr;
else
parent->left=repptr;
}
else
root=repptr;
repptr->left=remptr->left;
if(remptr->right!=repptr)
{
repparent->left=repptr->right;
repptr->right=remptr->right;
}
size--;
balance(root);
}
}
remptr->key=keyto;
pinsert_pseudo(root,remptr,nullptr);
}
template<typename k, typename t>
void dictionary<k,t>::printTree()const
{
vector<element*> storage;
unsigned maxlvl=0;
calclvls(root,0,storage,maxlvl);
cout<<"size: "<<storage.size()<<endl;
cout<<"maxlvl: "<<maxlvl<<endl;
for(int i=1; i<=maxlvl; i++)
{
for(int j=0; j<storage.size(); j++)
{
if(storage(j)->level==i)
{
cout<<storage(j)->key<<" "<<storage(j)->height;
cout<<"(";
if(storage(j)->right)
cout<<storage(j)->right->key;
cout<<",";
if(storage(j)->left)
cout<<storage(j)->left->key;
cout<<")"<<" | ";
}
}
cout<<endl;
}
}
template<typename u, typename i>
bool operator==(const dictionary<u,i> & check1,const dictionary<u,i> & check2)
{
return check1.comparator(check2.root);
}
template<typename u, typename i>
bool operator!=(const dictionary<u,i> & check1,const dictionary<u,i> & check2)
{
return !check1.comparator(check2.root);
}
template<typename u, typename i>
ostream & operator<< (ostream & os, const dictionary<u,i> & toprint)
{
toprint.printos(os,toprint.root);
return os;
}
template<typename k, typename t>
void dictionary<k,t>::printDescend(ostream & os)const
{
printosdes(os,root);
}
int main()
{
dictionary<int,string> lol;
lol.insert(5,"dont care");
lol.insert(8,"dont care");
lol.insert(3,"dont care");
lol.insert(1,"dont care");
lol.insert(4,"dont care");
lol.insert(10,"dont care");
lol.insert(6,"dont care");
lol.insert(12,"dont care");
lol.insert(11,"dont care");
lol.insert(7,"dont care");
lol.insert(13,"dont care");
lol.insert(2,"dont care");
lol.printTree();
lol.remove(8);
lol.printTree();
lol.getData(11)="well what do you know it works";
dictionary<int,string> lol2;
lol2+=lol;
cout<<(lol2==lol)<<endl;
cout<<lol<<endl;
lol.printDescend(cout);
lol2.insert(-10,"hi im new here");
lol2.insert(23,"hi im new here");
lol2.insert(7,"hi im new here");
lol2.insert(-1,"hi im new here");
cout<<(lol2==lol)<<endl;
lol2.changeKey(7,1000);
cout<<"Start keys found in order"<<endl;
for(int i=0; i<lol2.vgetKeys().size(); i++)
cout<<lol2.vgetKeys()(i)<<endl;
cout<<"End keys found in order"<<endl;
cout<<"Start keys found in order"<<endl;
for(int i=0; i<lol2.vgetKeys("dont care").size(); i++)
cout<<lol2.vgetKeys("dont care")(i)<<endl;
cout<<"End keys found in order"<<endl;
lol2.changeKey(lol2.vgetKeys("dont care")(0),666);
dictionary<int,string> lol3 = lol2+lol;
cout<<"we got here"<<endl;
(lol2-lol).printTree();
cout<<endl;
cout<<(lol2-lol).getSize();
cout<<endl;
lol.printTree();
cout<<endl;
lol2.printTree();
cout<<lol2.getData(11)<<endl;
cout<<lol2.vgetKeys("hiim new here").size()<<endl;
cout<<lol2.lgetKeys("dont care").size()<<endl;
cout<<endl<<endl<<endl<<"------------End Normal Testing------------------"<<endl;
srand(time(nullptr));
lol3.clear();
int loops = 10000;
cout<<"the loop length is: "<<loops<<endl;
for(int i=0; i<loops; i++)
lol3.insert(rand(),"does it matter");
for(int i=0; i<loops; i++)
lol3.remove(rand());
// lol3.printTree();
//cout<<lol3<<endl;
cout<<"the size is: "<<lol3.getSize()<<endl;
}
Could you please help me improve it