Dokusyo-nissi Bessitu 2005-08-06 φ(-_-) ■[lang]はじめての C 「二分木続き」 二分木 2回目の tutorial では、前に書いたことのある、木を変質させる- degenerate - 2つの最悪のケースを回避するための、さまざまな手法を詳しく調べ ることにしましょう。 先に学んだアルゴリズムでは、入力時にそれが十分ランダムになってる場合に、良 好な検索木 - good search tree - が実現されます。 復習をかねることにして、すでに知っている挿入のアルゴリズムだと、こうなりま す▽ int norm_insert(struct Tree **tree, int key) { int rc; if (*tree == NULL) { *tree = new_node(key); if (*tree == NULL) rc = 0; else rc = 1; } else if (key < (*tree)->data) rc = norm_insert(&(*tree)->left, key); else if (key > (*tree)->data) rc = norm_insert(&(*tree)->right, key); else rc = 0; return rc; } いくつか異なった変更が加えられてるのに注意してください。 再帰にダブルポインタが使われてるので、コードはより複雑に見えますが、それは 錯覚にすぎません。 一回、構造体へのダブルポインタの間接参照と、メンバへのアクセスという考え - concept - が使えるようになれば、このコードが簡単にたどれます。 このスタイルを選んだのは、それがより簡潔な傾向をもっていて、その短さ - brevity - が、この tutorial で後で学ぶことになるコードでは役にたつからです 。 もう一つ違ってるのは、(関数で) いろいろと返すかわりに、1つの返り値を使って いることです。 このアルゴリズムでほとんどの用途では十分です。しかし、入力データがソート順 かまたは交互順のどちらかで入るとすると、次のような最悪のケースのうちの一つ が生じることになります。 最悪のケース 1) データの到着がソート順だとすると、右 (あるいは左) の分肢が 生成し、結果として全く役たたずのリンクリストとして構築されてしまいます▽ 0 .1 ..2 ...3 ....4 .....5 ......6 最悪のケース 2) データの到着が交互順 - altemating order - なら、木はジグザ グに生成し、それだと前の場合と同じくらい悪いものになります。 問題は、常に 1方向のみの選択ということにあって、それが二分木の働きを無効に してしまうのです▽ 0 .6 1 .5 2 .4 3 これらのケースと比較するため、最良のケースを示してみましょう▽ ...3 .1...5 0.2.4.6 変質した木は最悪ですので、普通に戻すためこの問題を解決する必要があります。 必要なのは、木を最悪のケースから最良のケースに近づけるようにしておけるアル ゴリズムです。方法として、最悪のシナリオを心配せずに、二分木のすべての役に たつ性質を引き出せるようにします。 考え方としては十分シンプルに思えるのですが、実行上はとても難しくなります。 この tutorial では、検索時間を最適なものに近づけるよう保証された方法をもつ 、5つの例題を追っていきます。 手順にしたがって root ノードからの木全体のつりあいをとり、random number generator を通してランダムな順での挿入をひきうけ、すべてのノードが 1つの root にむかって集中するようもってくることでそれ自身で編成される - self-organize - ようにし、複合 AVL アルゴリズムによる挿入での再均衡 - rebalance - を行って、最終的には、ひどく複雑なものとならない、つりあいのと れた二分木をもった、確率的な (見込みのある) - probabilistic - データ構造体 として再現していきます。 2005-08-07 φ(-_-) ■[lang]はじめての 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 を取り換えてるのか ... 2005-08-09 φ(-_-) ■[lang]はじめての C 「二分木続き 3」 root のノードがあると、どうして木のつりあいをとることができるんでしょう ? それは、分割 - partition - というトリックにあります。 木のノードのどれかを選んで、それを root のノードにできるようにしたい、とし ます。 これは、再帰と、新しく回転 - rotation - のルーティンを書くことで、わりと簡 単に実装できます▽ void partition(struct Tree **tree, int n) { int nleft = count((*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 関数が使われてるのに 注意するでしょう*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:バレバレなんですけど ... ■[lang]はじめての C 「二分木続き 4」 データがランダム順に挿入されるのを保証することで、二分木は 2つの最悪のケー スとなるのを免れます。これが、なぜランダム順での入力を試みたのかという (理 由) なのです。 しかし、もしデータがランダムではなかったときに、その木をさらにランダムに構 築することができればいいですね。それは回転を使うことで、できるのです。 分割アルゴリズムで、どんな風にある (任意の) node を取り上げ、それを木全体の root にしたのかを思いだしてください。 このアルゴリズムと、木の root での新しいノードの挿入とを組み合わせることで 、可能になるのです▽ int root_insert(struct Tree **tree, int key) { int rc; if (*tree == NULL) { *tree = new_node(key); if (*tree == NULL) rc = 0; else rc = 1; } else if (key < (*tree)->data) { rc = root_insert(&(*tree)->left, key); rotate_right(tree); } else if (key > (*tree)->data) { rc = root_insert(&(*tree)->right, key); rotate_left(tree); } else rc = 0; return rc; } この関数を、以前つくった norm_insert 関数と比べてみると、再帰呼び出し後の回 転を除けば、まったく同じことに気づきます。 root_insert 関数を partition (関数) と比べると、partition では挿入がなく、 key による比較のかわりに counting を使ってること以外は、ほぼ同じに見えます 。 OK, これで木の root への挿入ができます。 でも、これがどうして、つりあいのとれた二分木を手に入れることになるんでしょ う ? 普通の挿入と、root への挿入とをランダムに選択することで、適正で平均したケー スを保つための確率的な方法が使えます。 それがなぜつりあいのとれた木を手に入れることになるのか、まごついてるのなら 、紙の上に書くことで試してみてください。 ソート順の数を選んで、root への挿入と通常の挿入とを、ランダムに選択してみる んです。 注意してほしいのは、つりあいが完璧なことはめったにありませんが、同じように 、深刻で最悪のケースもほとんどないということです。 そのコードは▽ int insert(struct Tree **tree, int key) { if (rand() < RAND_MAX/2) return root_insert(tree, key); else return norm_insert(tree, key); } これはシンプルですね。 このコードでは確率は 1/2 となりますが、(関数) rand との比較を調整することで 、それ以外のどんな (確率) であっても、weedle することができます*1。 また、norm_insert のコードを insert (関数) へ組み込み、root_insert を特別な helper 関数としています。 But I find the use of two insertion functions wrapped by a handler to be cleaner.*2 ランダムな二分木をつくってみるときには、自分自身の判断に従うようにしてくだ さい。 これは単に、ランダムな木への変換に必要なものなんです。 他のすべての操作は、基本的な二分木の操作として書くことができます。 ランダムな二分木は、次善の策としてのつりあいをとるために、簡単な実装により 返り値を 1つ受け入れることで、十分にシンプルになります。 優秀な random number generator *3 とその確率計算によって、たいていの場合で 、最適に近いつりあいが見込めます。 もちろん、最悪のシナリオとなるケースの可能性を完全に取り除きたいのでしたら 、たとえば、前につくった balance ルーティンのような厳格な balancing algorithm の使用が必要となります。 しかし、もしもつりあいよりも優れた機能が必要になったら、どうするんでしょう か ? いいですよ、そのためには、挿入と削除のためのローカルな balancing algorithm という恐ろしい世界へと入っていく必要があるのです。 *1:weedle って ? ポケモン ?? *2:訳せませんでした ... oLr *3:関数 rand のこと 2005-08-13 φ(-_-) ■[lang]はじめての C 「二分木続き 5」 つりあいのとれた二分木には、代表的なものが 3つあります。 はじめの 2つは、この tutorial で扱うことになる spray木と AVL木です。 もう 1つの red-black木ですが、この tutorial では、簡単な説明だけにしておき ます。でも多分将来の tutorial では、より完全なものができるでしょうね。 red-black木とは、(二分木とは) 別の木のタイプで 2-3-4木と呼ばれるものの、二 分形式での表記のことです。 2-3-4木では、root がすでにリンクを 2つもつときに 3つ目のリンクを追加し、別 のリンクを追加して合計 4つにするために分割を行うことで、その最小の高さ - minimal height - が保たれています。 M が挿入されると、次のような (Knuth 3, 6.2.3) 分割が実行されます▽ J / | E L,T / | / | | A,C G K M,N,R V,X J / | E L,N,T / | / | | | A,C, G K M R V,X J,N / | | E L T / | / | / | A,C G K M R V,X 二分木だと、リンクを追加するというようなゼイタクはできませんから、red-black 木では 2-3-4 という構成を表すためにカラー表記を使っています (red が内部リン ク、black は外部リンクに)。 red-black の構造体においては、ノードが 3つあるのと同じことを、次のように表 します▽ 3 Node Red-black Node (R = red link color) * R R / | | / or | * * ノードが 4つのときは、次のようになります▽ 4 Node Red-black Node (R = red link color) * R / | | | / | * * red-black の図式は全体としてとてもエレガントで、AVL木との違いは通常その入力 データによっています。 この tutorial で、red-black ではなくて AVL の方を選んだのは、まったくの独断 によるものです。 2005-08-14 φ(-_-) ■[lang]はじめての C 「二分木続き 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つなんです。 運の悪いことに、これもまたとっても不可解なんですよ ... 最後まで訳せるんだろうか ... (;_;) 2005-08-18 φ(-_-) ■[lang]はじめての C 「二分木続き 7」 AVL とは、この algorithm を生みだした 2人の数学者 Adelson-Velsky と Landies の 2人を意味しています。 基本となる考え方は、それぞれのノードの左の分肢の高さと、右の分肢の高さを比 べて、その差が必ず 1 以内に収まることで、木のつりあいをとる、ということです 。 この定義だと、(本来の) 最適なつりあいという結果にはなってませんが、実行上で は意外なことになるんです。 AVL木は、それぞれのノードが -1、0 または +1 であるというつりあい要因 - balance factor - によって、保たれています。 新しいノードが挿入されると、挿入によって右の分肢が +1 分伸びるか、または左 の分肢が -1 分小さくなり、そのためつりあい要因を 1つもつことになり、木の再 均衡が必要になります。 ここで 2つのケースが生じます (それぞれのケースでは、左に反映されています)( Knuth 3, 6.2.3)。 Case 1) 新しいノードが、B の右の分肢の高さを h から h+1 へと伸ばす▽ A / | h B / | h h+1 ここで求められるのは、つりあいを再均衡させるため、左への single 回転を実行 させることです。注意するのは、左への回転により高さが h+1 になるので、他の h の高さの分肢を、前よりもノード 1つ分高い h+1 となるよう適応させていることで す▽ B / | A h+1 / | h h Case 2) 新しいノードが、B の左の分肢の高さを h から h+1 へと伸ばす*1 ▽ A / | h B / | X h / | h-1 h これはより難しいケースで、はじめに B の右、次に X の左という、double 回転が 要求されています▽ X / | A B / | / | h h h h AVL木での挿入の実際の algorithm は、いくつかの step に分割する - be broken up into - ことができます。 1) Search (検索) a Compare (比較) b Move left or move right (移動) 2) Insert (挿入) a Adjust balance factors (調整) 3) Replacement (取り換え) a Single or double routine (回転) 当然ですが、(実際の) step では上のリストに比べると相当複雑になります。 ここでは AVL Algorithm の実行に、再帰を使います (おそらくその効果が認められ ないと文句がでるでしょうけどね)。 いいわけをしておくと、再帰での入力の方が、反復による挿入 - iterative insertion - よりもシンプルで短くなるからです。 反復による削除では、どこかに明示的に stack を求められます。それで、代わりに 再帰を使えば、操作のためのコードが簡素化されるのです。 さて、tutorial へと戻りましょう。この AVL 挿入ルーティンでは、次のような疑 似コードが用いられます▽ # Returns 1 if the changes, 0 otherwise sub avl_insert(tree, item) if empty tree insert node return 1 endif if tree > item # Move left if tree.left != null if avl_insert(tree.left, item) != 0 if tree.balance < 1 # Still balanced return tree.balance += 1 elif tree.left.balance > 0 # Case 1 rotate_right(tree) tree.balance = 0 tree.right.balance = 0 else # Case 2 rotate_left(tree.left) rotate_right(tree) # Adjust balance factors if tree.balance == 1 tree.left.balance = -1 tree.right.balance = 0 elif tree.balance == 0 tree.left.balance = 0 tree.right.balance = 0 else tree.left.balance = 0 tree.right.balance = 1 endif tree.balance = 0 endif else return 0 endif else tree.left = item return tree.balance += 1 endif elif tree < item # Move right if tree.right != null if avl_insert(tree.right, item) != 0 if tree.balance < 1 # Still balanced return tree.balance += 1 elif tree.left.balance > 0 # Case 1 rotate_left(tree) tree.balance = 0 tree.left.balance = 0 else # Case 2 rotate_right(tree.right) rotate_left(tree) # Adjust balance factors if tree.balance == 1 tree.left.balance = -1 tree.right.balance = 0 elif tree.balance == 0 tree.left.balance = 0 tree.right.balance = 0 else tree.left.balance = 0 tree.right.balance = 1 endif tree.balance = 0 endif else return 0 endif else tree.left = item return tree.balance += 1 endif endif return 0 end sub このコードは見てのとおり、helper 関数で wrap した*2 回転のコードと同じくら い、かなり複雑です。 その関数の多くが、つりあい要因の点検と交換とに費されています。 それで、多分すべての点においてまごつくでしょうけど、実際には見た目よりもず っと簡単なんです。 先へ進む前に、それが納得できるまで、ロジックを紙の上に書きだしてみることを 勧めます。 終わりました ? OK、では疑似コードを C に変換する前に、役にたつものがいくつ か必要になります。 最初に、メンバとしてのつりあい要因をもっている、新しい構造体が入用です▽ struct Avl { struct Avl *left; struct Avl *right; int balance; int data; }; comparison 関数も役にたってくれます。production code では、多分 comparison 関数を avl_insert 関数に渡すのにポインタが使われるでしょう。でもこの tutorial では、関数のポインタに詳しくない場合 (を考えて)、直接呼び出すこと にします▽ int compare(int a, int b) { if (a < b) return -1; else if (a > b) return +1; else return 0; } どちらもシンプルですので、説明の必要はないでしょう。もしも説明が必要だとす ると、この tutorial を読んでないんですね :p 次の rotation 関数には、ここでは読みやすくするためと、Avl 構造体に適応させ るために、ほんのわずか変更が加えられています▽ void rotate_left(struct Avl **subtree) { struct Avl *save; struct Avl *node; node = *subtree; save = node->right; node->right = save->left; save->left = node; *subtree = save; } void rotate_right(struct Avl **subtree) { struct Avl *save; struct Avl *node; node = *subtree; save = node->left; node->left = save->right; save->right = node; *subtree = save; } では最後に、これ以上めんどうなことはありませんので、avl_insert ルーティンを C のコードへとつくり換えてみましょう▽ *1:h-1 に小さくするではなくて *2:?? 2005-08-20 φ(-_-) ■[lang]はじめての C 「二分木続き 8」 int avl_insert(struct Avl **tree, struct Avl *new_item) { /* empty tree */ if (*tree == NULL) { *tree = new_item; return 1; } if (compare((*tree)->data, new_item->data) > 0) { /* Move left */ if ((*tree)->left != NULL) { if (avl_insert(&(*tree)->left, new_item) != 0) { /* Balancing act */ if ((*tree)->balance++ < 1) return (*tree)->balance; else if ((*tree)->left->balance > 0) { /* Case 1 */ rotate_right(tree); (*tree)->balance = 0; (*tree)->right->balance = 0; } else { /* Case 2 */ 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; } } else return 0; } else { (*tree)->left = new_item; return ++(*tree)->balance; } } else if (compare((*tree)->data, new_item->data) < 0) { /* Move right */ if ((*tree)->right != NULL) { if (avl_insert(&(*tree)->right, new_item) != 0) { /* Balancing act */ if ((*tree)->balance++ < 1) return (*tree)->balance; else if ((*tree)->right->balance > 0) { /* Case 1 */ rotate_left(tree); (*tree)->balance = 0; (*tree)->left->balance = 0; } else { /* Case 2 */ 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; } } else return 0; } else { (*tree)->right = new_item; return ++(*tree)->balance; } } return 0; } これはほぼ直訳なので、もし疑似コードが理解できて、C の基本のところを精通し ていれば、関数を読み解くのに何の問題もないでしょう。 とても驚くことに (私は、それが実現したときに本当に驚いたのですが)、この関数 では line 毎の description を必要としません。 すでに回転でも検討しましたが、再帰に通じてる人ならだれでも、この状況で何の 問題も起こりません。そしてコードの残りは、単に flag の反転 - flipping - と 比較とになります。 もしまだ困難をかかえてるのなら、紙と鉛筆とを引き寄せて、壊れてドロドロにな った - crushed-pulp - とでも呼びたい AVL木になんらかの値を挿入してください 。 いいかえると、書き出してみることで、そのアイデアを掴むのです。 ちょっとした tutorial ... ですか ? もっと複雑なアルゴリズムのコードを 1つ与えて、それを自分で計算するよう命じ ることです :p この上級の tutorial のやり方だと、早急に基礎をつくりあげられるので、より多 くの要点をつけ加えられることと、その後の (説明形式での) 失敗を少なくするこ とができます。 さて、考えるのですが、つりあいのとれた木について、本や tutorial では、 insertion (関数) に対しては、動かすための (ときには不十分なあるいは全ケース での) 全てのソースコードを含む、たっぷりの時間とスペースとが与えられていま すね。でも、deletion (関数) に関しては、まったく無視されています。 もっと悪いと、課題だけで止めてしまってます。 私の判断ですが、(それらの) 筆者は、簡単なところは説明もせず、難しい部分は最 小限の説明のみで済ませて、課題だけで止めてしまってるのです。 それで、avl_delete (関数) についても、その疑似コードと C のソースとを示すこ とにしましょう。 というのも、その方が、ちょっとだけでも、思いやりがあるでしょうしね :p ▽ # Returns 1 if height changes, 0 otherwise sub avl_remove(tree, item) heir rv if tree == item # We found it, now delete it if tree.left == null AND tree.right == null # No chirdren, unlink the node tree = null return 1 elif tree.left == null # Replace node with right child tree = tree.right return 1 elif # Replace node with left child tree = tree.left return 1 endif 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 endif # 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; endif # Search if tree > item # Move left if tree.left != null if avl_remove(tree.left, item) != 0 if tree.balance < 1 # Still balanced return tree.balance += 1 elif tree.right.balance == 0 rotate_left(tree) tree.balance = -1 tree.left.balance = 1 elif 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 elif tree.balance == 0 tree.left.balance = 0 tree.right.balance = 0 else tree.left.balance = 0 tree.right.balance = 1 endif tree.balance = 0 endif return 1 endif endif elif tree < item # Move right if tree.right != null if avl_remove(tree.right, item) != 0 if tree.balance > -1 # Still balanced return tree.balance -= 1 elif tree.left.balance == 0 rotate_right(tree) tree.balance = 1 tree.right.balance = -1 elif 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 elif tree.balance == 0 tree.left.balance = 0 tree.right.balance = 0 else tree.left.balance = 0 tree.right.balance = 1 endif tree.balance = 0 endif return 1 endif endif endif return 0 end sub 検索 (の箇所は) avl_insert (関数) で見たところと基本としては同じことです。 都合のよいことに (検索のような) 考え方は一度理解できれば、多くの場面で再利 用ができます。 それで、たとえコードが長くて複雑に見えたとしても、その大きな部分は理解でき てきます。 もう一度励ましますけど、どのようにすべてが動くのかが理解できるまでは、この ロジックを紙の上に書き出すようにしてください。 そのことが (例えば) ルーティンの内側での動きの異なった 10 の方法を説明しよ うと試みることなんかより、ずっとより有益でしょう。それに、私をタイピングで の大文字のトンネルから救い出してくれるでしょうしね :p 書いたものをいじってみるのは終わりましたか ? OK、これが C に翻訳したものです▽ 2005-08-22 φ(-_-) ■[lang]はじめての C 「二分木続き 9」 int avl_remove(struct Avl **tree, struct Avl *old_item) { struct Avl *heir; int rv; /* Delete */ if (*tree == old_item) { if ((*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 なつりあいです (シャレ ですよ !)*1。でも、その複雑なところにはびっくりさせられます。 red-black木も同じようなつりあいをもっています。しかしまた同じように複雑にな ります。 AVL木や red-black木に匹敵するにもかかわらず、splay木はいつでも片隅に追いや られています。 そして最後に、無作為の基本的な木というものは、AVL や red-black木よりはるか にシンプルなものです。ただしそれはたいていの場合、気に入るような完全な木と はほど遠いものです。 理解できるでしょうが、通常は性能と複雑性それと良好な結果の間で選択が行われ ます。 もちろん良好な結果と性能とは互いに一括することができます。というのは高速な つりあいの algorithm だと、貧弱な木が返ってきて、検索で悩むことになるからで す。 すでに気づいたように、もし検索が遅いと二分木で動く全てのものが遅くなります 。なぜなら、ほぼ全てのものが検索を要求しているからです。 たぶん今、希望のない迷いを感じてるでしょうが、この迷路から抜け出す方法を 1 つ勧めることにしましょう。 二分木と全ての baggage を使わずに、0(logN) の性能を引き出す方法を実現させる のです。 完全ではないですし、二分木のかわりを確実にするのでもないですが、その新しい データ構造体が役だつことは立証されています。それはバカバカしいほどシンプル で、skip list と呼ばれています。 *1:よくわからん ... 2005-08-26 φ(-_-) ■[lang]はじめての C 「二分木続き 10」 skip list は、ランダム数 = 乱数を使うことで、効率のよい構造をつくりあげる、 確率的な - probabilistic - データ構造です。 その方法は、(以前 つくった) ランダムに構築する - randomized - 二分木と同じ く、乱数をその挿入 algorithm で使っています。 skip list はとてもシンプルなリンクリストですが、次のノードをポインタで指す かわりに、次のノードへのポインタの配列をもっています。 しかし、より高いレベルでのポインタは、さらにリストの下側のノードを指し示し ています。 skip は次のような図であらわすことができます▽ 4) ------> 6 -----------------------------------------------> ~ 3) ------> 6 -----------------------------------> 25 -------> ~ 2) ------> 6 ------> 9 -------> 17 -------------> 25 -------> ~ 1) -> 3 -> 6 -> 7 -> 9 -> 12 -> 17 -> 19 -> 21 -> 25 -> 26 -> ~ これはよくできた skip list で、矢印(->)はリンク先をあらわし、N) は 1 から 4 までのレベルナンバーで、1 が lowest, 4 が highest (レベル) となります。チル ド(~)は、リストの終わりか null をあらわしています。 検索では、次のポインタを追跡していき、必要なときには下のレベルへ移動するこ とで、とても効率よく行えます。例えば、上の skip list で 19 を捜す検索だと、 次のように通路 - path - をたどっていきます▽ Level 4 -- 6 Level 2 -- 9 Level 2 - 17 Level 1 - 19 完全につりあいのとれた二分木だと▽ 12 6 21 1 7 17 25 9 19 26 同じように検索すると、通路を 12, 21, 17, 19 とたどっていきます。 同じ検索では、skip list (リンクリストですよ !) は、完全な二分木とまったく同 じだけの step 数で、かたずけてくれるのです。 このことは、特にそんな木をつくるのが難しく、リンクリストを使って何か簡単に 動かせないか、と考えたときに、非常に役にたちます。 skip list だと、どうして構築 - build - や検索がやさしくなるのでしょうか ? 普通のリンクリストほどはやさしくはありませんが、つりあいのとれた二分木より はずっと簡単です。では始めてみましょう。 はじめに、ノードへの定義が必要となります▽ struct Skip { struct Skip **forward; int level; int data; }; とてもシンプルですが、skip list を保守するには、挿入 algorithm でルーティン でランダムに確定するために、ノードにはどれだけのレベルがいるのかを知る必要 があります。 space を確保するため、skip のポインタには動的な割り当て配列 - dynamically allocated array - を使うことにしましょう。 レベルを最大値に設定することでも同じく、簡単に配列をつくって使うことができ ます。 しかし、1つのノードが使用できるリンクを 1つしかもてないとすると、例えば、14 個分の余分なポインタを設ける意味がありませんね。 この algorithm だと、どちらがより満足できるかで選んだとしても、そのいずれの 方法でもうまく動いてくれるでしょう。 次は、新しいノードが設定できるよう、ランダムなレベルを選択するための、何ら かのコードをセットアップする必要があります。 ここに示すのは、シンプルな algorithm で、skip list を紹介した論文に載ってい たものです (Skip List: A probablistic Alternative to Balanced Trees, William Pugh) ▽ int random_level(void) { int lvl; lvl = 0; while (rand() < RAND_MAX/2 && lvl < MAX_LEVEL) lvl++; return lvl; } また、状態をシンプルに保つためと、modularized since we are good little structured programmers*1 ためには、make_node 関数も必要です▽ int make_node(struct Skip **node, int level, int data) { int i *node = malloc(sizeof(**node)); if (*node == NULL) return 0; (*node)->forward = malloc(sizeof(*(*node)->forward) * level); if ((*node)->forward == NULL) return 0; for (i = 0; i < level; i++) (*node)->forward[i] = NULL; (*node)->data = data; (*node)->level = 0; return 1; } このコードでは割り当てを行っていて - allocate -、null に skip へのポインタ の配列を取り込むことで、新しいノードのデータとレベルとをセットしています。 *1:訳せません ... 2005-08-28 φ(-_-) ■[lang]はじめての C 「二分木続き 11」 さて、skip list の構築と削除の実際の algorithm ですが、ここが (一番) おもし ろいところです。 もっとも効率的とはいえませんが、これはもっともシンプルなものの 1つです。 skip list のいいところの 1つは、それを理解するのがとてもやさしくて、コード も簡単なので、試したり速度を最適化したりするのに、プログラマをひどくオビエ させることがない、という点です。 skip list の検索コードはシンプルで、highest レベルから始めて、count down し ていきます。 それぞれのレベルでは、それが null に届くまで、または key より大きな値となる まで、前方にポインタをたどります。 loop が終わると、検索により item が含まれているかそうでないかが (わかりま す)。 null へのチェックを忘れないよう。 コードは、▽ int skip_search(struct Skip **list, int search_key) { struct Skip *x; int i; x = *list; for (i = (*list)->level - 1; i >= 0; i--) { while (x->forward[i] != NULL && x->forward[i]->data < search_key) x = x->forward[i]; } x = x->forward[0]; if (x != NULL && x->data == search_key) return 1; return 0; } どう、シンプルでしょ ? もちろん二分木検索のほうがもっとシンプルです。その裏 付けが、挿入や削除のルーティンにあります。 OK、ではどのように skip list では挿入をおこなうのでしょう ? これは検索ほどシンプルではありません。しかし、もうわかったでしょうが、必要 とするものがどこかを見つけるために、検索が使われています▽ int skip_insert(struct Skip **list, int search_key) { struct Skip *update[MAX_LEVEL] = {0}; struct Skip *x; int i; x = *list; for (i = (*list)->level - 1; i >= 0; i--) { while (x->forward[i] != NULL && x->forward[i]->data < search_key) x = x->forward[i]; update[i] = x; } x = x->forward[0]; if (x == NULL || x->data != search_key) { int lvl = random_level(); if (lvl > (*list)->level) { for (i = (*list)->level; i < lvl; i++) update[i] = *list; (*list)->level = lvl; } make_node(&x, lvl, search_key); for (i = 0; i < lvl; i++) { x->forward[i] = update[i]->forward[i]; update[i]->forward[i] = x; } return 1; } return 0; } 配列 update が、それぞれ必要なレベルで、新しいノードを挿入しようとする箇所 の左側のリンクを保守 - save - しています。 update の使い方が、この algorithm で唯一少しばかりややこしいところです。で もそれは、リストを繋ぎあわせるのと、適切なノードの挿入には必要なのです。 がんばって、紙の上でこの logic をたどってみてください。 しかし、ほんのちょっと複雑なのにもかかわらず、skip list での挿入は、今まで 見てきたどのつりあいをとる方法よりも簡単なのです。 基本的な二分木では挿入だけだともっと短いのですが、そこでは再帰によって - recursively - のみ実行がされています。 skip list は反復で - iteratively - 書くことで、やさしくできるのです。これは 、関数呼び出しの overhead が回避できるため、実行上の利益 - boon - になって います。 削除のルーティンも同じようにシンプルになります▽ 2005-09-01 φ(-_-) ■[lang]はじめての C 「二分木続き 12」 int skip_delete(struct Skip **list, int search_key) { struct Skip *update[MAX_LEVEL] = {0}; struct Skip *x; int i; x = *list; for (i = (*list)->level - 1; i >= 0; i--) { while (x->forward[i] != NULL && x->forward[i]->data < search_key) x = x->forward[i]; update[i] = x; } x = x->forward[0]; if (x != NULL && x->data == search_key) { for (i = 0; i < (*list)->level; i++) { if (update[i]->forward[i] != x) break; update[i]->forward[i] = x->forward[i]; } free(x); while ((*list)->level > 1 && (*list)->forward[(*list)->level] == NULL) (*list)->level--; return 1; } return 0; } 同じように、配列 update と (今度は明らかに) 検索とが使われています。 このコードの残りを紙の上で動かしてみて、どのように動くのかを見てください。 これを受け取ったほとんどの人にとって、ざっと見ただけですぐこの logic を理解 するのに何の問題もないでしょう*1。でも、その推測を再度チェックしてみるのも 全然悪くありません。 当然、とてもわかりやすいので、このコードについての最初の推測はたぶん正しい はずです。 注意するのは、コードの中にところどころに - every once in a while - なにか、 マクロの MAX_LEVEL をこっそり紛れ込ませたことです。 これって何なんでしょう ? skip list では、それぞれのノードへの forward links (いわゆるレベルです) の 数をセットするのに乱数が求められています。もし単になにか乱数を取り入れるだ けだと、即刻大きな問題を起こしてしまいます。それで、乱数の範囲を与えること が可能な、レベルの最大限度を決めておきます。例えば、0-3 に対する可能なレベ ルの合計は 4 になります。 そのマクロの MAX_LEVEL はこうなります▽ #define MAX_LEVEL 4 とてもシンプルですね ? さて、それはかってに数を選び出すほどにはやさしくはあ りません。 レベルの最大限度では、リストの確率と、リストに入ってるらしいノードの上限と が基本になっています。 例えば、確率が 1/2 でリストの上限が 65,536 項目だと、MAX_LEVEL は、およそ 16 くらいになるでしょう。 ふぅ〜、この tutorial は長かったです。読む人とそれに自分自身のためにも、実 際にこの tutorial を書いたように、全てのコードを書き、テストして、デバッグ を行うため、時間をつくらなければなりませんでした。 でも、それだけの価値はありました。というのも、好みのコンパイラでこの tutorial から直接 copy & paste できますし、それは正確に動くでしょうから。 つりあいのとれた二分木を使って効率よく検索する場面で、いくらかでも (正しい) 判断ができるようになり、データ構造の選択にも目が開かれれば、と期待していま す。 1つの tutorial だと、十分に教えられるのは 1つの主題 - topic - の解釈だけで すので、完全なものを考えるには本に頼ることになります。 ですから、より多くの情報で topic を検討するためには、ネットで検索したり近く の本屋にでかけるようにしてください。 ここでは、データ構造の実際のセンスを養えるように試みました。なぜなら、ぼく らはプログラマであって、数学の証明を書くためただ座ってるだけの理論家ではな いからです。 ここに書かれたことから、実際にデータ構造を実装したり、それらを保守するのに 役にたつことがわかるでしょう。 このアプローチが参考になればと希望します ... ね。 *1:ちょっと難しいような気が ... 2005-09-24 φ(-_-) ■[lang]はじめての C balance tree だけど、tutorial では構造体 Tree を使って、root を返すようにしてい る。 それと、関数 norm_insert の中の new_node の引数が、このままだと 1つ足らない。 Tree は Node と入れ換えれば、そのまま使えるようなので、あとは norm_insert をち ょっといじって、コードを作成。 /* t_balance.c */ #include #include struct Node { int data; struct Node *left; struct Node *right; }; struct Tree { struct Node *root; }; int norm_insert(); void btree_walk(); int tree_height(); void rotate_right(); void rotate_left(); int count(); void partition(); void balance(); main() { int value; struct Tree *root; root = NULL; while (fscanf(stdin, "%d", &value) != EOF) norm_insert(&root, value); btree_walk(root); putchar('\n'); printf("%d\n", tree_height(root)); puts("balancing now"); balance(&root); printf("%d\n", tree_height(root)); return 0; } int norm_insert(struct Node **tree, int key) { int rc; if (*tree == NULL) { *tree = malloc(sizeof(**tree)); if (*tree == NULL) rc = 0; (*tree)->data = key; (*tree)->left = NULL; (*tree)->right = NULL; rc = 1; } else if (key < (*tree)->data) rc = norm_insert(&(*tree)->left, key); else if (key > (*tree)->data) rc = norm_insert(&(*tree)->right, key); else rc = 0; return rc; } void btree_walk(struct Node *tree) { if (tree == NULL) return; btree_walk(tree->left); printf("%d ", tree->data); btree_walk(tree->right); } int tree_height(struct Node *tree) { int left_height; int right_height; if (tree == NULL) return -1; left_height = tree_height(tree->left); right_height = tree_height(tree->right); if (left_height < right_height) return right_height + 1; else return left_height + 1; } void rotate_right(struct Node **root) { struct Node *save; save = (*root)->left; (*root)->left = save->right; save->right = *root; *root = save; } void rotate_left(struct Node **root) { struct Node *save; save = (*root)->right; (*root)->right = save->left; save->left = *root; *root = save; } int count(struct Node *tree) { if (tree == NULL) return 0; return count(tree->left) * count(tree->right) + 1; } void partition(struct Node **tree, int n) { int nleft = count((*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); } } void balance(struct Node **tree) { int n = count(*tree); if (n < 2) return; partition(tree, n/2); balance(&(*tree)->left); balance(&(*tree)->right); } コンパイルして、random.txt を使って確認。再度、入力データを変えて実行。 $cc -c t_balance.c $cc -o t_balance t_balance.o $./t_balance < random.txt データがリンクリストだとどうなるか試してみたけど、あまり役にたつとはいえないみ たい ... $./t_balance 0 1 2 3 4 5 (← ctrl + d) 0 1 2 3 4 5 5 balancing now 5 (追記) ちょっと訂正。 2005-09-25 φ(-_-) ■[lang]はじめての C ランダム関数 rand() を利用した balance tree をつくってみる。 RAND_MAX は生成さ れる乱数の範囲 (K&R 2nd p317)。ライブラリ time.h を使って srand() の引数を決め るようにした。 /* rand_insert.c */ #include #include #include struct Node { int data; struct Node *left; struct Node *right; }; struct Tree { struct Node *root; }; int insert(); int norm_insert(); int root_insert(); void btree_walk(); int tree_height(); void rotate_right(); void rotate_left(); main() { int value; struct Tree *root; srand(time(NULL)); root = NULL; while (fscanf(stdin, "%d", &value) != EOF) insert(&root, value); btree_walk(root); putchar('\n'); printf("%d\n", tree_height(root)); return 0; } int insert(struct Node **tree, int key) { if (rand() < RAND_MAX/2) return root_insert(tree, key); else return norm_insert(tree, key); } int norm_insert(struct Node **tree, int key) { int rc; if (*tree == NULL) { *tree = malloc(sizeof(**tree)); if (*tree == NULL) rc = 0; (*tree)->data = key; (*tree)->left = NULL; (*tree)->right = NULL; rc = 1; } else if (key < (*tree)->data) rc = norm_insert(&(*tree)->left, key); else if (key > (*tree)->data) rc = norm_insert(&(*tree)->right, key); else rc = 0; return rc; } int root_insert(struct Node **tree, int key) { int rc; if (*tree == NULL) { *tree = malloc(sizeof(**tree)); if (*tree == NULL) rc = 0; (*tree)->data = key; (*tree)->left = NULL; (*tree)->right = NULL; rc = 1; } else if (key < (*tree)->data) { rc = root_insert(&(*tree)->left, key); rotate_right(tree); } else if (key > (*tree)->data) { rc = root_insert(&(*tree)->right, key); rotate_left(tree); } else rc = 0; return rc; } void btree_walk(struct Node *tree) { if (tree == NULL) return; btree_walk(tree->left); printf("%d ", tree->data); btree_walk(tree->right); } int tree_height(struct Node *tree) { int left_height; int right_height; if (tree == NULL) return -1; left_height = tree_height(tree->left); right_height = tree_height(tree->right); if (left_height < right_height) return right_height + 1; else return left_height + 1; } void rotate_right(struct Node **root) { struct Node *save; save = (*root)->left; (*root)->left = save->right; save->right = *root; *root = save; } void rotate_left(struct Node **root) { struct Node *save; save = (*root)->right; (*root)->right = save->left; save->left = *root; *root = save; } 入力データとしてソート順のテキストを準備 ... あれっ? どうやってつくるんだった? (;_;) /* badtree.c */ #include #define MAX 100 main() { int i, n; n = 0; for (i = 0; i < MAX; i++) { n = i; printf("%d ", n); } putchar('\n'); return 0; } ソートデータを作成。 $cc -o badtree badtree.c $./badtree > badtree.txt コンパイルして、確認。 t_balance と比べてみる。 $cc -c rand_insert.c $cc -o rand_insert rand_insert.o $./rand_insert < random.txt $./t_balance < badtree.txt $./rand_insert < badtree.txt 2005-09-28 φ(-_-) ■[lang]はじめての C splay木を用いて tree の root を変更させてみる。その前に、ポインタをどう渡すか、 ちょっとチェック ... struct Node **tree; int value; if (*tree == NULL) new_node(tree, value); if ((*tree)->left == NULL) new_node(&(*tree)->left, value); これでよかったかな ? /* t_splay.c */ #include #include #include "t_splay.h" struct Node { int data; struct Node *left; struct Node *right; }; struct Tree { struct Node *root; }; int new_node(); int splay_insert(); int splay_search(); void rotate_right(); void rotate_left(); void btree_walk(); int tree_height(); main() { int value; struct Tree *root; root = NULL; while (fscanf(stdin, "%d", &value) != EOF) splay_insert(&root, value); btree_walk(root); putchar('\n'); printf("%d\n", tree_height(root)); printf("splay search > %d\n", ROOT); splay_search(&root, ROOT); printf("%d\n", tree_height(root)); return 0; } int new_node(struct Node **node, int value) { *node = malloc(sizeof(**node)); if (*node == NULL) return 0; (*node)->data = value; (*node)->left = NULL; (*node)->right = NULL; return 1; } int splay_insert(struct Node **tree, int key) { int rc; if (*tree == NULL) { new_node(tree, key); rc = (*tree == NULL) ? 0 : 1; } else if (key < (*tree)->data) { if ((*tree)->left == NULL) { new_node(&(*tree)->left, 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) { new_node(&(*tree)->right, 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; } int splay_search(struct Node **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; } void rotate_right(struct Node **root) { struct Node *save; save = (*root)->left; (*root)->left = save->right; save->right = *root; *root = save; } void rotate_left(struct Node **root) { struct Node *save; save = (*root)->right; (*root)->right = save->left; save->left = *root; *root = save; } void btree_walk(struct Node *tree) { if (tree == NULL) return; btree_walk(tree->left); printf("%d ", tree->data); btree_walk(tree->right); } int tree_height(struct Node *tree) { int left_height; int right_height; if (tree == NULL) return -1; left_height = tree_height(tree->left); right_height = tree_height(tree->right); if (left_height < right_height) return right_height + 1; else return left_height + 1; } ヘッダファイルも作成。 /* t_splay.h */ #define ROOT 30 コンパイルして、badtree.txt*1で確認。 $cc -c t_splay.c $cc -o t_splay t_splay.o $./t_splay < badtree.txt フムフム ... なかなか強力ですね。 *1:ソート順のデータ 2005-10-02 φ(-_-) ■[lang]はじめての C 今度は AVL木。関数 avl_insert では仮引数がそれぞれ構造体のポインタと構造体にな っているので、メモリの確保が別に必要となります。 でも、そんなことできそうにもないので、avl_insert を少し改悪 ? してみることに ... /* insert_avl.c */ #include #include #include "insert_avl.h" int new_node(); int avl_insert(); int compare(); void rotate_left(); void rotate_right(); void btree_walk(); int tree_height(); main() { struct Avl *root; int value; root = NULL; while (fscanf(stdin, "%d", &value) != EOF) avl_insert(&root, value); btree_walk(root); putchar('\n'); printf("%d\n", tree_height(root)); return 0; } int new_node(struct Avl **node, int value) { *node = malloc(sizeof(**node)); if (*node == NULL) return 0; (*node)->data = value; (*node)->balance = 0; (*node)->left = NULL; (*node)->right = NULL; return 1; } int avl_insert(struct Avl **tree, int new_item) { /* empty tree */ if (*tree == NULL) return new_node(tree, new_item); if (compare((*tree)->data, new_item) > 0) { /* Move left */ if ((*tree)->left != NULL) { if (avl_insert(&(*tree)->left, new_item) != 0) { /* Balancing act */ if ((*tree)->balance++ < 1) return (*tree)->balance; else if ((*tree)->left->balance > 0) { /* Case 1 */ rotate_right(tree); (*tree)->balance = 0; (*tree)->right->balance = 0; } else { /* Case 2 */ 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; } } else return 0; } else { new_node(&(*tree)->left, new_item); return ++(*tree)->balance; } } else if (compare((*tree)->data, new_item) < 0) { /* Move right */ if ((*tree)->right != NULL) { if (avl_insert(&(*tree)->right, new_item) != 0) { /* Balancing act */ if ((*tree)->balance++ < 1) return (*tree)->balance; else if ((*tree)->right->balance > 0) { /* Case 1 */ rotate_left(tree); (*tree)->balance = 0; (*tree)->left->balance = 0; } else { /* Case 2 */ 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; } } else return 0; } else { new_node(&(*tree)->right, new_item); return ++(*tree)->balance; } } return 0; } int compare(int a, int b) { if (a < b) return -1; else if ( a > b) return +1; else return 0; } void rotate_left(struct Avl **subtree) { struct Avl *save; struct Avl *node; node = *subtree; save = node->right; node->right = save->left; save->left = node; *subtree = save; } void rotate_right(struct Avl **subtree) { struct Avl *save; struct Avl *node; node = *subtree; save = node->left; node->left = save->right; save->right = node; *subtree = save; } void btree_walk(struct Avl *tree) { if (tree == NULL) return; btree_walk(tree->left); printf("%d ", tree->data); btree_walk(tree->right); } int tree_height(struct Avl *tree) { int left_height; int right_height; if (tree == NULL) return -1; left_height = tree_height(tree->left); right_height = tree_height(tree->right); if (left_height < right_height) return right_height + 1; else return left_height + 1; } あと、ヘッダファイルをつくって、構造体の宣言を入れておく。 /* insert_avl.h */ struct Avl { struct Avl *left; struct Avl *right; int balance; int data; }; コンパイルして、random.txt と badtree.txt とで確認。 $cc -c insert_avl.c $cc -o insert_avl insert_avl.o $./insert_avl < random.txt $./insert_avl < badtree.txt これ、最強 ... ですね。 2005-10-06 φ(-_-) ■[lang]はじめての C AVL木の削除。関数 avl_remove では再帰が使われてるが、引数に successor をとって る箇所がある。あまり安易にはいじれないみたいだ。 なので、削除するデータを含むノードを返り値とする検索関数をはさんでみた。 元にした search 関数はコチラ。 http://bal4u.dip.jp/algo/avlTree.txt /* delete_avl.c */ #include #include #include "avl.h" int new_node(); int avl_insert(); struct Avl *avl_search(); int avl_remove(); int compare(); void rotate_left(); void rotate_right(); void btree_walk(); int tree_height(); main() { struct Avl *root, *remove; int value; root = NULL; while (fscanf(stdin, "%d", &value) != EOF) avl_insert(&root, value); btree_walk(root); putchar('\n'); printf("%d\n", tree_height(root)); printf("removing item now > %d\n\n", DELETE); remove = avl_search(root, DELETE); avl_remove(&root, remove); free(remove); btree_walk(root); putchar('\n'); printf("%d\n", tree_height(root)); return 0; } int new_node(struct Avl **node, int value) { *node = malloc(sizeof(**node)); if (*node == NULL) return 0; (*node)->data = value; (*node)->balance = 0; (*node)->left = NULL; (*node)->right = NULL; return 1; } int avl_insert(struct Avl **tree, int new_item) { /* empty tree */ if (*tree == NULL) { return new_node(tree, new_item); } if (compare((*tree)->data, new_item) > 0) { /* Move left */ if ((*tree)->left != NULL) { if (avl_insert(&(*tree)->left, new_item) != 0) { /* balancing act */ if ((*tree)->balance++ < 1) return (*tree)->balance; else if ((*tree)->left->balance > 0) { /* Case 1 */ rotate_right(tree); (*tree)->balance = 0; (*tree)->right->balance = 0; } else { /* Case 2 */ 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; } } else return 0; } else { new_node(&(*tree)->left, new_item); return ++(*tree)->balance; } } else if (compare((*tree)->data, new_item) < 0) { /* Move right */ if ((*tree)->right != NULL) { if (avl_insert(&(*tree)->right, new_item) != 0) { /* balancing act */ if ((*tree)->balance++ < 1) return (*tree)->balance; else if ((*tree)->right->balance > 0) { /* Case 1 */ rotate_left(tree); (*tree)->balance = 0; (*tree)->left->balance = 0; } else { /* Case 2 */ 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; } } else return 0; } else { new_node(&(*tree)->right, new_item); return ++(*tree)->balance; } } return 0; } struct Avl *avl_search(struct Avl *tree, int key) { struct Avl *node; node = tree; while (node != NULL) { if (key == node->data) return node; if (key < node->data) node = node->left; else node = node->right; } return NULL; } int avl_remove(struct Avl **tree, struct Avl *old_item) { struct Avl *heir; int rv; /* Delete */ if (*tree == old_item) { if ((*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)->left->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; } int compare(int a, int b) { if (a < b) return -1; else if (a > b) return +1; else return 0; } void rotate_left(struct Avl **subtree) { struct Avl *save; struct Avl *node; node = *subtree; save = node->right; node->right = save->left; save->left = node; *subtree = save; } void rotate_right(struct Avl **subtree) { struct Avl *save; struct Avl *node; node = *subtree; save = node->left; node->left = save->right; save->right = node; *subtree = save; } void btree_walk(struct Avl *tree) { if (tree == NULL) return; btree_walk(tree->left); printf("%d ", tree->data); btree_walk(tree->right); } int tree_height(struct Avl *tree) { int left_height; int right_height; if (tree == NULL) return -1; left_height = tree_height(tree->left); right_height = tree_height(tree->right); if (left_height < right_height) return right_height + 1; else return left_height + 1; } random.txt から削除する数字を選んで、ヘッダファイルに入れておく。 /* avl.h */ struct Avl { struct Avl *left; struct Avl *right; int balance; int data; }; #define DELETE /* ← 削除するデータを記入 */ コンパイルして random.txt で確認。 $cc -c delete_avl.c $cc -o delete_avl delete_avl.o $./delete_avl < random.txt (追記) debian でうまくいかなかった件、単なるコードの写しまちがいでした。上のプ ログラムでダイジョウブだった ... (;_;) (05/10/8) (関数 compare の位置を、プロトタイプ宣言どおりに変更 - 他はいじってません)