c/c++代写 数据结构预算法:在老师给的class基础上再完成splayTree,cacheLRU
#ifndef splayTree_H_
#define splayTree_H_
#include “rotateBST.h”
using std::cout;
using std::endl;
using std::max;
template
class rotateBST;
template
class SplayTree:public rotateBST<Key,Value>
{
public:
SplayTree()
{
time_left_rotation=0;
time_right_rotation=0;
}
typename SplayTree<Key,Value>::iterator find(const Key& key)
{
Node<Key,Value> pre=NULL;
Node<Key,Value> cur=this->mRoot;
if(cur==NULL)
{
typename SplayTree<Key,Value>::iterator it(NULL);
return it;
}
if(cur->getKey()==key)
{
typename SplayTree<Key,Value>::iterator it(cur);
return it;
}
pre=cur;
while(cur!=NULL)
{
pre=cur;
if(cur->getKey()<key)//key is bigger ,go to right
{
cur=cur->getRight();
}else if(cur->getKey()>key)//key is smaller,go to left
{
cur=cur->getLeft();
}else {
splay(cur);
typename SplayTree<Key,Value>::iterator it(cur);
return it;
}
}
splay(pre);
typename SplayTree<Key,Value>::iterator it(NULL);
return it;
}
typename SplayTree<Key,Value>::iterator findMin()
{
Node<Key,Value> cur=this->mRoot;
if(cur==NULL)
{
typename SplayTree<Key,Value>::iterator it(NULL);
return it;
}
while(cur->getLeft()!=NULL)
{
cur=cur->getLeft();
}
splay(cur);
typename SplayTree<Key,Value>::iterator it(cur);
return it;
}
typename SplayTree<Key,Value>::iterator findMax()
{
Node<Key,Value> cur=this->mRoot;
if(cur==NULL)
{
typename SplayTree<Key,Value>::iterator it(NULL);
return it;
}
while(cur->getRight()!=NULL)
{
cur=cur->getRight();
}
splay(cur);
typename SplayTree<Key,Value>::iterator it(cur);
return it;
}
void deleteMinLeaf()
{
Node<Key,Value>* cur=this->mRoot;
if(cur==NULL) return ;
while(cur->getLeft()!=NULL||cur->getRight()!=NULL)
{
if(cur->getLeft()!=NULL)
{
cur=cur->getLeft();
}else if(cur->getRight()!=NULL)
{
cur=cur->getRight();
}
}
remove(cur->getKey());
}
void deleteMaxLeaf()
{
Node<Key,Value>* cur=this->mRoot;
if(cur==NULL) return;
while(cur->getLeft()!=NULL||cur->getRight()!=NULL)
{
if(cur->getLeft()!=NULL)
{
cur=cur->getLeft();
}else if(cur->getRight()!=NULL)
{
cur=cur->getRight();
}
}
remove(cur->getKey());
}
void insert(const std::pair<const Key,Value>& keyValuePair)
{
BinarySearchTree<Key,Value>::insert(keyValuePair);
Node<Key,Value>* cur=this->mRoot;
Key key=keyValuePair.first;
while(cur->getKey()!=key)
{
if(cur->getKey()<key)//key is bigger
{
cur=cur->getRight();
}else if(cur->getKey()>key)
{
cur=cur->getLeft();
}
}
splay(cur);
}
void remove(const Key& key)
{
Node<Key,Value>* pre=removeHelper(key);
splay(pre);
}
private:
Node<Key,Value>* splay(Node<Key,Value>* nod,Key k);//stand splay
typename SplayTree<Key,Value>::iterator findHelper(Node<Key,Value>* nod,const Key& key);
Node<Key,Value>* removeHelper(const Key& key)
{
if(this->mRoot==NULL) return NULL;
Key k=key;
Node<Key,Value>* nod=this->mRoot;
Node<Key,Value>* pat=NULL;
while(nod)
{
if(nod->getKey()<k)
{
nod=nod->getRight();
}else if(nod->getKey()>k)
{
nod=nod->getLeft();
}else
{
if(nod->getLeft()==NULL&&nod->getRight()==NULL)
{
if(nod->getParent()==NULL)
{
this->mRoot=NULL;
pat=nod->getParent();
delete nod;
nod=NULL;
break;
}else
{
Node<Key,Value>* p=nod->getParent();
if(p->getLeft()==nod)
{
p->setLeft(NULL);
pat=nod->getParent();
delete nod;
nod=p;
break;
}else if(p->getRight()==nod)
{
p->setRight(NULL);
pat=nod->getParent();
delete nod;
nod=p;
break;
}
}
}else if(nod->getLeft()!=NULL)
{
Node<Key,Value>* pre=nod->getLeft();
while(pre->getRight()!=NULL)
{
pre=pre->getRight();
}
Node<Key,Value>* sis=new Node<Key,Value>(pre->getKey(),pre->getValue(),nod->getParent());
sis->setLeft(nod->getLeft());
sis->setRight(nod->getRight());
if(sis->getParent()==NULL) this->mRoot=sis;
else {
Node<Key,Value>* p=sis->getParent();
if(p->getLeft()==nod)
{
p->setLeft(sis);
}else
{
p->setRight(sis);
}
}
Node<Key,Value>* left=nod->getLeft();
if(left!=NULL)
{
left->setParent(sis);
}
Node<Key,Value>* right=nod->getRight();
if(right!=NULL)
{
right->setParent(sis);
}
pat=nod->getParent();
delete nod;
k=pre->getKey();
if(pre->getParent()!=sis)
{
nod=pre->getParent();
}else
{
nod=sis->getLeft();
}
}else
{
Node<Key,Value>* suc=nod->getRight();
while(suc->getLeft()!=NULL)
{
suc=suc->getLeft();
}
Node<Key,Value>* sis=new Node<Key,Value>(suc->getKey(),suc->getValue(),nod->getParent());
sis->setLeft(nod->getLeft());
sis->setRight(nod->getRight());
if(sis->getParent()==NULL) this->mRoot=sis;
else {
Node<Key,Value>* p=sis->getParent();
if(p->getLeft()==nod)
{
p->setLeft(sis);
}else
{
p->setRight(sis);
}
}
Node<Key,Value>* l=sis->getLeft();
if(l!=NULL)
{
l->setParent(sis);
}
Node<Key,Value>* r=sis->getRight();
if(r!=NULL)
{
r->setParent(sis);
}
pat=nod->getParent();
delete nod;
k=suc->getKey();
if(suc->getParent()!=sis)
{ nod=suc->getParent();
}else
{ nod=sis->getRight(); }
}
}
}
while(nod)
{
Node<Key,Value>* node=nod;
if(node->getLeft()==NULL&&node->getRight()==NULL) node->setHeight(1);
else if(node->getLeft()==NULL) node->setHeight(node->getRight()->getHeight()+1);
else if(node->getRight()==NULL) node->setHeight(node->getLeft()->getHeight()+1);
else node->setHeight(max(node->getLeft()->getHeight(),node->getRight()->getHeight())+1);
nod=nod->getParent();
}
return pat;
}
int time_left_rotation;
int time_right_rotation;
protected:
void splay(Node<Key,Value>* x)//splay the given node to the root//the r is existed
{
if(x==NULL) return ;
Node<Key,Value>* p=x->getParent();
if(p==NULL) return ;
Node<Key,Value>* g=p->getParent();
if(g==NULL)//p is root
{
if(p->getLeft()==x)
{
rotateBST<Key,Value>::rightRotate(p);
return ;
}else if(p->getRight()==x)
{
rotateBST<Key,Value>::leftRotate(p);
return ;
}
}
if(g->getLeft()==p&&p->getLeft()==x)//left left
{
rotateBST<Key,Value>::rightRotate(g);
rotateBST<Key,Value>::rightRotate(p);
time_right_rotation+=2;
}else if(g->getLeft()==p&&p->getRight()==x)
{
rotateBST<Key,Value>::leftRotate(p);
rotateBST<Key,Value>::rightRotate(g);
time_left_rotation+=1;
time_right_rotation+=1;
}else if(g->getRight()==p&&p->getRight()==x)
{
rotateBST<Key,Value>::leftRotate(g);
rotateBST<Key,Value>::leftRotate(p);
time_left_rotation+=2;
}else if(g->getRight()==p&&p->getLeft()==x)
{
rotateBST<Key,Value>::rightRotate(p);
rotateBST<Key,Value>::leftRotate(g);
time_left_rotation+=1;
time_right_rotation+=1;
}
splay(x);
}
};
template<typename Key,typename Value>
typename SplayTree<Key,Value>::iterator SplayTree<Key,Value>:: findHelper(Node<Key,Value>* nod,const Key& k)
{
if(nod==NULL)
{
typename SplayTree<Key,Value>::iterator end(NULL);
return end;
}
if(nod->getKey()<k)//k is on the right subtree
{
return findHelper(nod->getRight(),k);
}else if(nod->getKey()>k)// k is on the left subtree
{
return findHelper(nod->getLeft(),k);
}else {
typename SplayTree<Key,Value>::iterator it(nod);
return it;
}
}
#endif