二分木の できあがったプログラムが ないと、ブツブツいってても しかたないので、net で 捜してみた*1。 http://mrl.nyu.edu/~harper/code/binsearchtree.c (作者は Harper Langston) さっそく ダウンロード。 ついでに コンパイルしてみる。 $w3m - dump m…

C++ World の tutorial も、二分木のところを なんとか 訳し終えたので、ここ 10日ほどは 訳文のコピーを ひっくりかえしたり、脳内妄想(?)コードを メモったりしていた。 データから 二分木をつくる 簡単な コードを 書いて、コンパイル。 実行させると、い…

C の ライブラリ stdlib.h に、二分木検索のための bsearch 関数が 含まれてるのは 知ってたけど、比較的最近では*1 search.h という ヘッダファイルも 用意されている。 Standard C library 92年版には 載ってませんでした。 search.h で 定義されている 関…

E. Kasner の 「数学の世界」を 読むと、数学の言葉と 日常に 使われてる言葉との くいちがいについて 述べられている。 数学には group, family, ring, simple curve, limit などという やさしい言葉が たくさん でてきます。 ただ これらの言葉は、日常の…

7月11日分の 日記が まちがっていたので、削除しました。 訂正分は 次のとおりです。 以前 つくった クイックソートプログラムを 元にして、シェルソートの コードを 書いてみる。 http://www4.kcn.ne.jp/~yoitiro/hatena/knr2nd_4.txt はじめに shell_sort …

いつのまにか Vine Linux で 3.2 β4 が でている。 数日中にも 3.2 rc に 移行するらしい。 http://beta.vinelinux.org/ はねさんの Linux Personal Workstation でも 早速、3.2 に 対応できるよう テスト版で 追っかけています。 http://www.lain.org/wingl…

「二分木 続き 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]->dat…

「二分木 続き 11」 さて、skip list の 構築と 削除の 実際の algorithm ですが、ここが (一番) おもしろいところです。 もっとも 効率的とは いえませんが、これは もっとも シンプルなものの 1つです。 skip list の いいところの 1つは、それを 理解する…

家に どんな本が あるのか、整理していたのが やっと 終わった (5000冊以上 ?)。 本来なら いつでも 手に取れるところに 置きたいのだが、さすがに それは 無理のようだ。 興味あります ? → コチラ

「二分木 続き 10」 skip list は、ランダム数 = 乱数を 使うことで、効率のよい 構造を つくりあげる、確率的な - probabilistic - データ構造です。 その方法は、(以前 つくった) ランダムに構築する - randomized - 二分木と 同じく、乱数を その 挿入 al…

「二分木 続き 9」 int avl_remove(struct Avl **tree, struct Avl *old_item) { struct Avl *heir; int rv; /* Delete */ if (*tree == old_item) { if left == NULL && (*tree)->right == NULL) { /* No children, unlink the node */ *tree = 0; return 1…

「二分木 続き 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) { …

「二分木 続き 7」 AVL とは、この algorithm を 生みだした 2人の 数学者 Adelson-Velsky と Landies の 2人を 意味しています。 基本となる 考え方は、それぞれの ノードの 左の分肢の 高さと、右の分肢の 高さを 比べて、その差が 必ず 1 以内に 収まるこ…

「二分木 続き 6」 splay木では、root への 挿入の 変更 - modification - を 利用することで、どちらの 最悪の ケースとなる 可能性も 除くように 考えられています。 必要となる 変更は 最小限ですが、一番 効果的に なるよう、挿入と 検索ルーティンの 両…

「二分木 続き 5」 つりあいの とれた 二分木には、代表的なものが 3つ あります。 はじめの 2つは、この tutorial で 扱うことになる spray木と AVL木です。 もう 1つの red-black木ですが、この tutorial では、簡単な 説明だけに しておきます。 でも 多…

「二分木 続き 4」 データが ランダム順に 挿入されるのを 保証することで、二分木は 2つの 最悪のケースと なるのを 免れます。 これが、なぜ ランダム順での 入力を 試みたのかという (理由) なのです。 しかし、もし データが ランダムでは なかったとき…

「二分木 続き 3」 root の ノードが あると、どうして 木の つりあいを とることが できるんでしょう ? それは、分割 - partition - という トリックに あります。 木の ノードの どれかを 選んで、それを root の ノードに できるように したい、と します…

「二分木 続き 2」 二分木の つりあいを とる方法では、多くの 場面で、回転 - rotation - という 操作が 必要と なってきます。 回転は、ある分肢の root を、それ自体の もつ 分肢の root の 1つと、その役割を 切り替える - switch -ときに、実行されます…

「議論と その前提 覚え書 (2) 1st ver.」 憲法によれば、裁判所は - その実態は ともかくとして - 三権分立の 一翼を 担っている、いわば、権力機構の 一端で あるわけだ。 そして、戦前戦後を 通じ、 civil court の 立場に 立ったことは 一度も ない。 そ…

「二分木 続き」 二分木 2回目の tutorial では、前に 書いたことのある、木を 変質させる- degenerate - 2つの 最悪のケースを 回避するための、さまざまな 手法を 詳しく 調べることにしましょう。 先に 学んだ アルゴリズムでは、入力時に それが 十分 ラ…

宇井純「下水処理と日本式利権構造」1997 http://www.sanseido.co.jp/booklet/nankaitusin.html#3 以前、三省堂の小冊子「ぶっくれっと」に 掲載された文章です。日本での「酸化溝」方式の 下水処理施設には、余計なモノが 相当 くっついているみたいですね…

「二分木 9」 これまで 見てきた 二分木では、すべて、データ構造体の テキスト内で 定義が されています。 より 多くの 制御が 必要と なったとき、例えば、下に 動くだけでなく、双方向リストと 同じように、木の 上方にも 移動させたいことが あります。 …

[住基ネット] オープンロー(a)hatena で、山根さんが 青柳武彦氏の 論文を、やんわりと 批判している。 http://openlaw.g.hatena.ne.jp/s-yamane/20050710/p2 青柳氏には - ちょっと 大げさに いえば - 歴史的な 視点が 欠けていますね。 あちらの 論文を 引…

[判決文の公開] 「下級裁主要判決情報」という web page が あります。 地裁等が、自主的に 判決文を 公開した場合、リンクして 国民に 知らせるのが その 主旨の ようです。 http://courtdomino2.courts.go.jp/kshanrei.nsf/TOP 5月末の 金沢での 住基ネッ…

「二分木 8」 それぞれの 走査は、stack か queue の どちらかを 使うことで、再帰を 用いることなしに、実行させることが できます。 一つの やり方として 反復版で inorder 走査を 書いてみましょう ▽ void tree_walk(struct Node *tree) { struct Node *n…

「二分木 7」 構築したり、二分木から 要素を 削除する 基本的な 操作は 手に入れました。 また、木に 要素が あるかどうかを 調べる コードも あります。 さて、あると 考えたものが、実際に あるのかを、はっきり 確かめる 必要が ありますよね。 それは、…

「二分木 6」 さてと 二分木を つくる コードも できたし、同じように、木から ノードを 削除できれば、というのは いい 考えですね。 これは より こみいった 作業です。 というのも、当てはまる ノードを 見つけた後で、処理に 3つの ケースが あるからで…

ふと 思いたって、戴震*1 のことを google で 検索していて、子欲居さんの page を 見つけた。 ただし 2001年以後 更新が 止まってるようで、リンク先の page も 削除されているところが 多い。 http://members.at.infoseek.co.jp/sumicom/ ただし、その発言…

「二分木 5」 木 - tree - への 挿入は、上の 検索と ほぼそのまま 同じになります。ただ 一つ 違ってるのは、null ノードが 見つかったときに、失敗時に 要求された 返り値をもつ 新しい (ノードを) 1つ 挿入することです ▽ int tree_insert(struct Node **…

「二分木 4」 さて、ノードを 1つ つくるための コードを 書かないといけませんね。それには、新しい ノードが 二分木へと リンクできる 必要が あります。 初めに 注意することの 一つは、木には いくつかの 検索形式を 含む、多くの 操作方法が あるという…