/**
* 目的：实现AVL
* 利用数组对左右儿子简化代码，但是对脑力难度反而增大不少，只适合acm模板
* 其实avl在acm中基本不用，基本被treap取代
* avl一般只要求理解思路，不要求写出代码，因为真心很烦
*/
#include
#include
#include
#include
#include
#include
#include
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 cur->data);
lr ? _singleRoate(cur, dir) : _doubleRoate(cur, dir);
}
}
cur->setHeight();
//cout son[0]);
//if(abs(cur->son[0]->height() - cur->son[1]->height()) >= 2)
{
cur->show();
}
_mid_travel(cur->son[1]);
}
}
//层次遍历，
//如果节点为空就输出0 来占位
template
void AVLTree::_cengci_travel(AVLNode * cur){
if(NULL == cur)
return;
queue q;
q.push(cur);
AVLNode *top = NULL;
queue tmp;
while(!q.empty()){
while(!q.empty()){
top = q.front();
q.pop();
if(NULL == top){
//用#代表该节点是空，#的后代还是#
cout son[dir] = k1->son[!dir];
k1->son[!dir] = k2;
k2 = k1;
k2->setHeight();
k1->setHeight();
}
//双旋转，即调两次单旋转
//dir = 0是左右情况； 否则为右左情况
template
void AVLTree::_doubleRoate(AVLNode *& cur, int dir){
_singleRoate(cur->son[dir], !dir);
_singleRoate(cur, dir);
}
/************* 公有方法（接口）开始**********************/
template
void AVLTree::insert(const T & data){
_insert(root, data);
}
template
void AVLTree::mid_travel(){
_mid_travel(root);
}
int main(){
AVLTree* avlt = new AVLTree();
const int num = 30;
for(int i = 0; i < num; i++){
DNode * d = new DNode(i);
avlt->insert(*d);
}
cout