はじめての C

lang

「二分木 続き 7」

AVL とは、この algorithm を 生みだした 2人の 数学者 Adelson-Velsky と Landies の 2人を 意味しています。

基本となる 考え方は、それぞれの ノードの 左の分肢の 高さと、右の分肢の 高さを 比べて、その差が 必ず 1 以内に 収まることで、木の つりあいを とる、ということです。

この定義だと、(本来の) 最適な つりあいという 結果には なってませんが、実行上では 意外なことに なるんです。

AVL木は、それぞれの ノードが -1、0 または +1 であるという つりあい要因 - balance factor - によって、保たれています。

新しいノードが 挿入されると、挿入によって 右の分肢が +1 分 伸びるか、または 左の分肢が -1 分 小さくなり、そのため つりあい要因を 1つ もつことになり、木の 再均衡が 必要に なります。

ここで 2つのケースが 生じます (それぞれの ケースでは、左に 反映されています)(Knuth 3, 6.2.3)。

Case 1) 新しいノードが、B の 右の分肢の 高さを h から h+1 へと 伸ばす ▽


  A
 /  |
h   B
   /  |
  h  h+1

ここで 求められるのは、つりあいを 再均衡させるため、左への single 回転を 実行させることです。 注意するのは、左への回転により 高さが h+1 に なるので、他の h の 高さの 分肢を、前よりも ノード 1つ分 高い h+1 と なるよう 適応させていることです ▽


     B
   /   |
  A   h+1
 /  |
h   h

Case 2) 新しいノードが、B の 左の分肢の 高さを h から h+1 へと 伸ばす*1 ▽


      A
    /   |
   h    B
       /  |
      X   h
    /  |
  h-1   h

これは より難しいケースで、はじめに B の右、次に X の左という、double 回転が 要求されています ▽


      X
    /   |
  A      B
 / |    / |
h   h  h   h

AVL木での 挿入の 実際の algorithm は、いくつかの step に 分割する - be broken up into - ことが できます。

1) Search (検索)
-a Compare (比較)
-b Move left or move right (移動)
2) Insert (挿入)
-a Adjust balance factors (調整)
3) Replacement (取り換え)
-a Single or double routine (回転)

当然ですが、(実際の) step では 上のリストに 比べると 相当 複雑になります。

ここでは AVL Algorithm の 実行に、再帰を 使います (おそらく その効果が 認められないと 文句が でるでしょうけどね)。

いいわけを しておくと、再帰での 入力の方が、反復による挿入 - iterative insertion - よりも シンプルで 短くなるからです。

反復による 削除では、どこかに 明示的に stack を 求められます。それで、代わりに 再帰を 使えば、操作のためのコードが 簡素化されるのです。

さて、tutorial へと 戻りましょう。 この AVL 挿入ルーティンでは、次のような 疑似コードが 用いられます ▽


# Returns 1 if the changes, 0 otherwise
sub avl_insert(tree, item)
  if empty tree
    insert node
    return 1
  endif
  if tree > item
    # Move left
    if tree.left != null
      if avl_insert(tree.left, item) != 0
        if tree.balance < 1
          # Still balanced
          return tree.balance += 1
        elif 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
          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
      else
        return 0
      endif
    else
      tree.left = item
      return tree.balance += 1
    endif
  elif tree < item
    # Move right
    if tree.right != null
      if avl_insert(tree.right, item) != 0
        if tree.balance < 1
          # Still balanced
          return tree.balance += 1
        elif tree.left.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
          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
      else
        return 0
      endif
    else
      tree.left = item
      return tree.balance += 1
    endif
  endif
  return 0
end sub

このコードは 見てのとおり、helper 関数で wrap した*2 回転のコードと 同じくらい、かなり 複雑です。

その関数の 多くが、つりあい要因の 点検と 交換とに 費されています。

それで、多分 すべての点において まごつくでしょうけど、実際には 見た目よりも ずっと 簡単なんです。

先へ 進む前に、それが 納得できるまで、ロジックを 紙の上に 書きだしてみることを 勧めます。



終わりました ? OK、では 疑似コードを C に 変換する前に、役にたつものが いくつか 必要になります。

最初に、メンバとしての つりあい要因を もっている、新しい 構造体が 入用です ▽

struct Avl
{
struct Avl *left;
struct Avl *right;
int balance;
int data;
};

comparison 関数も 役にたってくれます。production code では、多分 comparison 関数を avl_insert 関数に 渡すのに ポインタが 使われるでしょう。 でも この tutorial では、関数の ポインタに 詳しくない 場合 (を考えて)、直接 呼び出すことにします ▽

int compare(int a, int b)
{
if (a < b)
return -1;
else if (a > b)
return +1;
else
return 0;
}

どちらも シンプルですので、説明の必要は ないでしょう。 もしも 説明が 必要だとすると、この tutorial を 読んでないんですね :p

次の rotation 関数には、ここでは 読みやすくするためと、Avl 構造体に 適応させるために、ほんのわずか 変更が 加えられています ▽

void rotate_left(struct Avl **subtree)
{
struct Avl *save;
struct Avl *node;

node = *subtree;
save = node->right;
node->right = save->left;
save->left = node;
*subtree = save;
}

void rotate_right(struct Avl **subtree)
{
struct Avl *save;
struct Avl *node;

node = *subtree;
save = node->left;
node->left = save->right;
save->right = node;
*subtree = save;
}

では 最後に、これ以上 めんどうなことは ありませんので、avl_insert ルーティンを C の コードへと つくり換えてみましょう ▽

*1:h-1 に 小さくするではなくて

*2:??