はじめての C

「二分木 続き 2」

二分木の つりあいを とる方法では、多くの 場面で、回転 - rotation - という 操作が 必要と なってきます。

回転は、ある分肢の root を、それ自体の もつ 分肢の root の 1つと、その役割を 切り替える - switch -ときに、実行されます。

こんな説明だと、図で 示して たどってみる以外では 難しいので、右への回転 - rotation to the right - を 1つ 示してみます ▽

rotate_right [5]
1......1
....5.->.3
..3........5
...4......4

今度は、左への回転 - rotation to the left ▽

rotate_left [1]
1........3
..3.->.1
.2......2

どんな風にして、分肢の root が、右 (または 左) の いずれかの 分肢へと 変わるのかに、注意してください。

この変換のための ちょっとした コードです ▽

void rotate_right(struct Tree **root)
{
struct Tree *save;

save = (*root)->left;
(*root)->left = save->right; save->right = *root;
*root = save;
}

void rotate_left(struct Tree **root)
{
struct Tree *save;

save = (*root)->right;
(*root)->right = save->left;
save->left = *root;
*root = save;
}

これらの回転を 覚えておく - under one's belt - ことで、木の つりあいを 正しい位置に 保つための アルゴリズムを つくりだすことが できるのです。

このような ルーティンが ないと、むりやり 配列を 構築し、木の すべての要素を 配列に コピーし、それを ソートして、配列の 二分走査を 使って 木を 再構築することになります。

それだと、能率が 悪くなるように 思いますね。

この種の 再構築は、いつでも、できるだけ 避けるように したいものです。

save を 使って root を 取り換えてるのか ...