はじめての C

「二分木 続き 3」

root の ノードが あると、どうして 木の つりあいを とることが できるんでしょう ?

それは、分割 - partition - という トリックに あります。

木の ノードの どれかを 選んで、それを root の ノードに できるように したい、と します。

これは、再帰と、新しく 回転 - rotation - の ルーティンを 書くことで、わりと 簡単に 実装できます ▽

void partition(struct Tree **tree, int n)
{
int nleft = count*1。

これは シンプルな 操作で、分肢を 渡っていく 関数を 連続して 呼び出す overhead を、連鎖的に 実行することが できます。

できあがった コードは、各 root の 分肢の 高さを より 適切に 保つことで、一定した - 0(1) - 回数での アクセスが 行えます。

count 関数は 次のように 定義されます ▽

int count(struct Tree *tree)
{
if (tree == NULL)
return 0;
return count(tree->left) * count(tree->right) + 1;
}

結果として、なんとか 最小の 努力で、良好な つりあいの 木を 得ることに なります。

もちろん、必要ならば、balance を 呼び出すごとに、木全体の 検索と 再均衡 - rebalancing - が 行われます。

もし、どうにかして ローカルな balance argorithm または なにか 他の やり方を 使うことで、グローバルな 再均衡を 避けたいのなら、それも いいですね。

*1:*tree)->left);
int nright = count((*tree)->right);

if (nleft > n) {
partition(&(*tree)->left, n);
rotate_right(tree);
}
if (nright > n) {
partition(&(*tree)->right, n);
rotate_left(tree);
}
}

n が 与えられると、分肢の進路 - subtree path - が n より 短くなるまで、木を 検索 - sort - します。

そこから、このノードは 木の 上方に 向かって 回転 - rotation - が 行われ、それが 木全体の root と なります。

この関数を 使って、balance 関数を 書くことができ、そこでは n/2 除算 - dividing - によって、いつでも 木の 中間で 分割が 行われます ▽

void balance(struct Tree **tree)
{
int n = count(*tree);

if (n < 2)
return;
partition(tree, n/2);
balance(&(*tree)->left);
balance(&(*tree)->right);
}

目ざとい人なら、分肢にある ノードの数を 見つける、count 関数が 使われてるのに注意するでしょう((バレバレなんですけど ...