はじめての C

「二分木 続き 8」

int avl_insert(struct Avl **tree, struct Avl *new_item)
{
/* empty tree */
if (*tree == NULL) {
*tree = new_item;
return 1;
}
if (compare((*tree)->data, new_item->data) > 0) {
/* Move left */
if ((*tree)->left != NULL) {
if (avl_insert(&(*tree)->left, new_item) != 0) {
/* Balancing act */
if ((*tree)->balance++ < 1)
return (*tree)->balance;
else if ((*tree)->left->balance > 0) {
/* Case 1 */
rotate_right(tree);
(*tree)->balance = 0;
(*tree)->right->balance = 0;
}
else {
/* Case 2 */
rotate_left(&(*tree)->left);
rotate_right(tree);
/* Adjust balance factors */
if ((*tree)->balance == 1) {
(*tree)->left->balance = -1;
(*tree)->right->balance = 0;
}
else if ((*tree)->balance == 0) {
(*tree)->left->balance = 0;
(*tree)->right->balance = 0;
}
else {
(*tree)->left->balance = 0;
(*tree)->right->balance = 1;
}
(*tree)->balance = 0;
}
}
else
return 0;
}
else {
(*tree)->left = new_item;
return ++(*tree)->balance;
}
}
else if (compare((*tree)->data, new_item->data) < 0) {
/* Move right */
if ((*tree)->right != NULL) {
if (avl_insert(&(*tree)->right, new_item) != 0) {
/* Balancing act */
if ((*tree)->balance++ < 1)
return (*tree)->balance;
else if ((*tree)->right->balance > 0) {
/* Case 1 */
rotate_left(tree);
(*tree)->balance = 0;
(*tree)->left->balance = 0;
}
else {
/* Case 2 */
rotate_right(&(*tree)->right);
rotate_left(tree);
/* Adjust balance factors */
if ((*tree)->balance == 1) {
(*tree)->left->balance = -1;
(*tree)->right->balance = 0;
}
else if ((*tree)->balance == 0) {
(*tree)->left->balance = 0;
(*tree)->right->balance = 0;
}
else {
(*tree)->left->balance = 0;
(*tree)->right->balance = 1;
}
(*tree)->balance = 0;
}
}
else
return 0;
}
else {
(*tree)->right = new_item;
return ++(*tree)->balance;
}
}
return 0;
}

これは ほぼ 直訳なので、もし 疑似コードが 理解できて、C の 基本のところを 精通していれば、関数を 読み解くのに 何の 問題も ないでしょう。

とても 驚くことに (私は、それが 実現したときに 本当に 驚いたのですが)、この関数では line 毎の description を 必要としません。

すでに 回転でも 検討しましたが、再帰に 通じてる人なら だれでも、この状況で 何の 問題も 起こりません。 そして コードの残りは、単に flag の 反転 - flipping - と 比較とに なります。

もし まだ 困難を かかえてるのなら、紙と 鉛筆とを 引き寄せて、壊れて ドロドロになった - crushed-pulp - とでも 呼びたい AVL木に なんらかの 値を 挿入してください。

いいかえると、書き出してみることで、そのアイデアを 掴むのです。

ちょっとした tutorial ... ですか ?

もっと 複雑な アルゴリズムの コードを 1つ 与えて、それを 自分で 計算するよう 命じることです :p

この 上級の tutorial の やり方だと、早急に 基礎を つくりあげられるので、より多くの 要点を つけ加えられることと、その後の (説明形式での) 失敗を 少なくすることが できます。

さて、考えるのですが、つりあいの とれた 木について、本や tutorial では、insertion (関数) に 対しては、動かすための (ときには 不十分な あるいは 全ケースでの) 全ての ソースコードを 含む、たっぷりの 時間と スペースとが 与えられていますね。 でも、deletion (関数) に 関しては、まったく 無視されています。

もっと 悪いと、課題だけで 止めてしまってます。

私の 判断ですが、(それらの) 筆者は、簡単な ところは 説明も せず、難しい 部分は 最小限の 説明のみで 済ませて、課題だけで 止めてしまってるのです。

それで、avl_delete (関数) についても、その 疑似コードと C の ソースとを 示すことにしましょう。

というのも、その方が、ちょっとだけでも、思いやりが あるでしょうしね :p ▽

# Returns 1 if height changes, 0 otherwise
sub avl_remove(tree, item)
  heir
  rv

  if tree == item
    # We found it, now delete it
    if tree.left == null AND tree.right == null
      # No chirdren, unlink the node
      tree = null
      return 1
    elif tree.left == null
      # Replace node with right child
      tree = tree.right
      return 1
    elif
      # Replace node with left child
      tree = tree.left
      return 1
  endif
  if tree_balance < 0
    # Find left successor
    heir = tree.left
    while heir.right != null
      heir = heir.right
  else
    # Find right successor
    heir = tree.right
    while heir.left != null
      heir = heir.left
  endif
  # Rebalance
  rv = avl_remove(tree, heir)
  # Remove node
  heir.left = tree.left
  heir.right = tree.right
  heir.balance = tree.balance
  tree = heir
  if heir.balance == 0
    return rv;
  endif
  # Search
  if tree > item
    # Move left
    if tree.left != null
      if avl_remove(tree.left, item) != 0
        if tree.balance < 1
          # Still balanced
          return tree.balance += 1
        elif tree.right.balance == 0
          rotate_left(tree)
          tree.balance = -1
          tree.left.balance = 1
        elif tree.right.balance == 1
          rotate_left(tree)
          tree.balance = 0
          tree.left.balance = 0
        else
          rotate_right(tree.right)
          rotate_left(tree)
          # Adjust balance factors
          if tree.balance == 1
            tree.left.balance = -1
            tree.right.balance = 0
          elif tree.balance == 0
            tree.left.balance = 0
            tree.right.balance = 0
          else
            tree.left.balance = 0
            tree.right.balance = 1
        endif
        tree.balance = 0
      endif
      return 1
    endif
  endif
  elif tree < item
    # Move right
    if tree.right != null
      if avl_remove(tree.right, item) != 0
        if tree.balance > -1
          # Still balanced
          return tree.balance -= 1
        elif tree.left.balance == 0
          rotate_right(tree)
          tree.balance = 1
          tree.right.balance = -1
        elif tree.left.balance == -1
          rotate_right(tree)
          tree.balance = 0
          tree.right.balance = 0
        else
          rotate_left(tree.left)
          rotate_right(tree)
          # Adjust balance factors
          if tree.balance == 1
            tree.left.balance = -1
            tree.right.balance = 0
          elif tree.balance == 0
            tree.left.balance = 0
            tree.right.balance = 0
          else
            tree.left.balance = 0
            tree.right.balance = 1
          endif
          tree.balance = 0
        endif
        return 1
      endif
    endif
  endif

  return 0
end sub

検索 (の箇所は) avl_insert (関数) で 見たところと 基本としては 同じことです。

都合の よいことに (検索のような) 考え方は 一度 理解できれば、多くの場面で 再利用が できます。

それで、たとえ コードが 長くて 複雑に 見えたとしても、その大きな部分は 理解できてきます。

もう一度 励ましますけど、どのように すべてが 動くのかが 理解できるまでは、このロジックを 紙の上に 書き出すように してください。

そのことが (例えば) ルーティンの 内側での 動きの異なった 10 の 方法を 説明しようと 試みることなんかより、ずっと より 有益でしょう。 それに、私を タイピングでの 大文字のトンネルから 救い出してくれるでしょうしね :p

書いたものを いじってみるのは 終わりましたか ?

OK、これが C に 翻訳したものです ▽