蟻本 2－4 二分探索木の復習

プログラミングコンテストチャレンジブック（通称”蟻本”）の気になった項目を見ていきます。
素人の解説なので分かりにくい or 誤った説明があれば教えてくださいm(__)m
AtCoder社サイトのAPG4bをひと通り読んだくらいの方を対象に書いています（自分がそうなので）。
今回は二分探索木です。やや長いです。
◆二分探索木
…二分木の一種です。すべてのノードについて、左の子以下のノードの数字は自分の数字よりすべて小さく、右の子以下のノードの数字は自分の数字よりすべて大きいという構造をしています。
↓実装です。

qiita.c++

//ノードを表す構造体を作ります。
//valはノードの数字です。
//lch(left child),rch(right child)はそれぞれノードの子を意味します。
struct node{
  int val;
//ポインタ変数の設置 *lch,*rch（lch,rchはアドレスを意味します）。
  node *lch,*rch;
};

//ノードpに数xを追加します（pはアドレス）。
node *insert(node *p,int x){
//ノードpのアドレスが無い場合（つまりノードpがないとき）
  if(p == NULL){
//新たにnew nodeというノードを作り、アドレスをqとします。
    node *q = new node;
//「->」はアロー演算子です。q->valはqが指す構造体の変数valを指します。
//qのノードの数字をxとします。
    q->val = x;
//ノードqの左の子、右の子のアドレスは設定しません。
    q->lch = q->rch = NULL;
//追加した数字xのノードであるqのアドレスを返します。
    return q;
  }
//pのアドレスが存在する場合
  else {
//xがノードpの数字より小さい場合、ノードpの左の子ノードにxを追加します。
    if(x < p->val) p->lch = insert(p->lch,x);
//xがノードpの数字以上の場合、ノードpの右の子ノードにxを追加します。
    else p->rch = insert(p->rch,x);
//pのアドレスを返します。
    return p;
  }
}

//ノードpの数字がxかどうかを判定します。
bool find(node *p,int x){
//pのアドレスがない場合、falseを返します。
  if(p == NULL) return false;
//ノードpの数字がxのとき、trueを返します。
  else if (x == p->val) return true;
//ノードpの数字よりもxが小さいとき、ノードpの左の子ノードの数字を調べます。
  else if(x < p->val) return find(p->lch,x);
//ノードpの数字よりもxが大きいとき、ノードpの右の子ノードの数字を調べます。
  else return find(p->rch,x);
}

//ノードpの数字を調べ、xであれば消去します。
//pの代わりに入ったノードのアドレスを返します。
node *remove(node *p,int x){
//pのアドレスが無い場合、消去できません。
  if(p == NULL) return NULL;
//ノードpの数字よりもxが小さいとき、ノードpの左の子ノードの数字を調べます。
//xであれば消去します。
  else if(x < p->val) p->lch = remove(p->lch,x);
//ノードpの数字よりもxが大きいとき、同じ操作をノードpの右の子に対して行います。
  else if(x > p->val) p->rch = remove(p->rch,x);
//ノードpの数字がxであり、ノードpの左の子が無い場合
  else if(p->lch == NULL){
//ノードpの左の子qを作ります。
    node *q = p->lch;
//qの右の子としてpの右の子を指定します。
    q->rch = p->rch;
//ノードpを消去し、qのアドレスを返します。
    delete p;
    return q;
  }
//ノードpの数字がxであり、ノードpの左の子が存在する場合
  else {
//ノードqをnode型の変数として設定します。
    node *q;
//for文を作り、ノードpの左の子以下で最も大きいノードを見つけます（↓手順）。
//q = p->lchは初期値。
//for内の操作を行った後、qの右の子に移ります。
//qの右の子の右の子が無くなるまで繰り返します。
//よく目にする「for(int i=0;i<n;i++)」と比べればすぐ理解できます。
    for(q = p->lch; q->rch->rch != NULL; q = q->rch);

//ノードqの右の子の右の子が無くなったとき
//ノードrをノードqの右の子とします（このrはノードpが消去された場所に行きます）。
    node *r = q->rch;
//rが無くなるので、代わりにqの右の子にr->lchを設定します。
    q->rch = r->lch;
//rはノードpが消去された場所に行くので、rの左、右の子はpの左、右の子とします。
    r->lch = p->lch;
    r->rch = p->rch;
//pを消去し、rのアドレスを返します。
    delete p;
    return r;
  }
  return p;
}