ランダム化BSTとスプレイ木はどちらも特殊な探索が線形時間となる可能性がある。そのため、根から外部節点への距離がすべて等しくなるような木構造を考える。2分探索木のノードに赤か黒の色をつけ、以下の条件を満たすものを赤黒木と呼ぶ ノードは赤か黒 根…

挿入時に左右の回転を使用して新たな節点を根にするという動作に加え、回転がある意味で木を平衡させるように根への挿入を修正する。 新しい節点を木のトップに持ってくる単純回転を使う代わりに、節点を根の孫の位置から木のトップに移動する二つの回転を行…

BSTの平衡化 次のプログラムは分割関数を使用しBSTを完全に平衡させる。中央値を根において分割し、部分木に対しても再帰的に分割を行う。 link balanceR(link h) { if (h->N < 2) return h; h = partR(h, h->N/2); h->l = balanceR(h->l); h->r = balanceR(…

根への挿入 BSTの標準的な実現では新しい節点は木の底だが、次のプログラムはトップに配置する。これを実現する為に、木に対して回転を行う。 右回転は根を右側におく。根の左リンクは回転前は根から左の個へ向いているが回転後は、左の子（新しい根）から古…

２分探索木で項目を移動せずに項目を見つけやすくするため索引（index）を使う。 例えば、配列の添字をBSTの項目として使用し、keyマクロを通して項目からキーが取り出せるようにする。 #define key(A) real key(a[A]).このやり方を拡張して、リンクを配列の…

挿入操作が高くつくという問題を解決する為に、記号表の実現に木構造を使用する。これによりsearch,insert, select, sort操作に対して高速な性能を持つアルゴリズムを開発できる。 用語の説明 節点は他の節点あるいは外部節点（リンクを持たない）を指すリン…

二分探索法は配列を用いた逐次探索に分割統治法を適用した探索手続きを用いること。次のプログラムは配列による記号表を二分探索で実現したもの。 #include <stdlib.h> #include "Item.h" #include "ST.h" static Item *st; static int N; void STinit(int maxN) { st </stdlib.h>…

次のプログラムは記号表を実現するのに、配列を使用するが空の項目はない。あたらしい項目を挿入する時は、挿入整列と同様にそれより大きな項目を一つずつ右に移動して配列を整列しておく。探索はすでに整列されている配列を操作するので、探索キーより大き…

記号表はキーをもつ項目からなるデータ構造。新しい項目を挿入する、与えられたキーを持つ項目を返すを提供する。記号表のインターフェースは以下の操作を行う必要がある。 insert, search, delete, select, sort,次のプログラムはキー添字配列に基づく記号…

非適応型の整列アルゴリズムを調べるための最も簡単なモデルは比較交換の操作だけでデータにアクセスする抽象マシーンである。このようなマシーンを整列ネットワークという。整列ネットワークは比較器を構成要素としてそれらを線で結合したもの。整列ネット…

シャッフル（完全シャッフルと完全逆シャッフル）と比較交換走査だけを使った整列法をBatcher奇遇マージソートという。 完全シャッフル ファイルの第一要素、次に後半部分の第一要素、次に前半部分の第二要素、後半部分の第二要素というように並べ、前半部分…

バイトを右から左へ調べていく整列法。安定性を優先する場合に使用する？プログラム10.4 LSD基数整列法 右から左に動いてワードの中のバイトに関してキー添字計数法を実現したもの。キー添字計数法は必ず安定であるように実現する。Rが2の時（byteswordとbit…

三分岐基数クイックソート クイックソートによりキーの先頭の文字でファイルを整列し、キーの残りについてこの方法を再帰的に適用する。この方法は文字列の整列に対して標準のクイックソートやMSD基数整列法より優れている。プログラム10.3 三分岐クイックソ…

2進クイックソートにおいて1ビットを分割に使うことは、キーを基数2の数（2進数）として扱い、最高位のビットから調べていくということである。上位のバイトから調べることによって基数Rの数を整列するにはR個の部分に配列を分割する必要がある。このように…

整列法において、キーを分解して一定の大きさ（バイト）の列と見なすという抽象に話を移す。2進数はビットの列であり、文字列は文字の列であり、10進数は数字の列であるというように見る。一時に数の一部分を扱う事に基づく整列法は基数整列法（radixsort）…

今までの順位キュー、ヒープのプログラムでは操作join, delete_the_maximum, insertが最悪の場合に能率よく実行できない。順序のないリストではjoin, insertは速いが、delete_the_maximumは遅い。順序のあるリストではdelete_the_maximumは速いがjoinとinser…

順位キュー キューを使用する多くの場合、必ずしも完全に整列している必要もなく、すべてのレコードが同時に必要になることもない。また、レコードの中で最大要素を処理し次にもっと多くのレコードを集めてその中で現時点での最大要素を処理することが多い。…

順位キューの中のレコードが配列に入っている場合、順位キューのルーチンは配列の添字を通して項目を参照するのが良い。プログラム9.11 添字の順位キュー ADTインターフェース クライアントは二つのレコードを比較するlessルーチンを用意する。less(i, j)の…

プログラム9.8 一級順位キュー ADT インターフェース typedef struct pq* PQ; typedef struct PQnode* PQlink; PQ PQinit(); int PQempty(PQ); PQlink PQinsert(PQ, Item); Item PQdelmax(PQ); void PQchange(PQ, PQlink, Item); void PQdelete(PQ, PQlink);…

プログラム9.7 ヒープソート forループでヒープを作成する。ヒープ作成後、whileループで配列の最後の要素と最大の要素を交換してヒープが空になるまでヒープを作り直す。これでa[1]が最小要素、a[N]が最大要素の配列が出来上がる。 void heapsort_pq(Item a…

マージソートで使う補助配列のための作業領域を使う代わりにリンクの為の作業領域を使う。マージソートはリンクリストと相性が良い。プログラム8.6 リンクリストの併合 link merge(link a, link b) { struct node head; link c = &head; while ((a != NULL) …

どの再帰的プログラムにもそれに対応する非再帰的プログラムがある。 大きさ15のファイルに対するマージソートを例にする。 以下の用に要素を併合していく。 1-1 1-1 1-1 1-1 1-1 1-1 1-1 2-2 2-2 2-2 2-1 4-4 4-3 8-71-1併合を７回、2-2併合を3回、2-1併合…

マージそーとのアルゴリズムを改良する 一つ目の改良はクイックソートで行ったように小さい部分ファイルには挿入ソートを使うようにする。 二つ目の改良は補助配列のコピーに使う時間を省く。二つのルーチンを用意して一方が入力をaux、出力をaに、他方が入…

全部理解できては無いけどマージソートの性質を以下に残しておきます。 性質1 マージソートは要素N個の任意のファイルを約NlogN回の比較で整列する。（説明) 併合のプログラムでは(N/2)-(N/2)併合がN回の比較で実行できる。整列全体の比較回数は以下の標準的…

マージソートはクイックソートに相補的であり、二つの再帰呼び出しの後で併合操作を行うもの。良い点として最悪の場合でもNlogNに比例する時間で整列できることがある。欠点として、Nに比例する作業領域が必要になる。2ウェイ併合 入力ファイルが二つありそ…

整列に関する重要な問題として必ずしも完全に整列する必要がなく、数の集合の中の中央値を求める事がある。 これにクイックソートの分割を利用する。 クイックソートは配列a[l],....,a[r]を並び変えてある整数iを返すとともにa[l],...,a[i-1]がiより小さいか…

重複したキーがある場合の対処として、ファイルを三つに分割し分割要素と比べ部分ファイルをそれぞれ小さい、等しい、大きいキーだけからなるようにする。 vより小さい vに等しい vより大きい l j i rこの実装法として以下の方法がある 左の部分ファイル内で…

改良1：挿入整列法 小さい部分ファイルに対してはクイックソートではなく挿入ソートを使用する。下のMはパラメータで大体5から25を選ぶ。この範囲内のMであればM＝1を選ぶより10%くらい実行時間が少なくなる。 if (r-l <= M) insertion(a, l, r); もしくは以…

クイックソートにスタックを使用する場合、スタックの大きさはlogNに比例する。しかし縮退する場合はスタックがNに比例して大きくなりうる。既に整列済みのファイルの場合最悪のケースになる。この問題を解決するため、二つの部分ファイルの大きさをチェック…

ここからクイックソートのお勉強 クイックソートの特徴 スタック領域を少ししか使わないのでその場で整列できる N個の項目の整列に平均約NlogN回の操作しか必要でない 内側のループが極端に短く書けること 安定でなく最悪の場合約N2乗に比例する回数の操作が…