#include "p353.cpp"		template <class Type> int Btree<Type>::Remove ( const Type & x ) {		//從駐留磁盤(pán)上的m階B-樹(shù)上刪除x。		   Triple<Type> loc = Search (x);			//在樹(shù)中搜索x		   if ( loc.tag ) return 0;					//x不在B-樹(shù)中, 返主		   Mnode<Type> *p = loc.r, *q, *s;			//p是關(guān)鍵碼x所在結(jié)點(diǎn)		   int j = loc.i;						//j是關(guān)鍵碼在結(jié)點(diǎn)中的位置		   if ( p->ptr[j] != NULL ) {				//若p非葉結(jié)點(diǎn)			 s = p->ptr[j];  GetNode (s);  q = p;		//讀取磁盤(pán)上的s結(jié)點(diǎn)			 while ( s != NULL ) { q = s;  s = s->ptr[0]; }	//找大于x但最接近于x的最小關(guān)鍵碼(q是葉結(jié)點(diǎn))			 p->key[j] = q->key[1];				//用最小關(guān)鍵碼填補(bǔ)			 compress ( q, 1 );					//在q結(jié)點(diǎn)中關(guān)鍵碼與指針前移填補(bǔ)key[1], q->n減1			 p = q;						//下一步處理q結(jié)點(diǎn)中的刪除   		   }		   else compress ( p, j );					//p是葉結(jié)點(diǎn), 關(guān)鍵碼與指針前移填補(bǔ)key[j], p->n減1		   int d = (m+1)/2;						//結(jié)點(diǎn)容納關(guān)鍵碼的下限		   if (!(p==root))		   while (1) {			 if ( p->n < d-1 ) {					//需要調(diào)整			   j = 0;  q = p->parent;			//在q中找指向p的指針			   GetNode (q);			   while ( j <= q->n && q->ptr[j] != p ) j++;			   if ( !j ) LeftAdjust ( p, q, d, j );		//p是q的最左子女, 與其右兄弟與雙親結(jié)點(diǎn)做調(diào)整			   else 				if (j==q->n) RightAdjust ( p, q, d, j );			//p是q的最右子女, 與其左兄弟與雙親結(jié)點(diǎn)做調(diào)整			   else													//p是中間,選擇一個(gè)較簡(jiǎn)單的合并方法				if ( (q->ptr[j+1]->n) > d-1 ) LeftAdjust(p,q,d,j);  			   else				RightAdjust ( p, q, d, j );					   p = q;						//繼續(xù)向上做結(jié)點(diǎn)調(diào)整工作			   if ( p == root ) break;			 }			 else break;						//不需要進(jìn)行調(diào)整, 跳出循環(huán)		   }		   if ( !root->n ) {					//當(dāng)根結(jié)點(diǎn)為空時(shí)刪根結(jié)點(diǎn)			 p = root->ptr[0];  delete root;  root = p;  			 if (root) root->parent = NULL;		   }		   return 1;		}		template <class Type>		void Btree<Type>::LeftAdjust ( Mnode<Type> *p, Mnode<Type> *q, const int d, const int j ) {		   Mnode<Type> *p1 = q->ptr[j+1];			//p的右兄弟		   if ( p1->n > d-1 ) {					//右兄弟空間還夠, 不用合并, 僅做調(diào)整			 ( p->n ) ++;			 p->key[p->n] = q->key[j+1];			//雙親結(jié)點(diǎn)相應(yīng)關(guān)鍵碼下移			 q->key[j+1] = p1->key[1];				//右兄弟最小關(guān)鍵碼上移到雙親結(jié)點(diǎn)			 p->ptr[p->n] = p1->ptr[0];			//右兄弟最左指針左移			 compress ( p1, 0 );		   }		   else merge ( p, q, p1,j );				//p與p1合并, 保留p結(jié)點(diǎn)		}		template <class Type> void Btree<Type>::compress ( Mnode<Type> *p, const int j ) {		   for ( int i=j; i<p->n; i++ )				//左移 			 { p->key[i] = p->key[i+1];  p->ptr[i] = p->ptr[i+1]; }		   p->n --;							//結(jié)點(diǎn)中元素個(gè)數(shù)減1		}		template <class Type>		 void Btree<Type>::merge ( Mnode<Type> *p, Mnode<Type> *q, Mnode<Type> *p1, const int j) {		   p->key[(p->n)+1] = q->key[j+1];			//從雙親結(jié)點(diǎn)下降一個(gè)關(guān)鍵碼		   p->ptr[(p->n)+1] = p1->ptr[0];			//從右兄弟結(jié)點(diǎn)左移一個(gè)指針		   for ( int k=1; k<=p1->n; k++ ) {				//從右兄弟結(jié)點(diǎn)		      p->key[(p->n)+k+1] = p1->key[k];		//關(guān)鍵碼從p1到p左移	      	p->ptr[(p->n)+k+1] = p1->ptr[k];		//指針從p1到p左移		   }		   compress ( q, j+1 );					//雙親結(jié)點(diǎn)q中值與指針左移		   p->n = p->n + p1->n + 1;		   delete p1;		}		template <class Type>		void Btree<Type>::RightAdjust ( Mnode<Type> *p, Mnode<Type> *q, const int d, const int j )		//此程序與LeftAdjust功能基本相同，但與LeftAdjust是對(duì)稱(chēng)的：左右指針互換，前端與后端互換。		{		   Mnode<Type> *p1 = q->ptr[j-1];			//p的左兄弟		   if ( p1->n > d-1 ) {					//左兄弟空間還夠, 不用合并, 僅做調(diào)整			 ( p->n ) ++;			 for (int i=p->n; i>=1;i--)			 {				 p->key[i]=p->key[i-1];				 p->ptr[i]=p->ptr[i-1];			 }			 p->key[1]=q->key[j];			 q->key[j]=p1->key[p1->n];			 p->ptr[0]=p1->ptr[p1->n];			 (p1->n)--;		   }		   else merge ( p1, q, p,j-1 );				//p1與p合并, 保留p結(jié)點(diǎn)		}