「二分木 続き 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 以前、三省堂の小冊子「ぶっくれっと」に 掲載された文章です。日本での「酸化溝」方式の 下水処理施設には、余計なモノが 相当 くっついているみたいですね…