关于程序员: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 树插入结点以及建树不再赘述，调用上述函数即可。须要留神插入结点后更新根结点的高度，并且什么状况执行什么旋转操作要分明。