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

質問

二分探索木でアドレス帳を作っています。

二分探索木はノードの削除を繰り返すと退化木になってしまいますが、
これを回避するために二分探索木を再構成して、バランス木に近い形にしたいのです。

この二分探索木を再構成するアルゴリズムが全く思いつかず困っています。
詳しい方、ご教授お願い申し上げます。

ちなみに言語はCです。

回答No.4

LCR707 · ベストアンサー

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

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を追加します。
再帰呼び出しの終了条件がこれで良いかどうか、自信無しです。
文法的にもかなりいいかげんなので、処理の概念の参考程度にして下さい。

補足

ご回答ありがとうございます。
count_node関数は何の値を返す関数になるのでしょうか？

回答No.5

LCR707

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

お礼

ご回答ありがとうございました。
試してみることにします。
本当にありがとうございました。

回答No.3

lawson

2分木にこだわるなら、バランスを保った
2文探索木でAVL木という概念があります。
ノートを１つ追加した時に、AVL木が崩れた時に。
再構築処理をします。
この
「ノートを１つ追加した時に、AVL木が崩れた時に。
再構築処理をします。
」についてのアルゴリズムを探すとよいと思いますが。かなり複雑な部類にはいるのでそんなに情報もないかも。あったとしても理解できるか・・。

多分木でもよいならNo2さんの回答も参考にして、
B木という方法もあるかも。

あんまりこの手のアルゴリズムをゴリゴリと
コードで書くのは、職業ＰＧではあまりしないように
思えます。なにかの研究をするのでなければ、
STL等を学習してデータ処理周りは自分で書かないのが
理想です。

C#や、Javaにおいてもテンプレートのような
型汎用性のあるコードを書けるように進化してきているので、今後はその傾向がますます色濃くなるかも
しれないです。

お礼

ご回答頂き、ありがとうございます。

回答No.2

coredump

どもです。

「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

お礼

ご回答頂き、ありがとうございます。
ご紹介された本を買ってみることにします。

回答No.1

nofutureforyou

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

お礼

ご回答頂き、ありがとうございます。