/*
 *平衡二叉樹應(yīng)該有些功能
 *插入 刪除 查找 
 *前序遍歷 中序遍歷 后序遍歷 層次遍歷
 *統(tǒng)計(jì)結(jié)點(diǎn)數(shù)目
 */
 //代碼已經(jīng)調(diào)好，寫了很久才寫出來(lái)
 

#ifndef _AVLTREE_
#define _AVLTREE_
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define MAXFACTOR = 2;
template<class Key , class E>
class AVLNode
{
    private:
        Key key;
        E value;
        AVLNode<Key,E>* left;
        AVLNode<Key,E>* right;
        AVLNode<Key,E>* parent;
    public:
        AVLNode():left(nullptr),right(nullptr),parent(nullptr){}
        AVLNode(Key _key,E _value , AVLNode<Key,E>* _parent = nullptr,AVLNode<Key,E>*_left = nullptr, AVLNode<Key,E>*_right = nullptr):
                key(_key),value(_value),left(_left),right(_right),parent(_parent){}
        
        bool isLeaf(){return left==nullptr && right == nullptr ;}

        //元素設(shè)置
        Key getKey() const { return key;}
        void setKey(Key set) {key = set;}
        
        E getValue() const { return value;}
        void setValue(E set) {value = set;}

        AVLNode<Key,E>*  getLeft() { return left; }
        void setLeft (AVLNode< Key,E >* set){ left = set;}

        AVLNode<Key,E>*  getRight()  { return right;}
        void setRight (AVLNode<Key,E>* set) {right = set ;}

        AVLNode<Key,E>* getParent()  {return parent;}
        void setParent(AVLNode<Key,E>* set) { parent = set;}

};
template<class Key , class E>
class AVLTree
{
    private:
        AVLNode<Key,E>* root;
        void clear(AVLNode<Key,E>* &r)
        {
            if(r==nullptr)return;

            if(r->getLeft())clear(r->getLeft());
            if(r->getRight())clear(r->getRight);

            delete r; 
        }

        void Init()
        {
            root = new AVLNode<Key,E>();
            root=nullptr;
        }
        void preOrder(AVLNode<Key,E>* r,void(*visit) (AVLNode<Key,E> * node))
        {
            if(r==nullptr)return;
            (*visit) (r);
            preOrder(r->getLeft() , visit);
            preOrder(r->getRight(), visit);
        }

        void inOrder(AVLNode<Key,E>* r , void(*visit)(AVLNode<Key,E>* node) )
        {
            if(r==nullptr)return;
            inOrder(r->getLeft() , visit);
            (*visit)(r);
            inOrder(r->getRight(),visit);
        }

        void postOrder(AVLNode<Key,E>*r , void (*visit) (AVLNode<Key,E>* node))
        {
            if(r==nullptr)return;
            postOrder(r->getLeft(),visit);
            postOrder(r->getRight(),visit);
            (*visit)(r);
        }

        void levelOrder(AVLNode<Key,E>*r , void (*visit) (AVLNode<Key,E>* node))
        {
            queue< AVLNode<Key,E>* > q;
            if(r==nullptr)return;
            q.push(r);
            while( ! q.empty() )
            {
                AVLNode<Key,E>* tmp = q.front();
                q.pop();
                (*visit)(tmp);
                if(tmp->getLeft() ) q.push(tmp->getLeft() );
                if(tmp->getRight()) q.push(tmp->getRight());
                
            }
        }

        AVLNode<Key,E>* find(AVLNode<Key,E>* r,Key k)
        {
            if(r==nullptr)return nullptr;
            if(k == r->getKey() ) return r;
            else if( k < r->getKey())
            {
                find(r->getLeft(),k);
            }
            else {
                find(r->getRight(),k);
            }
        }
        //Find the smallest element in the avl tree
        AVLNode<Key,E>* getMin(AVLNode<Key,E>* r)
        {
            if(r->getLeft() == nullptr) return r;
            else{
                getMin(r->getLeft());
            }
        }
        //Remove the smallest element 
        AVLNode<Key,E>* deleteMin(AVLNode<Key,E>* rt)
        {
            if(rt->getLeft() == nullptr) return rt->getRight();
            else{
                rt->setLeft(deleteMin(rt->getLeft()));
                return rt;
            }
        }

        AVLNode<Key,E>* leftRotate(AVLNode<Key,E>* node)
        {
            if( node == nullptr) return nullptr;
            AVLNode<Key,E>* newHead = node->getRight();
            node->setRight( newHead -> getLeft() );
            newHead -> setLeft( node );
            return newHead; 
        }
        AVLNode<Key,E>* rightRotate(AVLNode<Key,E>* node)
        {
            if(node == nullptr)return nullptr;
            AVLNode<Key,E>* newHead = node->getLeft();
            node->setLeft( newHead->getRight() );
            newHead ->setRight(node);
            return newHead;
        }

        int getHeight(AVLNode<Key,E>*node)
        {
            if(node == nullptr)return 0;
            if(node->isLeaf())return 1;
            else return ( getHeight( node->getLeft() ) > getHeight( node->getRight() ) ?
                        getHeight( node->getLeft() ) : getHeight( node->getRight() ) ) + 1;
        }

        int getBalanceFactor(AVLNode<Key,E>* node)
        {
            return getHeight(node->getLeft()) - getHeight(node->getRight() );
        }
        AVLNode<Key,E>* balance(AVLNode<Key,E>* node)
        {
            if(!node) return nullptr;
            else if ( getBalanceFactor( node ) == 2)
            {
                if(getBalanceFactor( node ->getLeft() ) == 1)
                {
                    node = rightRotate(node);
                }
                else
                {
                    node->setLeft(leftRotate( node->getLeft() ) );
                    node = rightRotate(node);
                }
            }
            else if(getBalanceFactor( node ) == -2)
            {
                if(getBalanceFactor( node->getRight()) == -1)
                {
                    node = leftRotate(node);
                }
                else
                {
                    node->setRight( rightRotate( node->getRight() ) );
                    node = leftRotate(node);
                }
            }
            return node;
        }

        AVLNode<Key,E>* insert( AVLNode<Key,E>* root ,const pair<Key,E>& it)
        {
            if(root == nullptr)
            {
                return new AVLNode<Key,E>(it.first , it.second,NULL,NULL,NULL);
            }
            else if (it.first < root->getKey() )
            {
                
                root ->setLeft( insert(root->getLeft() , it) ) ;
            }
            else{
                root ->setRight( insert(root->getRight() , it) );
                
            }
            root = balance(root);
            return root;
        }

        AVLNode<Key,E>* remove(AVLNode<Key,E>*  node , const Key k)
        {
            if(node == nullptr) return nullptr;
            if(node->getKey() > k)
            {
                node->setLeft( remove(node->getLeft() , k) );
                node = balance(node);
            }
            else if(node->getKey() < k)
            {
                node->setRight( remove(node->getRight(), k) );
                node = balance(node);
            }
            else if(node->getKey() == k)
            {
                if(! node->isLeaf() )
                {
                    AVLNode<Key,E>* tmp = getMin(node->getRight() );
                    node->setKey( tmp->getKey() );
                    node->setValue( tmp->getValue() );
                    node->setRight( deleteMin(node->getRight() ) );
                    delete tmp;
                }
                else {
                    AVLNode<Key,E>* tmp = node;
                    node = (node->getLeft() != nullptr) ? node->getLeft() : node->getRight() ;
                    delete tmp;
                }
            }
            return node;
        }
   
    public:
        ~AVLTree(){clear(root);}
        AVLTree(){/*Init();*/ root = nullptr; }
    //四種遍歷方式
        void preOrder( void (*visit)(AVLNode<Key,E>* r))
        {
            preOrder(root,visit);
        }
        void inOrder(void (*visit)(AVLNode<Key,E>* r))
        {
            inOrder(root,visit);
        }
        void postOrder(void (*visit)(AVLNode<Key,E>* r))
        {
            postOrder(root,visit);
        }
        void levelOrder( void(*visit)(AVLNode<Key,E>*r) )
        {
            levelOrder(root,visit);
        }
         //插入
        void insert(const pair<Key,E> &it)
        {
            root = insert(root,it);
        }

        //刪除
       void remove(const Key& k)
        {
            remove(root,k);
        }
        bool find(const Key&k)
        {
            return find(root,k);   
        }   



            
};
#endif

//AVLtest.cpp
#include"NewAvl.h"
#include<iostream>
using namespace std;
template<typename Key,typename E>
void traverse(AVLNode<Key,E>* root)
{
    cout<<root->getKey()<<" "<<root->getValue()<<" ";
    cout<<endl;
}
int main()
{
    AVLTree<int,int>* tree = new AVLTree<int ,int>;
    for(int i = 0 ; i < 5 ; i ++)
    {
        tree->insert(make_pair(i,i));
    }
    tree->remove(1);
    cout<<"PreOrder: "<<endl;
    tree->preOrder(traverse);
    cout<<endl;
    cout<<"LevelOrder: "<<endl;
    tree->levelOrder(traverse);
    cout<<endl;
    cout<<"InOrder: "<<endl;
    tree->inOrder(traverse);
    cout<<endl;
    cout<<"PostOrder: "<<endl;
    tree->postOrder(traverse);
    cout<<endl;
    cout<<tree->find(2)<<endl;
    tree->insert(make_pair(9,9));
    tree->levelOrder(traverse);

}