2分探索木のアルゴリズムに関する問題について質問させていただきます。
[問題]
集合Sに対する2文探索木とは、ラベルつきの2分木で、
その頂点vにはSのある要素l(v)がラベルとしてつけられている。
l(v)は次の性質を満たす。
1.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)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、
参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。
長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。
No.1ベストアンサー
- 回答日時:
確かによくわからないですね。
というのは、例示されている擬似言語で書けばよさそうなのですが、擬似言語では要素の削除や移動(または複写)の方法は定義されていないようです。擬似言語における要素の削除等を勝手に定義して擬似言語で書くか、そうでなければ言葉で説明するくらいでしょうか。(言葉での説明ならかなり書きやすいと思いますがいかがでしょうか)
回答ありがとうございます。
やはりそうですよね…
この問題がどのような解答を求めているのかいまいちわかりません(汗)
言葉なら説明できそうなので、そうしたいと思います!
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- Visual Basic(VBA) VBAで実行時エラー'424' オブジェクトが必要ですと出る 2 2022/10/07 09:25
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- JavaScript HTMLでJavaScriptを使ってパスワードの強化判定のプログラムを作成しています。 一通り作っ 2 2022/10/19 01:41
- Excel(エクセル) SUMIFのIF分岐について 4 2023/04/15 12:57
- Excel(エクセル) VBAで組み合わせ算出やCOUNTIFSの処理を高速化したいです。 4 2022/04/07 02:38
- Visual Basic(VBA) エクセルで、1つのセルで上書き足し算して セルの範囲を指定できますか? パソコン初心者です。 お時間 3 2023/07/05 06:13
- Java java 引数 戻り値のあるメソッド 3 2023/02/12 06:23
- C言語・C++・C# c言語の問題の説明、各所ごとに 5 2023/07/26 11:03
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正しい五十音順について
-
アルゴリズムとプロトコールの違い
-
Dijkstraて
-
C言語初心者の質問失礼いたしま...
-
画像から文字を認識してテキス...
-
[ EXCEL VBA ] 図形を読み込む...
-
期間重複チェックがわかりません
-
プログラミング能力とアルゴリ...
-
「FFTW」についての質問です。
-
C# 再帰よるスタックオーバー...
-
連立方程式を解く
-
タテヨコで数字の被らない二次...
-
アルゴリズムが全くわからない
-
アルゴリズム オーダー記法 定...
-
対話型遺伝的アルゴリズムにつ...
-
BCDについて
-
ランダム関数を作りたい。
-
Vba 実数および実数タイプの変...
-
0除算して、落ちるプログラムと...
-
VBAで仕様書は書きますか?
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
Dijkstraて
-
Stuck
-
[ EXCEL VBA ] 図形を読み込む...
-
BCDについて
-
アルゴリズムとプロトコールの違い
-
期間重複チェックがわかりません
-
グループを均等に分けるには?...
-
三次元形状曲面の導出法
-
あいまい検索(文字列一致率)
-
Visual studio2019 C#で生まれ...
-
gooという検索エンジンの後にGo...
-
フリーセルの難易度について
-
CRC-CCITT16の算出法
-
経路探索について
-
C♯で電卓を作成しています。演...
-
理系の高校生です。大学で情報...
-
OpenCVのライセンスについて
-
偏りのある乱数のアルゴリズム
-
詰め将棋をとくのは、アルゴリ...
おすすめ情報