はじめての C

lang

「二分木 続き 6」

splay木では、root への 挿入の 変更 - modification - を 利用することで、どちらの 最悪の ケースとなる 可能性も 除くように 考えられています。

必要となる 変更は 最小限ですが、一番 効果的に なるよう、挿入と 検索ルーティンの 両方で、同様の 操作を行う 必要が あります。

結果的に、splay木による 良好な 自己最適化 - self-organizing - を 促すことで、検索パターンが 頻繁に small set of keys と なる場合では とても 役にたちます。

splay の 操作では、ノードを root へと 移動する simple 回転の かわりに、ノードを root へと 移動し 他のノードを root に 近い 途中へ 移動するという double 回転を 使っています。

簡単に いえば、実行する 回転では、root から 途中 出会う 他のノードに つながる 通路を、半分だけ 切り離すのです。

注意するのは、この実装では、すべての 操作で その平均的 cost が 保証されていることです。

単一の 検索 または 挿入では linear time が かかるのですが、実装が 全体的に 集中することで、代表的な アプリケーションでは、他の バランスのとれた木と 同様になります。

splay によって どのように 変質した木を、わずかな 検索で、つりあいよく (ノードを) 移動させるのでしょう ?

tutorial用に 書いた テストケースから、0 から 6 間での 数のある 検証用の木を 1つ 示してみます ▽


      6
     5
    4
   3
  2
 1
0

value を 3 として、splay 検索を 実行すると、木は このように 変化します ▽


  3
 2 5
  4 6

つりあいが 大きく 変化したとは 思いませんか ? spray 検索の コードは 次のように なります ▽

int splay_search(struct Tree **tree, int key)
{
int rc;

if ((*tree)->data == key)
rc = 1;
else if (key < (*tree)->data) {
if ((*tree)->left->data == key)
rc = 1;
else if (key < (*tree)->left->data) {
rc = splay_insert(&(*tree)->left->left, key);
rotate_right(tree);
}
else if (key > (*tree)->left->data) {
rc = splay_insert(&(*tree)->left->right, key);
rotate_left(&(*tree)->left);
}
else
rc = 0;
rotate_right(tree);
}
else if (key > (*tree)->data) {
if ((*tree)->right->data == key)
rc = 1;
else if (key < (*tree)->right->data) {
rc = splay_insert(&(*tree)->right->right, key);
rotate_left(tree);
}
else if (key > (*tree)->right->data) {
rc = splay_insert(&(*tree)->right->left, key);
rotate_right(&(*tree)->right); }
else
rc = 0;
rotate_left(tree);
}
else
rc = 0;

return rc;
}

ここでは、次の 4つの 移動ケースの あることに 注意してください。

left-left, left-right, right-left, right-right

それぞれの ケースでは、分肢の 構造体によって 異なった タイプの 回転が 求められます。

これと root_insert 関数とで、たった 1つ 異なる点は (項目を 挿入するかわりに、単に flag を 返してるところは 別にすると)、bottom からの single 回転よりも、top からの double 回転を 使ってるところです。

splay を 用いた 挿入の コードも まったく 同様で、ただ 検索の ところが 挿入に 変更されています。

これは、基本的には、item == key の ケースが item == NULL に 取り換えられ、new_node を 呼び出している、ということを 意味しています ▽

int splay_insert(struct Tree **tree, int key)
{
int rc;

if (*tree == NULL) {
*tree = new_node(key);
rc = (*tree == NULL) ? 0 : 1;
}
else if (key < (*tree)->data) {
if ((*tree)->left == NULL) {
(*tree)->left = new_node(key);
rc = ((*tree)->left == NULL) ? 0 : 1;
}
else if (key < (*tree)->left->data) {
rc = splay_insert(&(*tree)->left->left, key);
rotate_right(tree);
}
else if (key > (*tree)->left->data) {
rc = splay_insert(&(*tree)->left->right, key);
rotate_left(&(*tree)->left);
}
else
rc = 0;
rotate_right(tree);
}
else if (key > (*tree)->data) {
if ((*tree)->right == NULL) {
(*tree)->right = new_node(key);
rc = ((*tree)->right == NULL) ? 0 : 1;
}
else if (key < (*tree)->right->data) {
rc = splay_insert(&(*tree)->right->right, key);
rotate_left(tree);
}
else if (key > (*tree)->right->data) {
rc = splay_insert(&(*tree)->right->left, key);
rotate_right(&(*tree)->right);
}
else
rc = 0;
rotate_left(tree);
}
else
rc = 0;

return rc;
}

次は、それぞれの 分肢の 高さの つりあいを 見てまわることで つりあいを 保つという、より 複雑な algorithm を 調べてみましょう。

そうは 思えないかも しれませんけど、この algorithm は 二分木の つりあいを 保つための、一番 効果のある 方法の 1つなんです。

運の悪いことに、これもまた とっても 不可解なんですよ ...

最後まで 訳せるんだろうか ... (;_;)
(追記) ちょっと 訂正。