- 締切済み
探索二分木をバランス化する。
書き込みや削除を繰り返して深さに差の出た探索二分木をバランス化する手続きを作りたいのですが、どのようなアルゴリズムで組めばよいでしょうか。 使用言語はPascalです。 よろしくお願いします。
- pwpr
- お礼率25% (11/44)
- その他(プログラミング・開発)
- 回答数3
- ありがとう数1
- みんなの回答 (3)
- 専門家の回答
みんなの回答
- chie65536
- ベストアンサー率41% (2512/6032)
>親の入れ替えを行う際枝の分かれ方によって入れ替え方が4パターンあると思うのですが、それは全て場合分けして書くのでしょうか。 場合分けは 右にズラしてバランスするか左にズラしてバランスするか、で2パターン 親から見て、ズラすノードが右腕にあるか左腕にあるか、で2パターン になります。 これら2つの処理をいっぺんに書けば、2パターン×2パターンで4パターンになりますが、別々に書けば4パターンも要りません。
- chie65536
- ベストアンサー率41% (2512/6032)
>書き込みや削除を繰り返して深さに差の出た探索二分木をバランス化する手続きを作りたい う~む。普通は「削除を終えた直後」「挿入を終えた直後」に「バランス化を行う」のですが。 因みに「更新(書き込み)」は「更新前データを削除して、更新データを挿入する」と言う手続きで可能です。 で、バランスを取る際は各ノードの「右腕の長さ」と「左腕の長さ」を調べる必要があります。 根 / A / \ B C / D の状態でCを削除すると 根 / A / B / D となり「Aの左腕は長さ2、右腕は長さ0」になります。 ここで「左右の長さの差が2以上になっていたら」 根 / B / \ D A のように、親の入れ替えを行います。 これを「変化(挿入か削除)があったノードの親からスタートして、根に辿り付くまで」繰り返します。 なお「ある時点で一気にバランス化する」のであれば「最小値のノードから、最大値のノードまでを順に、各ノードすべてにおいて、上記の腕の長さのチェックと入れ替え」が必要になります。
- sakusaker7
- ベストアンサー率62% (800/1280)
とりあえず「赤黒木」(red-black tree)とか 「AVL木」(AVL tree)というキーワードで検索してみて、 見つかった説明でわからなかったらどのあたりがわからないのかを 具体的に書いてみてください。
関連するQ&A
- 退化木をバランス木にしたい
二分探索木でアドレス帳を作っています。 二分探索木はノードの削除を繰り返すと退化木になってしまいますが、 これを回避するために二分探索木を再構成して、バランス木に近い形にしたいのです。 この二分探索木を再構成するアルゴリズムが全く思いつかず困っています。 詳しい方、ご教授お願い申し上げます。 ちなみに言語はCです。
- ベストアンサー
- C・C++・C#
- 二分探索木を用いての探索
C言語でプログラミングしています。 二分探索木を用いて探索するプログラムなのですが 与えられた値の前後の値(与えられた値より大きく(小さく)てその値 に一番近いもの)を見つけたいのですが分かりません。 いろいろとネット等で調べてみると「挿入してその左右を見る」 となっているのですが…。 普通の二分探索木ではだめなのでしょうか? よろしくお願いします。
- 締切済み
- C・C++・C#
- 二分探索木と二分探索の違い
高校のときにCOBOLを用いた二分探索を習いました。 今大学でコンピューター科学を勉強しています。予習をしていたら二分探索木が出てきました。 添付画像のような二分木があるとき、a~jの各ノードに1~10の整数のどの整数が入るか。 という問題ですが、ちんぷんかんぷんです。 二分探索木というのは、検索で用いる二分探索と同じ考えなのでしょうか。 もし、同じなら、1~10の中央値の5がルートになりますよね。 このような問題の簡単な求め方があれば教えてください。お願いいたします。
- ベストアンサー
- その他([技術者向] コンピューター)
- 二分探索は木のように例えられる?
二分探索は、「半分にして対象外の値を除去しながら探索する」ということですが、分かりやすい例えで言うと、木の枝が伸びるような感じで探索する感じでしょうか? 回答のほうよろしくお願いいたします。
- ベストアンサー
- その他(プログラミング・開発)
- アルゴリズム(2分探索木)の問題について
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)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、 参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。 長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。
- ベストアンサー
- その他(プログラミング・開発)
- 二分探索木のheight(高さ?)を見つけるアルゴリズム
Binary Search Tree(=二分探索木)のheight(高さ?)を見つけるメソッドを作りたいのですが、 そのアルゴリズムが頭にうまく浮かびません。 まず思いついたのは一つ一つのNode(=ノード)をそれぞれのLeaf(=リーフ、葉?)まで辿っていって それらのheightを全部記憶させておいて後で比較するという…最も原始的な方法です。 しかし、Treeの大きさも未知なので用意する変数の数も未知になって どう考えても不適当でしょう(当たり前か(^^ゞ)。 Recursion(=再帰)を使えばいいのでしょうか? そうだとしてもどうすればいいのか…。 アルゴリズムがパッと浮かぶ方、どうか教えて下さい。
- ベストアンサー
- Java
- 二分探索木の行きがけ順走査
二分探索木の行きがけ順走査は、普通再起を使うと思います。 再起を使わず、しかも木以外のデータ構造を一切使わないでやることもできる聞いたのですが、具体的にはどうすればいいのでしょう。 木以外に何か使ってもいいのなら、 http://www.psg.cs.titech.ac.jp/pro1/11.pdf の『再起を使わないアルゴリズム』みたいにすれば良いことは調べてわかりました。 再起も使わないで出来るのであれば、自分でもJavaを使って書いてみようかと思っているのでカテゴリはJavaにしました。よろしくお願いします。
- ベストアンサー
- Java
お礼
返事遅くなりました。 わかりやすい説明ありがとうございます。 重ねて質問なのですが、親の入れ替えを行う際枝の分かれ方によって入れ替え方が4パターンあると思うのですが、それは全て場合分けして書くのでしょうか。