平衡二叉树

平衡二叉树的插入

#include<iostream>
#include<stack>
using namespace std;

typedef struct AVLnode{
    int data;
    int height;
    AVLnode *left , *right;

}AVLnode , *AVLtree;

int getHeight(AVLtree tree){
    if(tree == NULL){
        return 0;
    }
    return tree->height;
}

void updateHeight(AVLtree tree){       //每次插入后都要更新高度，由于是递归，所以在每次插入后加1就可以更新全部节点的高度
    tree->height = max(getHeight(tree->left) , getHeight(tree->right)) + 1;
}

int getBalance(AVLtree tree){   //左子树高度-右子树高度，如果是2或-2，那么说明不平衡了
    return getHeight(tree->left) - getHeight(tree->right);
}

void leftTurn(AVLtree &tree){   //左旋操作
    AVLtree temp = tree->right;
    tree->right = temp->left;
    temp->left = tree;
    updateHeight(tree);         //旋转后位置变化，要更新节点高度
    updateHeight(temp);
    tree = temp;
}

void rightTurn(AVLtree &tree){   //右旋操作
    AVLtree temp = tree->left;
    tree->left = temp->right;
    temp->right = tree;
    updateHeight(tree);    //先更新高度低的节点
    updateHeight(temp);
    tree = temp;
}

void insertt(AVLtree &tree , int v){  //传入的是指针的引用，如果只传入指针，无法改变指针参数所指向的地址，只有传入指针引用才能改变地址
    if(tree == NULL){
        tree = new AVLnode;
        tree->data = v;
        tree->height = 1;
        tree->left = tree->right = NULL;
        return ;
    }

    if(v < tree->data){
        insertt(tree->left , v);
        updateHeight(tree);
        if(getBalance(tree) == 2){
            if(getBalance(tree->left) == 1){    //LL型  根节点右旋
                rightTurn(tree);
            }
            else if(getBalance(tree->left) == -1){   //LR，先左子树左旋，然后根节点右旋
                leftTurn(tree->left);
                rightTurn(tree);
            }
        }
    }

    else {
        insertt(tree->right , v);
        updateHeight(tree);
        if(getBalance(tree) == -2){
            if(getBalance(tree->right) == -1){  //RR  根节点左旋
                leftTurn(tree);
            }
            else if(getBalance(tree->right) == 1){ //RL  右子树右旋，根节点左旋
                rightTurn(tree->right);
                leftTurn(tree);
            }
        }
    }

}

int main()
{
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    AVLtree tree = NULL;
    for(int i = 0 ; i<n ; ++i){
        int a;
        cin>>a;
        insertt(tree , a);
    }
    cout<<tree->data;
}