はじめての C

「二分木 続き 9」

int avl_remove(struct Avl **tree, struct Avl *old_item)
{
struct Avl *heir;
int rv;

/* Delete */
if (*tree == old_item) {
if *1。 でも、その複雑なところには びっくりさせられます。

red-black木も 同じような つりあいを もっています。しかし また 同じように 複雑に なります。

AVL木や red-black木に 匹敵するにも かかわらず、splay木は いつでも 片隅に 追いやられています。

そして 最後に、無作為の 基本的な 木というものは、AVL や red-black木より はるかに シンプルなものです。 ただし それは たいていの場合、気に入るような 完全な 木とは ほど遠いものです。

理解できるでしょうが、通常は 性能と 複雑性 それと 良好な結果の 間で 選択が 行われます。

もちろん 良好な結果と 性能とは 互いに 一括することが できます。 というのは 高速な つりあいの algorithm だと、貧弱な木が 返ってきて、検索で 悩むことに なるからです。

すでに 気づいたように、もし 検索が 遅いと 二分木で 動く 全てのものが 遅くなります。 なぜなら、ほぼ 全てのものが 検索を 要求しているからです。

たぶん 今、希望のない 迷いを 感じてるでしょうが、この迷路から 抜け出す 方法を 1つ 勧めることにしましょう。

二分木と 全ての baggage を 使わずに、0(logN) の 性能を 引き出す方法を 実現させるのです。

完全では ないですし、二分木の かわりを 確実に するのでも ないですが、その 新しい データ構造体が 役だつことは 立証されています。 それは バカバカしいほど シンプルで、skip list と 呼ばれています。

*1:*tree)->left == NULL && (*tree)->right == NULL) {
/* No children, unlink the node */
*tree = 0;
return 1;
}
else if ((*tree)->left == NULL) {
/* Replace node with right child */
*tree = (*tree)->right;
return 1;
}
else if ((*tree)->right == NULL) {
/* Replace node with left child */
*tree = (*tree)->left;
return 1;
}
if ((*tree)->balance < 0) {
/* Find left successor */
heir = (*tree)->left;
while (heir->right != NULL)
heir = heir->right;
}
else {
/* Find right successor */
heir = (*tree)->right;
while (heir->left != NULL)
heir = heir->left;
}
/* Rebalance */
rv = avl_remove(tree, heir);
/* Remove node */
heir->left = (*tree)->left;
heir->right = (*tree)->right;
heir->balance = (*tree)->balance;
*tree = heir;
if (heir->balance == 0)
return rv;
}
/* Search */
if (compare((*tree)->data, old_item->data) > 0) {
/* Move left */
if ((*tree)->left != NULL) {
if (avl_remove(&(*tree)->left, old_item) != 0) {
/* Balancing act */
if ((*tree)->balance++ < 1)
return (*tree)->balance;
else if ((*tree)->right->balance == 0) {
rotate_left(tree);
(*tree)->balance = -1;
(*tree)->left->balance = 1;
return 0;
}
else if ((*tree)->right->balance == 1) {
rotate_left(tree);
(*tree)->balance = 0;
(*tree)->left->balance = 0;
}
else {
rotate_right(&(*tree)->right);
rotate_left(tree);
/* Adjust balance factors */
if ((*tree)->balance == 1) {
(*tree)->left->balance = -1;
(*tree)->right->balance = 0;
}
else if ((*tree)->balance == 0) {
(*tree)->left->balance = 0;
(*tree)->right->balance = 0;
}
else {
(*tree)->left->balance = 0;
(*tree)->right->balance = 1;
}
(*tree)->balance = 0;
}
return 1;
}
}
}
else if (compare((*tree)->data, old_item->data) < 0) {
/* Move right */
if ((*tree)->right != NULL) {
if (avl_remove(&(*tree)->right, old_item) != 0) {
/* balancing act */
if ((*tree)->balance-- > -1)
return (*tree)->balance;
else if ((*tree)->left->balance == 0) {
rotate_right(tree);
(*tree)->balance = 1;
(*tree)->right->balance = -1;
return 0;
}
else if ((*tree)->left->balance == -1) {
rotate_right(tree);
(*tree)->balance = 0;
(*tree)->right->balance = 0;
}
else {
rotate_left(&(*tree)->left);
rotate_right(tree);
/* Adjust balance factors */
if ((*tree)->balance == 1) {
(*tree)->left->balance = -1;
(*tree)->right->balance = 0;
}
else if ((*tree)->balance == 0) {
(*tree)->left->balance = 0;
(*tree)->right->balance = 0;
}
else {
(*tree)->left->balance = 0;
(*tree)->right->balance = 1;
}
(*tree)->balance = 0;
}
return 1;
}
}
}

return 0;
}

うまいぐあいに、ここでは AVL木で 動かすのに 必要な 作業の範囲で 収まっています。

求められる 基本となる 検索が 全て 備わってるのです。

もちろん、2つの木を 繋ぐような より複雑な 操作だと、ほんの少しだけ 難しくなるでしょうけど。

しかし、そんな操作は、挿入や 削除 それに 検索のような よりシンプルなものに 比べても そう 頻繁には 起こりません。

And Why Are We Doing This?

結局のところ、それで つりあいのとれた 二分木を 実現する 効果と 同じ価値を もつのか、たぶん 不思議に 思うでしょう。

その答えは 条件に よるのです。

もし データが 十分 ランダムで、より 適切な 木の構造体を 必要と しないのなら、困ることは ありません。

もし そのデータが ソートされてるようで、項目の 数も 多いと、変質した木が 重大な 問題を 起こすに 違いないので、多分 バランスの とれた 木が 必要に なってきます。

それで、完璧な 作業と 経験を つむために、難しい algorithm を 使って 動かしてみるのも、もちろん、一理 ありますね。

当然、この 私のように するのなら、空いてる 時間に、完全に 理解できるまで 多分 それを 動かしてみるでしょうし、自分で binary を 書いて、二度と そいつを 使わない なんてことに なるでしょう :p

これまで 見てきた 3つの つりあいを とる方法で、manual な やり方で つりあいを とることで、より 完璧な つりあいの とれた木が 返されますし、書くのも 容易ですが、しかし 効率が 悪くなる 傾向は あります。

AVL木は、perfect な 木と basic な 木との 間の excellent な つりあいです (シャレですよ !)((よく わからん ...