アルゴリズム(2分探索木)の問題について
２分探索木のアルゴリズムに関する問題について質問させていただきます。
[問題]
集合Sに対する2文探索木とは、ラベルつきの2分木で、
その頂点vにはSのある要素l(v)がラベルとしてつけられている。
l(v)は次の性質を満たす。
１．vの左部分木の頂点uに対して l(u) < l(v)
2．vの右部分木の頂点uに対して l(u) > l(v)
3．Sの任意の要素aに対して l(v) = a となる頂点vはちょうどひとつある。
図はキーワード集合{begin,else,end,if,then}をあらわす2分探索木の例である。
いま、集合Sを表す2分探索木と要素aが与えられているときa∈Sならば"はい"、
そうでなければ"いいえ"を出力するアルゴリズムを考える。
このアルゴリズムは、木の根rについて一回だけ再帰手続きSEARCH(a,r)を呼び出せばよい。
ただし、SEARCH(a,v)はvを根とする部分木中に要素aが含まれているかを判定する。
含まれているときに値"はい"を、そうでなければ値"いいえ"を返す。
・アルゴリズム
procedure SEARCH(a,v):
if a = l(v) then return "はい"
else
if a < l(v) then
if vが左の子wを持つ then return SEARCH( ア )
else return "いいえ"
else
イ
以下の問題に答えよ。
(1) 上のアルゴリズムのア,イを埋めよ。
(2) 上のアルゴリズムを参考にして、集合Sからのデータの削除DELETE(a,S)を考える。
削除すべき要素aが頂点vのラベルであったとする。そのとき次の3つの場合について、行うべき操作を記述せよ。
(i) 頂点vが葉である (ii) 頂点vの子が1個ある (iii) 頂点vの子が2個ある
以上です。
設問(1)は解けました。
答えは
ア: a,w
イ: a > l(v) then
if vが右の子wを持つ then return SEARCH(a,w)
else return "いいえ"
になるのではないかと思います。
設問(2)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、
参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。
長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。
![その他([技術者向] コンピューター) イメージ](https://gazo.okwave.jp/okwave/spn/images/related_qa/c205_1_thumbnail_img_sm.png)
