ALDS1_8_C Binary Search Tree III

問題
二分探索木 削除 | アルゴリズムとデータ構造 | Aizu Online Judge

平衡木であるAVL木の実装に挑戦しようと思い、その前に二分探索木おさらいしとくか～って軽い気持ちで解きなおしたらかなり苦労しました。
ポインタのポインタの理解が疎かになっていました。

insert、find、printは何の問題もなく実装できたのですが、delete部分でかなり悩みました。
アルゴリズムとしては

void Delete(Node **p,int x){
	Node *q=*p;		//*q:探索ポインタ、p：qを持つノード
	
	while(q!=NULL){
	
		//該当ノード発見
		if(q->key == x){
		
			if(該当ノードが葉){そのまま削除}
			
			else if(子が１つ){pが子を指すようにする}
			
			else if(子が２つ){右の部分木の最小要素の値をコピーし、その要素をDeleteで削除}
			
		}
		
		else if(q->key > x){左ノードに移動}
		else {右ノードに移動}
		
	}
	
}

こんな感じです。ここまでは大丈夫なのですが、日本語で書いてある部分のポインタ操作を全て間違えました。

・左（右）ノードに移動

	//正解
	else if(q->key > x){
		p=&(q->left);
		q=*p;
	}
	
	//間違い
	else if(q->key > x){
		q=q->left;
		p=&q;
	}

こんな風に間違えました。恥ずかしや。
正しい方は、一行目で「q->leftというポインタがあるアドレス」にpを移動し、二行目で「pに入っているポインタ」をqに代入しています。
間違っている方は、一行目で「q->leftというポインタ」をqに代入し、二行目で「qというポインタのアドレス」をpに代入しています。
qの中身は変わりますが、pにはqという変数のアドレスが入り続けるので、pは変わりません。

・pが子を指すようにする

	//正解
	else if(q->left==NULL && q->right!=NULL){
		*p=q->right;
		return;
	}
	
	//間違い
	else if(q->left==NULL && q->right!=NULL){
		p=&(q->right);
		return;
	}

正解の方は「pの中身をq->rightに変更」していますが、間違ってる方は「pにq->rightのアドレスを代入（つまりpの移動）」になります。ダメですね。

・右の部分木の最小要素の値をコピーし、その要素をDeleteで削除

else {
	r=&(q->right);
	q=*r;
	while(q->left!=NULL){
		r=&(q->left);
		q=*r;
	}
	(*p)->key=q->key;
	Delete(r,q->key);
	return;
}

rとqの設定とwhileの中身を間違えました。具体的には、上で書いたようにポインタの更新を間違えました。

以上を踏まえて、こんな実装になりました。

#include<stdio.h>
#include<stdlib.h>

typedef struct Node{
	int key;
	struct Node *left;
	struct Node *right;
}Node;

void insert(Node **p,int x){
	
	while((*p)!=NULL){
		
		if((*p)->key > x)
			p=&((*p)->left);
		else
			p=&((*p)->right);
			
	}
	
	*p=malloc(sizeof(Node));
	(*p)->key=x;
	(*p)->left=NULL;
	(*p)->right=NULL;
	
	return;
}

void Delete(Node **p,int x){
	Node *q=*p;
	Node **r;
	
	while(q!=NULL){
	
		if(q->key == x){
		
			if(q->left==NULL && q->right==NULL){
				free(q);
				*p=NULL;
				return;
			}
			else if(q->left==NULL && q->right!=NULL){
				*p=q->right;
				return;
			}
			else if(q->left!=NULL && q->right==NULL){
				*p=q->left;
				return;
			}
			else {
				r=&(q->right);
				q=*r;
				while(q->left!=NULL){
					r=&(q->left);
					q=*r;
				}
				(*p)->key=q->key;
				Delete(r,q->key);
				return;
			}
			
		}	
		
		else if(q->key > x){
			p=&(q->left);
			q=*p;
		}
		else {
			p=&(q->right);
			q=*p;
		}
		
	}

	return;
}

void inorder(Node *p){
	
	if(p->left!=NULL)
		inorder(p->left);
	
	printf(" %d",p->key);
	
	if(p->right!=NULL)
		inorder(p->right);
	
	return;
}

void preorder(Node *p){
	
	printf(" %d",p->key);
	
	if(p->left!=NULL)
		preorder(p->left);
	
	if(p->right!=NULL)
		preorder(p->right);
	
	return;
}

void print(Node *root){
	inorder(root);
	printf("\n");
	
	preorder(root);
	printf("\n");
	
	return;
}

int find(Node *p,int x){

	while(p!=NULL){
		if(p->key == x)return 1;
		
		if(p->key > x)
			p=p->left;
		else
			p=p->right;
	}
	
	return 0;
	
}

int main(){
	int q,x;
	Node *root=NULL;
	char com[10];
	
	scanf("%d",&q);
	
	for(int i=0;i<q;i++){
		scanf("%s",com);
		
		if(com[0]=='i'){
			scanf("%d",&x);
			insert(&root,x);
		}
		
		else if(com[0]=='f'){
			scanf("%d",&x);
			if(find(root,x))
				printf("yes\n");
			else
				printf("no\n");
		}
		
		else if(com[0]=='p')
			print(root);
		
		else if(com[0]=='d'){
			scanf("%d",&x);
			Delete(&root,x);
		}
	}
	
	return 0;
	
}

詳しく書いてみましたが、日本語がめちゃくちゃですね。恥ずかしい。