手写AVL 树（下）

#include <iostream>

template<typename T1,typename T2> struct Tree
{
    Tree* leftChild;
    Tree* rightChild;
    Tree* father;
    T1 key;
    T2 value;
    int leftHeight;
    int rightHeight;
    
};

template<typename T1,typename T2> class AVL
{
public:
    AVL();
    void Put(T1 key,T2 value);
    void Delete(T1 key);
    T2 Get(T1 key);
    
private:
    Tree<T1,T2>* tree;
    void ReComputeRightHeight(Tree<T1,T2>*& root);
    void ReComputeLeftHeight(Tree<T1,T2>*& root);
    void LeftSpin(Tree<T1,T2>*& root);
    void RightSpin(Tree<T1,T2>*& root);
    void LeftRightSpin(Tree<T1,T2>*& root);
    void RightLeftSpin(Tree<T1,T2>*& root);
    void Rebalance(Tree<T1,T2>*& root);
    void Insert(Tree<T1,T2>*& father,Tree<T1,T2>*& root,T1 key,T2 value);
    void DeleteNode(Tree<T1,T2>*& root,int tag);
    void LeftScoper(Tree<T1,T2>*& source,Tree<T1,T2>*& root,int tag);
    void RightScoper(Tree<T1,T2>*& source,Tree<T1,T2>*& root,int tag);
    void Remove(Tree<T1,T2>*& root,T1 key,int tag);
    T2 Find(Tree<T1,T2>* root,T1 key);
};

#include "AVL.h"
#include <stdio.h>
#include <math.h>
#include <iostream>

using namespace std;

template<class T1,class T2>
AVL<T1,T2>::AVL()
{
    tree = NULL;
}

template<class T1,class T2>
void AVL<T1,T2>::ReComputeRightHeight(Tree<T1,T2>*& root)
{
    if(root->rightChild==NULL)
        root->rightHeight = 0;
    else
        root->rightHeight = max(root->rightChild->leftHight,root->rightChild->rightHeight)+1;
}

template<class T1,class T2>
void AVL<T1,T2>::ReComputeLeftHeight(Tree<T1,T2>*& root)
{
    if(root->leftChild==NULL)
        root->leftHeight = 0;
    else
        root->leftHeight = max(root->leftChild->leftHight,root->leftChild->rightHeight)+1;
}

template<class T1,class T2>
void AVL<T1,T2>::LeftSpin(Tree<T1,T2>*& root)
{
    if(root->rightChild==NULL) return;
    Tree<T1,T2>* father = root->father;
    Tree<T1,T2>* temp = root;
    Tree<T1,T2>* temp2 = root->rightChild->leftChild;
    
    root = temp->rightChild;
    root->leftChild = temp;
    root->father = father;
    temp->father = root;
    temp->rightChild = temp2;
    if(temp2!=NULL)
        temp2->father = temp;
    
    ReComputeRightHeight(root->leftChild);
    ReComputeLeftHeight(root);
}

template<class T1,class T2>
void AVL<T1,T2>::RightSpin(Tree<T1,T2>*& root)
{
    if(root->leftChild==NULL) return;
    Tree<T1,T2>* father = root->father;
    Tree<T1,T2>* temp = root;
    Tree<T1,T2>* temp2 = root->leftChild->rightChild;
    
    root = temp->leftChild;
    root->rightChild = temp;
    root->father = father;
    temp->father = root;
    temp->leftChild = temp2;
    if(temp2!=NULL)
        temp2->father = temp;
    
    ReComputeLeftHeight(root->rightChild);
    ReComputeRightHeight(root);
}

template<class T1,class T2>
void AVL<T1,T2>::LeftRightSpin(Tree<T1,T2>*& root)
{
    LeftSpin(root->leftChild);
    RightSpin(root);
}

template<class T1,class T2>
void AVL<T1,T2>::RightLeftSpin(Tree<T1,T2>*& root)
{
    RightSpin(root->rightChild);
    LeftSpin(root);
}

template<class T1,class T2>
void AVL<T1,T2>::Rebalance(Tree<T1,T2>*& root)
{
    if(root->leftHeight > root->rightHeight+1)
    {
        if(root->leftChild->leftHeight < root->leftChild->rightHeight)
        {
            LeftRightSpin(root);
        }
        else
            RightSpin(root);
    }
    else if(root->leftHeight<root->rightHeight-1)
    {
        if(root->rightChild->rightHeight<root->rightChild->leftHeight)
        {
            RightLeftSpin(root);
        }
        else
            LeftSpin(root);
    }
}

template<class T1,class T2>
void AVL<T1,T2>::Insert(Tree<T1,T2>*& father, Tree<T1,T2>*& root, T1 key,T2 value)
{
    if(root==NULL)
    {
        root = new Tree<T1,T2>;
        root->leftChild=NULL;
        root->rightChild=NULL;
        root->key = key;
        root->value = value;
        root->leftHeight = 0;
        root->rightHeight = 0;
        root->father = father;
        return;
    }
    
    if(key == root->key)
    {
        root->value = value;
        return;
    }
    
    if(key < root->key)
    {
        Insert(root,root->leftChild,key,value);
        ReComputeLeftHeight(root);
        Rebalance(root);
        
    }
    else if(key > root->key){
        Insert(root,root->rightChild,key,value);
        ReComputeRightHeight(root);
        Rebalance(root);
    }
}

template<class T1,class T2>
void AVL<T1,T2>::Put(T1 key,T2 value)
{
    Insert(tree,tree,value, value);
}

template<class T1,class T2>
T2 AVL<T1,T2>::Find(Tree<T1,T2>* root,T1 key)
{
    if(root==NULL)
        return NULL;
    if(key<root->key&&root->leftChild!=NULL)
    {
        return Get(root->leftChild,key);
    }
    if(key>root->key&&root->rightChild!=NULL)
    {
        return Get(root->rightChild,key);
    }
    if(key==root->key)
    {
        return root->value;
    }
    return NULL;
}

template<class T1,class T2>
T2 AVL<T1,T2>::Get(T1 key)
{
    Find(tree,key);
}

template<class T1,class T2>
void AVL<T1,T2>::DeleteNode(Tree<T1,T2>*& root,int tag)
{
    if(root->leftChild!=NULL)
    {
        if(tag==0)
        {
            if(root->father == root)
                root->leftChild = NULL;
            else
            {
                root->father->leftChild = root->leftChild;
                root->father = root->father->father;
                
            }
        }
        else if(tag==1)
        {
            if(root->father == root)
                root->rightChild = NULL;
            else
            {
                root->father->rightChild = root->leftChild;
                root->father = root->father->father;
            }
        }
    }
    else if(root->rightChild!=NULL)
    {
        if(tag==0)
        {
            if(root->father == root)
            {
                root->leftChild = NULL;
            }
            else
            {
                root->father->leftChild = root->rightChild;
                root->father = root->father->father;
            }
        }
        else if(tag==1)
        {
            if(root->father == root)
            {
                root->rightChild = NULL;
            }
            else
            {
                root->father->rightChild = root->rightChild;
                root->father = root->father->father;
            }
        }
        
    }
    else
    {
        if(root->father == root)
            root = NULL;
        else
        {
            if(tag==0)
                root->father->leftChild=NULL;
            else if(tag==1)
                root->father->rightChild=NULL;
        }
    }
}

template<class T1,class T2>
void AVL<T1,T2>::LeftScoper(Tree<T1,T2>*& source, Tree<T1,T2>*& root,int tag)
{
    if(root->leftChild!=NULL)
    {
        LeftScoper(source,root->leftChild,0);
        ReComputeLeftHeight(root);
        Rebalance(root);
    }
    else
    {
        source->key = root->key;
        source->value = root->value;
        DeleteNode(root,tag);
    }
}

template<class T1,class T2>
void AVL<T1,T2>::RightScoper(Tree<T1,T2>*& source, Tree<T1,T2>*& root,int tag)
{
    if(root->rightChild!=NULL)
    {
        RightScoper(source,root->rightChild,1);
        ReComputeRightHeight(root);
        Rebalance(root);
    }
    else
    {
        source->key = root->key;
        source->value = root->value;
        DeleteNode(root, tag);
    }
}

template<class T1,class T2>
void AVL<T1,T2>::Remove(Tree<T1,T2>*& root,T1 key,int tag)
{
    if(root==NULL)
        return;
    if(key == root->key)
    {
        if(root->leftChild==NULL&&root->rightChild==NULL)
        {
            DeleteNode(root,tag);
        }
        else
        {
            if(root->rightChild!=NULL)
            {
                LeftScoper(root,root->rightChild,1);
                ReComputeRightHeight(root);
                Rebalance(root);
            }
            else if(root->leftChild!=NULL)
            {
                RightScoper(root,root->leftChild,0);
                ReComputeLeftHeight(root);
                Rebalance(root);
            }
        }
        return;
    }
    
    if(key<root->key)
    {
        Remove(root->leftChild,key,0);
        ReComputeLeftHeight(root);
        Rebalance(root);
    }
    if(key>root->key)
    {
        Remove(root->rightChild,key,1);
        ReComputeRightHeight(root);
        Rebalance(root);
    }
}

template<class T1,class T2>
void AVL<T1,T2>::Delete(T1 key)
{
    remove(tree,key,0);
}