第54回 プログラミングについて『２分木を考える』
プログラミングの本を読んでいると、２分木という文字に出くわすことがあります。これは以前にソートのお話をしたときのヒープ木に似ているのですが、どのように並ぶかが違っていて次の図のようになります。
５
┌──┴──┐
３ ７
┌─┴─┐ ┌─┴─┐
１ ４ ６ ８
┌--┴─┐ ┌--┴─┐
２ ９
木の親より小さいものを左側の子に、以上のものを右側の子にした木構造になるものです。ということは、木の最も左側のものが最小で、最も右側のものが最大の値になるということです。
５３７１４６８２９の順で木を成長させても、５７８３９１４２６の順で木を成長させても上の図のようになります。もう少し理解を深めるために、この木の成長の様子を見てみましょう。
いま５７８３９１４２６の順で木を成長させるとします。
最初の５のときには木には何もありませんので、この値が木の根になります。
５
次に７は５以上なので、
５
┌──┴──┐
７
８は５以上、７以上なので、
５
┌──┴──┐
７
┌─┴─┐
８
３は５未満なので、
５
┌──┴──┐
３ ７
┌─┴─┐
８
９は５以上、７以上、８以上なので、
５
┌──┴──┐
３ ７
┌─┴─┐
８
┌─┴─┐
９
１は５未満、３未満なので、
５
┌──┴──┐
３ ７
┌─┴─┐ ┌─┴─┐
１ ８
┌─┴─┐
９
４は５未満、３以上なので、
５
┌──┴──┐
３ ７
┌─┴─┐ ┌─┴─┐
１ ４ ８
┌─┴─┐
９
２は５未満、３未満で２以上なので、
５
┌──┴──┐
３ ７
┌─┴─┐ ┌─┴─┐
１ ４ ８
┌─┴─┐ ┌─┴─┐
２ ９
最後に６は、５以上、７未満なので、
５
┌──┴──┐
３ ７
┌─┴─┐ ┌─┴─┐
１ ４ ６ ８
┌─┴─┐ ┌─┴─┐
２ ９
というようになります。
これをプログラムにしてみましょう。
#include <stdio.h>
#include <malloc.h>
#define NEW(type,element) (type *)malloc(sizeof(type)*(element))
struct tree_strct{
int value;
struct tree_strct *left,*right;
};
struct tree_strct *tree_root=NULL;
void add_tree();
struct tree_strct *add_node();
main()
{
int i;
while(1){
scanf("%d",&i);
add_tree(tree_root,i);
display_tree(tree_root,0);
}
}
struct tree_strct *add_node(i)
int i;
{
struct tree_strct *tree;
tree=NEW(struct tree_strct,1);
tree->value=i;
tree->left =NULL;
tree->right=NULL;
return tree;
}
void add_tree(tree,i)
struct tree_strct *tree;
int i;
{
if(tree==NULL){
tree_root=add_node(i);
}
else if(i<tree->value){
if(tree->left==NULL)tree->left=add_node(i);
else add_tree(tree->left,i);
}
else{
if(tree->right==NULL)tree->right=add_node(i);
else add_tree(tree->right,i);
}
}
display_tree(tree,depth)
struct tree_strct *tree;
int depth;
{
int i;
if(tree->right)display_tree(tree->right,depth+1);
for(i=0;i<depth*2;i++)putchar(' ');
printf("%d\n",tree->value);
if(tree->left )display_tree(tree->left ,depth+1);
}
２分木の例としては多分ありふれたものだと思います。この例のように２分木は再帰的に処理するとプログラムをスッキリ記述することができます。このプログラムで上の例と同じことを行なうと、
9
8
7
6
5
4
3
2
1
と表示されます。
２分木が上のようになっているとき、４があるかないかを検索するには、最初に５と比較し、４は５未満なので次に３と比較し、４は３以上なので４に辿り着くことができます。もし、このように２分木が綺麗な木になっているときには、要素の数が１万個のときでも、深さが１２程度になるので１２回の比較で検索できることになります。
ところが、あくまでもこれは木が理想的なときのことです。もし、木を成長させるときに１２３４５６７８９の順で成長させると、
9
8
7
6
5
4
3
2
1
となり、２分木ではなく単なるリストになってしまうのです。これでは１万個の要素の検索に最大で１万回の比較を行なわなければなりません。
そこで、あくまでもこの２分木に執着することにして、まず上のプログラムに１つの木の葉の深さを表示するように変更します。例えば、
５
┌──┴──┐
３ ７
┌─┴─┐ ┌─┴─┐
１ ４ ６ ８
┌--┴─┐ ┌--┴─┐
２ ９
のときには、
9(0,0)
8(0,1)
7(1,2)
6(0,0)
5(3,3)
4(0,0)
3(2,1)
2(0,0)
1(0,1)
のように表示されるようにします。カッコの中の左側の数がその木の左側の深さの最大数、右側が同じく右側の深さの最大数を表示します。
#include <stdio.h>
#include <malloc.h>
#define NEW(type,element) (type *)malloc(sizeof(type)*(element))
struct tree_strct{
int value;
struct tree_strct *left,*right;
char ldepth,rdepth; /* 深さを保持するメンバーを追加 */
};
struct tree_strct *tree_root=NULL;
void add_tree();
void set_depth();
struct tree_strct *add_node();
main()
{
int i;
while(1){
scanf("%d",&i);
add_tree(tree_root,i);
display_tree(tree_root,0);
}
}
struct tree_strct *add_node(i)
int i;
{
struct tree_strct *tree;
tree=NEW(struct tree_strct,1);
tree->value =i;
tree->left =NULL;
tree->right =NULL;
tree->ldepth=0; /* 新しいノードの深さは左右とも０ */
tree->rdepth=0;
return tree;
}
display_tree(tree,depth)
struct tree_strct *tree;
int depth;
{
int i;
if(tree->right)display_tree(tree->right,depth+1);
for(i=0;i<depth*2;i++)putchar(' ');
/* 左右の深さの表示を追加 */
printf("%d(%d,%d)\n",tree->value,tree->ldepth,tree->rdepth);
if(tree->left )display_tree(tree->left,depth+1);
}
/* 左右の深さを設定する関数 */
void set_depth(tree)
struct tree_strct *tree;
{
if(tree->left){ /* 左側に子があるときには、
子の左右の深さの最大値＋１を設定 */
tree->ldepth=(tree->left->ldepth > tree->left->rdepth ?
tree->left->ldepth : tree->left->rdepth )+1;
}
else{ /* 左側に子がないときには深さは０ */
tree->ldepth=0;
}
if(tree->right){ /* 右側に子があるときには、
子の左右の深さの最大値＋１を設定 */
tree->rdepth=(tree->right->ldepth > tree->right->rdepth ?
tree->right->ldepth : tree->right->rdepth )+1;
}
else{ /* 右側に子がないときには深さは０ */
tree->rdepth=0;
}
}
void add_tree(tree,i)
struct tree_strct *tree;
int i;
{
if(tree==NULL){
tree_root=add_node(i);
return;
}
if(i<tree->value){
if(tree->left==NULL)tree->left=add_node(i);
else add_tree(tree->left,i);
}
else{
if(tree->right==NULL)tree->right=add_node(i);
else add_tree(tree->right,i);
}
set_depth(tree); /* ノードを追加した後に深さを設定 */
}
ちょっと長くなってしまいましたが、基本的な変更は、構造体 tree_strct に左側と右側の深さの最大値のメンバーを追加し、ノードを追加するたびにその深さを設定するようにしています。またこの深さを保持する ldepth と rdepth メンバーは char 型になっていますが、以後に加える変更の含みがあるためなので上のプログラムでは深さが１２７までしか正常に動作しないので注意して下さい。
このプログラムを実行してみましょう。まず１２３を順に入力すると、
3(0,0)
2(0,1)
1(0,2)
となります。次に１３２の順では、
3(1,0)
2(0,0)
1(0,2)
となります。５４６７８では、
8(0,0)
7(0,1)
6(0,2)
5(1,3)
4(0,0)
となります。この結果を見てみると、左と右の深さの差が２以上になったときには木の左右のバランスが悪くなっているのが分かると思います。ということはどの節でも左右の深さの差が１以下になるようにできれば木のバランスが最高に良くなるということになります。
まず、１２３の順で木が成長した場合を考えましょう。
１(0,2)
┌─┴─┐
２(0,1)
┌─┴─┐
３(0,0)
このときには、１の左右の深さの差が２になりますので、
２(1,1)
┌─┴─┐
１(0,0) ３(0,0)
というようになれば深さの差は１以下（この場合は０）になります。１３２の順で成長したときには、
１(0,2)
┌─┴─┐
３(1,0)
┌─┴─┐
２(0,0)
のときにも、
２(1,1)
┌─┴─┐
１(0,0) ３(0,0)
となればいいということになります。
もう少し詳しく考えてみましょう。木が成長してしていく過程で、１２３の順で木が成長したときに木が次のようになったとします。このときのＡＢＣＤは既に木に加えられているとします。
１(n,n+2)
┌─┴─┐
Ａ ２(n,n+1)
┌─┴─┐
Ｂ ３(n,n)
┌┴┐
Ｃ Ｄ
このときには、
２
┌─┴─┐
１ ３
┌┴┐ ┌┴┐
Ａ Ｂ Ｃ Ｄ
となれば良い訳です。３の下のＣとＤはそのまま３にぶら下がり、１の左側のＡもそのまま１にぶら下がります。Ｂは２の左側ですが、２の左側に１をぶら下げるので、Ｂは必ず１よりも大きいことから１の右側にぶら下げます。
成長の過程で１３２と成長したときには、
１(n,n+2)
┌─┴─┐
Ａ ３(n,n+1)
┌─┴─┐
２(n,n) Ｂ
┌┴┐
Ｃ Ｄ
次のようになれば良い訳です。
２
┌─┴─┐
１ ３
┌┴┐ ┌┴┐
Ａ Ｃ Ｄ Ｂ
即ち、１の左側のＡはそのまま１にぶら下がり、３の右側のＢもそのままＢにぶら下がります。２の左のＣは、２に左に１をぶら下げるので、１の右側にぶら下げます。また２の右側のＤは２の右側に３をぶら下げるので３の左にぶら下げます。
このように木の成長過程で木をバランスのとれたものにしていけば常に木全体が理想的なものになる訳です。
この機能を上のプログラムに追加してみましょう。まず add_tree 関数の set_depth関数を呼び出した後に,
rehash_tree(tree);
を追加します。この rehash_tree 関数は、
void rehash_tree(tree)
struct tree_strct *tree;
{
struct tree_strct tt,*tl,*tr,*tlr,*trl;
int diff;
diff=tree->ldepth - tree->rdepth;
if(diff==2){
tl=tree->left;
diff=tl->ldepth - tl->rdepth;
if(diff==1){
tt = *tree;
*tree= *tl;
*tl = tt;
tl->left =tree->right;
tree->right=tl;
}
else{
tlr=tl->right;
tt = *tree;
*tree= *tlr;
*tlr = tt;
tlr->left =tree->right;
tree->right=tlr;
tl->right=tree->left;
tree->left =tl;
set_depth(tlr);
}
set_depth(tl);
}
else if(diff== -2){
tr=tree->right;
diff=tr->ldepth - tr->rdepth;
if(diff== -1){
tt = *tree;
*tree= *tr;
*tr = tt;
tr->right=tree->left;
tree->left =tr;
}
else{
trl=tr->left;
tt = *tree;
*tree= *trl;
*trl = tt;
trl->right=tree->left;
tree->left =trl;
tr->left =tree->right;
tree->right=tr;
set_depth(trl);
}
set_depth(tr);
}
else{
return;
}
set_depth(tree);
}
この関数も長くなってしまいましたが、上で考えた方法をそのままプログラムにしてあります。
このプログラムを１から順に１０まで数値を入力して木の成長を見てみましょう。
１
1(0,0)
----------
２
2(0,0)
1(0,1)
----------
３
3(0,0)
2(1,1)
1(0,0)
----------
４
4(0,0)
3(0,1)
2(1,2)
1(0,0)
----------
５
5(0,0)
4(1,1)
3(0,0)
2(1,2)
1(0,0)
----------
６
6(0,0)
5(0,1)
4(2,2)
3(0,0)
2(1,1)
1(0,0)
----------
７
7(0,0)
6(1,1)
5(0,0)
4(2,2)
3(0,0)
2(1,1)
1(0,0)
----------
８
8(0,0)
7(0,1)
6(1,2)
5(0,0)
4(2,3)
3(0,0)
2(1,1)
1(0,0)
----------
９
9(0,0)
8(1,1)
7(0,0)
6(1,2)
5(0,0)
4(2,3)
3(0,0)
2(1,1)
1(0,0)
----------
１０
10(0,0)
9(0,1)
8(2,2)
7(0,0)
6(1,1)
5(0,0)
4(2,3)
3(0,0)
2(1,1)
1(0,0)
細かい説明はしませんが、木が理想的にバランスを保って成長しているのが分かると思います。また理想的に木が成長しているということは、 tree_strct 構造体の深さを保持する変数
ldepth と rdepth は要素数が１万個でも深さがたかだか１３ですので、実用上１２７も表現できれば十分ということになります。
さて、気になるのは１つのノードの追加で木の整形がどれくらいの回数になるのかということですが、いろいろと実験してみたところ最大でも１にしかなりませんでした。実験したデータが悪いのかも知れませんが、これを証明するだけの時間がありませんので、この実験値を基にすると無駄な動作を殆どせずに理想的な２分木を生成することが可能であるということになります。
今回は２分木に執着して考えてみましたが、ひも付き２分木やＢ木などいろいろと工夫されたものがありますので、そちらのほうも参考にして下さい。
ではまた次回。
