AVL 树¶
AVL 树 是一种 基于旋转 的 二叉搜索树，树中任一节点对应的两棵子树的最大高度差为 1，因此也被称为 高度平衡树，能在 \(O(\log n)\) 的时间内完成插入、查找、修改和删除操作
再平衡¶
int h(const node* root){
return root==nullptr ? -1 : root->h;
}
int calc_h(const node* root){
return max(h(root->lc),h(root->rc))+1;
}
node* R_rotate(node* root){
node* tmp=root->lc;
root->lc=tmp->rc;
tmp->rc=root;
// 观察发现右旋操作中，只有 tmp 和 tmp->rc 的树高会变
// 而之前 temp->rc=root，所以只需要做如下更新即可
tmp->h=calc_h(tmp);
root->h=calc_h(root);
return tmp;
}
node* L_rotate(node* root){
node* tmp=root->rc;
root->rc=tmp->lc;
tmp->lc=root;
// 观察发现左旋操作中，只有 tmp 和 tmp->lc 的树高会变
// 而之前 temp->lc=root，所以只需要做如下更新即可
tmp->h=calc_h(tmp);
root->h=calc_h(root);
return tmp;
}
int fac(node* root){
return (root->lc==nullptr ? -1 : root->lc->h) - (root->rc==nullptr ? -1 :root->rc->h);
}
node* rebalance(node* root){
if(fac(root)>1){
if(fac(root->lc)>0) return R_rotate(root); // LL 型 -> 右旋
else { // LR 型 -> 先左旋，再右旋
root->lc=L_rotate(root->rc);
return R_rotate(root);
}
}else if(fac(root)<-1){
if(fac(root->rc)<0) return L_rotate(root); // RR 型 -> 左旋
else { // RL 型 -> 先右旋，再左旋
root->rc=R_rotate(root->rc);
return L_rotate(root);
}
}else return root;
}
插入¶
void insert(node*& root,int _val){
if(root==nullptr){
root=new node;
root->val=_val;
return;
}
if(root->val==_val){
root->cnt++;
return;
}
// 递归搜索插入点
if(_val<root->val) insert(root->lc,_val);
if(_val>root->val) insert(root->rc,_val);
// 再平衡
root=rebalance(root);
// 回溯更新父结点高
root->h=calc_h(root);
return;
}
删除¶
void left_del(node* target,node* root){
if(root->lc==nullptr){ // no need to check rc
swap(target->val,root->val);
delete root;
root=nullptr;
return;
}
return left_del(target,root->lc);
}
void del(node*& root,int _val){
if(root->val==_val){
if(root->cnt>1){
root->cnt--;
return;
}
if(root->lc==nullptr){
if(root->rc==nullptr){
delete root;
root=nullptr;
return;
}
delete root;
root=root->rc;
return;
}
if(root->rc==nullptr){
delete root;
root=root->lc;
return;
}
left_del(root,root);
return;
}
if(_val<root->val) del(root->lc,_val);
if(_val>root->val) del(root->rc,_val);
root=rebalance(root); // 回溯再平衡
return;
}