平衡二分木を実装する（C言語）

前回は二分木を実装してみました。二分木は、要素の探索が線形探索よりも早くなる可能性があります。ノードが左右に分散していればいいのですが、



ノードの挿入の順番によっては、偏った二分木になってしまい、線形探索と同じ時間が係ってしまいます。



平衡二分木は、ノードの挿入、削除のときに、左右のノードが平衡するように調整します。この平衡二分木の一つであるAVL木を実装してみます。

AVL木

AVL木は、「各ノードの左右の部分木の高さの差が1以下」という条件を満たす。ノードの挿入や削除は二分木の挿入、削除と同じ操作を行い、その後に、ノードの左右部分木の高さを調べて、高さの差が2以上となっていた場合はノードの部分木の高さを調整する、という操作を追加する。

データ構造

各ノード(節点）は、要素の値と子のノードへのポインタに加え、そのノードの高さを持つ。ノードの高さとは、そのノードから末端ノードまでのノードの数の最大値である。

typedef struct Node {
  int item;
  int hight;
  struct Node* lr[2];
} NODE;

ノードの作成

新しいノードを作成し、作成したノードのポインタを戻り値として返す。新しく作成したノードは末端のノードなので、このノードの高さは1である。

NODE* node_create(int x) {
  NODE *node = malloc(sizeof(NODE));
  node->item = x;
  node->hight = 1;
  node->lr[0] = NULL;
  node->lr[1] = NULL;
  return node;
}

ノードの高さ

そのノードの高さは、左右の部分木の高さの高い方に+1をして得られる。ただし、部分木がNULLの場合はその部分木の高さは0である。

int node_hight_calc(NODE *node) {
  if (node == NULL) {
    return 0;
  }
  int left = (node->lr[0] == NULL) ? 0 : node->lr[0]->hight;
  int right = (node->lr[1] == NULL) ? 0 : node->lr[1]->hight;
  int hight = (left > right) ? left : right;
  return hight + 1;
}

ノードの回転

左右の部分木の高さの差が2以上の場合、ノードを回転させることで、部分木の高さの差を解消する。左回転は、右側の子ノードを今のノードの場所に移動してきて、今のノードが左側の子ノードの位置に移動する。このとき、右側の子ノードの左側の子ノードは、今のノードの右側の子ノードになる。



右回転では、逆に、左側の子ノードが今のノードの場所に移動してきて、今のノードが右側の子ノートの位置に移動する。



その結果、回転後のノードの左右の部分木の高さのバランスが変わる。

実装している操作（左回転の場合）は、次の図のようになっている。

NODE *node_rotate(NODE *node, int rotDir) {
  int invDir = (rotDir == 0) ? 1 : 0;
  if (node->lr[invDir] == NULL) {
    return node;
  }
  NODE *rotNod = node->lr[invDir];    /* node to be rotated to x */
  node->lr[invDir] = node->lr[invDir]->lr[rotDir];
  node->hight = node_hight_calc(node);
  rotNod->lr[rotDir] = node;
  rotNod->hight = node_hight_calc(rotNod);
  return rotNod;
}

左右部分木の高さの差の調整

ノードの回転ができるようになったので、左右部分木の高さの差を求めて、差が2以上の場合にノードを回転させて部分木の高さの差を解消する。



ただし、左右部分木の機構造によっては、回転後も左右部分木の高さの差を解消できない場合がある。



例えば、ノードを右回転させた場合を考える。元のノードの左側子ノードの右側部分木が、右側に移動したノードの左側部分木になるので、この左側から右側に移動した部分木の高さが高いことが問題であることが分かる。そこで、右回転させる前に、この高さが高い部分木を左回転させておく。こうしておくと、右回転させることで左右部分木の高さの差が解消できる。

NODE *node_balance(NODE *node) {
  int left = (node->lr[0] == NULL) ? 0 : node->lr[0]->hight;
  int right = (node->lr[1] == NULL) ? 0 : node->lr[1]->hight;
  if (abs(left - right) > 1) {
    int rotDir = (left < right) ? 0 : 1;
    int invDir = (rotDir == 0) ? 1 : 0;
    NODE *child = node->lr[invDir];
    int dir1 = (child->lr[rotDir] == NULL) ? 0 : child->lr[rotDir]->hight;
    int dir2 = (child->lr[invDir] == NULL) ? 0 : child->lr[invDir]->hight;
    if (dir1 > dir2) {
      child = node_rotate(child, invDir);
    }
    node = node_rotate(node, rotDir);
  }
  return node;
}

ノードの挿入

ノードの挿入は、単純二分木と同じ操作を行った後、追加したノードの親ノードの左右部分技の高さの差を調整する。

NODE *node_insert(NODE *node, int x) {
  if (node == NULL) {
    return node_create(x);
  }
  int lr = (x < node->item) ? 0 : 1;
  node->lr[lr] = node_insert(node->lr[lr], x);
  node->hight = node_hight_calc(node);
  node = node_balance(node);
  return node;
}

ノードの削除

ノードの削除は、単純二分木と同じ操作でノードの削除を行った後、削除したノードの親ノードの左右部分技の高さの差を調整する。

NODE *node_remove(NODE *node, int x) {
  if (node == NULL) {
    return NULL;
  }
  if (x - node->item == 0) {             /* if item found */
    if (node->lr[0] == NULL || node->lr[1] == NULL) {
      int lr = (node->lr[0] != NULL) ? 0 : 1;
      NODE *res = node->lr[lr];          /* connect existing node */
      free(node);
      return res;
    }
    NODE *dst = node->lr[0];             /* find max item node in left */
    while (dst->lr[1] != NULL) {
      dst = dst->lr[1];
    }
    node->item = dst->item;              /* copy max item to node */
    node->lr[0] = node_remove(node->lr[0], dst->item);
    node = node_balance(node);
    return node;
  }
  int lr = (x - node->item < 0) ? 0 : 1;
  node->lr[lr] = node_remove(node->lr[lr], x);     /* search item */
  return node;
}

その他

その他は、単純二分木と同じ操作でよい。