今天在写AVL删除的时候犯了一个傻逼错误,调了很久,教训惨痛,引以为鉴。
树中允许有重复节点,如果删除的节点有重复,则只删除1个。
AVL删除采取的方法是首先判断待删除节点是否存在,如果存在,那么判断该节点是否有两个儿子,如果有,则找到它左子树中的最大节点,设其值为t,将之删除,并将它的值去覆盖待删除节点。此处删除函数是带返回值的,为删除的节点的值。但是如果树中节点可以重复出现,碰巧待删除节点有多个,那么这些节点的值可能有多个被t覆盖,导致发生错误。
那么怎么避免这一错误呢?
当然我们可以把重复的节点弄成一个节点,用一个cnt来标记它出现的次数。
或者,在将t覆盖带删除节点,保证只覆盖一次。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; #define MAXN 100055 int root,tot=0,n,m; char opt[10]; struct node {int ch[2],val,h,sz; }tree[MAXN]; void update(int r) { tree[r].h=max(tree[tree[r].ch[0]].h,tree[tree[r].ch[1]].h)+1; tree[r].sz=tree[tree[r].ch[0]].sz+tree[tree[r].ch[1]].sz+1; } void zig(int &r) //鍙虫棆 { int t=tree[r].ch[0]; if(t==0)return; tree[r].ch[0]=tree[t].ch[1]; tree[t].ch[1]=r; update(r); update(t); r=t; } void zag(int &r) { int t=tree[r].ch[1]; if(t==0)return; tree[r].ch[1]=tree[t].ch[0]; tree[t].ch[0]=r; update(r); update(t); r=t; } void zigzag(int &r) { zig(tree[r].ch[1]); zag(r); } void zagzig(int &r) { zag(tree[r].ch[0]); zig(r); } bool find(int r,int x) { if(r==0)return 0; if(tree[r].val==x) return 1; else if(tree[r].val<x) return find(tree[r].ch[1],x); else return find(tree[r].ch[0],x); } void insert(int &r,int x) { if(r==0) {tree[++tot].val=x; tree[tot].sz=1; tree[tot].h=1; r=tot; return; } if(x<=tree[r].val) { insert(tree[r].ch[0],x); if(tree[tree[r].ch[0]].h==tree[tree[r].ch[1]].h+2) { if(x<=tree[tree[r].ch[0]].val) zig(r); else zagzig(r); } } else { insert(tree[r].ch[1],x); if(tree[tree[r].ch[1]].h==tree[tree[r].ch[0]].h+2) { if(x>tree[tree[r].ch[1]].val) zag(r); else zigzag(r); } } update(r); } void maintain(int &r) { if(r==0)return; if(tree[tree[r].ch[0]].h==tree[tree[r].ch[1]].h+2) { int t=tree[r].ch[0]; if(t==0)return; if(tree[tree[t].ch[0]].h==tree[tree[r].ch[1]].h+1) zig(r); else zagzig(r); } else if(tree[tree[r].ch[1]].h==tree[tree[r].ch[0]].h+2) { int t=tree[r].ch[1]; if(t==0)return; if(tree[tree[t].ch[1]].h==tree[tree[r].ch[0]].h+1) zag(r); else zigzag(r); } update(r); } int del(int &r,int x) { int temp; if(tree[r].val==x||(tree[r].val<x&&tree[r].ch[1]==0)||(tree[r].val>x&&tree[r].ch[0]==0)) { if(tree[r].ch[1]==0||tree[r].ch[0]==0) { temp=tree[r].val; r=tree[r].ch[1]+tree[r].ch[0]; return temp; } else { temp=tree[r].val; //注意这里,这样保证待删除节点只删掉了一个。 tree[r].val=del(tree[r].ch[0],x); } } else if(tree[r].val<x) temp= del(tree[r].ch[1],x); else temp=del(tree[r].ch[0],x); maintain(r); return temp; } int query(int r,int rk)//鎵炬帓鍚嶄负绗瑀k鐨勫厓绱? { if(r==0)return 0; int t=tree[r].ch[0]; if(tree[t].sz>=rk) return query(tree[r].ch[0],rk); else if(tree[t].sz+1<rk) return query(tree[r].ch[1],rk-tree[t].sz-1); else return tree[r].val; } int main() { int t,u,rnk=0; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { scanf("%d",&t); insert(root,t); } rnk=n; for(int i=0;i<m;i++) { scanf("%s",opt); if(opt[0]=='I') { rnk++; scanf("%d",&t); insert(root,t); } else if(opt[0]=='D') { scanf("%d",&t); if(find(root,t)) { del(root,t); rnk--; } } else if(opt[0]=='M') { scanf("%d%d",&t,&u); if(find(root,t)) { del(root,t); insert(root,u); } } else if(opt[0]=='Q') { printf("%d ",query(root,(rnk+1)/2)); } } return 0; }