リストと二分探索ツリー

Algorithm C

いきなり大上段に構えたような題名をつけてしまいましたが、大それたことを書こうというわけではありません。 これまでアルゴリズムの勉強において、配列のことしか考えてきませんでしたが、今回はリストやツリーについて考えてみようという、ただそれだけのことであります。

リストが配列よりも優る点としては、要素の個数があらかじめ決まっていなくても柔軟に対応することができることや、要素の挿入や削除がしやすいといったことが挙げられるようです。 ただし、要素の挿入や削除は、まずそれをおこなう場所を見つけることが必要であって、ランダムアクセスのしにくい (したがってサーチのアルゴリズムとしてはリニアサーチに頼りがちの) リストには、はたしてどれだけの優位性があるのだろうか、という疑問も残ります。 バイナリサーチのようなことを実現したいなら、リストもそれに適した構造にする必要があるでしょう。 それなら、いっそのこと、リストをやめて、二分探索ツリーにしてみたらどうでしょう。

もちろん、ただのリストと二分探索ツリーとで、それぞれを生成するコストに大きな差があるようであれば、それはそれでまた考えなければなりません。

というわけで、リストと二分探索ツリーの比較をおこなってみたいと思います。

リスト

簡単なテストのため、昇順にソートされたリストを生成するコードを書いてみます。

typedef struct ListNode {
  int value;
  struct ListNode *next;
} ListNode;

typedef struct {
  ListNode *first;
} List;

void addToList(List *list, ListNode *node) {
  if (list->first == NULL) {
    list->first = node;
    return;
  }
  if (list->first->value > node->value) {
    node->next = list->first;
    list->first = node;
    return;
  }
  ListNode *x;
  x = list->first;
  while (1) {
    if (x->next == NULL) {
      x->next = node;
      return;
    }
    if (x->next->value > node->value) {
      node->next = x->next;
      x->next = node;
      return;
    }
    x = x->next;
  }
}

typedef の使い方がこれでいいのかどうか、ちょっと自信がありません。 また、while ループの条件式に 1 と書くのは、何となく気味が悪いのですが、C 言語の流儀では一般的に真の値をどう書くのか、わたしはまだ知らないので、とりあえず上記のように書いてみました。

二分探索ツリー

つづいて、簡単なテストのため、二分探索ツリーを生成するコードを書いてみます。

typedef struct TreeNode {
  int value;
  struct TreeNode *left;
  struct TreeNode *right;
} TreeNode;

typedef struct {
  TreeNode *root;
} Tree;

void addToTree(Tree *tree, TreeNode *node) {
  if (tree->root == NULL) {
    tree->root = node;
    return;
  }
  TreeNode *x;
  x = tree->root;
  while (1) {
    if (x->value > node->value)
      if (x->left == NULL) {
        x->left = node;
        return;
      } else
        x = x->left;
    else
      if (x->right == NULL) {
        x->right = node;
        return;
      } else
        x = x->right;
  }
}

typedef の使い方や while ループでの条件式のあり方などは、リストの場合と同様に自信がありませんが、とりあえず先に進みます。

処理速度の比較

ランダムに 50,000 個のデータを用意し、それをリストと二分探索ツリーの双方にどんどん挿入していくテストをおこなってみたいと思います。

テストコードは、たとえば、次のようになりましょうか。 (宣言部分など一部省略しています。)

#define N 50000

int main(void) {
  
  int i, j, data[N];
  clock_t t0, t1;
  
  srand((unsigned int)time(NULL));
  
  for (i = 0; i < 10; i++) {
    
    printf("[%d] ", i);
    
    for (j = 0; j < N; j++)
      data[j] = rand() % N;
    
    List *list;
    list = (List *)calloc(1, sizeof(List));
    t0 = clock();
    for (j = 0; j < N; j++) {
      ListNode *node;
      node = (ListNode *)calloc(1, sizeof(ListNode));
      node->value = data[j];
      addToList(list, node);
    }
    t1 = clock();
    printf("addToList=%u, ", t1 - t0);
    
    Tree *tree;
    tree = (Tree *)calloc(1, sizeof(Tree));
    t0 = clock();
    for (j = 0; j < N; j++) {
      TreeNode *node;
      node = (TreeNode *)calloc(1, sizeof(TreeNode));
      node->value = data[j];
      addToTree(tree, node);
    }
    t1 = clock();
    printf("addToTree=%u\n", t1 - t0);
    
  }
  
  return EXIT_SUCCESS;
  
}

リストに対しては、要素をひとつ追加するたびに、リストが昇順に並ぶようにしています。 また、あとから追加する要素と同じ値をもつ要素がすでに存在する場合は、そのすぐうしろに追加するようにしています。 (安定ソート的なものを意識しています。)

二分探索ツリーに対しては、その定義に鑑みて、親要素よりも値の小さい要素は左側の子要素 (もしくはその子孫要素) とし、そうでない要素は右側の子要素 (もしくはその子孫要素) とします。 親要素と同じ値をもつ場合は、右側にします。 (ここでも安定ソート的なものを意識しています。)

で、このテストコードをコンパイルして実行してみたところ、次のような結果を得ました。

[0] addToList=5417, addToTree=17
[1] addToList=5327, addToTree=20
[2] addToList=5290, addToTree=15
[3] addToList=5298, addToTree=18
[4] addToList=5224, addToTree=18
[5] addToList=5245, addToTree=18
[6] addToList=5278, addToTree=17
[7] addToList=5260, addToTree=17
[8] addToList=5257, addToTree=17
[9] addToList=5260, addToTree=15

どう考えるか

正直なところ、これほど差が開くとは思っていませんでした。 32-bit マシンにおいて、ひとつひとつの要素のサイズは、リストの場合は 8 バイト、二分探索ツリーの場合は 12 バイトとなります。 つまり、メモリ消費量は、2 対 3 の比率になると考えていいでしょう。 それに対して、処理速度を比べると、2 桁以上の大変な差がついてしまいました。

ここからは推測になりますが、特定の要素を探索する場合は、リニアサーチしか使えないリストよりも、バイナリサーチ的なサーチが使える二分探索ツリーのほうが効率はいい (処理は速い) はずでしょうから、こうなると、問答無用で、単純なリストを考えるくらいなら二分探索ツリーを考えたほうがずっといいんじゃないか、という気がしてきます。

もしかしたら、何か大事なことを見落としているのかもしれません。 しかし、残念ながら、いまのわたしには、具体的に何を見落としているのか、まだ見当もつきません。

まとめ

二分探索ツリーが単純なリストに比べて効率がいいと言えるためには、二分探索ツリーが適度に左右にバランスしていることが大事です。 すべて左側もしくは右側にだけ要素がずらずらと数珠つなぎに並ぶと、それは単純なツリーと変わらなくなるからです。

適度に左右にバランスしている状態の理想形は、「平衡木 (balanced tree)」 と呼ばれるのだそうです。 実は、データ構造とアルゴリズムに関してはじめて買って読んだ本 Java データ構造とアルゴリズム基礎講座 (長尾和彦著, 技術評論社, 2009 年, ISBN978-4-7741-3697-4) では、二分探索ツリーがどういう構造になっていれば最も効率がよいのかという点について、何ら言及がありませんでした。 その後、たまたま目にした id:bleis-tift さんの記事 Java データ構造とアルゴリズム基礎講座 (July 2, 2009) に 「平衡木に触れられてもいないのはちょっと・・・」 と書かれているのを見つけて、はじめて平衡木という用語を知りました。 そして、その直後に、これもたまたま、本屋で見かけた プログラミングの宝箱 アルゴリズムとデータ構造 第2版 (紀平拓男・春日伸弥著, ソフトバンククリエイティブ, 2011 年, ISBN978-4-7973-6328-9) という本の pp.190-199 に平衡木に関する解説が載っているのを見つけました。 いま愛読している紀平さん・春日さんの本を買って読むことになったもともとのきっかけは、そんなところだったのでありました。

さて、今回掲載した二分探索ツリーの生成コードでは、単純なリストと同じ形になることが稀なら、完璧な平衡木の形になることも稀だと思います。 だとすると、一般的に、ある二分探索ツリーの 「平衡木らしさ」 のようなものを示す指標として、どのようなものがあるでしょうか。 また、どのような確率で、どの程度の 「平衡木らしさ」 になるものでしょうか。 そんなことを考えてみるために、まずすべてのありうるパターンを用意するところからはじめてみようか、と思い立ったのが、もう半月も前に 順列を列挙する (Nov 15, 2011) という記事を書くことになったきっかけでした。 いまとなっては、そんな愚直なことをするより、もう少しエレガントでスマートな調べ方はないものかなあ、などとないものねだりをするにとどまっていますが。

とりあえず、平衡木については、また機会があれば、ゆっくり考え直してみたいと思います。