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