<?php
echo 'Hellow';/**
*        ?????AVL
*        ???????????????????????????????acm??
*        ??avl?acm?????????treap??
*        avl????????????????????????
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <time.h>
#include <queue>
using namespace std;

int COUNT;        //????????????
int HEIGHT; //??????

//????
class DNode
{
public:
        int data;
        DNode():data(0){};
        DNode(int d):data(d){}

        bool operator = (const DNode &d){
                return data = d.data;
        }
        bool operator == (const DNode &d){
                return data == d.data;
        }
        bool operator > (const DNode &d){
                return data > d.data;
        }
        bool operator < (const DNode &d){
                return data < d.data;
        }
        void show(){
                cout << endl;
                cout << "***************" << endl;
                cout << "data: " << data << endl;
        }
};
//treap???
template<class T>
class AVLNode{
private:
        int hgt;        //?????
public:
        T data;
        int count;
        
        AVLNode<T> *son[2];        //0?????1????
        AVLNode<T>(T data):data(data), count(1){
                son[0] = son[1] = NULL;
                hgt = 1;
        }

        int max(int a, int b){return a > b ? a : b;}
        void show(){
                data.show();
                cout << "c hgt: " << this->height() << endl;
                cout << "l hgt: " << this->son[0]->height() << endl;
                cout << "r hgt: " << this->son[1]->height() << endl;
                cout << "count: " << count << endl;
                cout << endl;
        }
        int height(){
                if(NULL == this)
                        return 0;
                return _getHeight(this);
        }
        int _getHeight(AVLNode<T> * cur){
                if(NULL == cur)
                        return 0;
                return 1 + max(_getHeight(cur->son[0]), _getHeight(cur->son[1]));
        }
        void setHeight(){
                hgt = _getHeight(this);
        }
};

//AVL Tree
//???T?????????
template<class T>
class AVLTree{
private:
        AVLNode<T> * root;                //???
        int hgt;                        //????
        int size;                        //?????????
        void _insert(AVLNode<T> *& cur, T data);
        void _mid_travel(AVLNode<T> *cur);
        //????
        void _cengci_travel(AVLNode<T> *cur);
        //??????????, ???????????? ????????????????
        //?treap???????
        void _singleRoate(AVLNode<T> *& cur, int dir);
        //??????????
        void _doubleRoate(AVLNode<T> *& cur, int dir);
        int max(int a, int b){
                return a > b ? a : b;
        }
public:
        AVLTree():root(NULL), hgt(0){}
        void insert(const T & data);
        void mid_travel();
        int height(){
                return root->height();
        }
        //????
        void cengci_travel(){
                _cengci_travel(root);
        };

};

/*************  ??????**********************/
template<class T>
void AVLTree<T>::_insert(AVLNode<T> *& cur, T data){
        if(NULL == cur){
                cur = new AVLNode<T>(data);
        }else if(data == cur->data){
                cur->count++;
        }else{
                int dir = (data > cur->data);
                _insert(cur->son[dir], data);
                if(2 <= cur->son[dir]->height() - cur->son[!dir]->height()){
                        bool lr = (data > cur->data);
                        lr ? _singleRoate(cur, dir) : _doubleRoate(cur, dir);
                }
        }
        cur->setHeight();
        //cout << "set height: " << endl;
        //cur->show();
}
template<class T>
void AVLTree<T>::_mid_travel(AVLNode<T> * cur){
        if(NULL != cur){
                //??????
                _mid_travel(cur->son[0]);
                //if(abs(cur->son[0]->height() - cur->son[1]->height()) >= 2)
                {
                        cur->show();
                }
                _mid_travel(cur->son[1]);
        }
}
//?????
//?????????0 ???
template<class T>
void AVLTree<T>::_cengci_travel(AVLNode<T> * cur){
        if(NULL == cur)
                return;
        queue<AVLNode<T>*> q;
        q.push(cur);
        AVLNode<T> *top = NULL;
        queue<AVLNode<T>*> tmp;
        
        while(!q.empty()){
                while(!q.empty()){
                        top = q.front();
                        q.pop();
                        if(NULL == top){
                                //?#????????#?????#
                                cout << '#' << " ";
                                tmp.push(top);
                        }else{
                                cout << top->data.data << " ";
                                tmp.push(top->son[0]);
                                tmp.push(top->son[1]);
                        }
                }
                bool flag = false;
                while(!tmp.empty()){
                        if(NULL != tmp.front())
                                flag = true;
                        q.push(tmp.front());
                        tmp.pop();
                }
                cout << endl;
                if(!flag)
                        break;
        }
}

//??????????
//dir = 0?,????????????
template<class T>
void AVLTree<T>::_singleRoate(AVLNode<T> *& cur, int dir){
        AVLNode<T> *& k2 = cur, * k1 = k2->son[dir];        //k2 ?????
        k2->son[dir] = k1->son[!dir];
        k1->son[!dir] = k2;
        k2 = k1;
        
        k2->setHeight();
        k1->setHeight();
}
//???????????
//dir = 0?????? ???????
template<class T>
void AVLTree<T>::_doubleRoate(AVLNode<T> *& cur, int dir){
        _singleRoate(cur->son[dir], !dir);
        _singleRoate(cur, dir);
}

/*************  ??????????**********************/
template<class T>
void AVLTree<T>::insert(const T & data){
        _insert(root, data);
}
template<class T>
void AVLTree<T>::mid_travel(){
        _mid_travel(root);
}

int main(){
        AVLTree<DNode>* avlt = new AVLTree<DNode>();
        const int num = 30;
        for(int i = 0; i < num; i++){
                DNode * d = new DNode(i);
                avlt->insert(*d);

        }
        cout << "*************????***************" << endl;
        avlt->mid_travel();
        cout << "**************??????**********" << endl;

        cout << "*************??????***************" << endl;
        avlt->cengci_travel();
        cout << "**************??????**********" << endl;
        cout << "?????? " << avlt->height() << endl;
        return 0;
}