关于程序员:PATAVL树模板

//定义结点struct node{    int data, height;    node *left, *right;};//创立新结点node* newNode(int x){    node* root = new node;    root->data = x;    root->height = 1;   //此处要初始化为1    root->left = NULL;    root->right = NULL;    return root;}//获取结点高度（次要是省略了对空结点的特判，便于更新结点高度）int getHeight(node* root){    if(root == NULL)    return 0;    else    return root->height;}//获取结点均衡因子int getBalanceFactor(node* root){    return getHeight(root->left) - getHeight(root->right);}//更新结点的高度void updateHeight(node* root){//此处是批改结点外部的值，因而不必援用，目前为止只有上面的两个旋转操作须要应用援用，因为波及到扭转整个树结点之间的构造关系    root->height = max(root->left->height, root->right->height) + 1;}//左旋void L(node* &root){    node* temp = root->right;    root->right = temp->left;   //上面这两句话程序不能搞反，不分明时能够画一个图    temp->left = root;    updateHeight(root); //上面这两句更新高度不能忘    updateHeight(temp);    root = temp;}//右旋void R(node* &root){    node* temp = root->left;    root->left = temp->right;    temp->right = root;    updateHeight(root);    updateHeight(temp);    root = temp;}

向avl树插入结点以及建树不再赘述，调用上述函数即可。须要留神插入结点后更新根结点的高度，并且什么状况执行什么旋转操作要分明。