平衡二叉數(shù)資料

平衡二叉數(shù).txt昨天是作廢的支票；明天是尚未兌現(xiàn)的期票；只有今天才是現(xiàn)金，才能隨時兌現(xiàn)一切。人總愛欺騙自己，因?yàn)槟潜绕垓_別人更容易。{treap示范代碼：標(biāo)準(zhǔn)的代碼縮進(jìn)風(fēng)格，優(yōu)美的算法實(shí)現(xiàn)。經(jīng)典標(biāo)程，完全掌握后水平會提高很多不改變bst的性質(zhì)(在bst所有子樹中均滿足：左子樹的所有節(jié)點(diǎn)<=根<=右子樹的所有節(jié)點(diǎn))通過旋轉(zhuǎn)操作，使根的hr最小(即所有的hr構(gòu)成堆的關(guān)系)}var//l[i],r[i],v[i]:i號結(jié)點(diǎn)的左兒子、右兒子，關(guān)鍵值//hr[i]:i號節(jié)點(diǎn)的優(yōu)先值(treap所有子樹中,根的hr必須是最小的)//s[i]:i號節(jié)點(diǎn)為根的子樹節(jié)點(diǎn)總數(shù)l,r,hr,s,v:array[0..2000000]oflongint;n,root,m:longint;procedureinit;//初始化beginreadln(n);m:=0;//randomize;//考試要求程序每次運(yùn)行結(jié)果必須一致,慎用。確實(shí)要用：randomize100;fillchar(s,sizeof(s),0);fillchar(l,sizeof(l),0);fillchar(r,sizeof(r),0);root:=0;end;//旋轉(zhuǎn)是平衡二叉樹的精髓，它不會改變bst的性質(zhì)(左子樹<=根<=右子樹)//左旋使樹的左子樹深度+1,右子樹深度-1//右旋使樹的右子樹深度+1,左子樹深度-1procedurel_rotate(varx:longint);inline;//左旋以x為根的子樹（注意var參數(shù)及意義）vary:longint;beginy:=r[x];//保存x的右兒子到y(tǒng)中r[x]:=l[y];//將y的左兒子作為x的右兒子l[y]:=x;//x作為y的左兒子s[y]:=s[x];//維護(hù)旋轉(zhuǎn)后的子樹大小s[x]:=s[l[x]]+s[r[x]]+1;x:=y;//y為根end;procedurer_rotate(varx:longint);inline;//右旋以x為根的子樹vary:longint;beginy:=l[x];l[x]:=r[y];r[y]:=x;s[y]:=s[x];s[x]:=s[l[x]]+s[r[x]]+1;x:=y;end;//插入（遞歸，ifkey<=root,則插入到左子樹，否則到右子樹，直到盡頭再新建節(jié)點(diǎn)）procedureinsert(vark,key:longint);inline;beginifk=0then//已到盡頭，新建節(jié)點(diǎn)并寫入key及隨機(jī)值hrbegininc(m);v[m]:=key;s[m]:=1;hr[m]:=random(maxlongint);k:=m;//修改k,使父節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)(修改前從父節(jié)點(diǎn)指向0)exit;end;inc(s[k]);ifkey<=v[k]then//若key<=根則插入到左子樹，否則到右子樹begininsert(l[k],key);//若l[k]=0,到下層則新建節(jié)點(diǎn)并修改l[k]=mifhr[l[k]]>hr[k]then//旋轉(zhuǎn)r_rotate(k);exit;end;ifkey>v[k]thenbegininsert(r[k],key);ifhr[r[k]]>hr[k]thenl_rotate(k);exit;end;end;(刪除:在k號節(jié)點(diǎn)為根的子樹中刪除ke