ﾄﾚｰｽの方法についてですが､実際に数値を当てはめてみて､その流れを追うだけです｡せっかく図1というものがあるのですからそれを利用しましょう｡

例として､8を削除する場合､

function removeNode(k, p) // 受け取る引数は､k=8, p=15(8を削除するための指示)
# p=15なので､p.left=8, p.right=25です｡

p.left ← removeNode(k, p.left) // 受け渡す引数は､k=8, p.left=8 ?

function removeNode(k, p) // 受け取る引数は､k=8, p=8
# p=8なので､p.left=2, p.right=10

p.left ← extractMaxNode(p.left) // 受け渡す引数は､p.left=2 ?

と､本来ならここからextractMaxNodeのﾙｰﾌﾟに入るようなのですが､図1の構造の場合､8を消してそこに左下の2を持ってくるだけで終了となります｡

function extractMaxNode(p) // 受け取る引数はp=2
# p=2なので､p.left=null, p.right=null

extractedNode ← p // extractedNode=2
p ← p.left // p=null
return p // ?に戻ります｡返す値はnull

p.left ← extractMaxNode(p.left) // 8のleftはnullで上書きされました ?
r ← extractedNode // r=2
r.left ← p.left // r.left=null(extractMaxNodeの戻り値と一緒)
r.right ← p.right // r.right=10
[ ｷ ] // ﾌﾞﾗｯｸﾎﾞｯｸｽな処理
return p // ?に戻ります｡返す値はp

p.left ← removeNode(k, p.left) // ?
# p=15です｡つまり､p.left=2になれば処理を終了してもいいという事ですね？
# 模範解答が http://www.ap-siken.com/kakomon/27_aki/pm03.html にあって､
# [ ｷ ]は p ← r が正解のようです｡
# (が､ p ← extractedNode と仮に回答しても減点はされないはず)

行った動作を最後にまとめると､8の左側にある数字のうち一番大きな数字である2を8が元あった位置に挿げ替え､こうして8の削除を達成したという事です｡

--------------------------------------------------------

extractMaxNodeでﾙｰﾌﾟさせる例として､15を削除する場合､

function removeNode(k, p) // 受け取る引数は､k=15, p=15(15を削除するための指示)
# p=15なので､p.left=8, p.right=25です｡

p.left ← extractMaxNode(p.left) // 受け渡す引数は､p.left=8 ?

いきなり条件が合致したので､さっそくﾙｰﾌﾟ開始です｡

function extractMaxNode(p) // 受け取る引数はp=8
# p=8なので､p.left=2, p.right=10

p.right ← extractMaxNode(p.right) // 受け渡す引数は､p.right=10 ?

function extractMaxNode(p) // 受け取る引数はp=10
# p=10なので､p.left=9, p.right=12

p.right ← extractMaxNode(p.right) // 受け渡す引数は､p.right=12 ?

function extractMaxNode(p) // 受け取る引数はp=12
# p=12なので､p.left=[ ｱ ], p.right=null

extractedNode ← p // extractedNode=12
p ← p.left // p=[ ｱ ]
return p // ?に戻ります｡返す値は[ ｱ ]

p.right ← extractMaxNode(p.right) // 10のrightは[ ｱ ]で上書きされました ?
return p // ?に戻ります｡返す値は10

p.right ← extractMaxNode(p.right) // 8のrightは10で上書きされました ?
# といっても､元々10が入っていたところに同じ数字で上書きしただけです
return p // ?に戻ります｡返す値は8

p.left ← extractMaxNode(p.left) // 15のleftは8で上書きされました ?
# 実はこれも同じ数字で上書きしただけという

r ← extractedNode // r=12
r.left ← p.left // r.left=8(extractMaxNodeの戻り値と一緒)
r.right ← p.right // r.right=25
p ← r // [ ｷ ] // pそのものが15から12に上書きされました
return p // ?に戻ります｡返す値は12


行った動作を最後にまとめると､15の左側にある数字のうち一番大きな数字である12を15が元あった位置に挿げ替え､こうして15の削除を達成したという事です｡その際､12が元あった位置は12のleftにあった[ ｱ ]に置き換えています｡

図1の15を12にし､12を[ ｱ ]に置き換えて考えてみましょう｡

> ･Nの左部分木にある全てのﾉｰﾄﾞのｷｰ値は､Nのｷｰ値よりも小さい｡
> ･Nの右部分木にある全てのﾉｰﾄﾞのｷｰ値は､Nのｷｰ値よりも大きい｡

という構造条件はきちんと維持されている事がわかります｡あとはその下にある設問4の動画を見れば何をしているのかが理解できるのではないかと｡

--------------------------------------------------------

この辺の事は私も学んではいないのですが､たぶん2分探索木というのはこういう動作なのだという事で､概念そのものを丸暗記してしまった方がいいのかもしれません｡つまりこの問題の意味するところというのは､応用情報技術者ならばこの程度の事は基礎知識として知っていて当然である､という事なんだと思います(PERTなんかと一緒で)｡

wikipedia:二分探索木#削除

(二分探索木の性質上､探索ﾉｰﾄﾞには右の子は無い)

ﾒﾘｯﾄとﾃﾞﾒﾘｯﾄ
http://ufcpp.net/study/algorithm/col_tree.html