class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
inserthelp(BinNode<Elem>* subroot, const Elem& val) {
if (subroot == NULL) // Empty tree: create node
return (new BinNodePtr<Elem>(val, NULL, NULL));
if (EEComp::lt(val, subroot->val())) // Insert on left
subroot->setLeft(inserthelp(subroot->left(), val));
else subroot->setRight(inserthelp(subroot->right(), val));
return subroot; // Return subtree with node inserted
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
deletemin(BinNode<Elem>* subroot, BinNode<Elem>*& min) {
if (subroot->left() == NULL) { // Found min
min = subroot;
return subroot->right();
}
else { // Continue left
subroot->setLeft(deletemin(subroot->left(), min));
return subroot;
}
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
removehelp(BinNode<Elem>* subroot, const Key& K,
BinNode<Elem>*& t) {
if (subroot == NULL) return NULL; // Val is not in tree
else if (KEComp::lt(K, subroot->val())) // Check left
subroot->setLeft(removehelp(subroot->left(), K, t));
else if (KEComp::gt(K, subroot->val())) // Check right
subroot->setRight(removehelp(subroot->right(), K, t));
else { // Found it: remove it
BinNode<Elem>* temp;
t = subroot;
if (subroot->left() == NULL) // Only a right child
subroot = subroot->right(); // so point to right
else if (subroot->right() == NULL) // Only a left child
subroot = subroot->left(); // so point to left
else { // Both children are non-empty
subroot->setRight(deletemin(subroot->right(), temp));
Elem te = subroot->val();
subroot->setVal(temp->val());
temp->setVal(te);
t = temp;
}
}
return subroot;
}
template <class Key, class Elem, class KEComp, class EEComp>
bool BST<Key, Elem, KEComp, EEComp>:: findhelp(
BinNode<Elem>* subroot, const Key& K, Elem& e) const {
if (subroot == NULL) return false; // Empty tree
else if (KEComp::lt(K, subroot->val())) // Check left
return findhelp(subroot->left(), K, e);
else if (KEComp::gt(K, subroot->val())) // Check right
return findhelp(subroot->right(), K, e);
else { e = subroot->val(); return true; } // Found it
}
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::
printhelp(BinNode<Elem>* subroot, int level) const {
if (subroot == NULL) return; // Empty tree
printhelp(subroot->left(), level+1); // Do left subtree
for (int i=0; i<level; i++) // Indent to level
cout << " ";
cout << subroot->val() << "\n"; // Print node value
printhelp(subroot->right(), level+1); // Do right subtree
}
file name: dictionary.h // The Dictionary abstract class. KEComp compares a key
// and an element. EEComp compares two elements.
template <class Key, class Elem, class KEComp, class EEComp>
class Dictionary {
public:
// Reinitialize dictionary
virtual void clear() = 0;
// Insert an element. Return true if insert is
// successful, false otherwise.
virtual bool insert(const Elem&) = 0;
// Remove some element matching Key. Return true if such
// exists, false otherwise. If multiple entries match
// Key, an arbitrary one is removed.
virtual bool remove(const Key&, Elem&) = 0;
// Remove and return an arbitrary element from dictionary.
// Return true if some element is found, false otherwise.
virtual bool removeAny(Elem&) = 0;
// Return a copy of some Elem matching Key. Return true
// if such exists, false otherwise. If multiple elements
// match Key, return an arbitrary one.
virtual bool find(const Key&, Elem&) const = 0;
// Return the number of elements in the dictionary.
virtual int size() = 0;
};
file name: Elem.h //This is the element of login system
class KEComp
{
public:
static bool lt(int key, int elem) {return key<elem;}
static bool eq(int key, int elem) {return key==elem;}
static bool gt(int key, int elem) {return key>elem;}
};
class EEComp
{
public:
static bool lt(int e1, int e2)
{ return e1<e2;}
static bool eq(int e1, int e2)
{ return e1==e2;}
static bool gt(int e1, int e2)
{ return e1>e2;}
}; file name: AVLTree.h #include "BST.h"
template<class Elem>
struct Descriptor
{
BinNode<Elem>* parent;
bool isRoot;
bool isLeft;
bool isSingle;
bool left2right;
};
template<class Key, class Elem, class KEComp, class EEComp>
class AVL: public BST<Key, Elem, KEComp, EEComp>
{
protected:
// BinNode<Elem>* startPtr;
void clearhelp(BinNode<Elem>*);
BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&);
BinNode<Elem>* removehelp(BinNode<Elem>*, const Key&,
BinNode<Elem>*&);
bool findhelp(BinNode<Elem>*, const Key&, Elem&) const;
void printhelp(BinNode<Elem>*, int) const;
void updateHeight(BinNode<Elem>*& subroot);
int getFactor(BinNode<Elem>* subroot);
void adjust(BinNode<Elem>*& subroot, bool isRoot);
int getTreeHeight(BinNode<Elem>* subroot);
void adjustHeight(BinNode<Elem>* subroot);
BinNode<Elem>* singleRotate(BinNode<Elem>* parent, bool isRoot, bool left2right);
BinNode<Elem>* doubleRotate(BinNode<Elem>* parent, bool isRoot, bool left2right);
void checkDir(BinNode<Elem>* subroot, bool& isSingle, bool& left2right);
BinNode<Elem>* doDouble(BinNode<Elem>* oldRoot, bool left2right);
public:
AVL() { root = NULL; nodecount = 0; } // Constructor
~AVL() { clearhelp(root); root=NULL; } // Destructor
bool insert(const Elem& e)
{
root = inserthelp(root, e);
nodecount++;
return true;
}
};
//do not use recursive!!!!!
template <class Key, class Elem, class KEComp, class EEComp>
int AVL<Key, Elem, KEComp, EEComp>::getTreeHeight(BinNode<Elem>* subroot)
{
AVLNodePtr<Elem>* ptr, *l, *r;
int newHeight, lHeight, rHeight;//, factor;//, sonFactor;
if (subroot==NULL)
{
return 0;
}
ptr=(AVLNodePtr<Elem>*)subroot;
l=(AVLNodePtr<Elem>*)ptr->left();
r=(AVLNodePtr<Elem>*)ptr->right();
if (l==NULL)
{
lHeight=0;
}
else
{
lHeight=l->getHeight();
}
if (r==NULL)
{
rHeight=0;
}
else
{
rHeight=r->getHeight();
}
newHeight=1+(lHeight>rHeight?lHeight:rHeight);
return newHeight;
}
template <class Key, class Elem, class KEComp, class EEComp>
void AVL<Key, Elem, KEComp, EEComp>::adjustHeight(BinNode<Elem>* subroot)
{
int height;
if (subroot==NULL)
{
return;
}
height=getTreeHeight(subroot);
((AVLNodePtr<Elem>*)(subroot))->setHeight(height);
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* AVL<Key, Elem, KEComp, EEComp>::doDouble(BinNode<Elem>* oldRoot,
bool left2right)
{
BinNode<Elem> *small, *mid, *big,*t1,*t2,*t3,*t4;
if (left2right)
{
big=oldRoot;//the root;
small=oldRoot->left();
mid=small->right();
t1=small->left();
t2=mid->left();
t3=mid->right();
t4=big->right();
}
else
{
small=oldRoot;
big=small->right();
mid=big->left();
t1=small->left();
t2=mid->left();
t3=mid->right();
t4=big->right();
}
mid->setLeft(small);
mid->setRight(big);
small->setLeft(t1);
small->setRight(t2);
big->setLeft(t3);
big->setRight(t4);
adjustHeight(small);
adjustHeight(big);
adjustHeight(mid);
return mid;
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* AVL<Key, Elem, KEComp, EEComp>::doubleRotate(BinNode<Elem>* parent,
bool isRoot, bool left2right)
{
BinNode<Elem>* oldRoot;
bool isLeft;
if (isRoot)
{
oldRoot=parent;
root=doDouble(oldRoot, left2right);
return root;//because we need parent return as real root
}
else
{
isLeft=((AVLNodePtr<Elem>*)parent)->getSide();
oldRoot=parent->getSon(isLeft);
parent->setSon(doDouble(oldRoot, left2right), isLeft);
adjustHeight(parent);
return parent;
}
}
//if isRoot, we don't need isLeft, it is useful when it is not root and
//we need to know which son it is in
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* AVL<Key, Elem, KEComp, EEComp>::singleRotate(BinNode<Elem>* parent,
bool isRoot, bool left2right)
{
BinNode<Elem>* oldRoot=parent, *son, *t1;
bool isLeft=((AVLNodePtr<Elem>*)parent)->getSide();
上一页 [1] [2] [3] [4] 下一页 |
热门搜索: 
