退化木をバランス木にしたい

Question

二分探索木でアドレス帳を作っています。

二分探索木はノードの削除を繰り返すと退化木になってしまいますが、
これを回避するために二分探索木を再構成して、バランス木に近い形にしたいのです。

この二分探索木を再構成するアルゴリズムが全く思いつかず困っています。
詳しい方、ご教授お願い申し上げます。

ちなみに言語はCです。

LCR707 · Accepted Answer

ずっと以前に作ったことがあるので、うろ覚えですが・・・。

balance(node)
{
　　if (node == NULL) break;
　　nl = count_node(node.left);
　　nr = count_node(node.right);
　　while (abs(nl - nr) > 1) {
　　　　if (nl > nr+1) {
　　　　　　data = get_max_node(node.left);
　　　　　　append_node(node.right,data);
　　　　} else if (nr > nl+1) {
　　　　　　data =get_min_node(node.right);
　　　　　　append_node(node.left,data);
　　　　}
　　　　nl = count_node(node.left);
　　　　nr = count_node(node.right);
　　}
　　balance(node.left);
　　balance(node.right);
}

木のrootに対して、balance(root)を行います。
get_max_node(node)は、node以降の枝から最大のdataを削除し、そのdataを返します。
append_node(node,data)は、node以降の木にdataを追加します。
再帰呼び出しの終了条件がこれで良いかどうか、自信無しです。
文法的にもかなりいいかげんなので、処理の概念の参考程度にして下さい。

LCR707 · Answer

#4です。
count_node(node)は、nodeを含み、その枝側のnodeの個数を返します。

lawson · Answer

2分木にこだわるなら、バランスを保った
2文探索木でAVL木という概念があります。
ノートを１つ追加した時に、AVL木が崩れた時に。
再構築処理をします。
この
「ノートを１つ追加した時に、AVL木が崩れた時に。
再構築処理をします。
」についてのアルゴリズムを探すとよいと思いますが。かなり複雑な部類にはいるのでそんなに情報もないかも。あったとしても理解できるか・・。

多分木でもよいならNo2さんの回答も参考にして、
B木という方法もあるかも。

あんまりこの手のアルゴリズムをゴリゴリと
コードで書くのは、職業ＰＧではあまりしないように
思えます。なにかの研究をするのでなければ、
STL等を学習してデータ処理周りは自分で書かないのが
理想です。

C#や、Javaにおいてもテンプレートのような
型汎用性のあるコードを書けるように進化してきているので、今後はその傾向がますます色濃くなるかも
しれないです。

coredump · Answer

どもです。

「C―データ構造とプログラム」という本に、
(1) データが昇順で与えられる
(2) データの数が予めわかっている
を条件に、完全にバランスした2分木を構築する方法が載っています。
なので、そのアプリの起動時等に完全にバランスした2分木にするとかで良いのではないでしょうか。

ちなみにこの本にはB木の構築方法も載っているので、B木にしてしまった方が良いかもしれません。

ではでは。

参考URL：http://www.amazon.co.jp/exec/obidos/ASIN/4274075524/qid=1135822753/sr=8-6/ref=sr_8_xs_ap_i6_xgl14/249-1799612-0369100

nofutureforyou · Answer

データを全部読み出すついでに乱数を付加してそれでソートしてデータを書き戻すというのはどうでしょう？

退化木をバランス木にしたい

ずっと以前に作ったことがあるので、うろ覚えですが・・・。

この回答への補足

#4です。

2分木にこだわるなら、バランスを保った

どもです。

データを全部読み出すついでに乱数を付加してそれでソートしてデータを書き戻すというのはどうでしょう？

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

　ずっと以前に作ったことがあるので、うろ覚えですが・・・。