基本１

ADT（抽象データ型）

ADT（Abstract Data Type）とは、具体的な実装は定義されておらず、単にどのような操作を持つかということのみが定義された抽象的なデータ型である。例えば、スタックというADTはpush、popという操作を持つデータ型であるが、具体的な実装は規定されていない。他に、リスト、セット、辞書、キュー、ツリー、グラフなどもADTである。

例えばマップは、キーとそれに対応する値のペアを持ち、挿入（insert）、削除（delete）、検索（find）などの操作を持つADTだが、具体的な実装方法は規定されておらず、GoやPythonでは内部的にはハッシュテーブルを用いて実装されているのに対し、C++では平衡二分探索木（赤黒木）を用いて実装されている。

対してデータ型は、データの内部表現や操作方法がプログラミング言語やユーザーによって明確に定義されたデータ型である。例えば、int、float、charなどの基本データ（primitive）型や、配列、構造体、クラスなどの複合データ型、列挙型（Enum）などがデータ型であると言える。

配列

数値配列と非数値配列、文字列

C++やRustでは、行列（matrix）との対比で、（１次元）配列のことをベクトル（vector）とも呼ぶ。データの追加や削除などの操作を持ち、特に末尾にデータを追加する操作をpush-back、末尾からデータを取り出す操作をpop-backと呼ぶ。

各操作の時間計算量は、ランダムアクセスは$O(1)$、末尾への追加/削除は$O(1)$、先頭・途中への追加/削除は配列の要素をずらす必要があるため最悪$O(n)$かかる。

基本データ型としての配列型とクラスとしての配列型の２種類がある。基本データ型としての配列型はCの配列のように単なるアドレスでしかなく、対してクラスとしての配列型にはさまざまなメソッドが定義されており、基本データ型としての配列型をより便利に操作できるようにしたラッパーとなっている。

クラスとしての配列型には容量（capacity）というパラメータを指定でき、例えば要素は３つしか入っていないが、容量は８になっている場合などある。容量を超える要素を格納する必要がある場合は、新しくより大きい領域を用意して、すでにある要素をそこにコピーする必要がある。

新しい領域を用意する際に容量を１つしか増やさないとすると、要素の数が$n$個の場合、$n-1$回のコピーが必要になる。つまり$n-1$個の要素を追加する場合は合計で$0 + 1 + 2 + ... + n-1 = \frac{(n-1) \times n}{2}$回のコピーが必要になるため、$O(n^2)$の計算量がかかってしまう。

容量を倍ずつ増やすとすると、例えば$n = 5$のとき、2個目の要素を追加する際にダブリングが生じてすでに存在する1個の要素をコピーする必要があり、次は3個目の要素を追加する際にすでに存在する2個の要素をコピーする必要があり、その次は5個目の要素を追加する際にすでに存在する4個の要素をコピーする必要があるので、合計で$1 + 2 + 4 = 7$回のコピーが必要になる。つまり、合計で$n \text{以上の最小の2の累乗数} - 1$回のコピーが発生する。そのため１回あたりのコピーにかかる平均時間は$O(1)$であり、償却定数時間になる。このように、配列の容量を倍ずつ増やすことをダブリング（doubling）と呼ぶ。

オブジェクトの参照のみをコピーする（参照先オブジェクトは同じものを指す）ことをshallow copyと呼び、オブジェクトの実体もコピーすることをdeep copyと呼ぶ。配列をコピーする際に、配列の要素がポインタやオブジェクトの参照である場合は、その参照先のオブジェクトはコピーされないため、配列のコピーはどちらかというとshallow copyであると言える。

LeetCode - Is Subsequence

１次元配列（ベクトル）と多次元配列（行列）

多次元配列を表現する方法としては、単純に連続したメモリ領域に全ての要素を並べる方法（data[2][2]なら0-0, 0-1, 1-0, 1-1が連続したメモリ領域に並ぶという感じ）と、配列の中に配列のポインタを並べる方法がある。

プリミティブなやり方は、連続したメモリ領域に全ての要素を並べる方法であり、C/C++でも使われている。この方法のメリットとしては、領域を割り当てるときに一気に領域を確保できることや、ある範囲のデータを一気にコピーするという方法を取りやすいことが挙げられる。一方で、全ての配列を同じ長さにする必要があるというデメリットがあり、一方でポインタを使う方法は各配列の長さを自由に設定できるというメリットがある。

連続したメモリ領域に全ての要素を並べる方法には、行優先（row-major order）と列優先（column-major order）の２種類がある。行優先の場合は行ごとに順にアクセスするとメモリ上ではシーケンシャルなアクセスになる。一方で列優先の場合は列ごとに順にアクセスするとメモリ上ではシーケンシャルなアクセスになる。C/C++、Go、Numpyなどは行優先であり、Fortran、Matlab、Rなどは列優先である。ポインタを使用する方法では、iliffe vectorと呼ばれるデータ構造が用いられており、Java、C#、Scala、Swiftなどがこれを採用している。

行優先やiliffe vectorは、行列の要素を連続したメモリ領域に並べるため、行ごとにアクセスするとキャッシュヒット率が高くなる。列優先は列ごとにアクセスするとキャッシュヒット率が高くなる。

多次元配列のメモリレイアウト方式について

具体的には、例えばCで下記のような２次元配列を宣言した場合、メモリ上では1, 2, 3, 4, 5, 6, 7, 8, 9の順に並ぶ。要素へアクセスする際は行と列のインデックスを指定するが、内部的には１次元配列として扱われているため、$\text{行列のベースアドレス} + \text{行インデックス} \times \text{列数} + \text{列インデックス}$のようにしてアドレスが計算される。

int matrix[3][3] = {
  {1, 2, 3},
  {4, 5, 6},
  {7, 8, 9}
};

LeetCode - Zigzag Conversion

レコード、構造体、タプル、オブジェクト

レコードは、構造体や複合データとも呼ばれ、データベースでは行と呼ばれる。フィールドの集まりであり、通常は固定の数と並びのフィールドから成り、配列と違って各フィールドのデータ型は異なってよい。各フィールドには名前が付いており、それによってデータにアクセスする。

レコードのフィールドは、言語によってはメンバーあるいはメンバー変数と呼ばれることもある。レコードの専用構文がない言語であっても、クラス構文をサポートする場合は、ほとんどの場面においてクラスで代用可能である。例えばJavaにはレコード型があるが、内部的にはクラスで実現される糖衣構文（syntax sugar、読み書きのしやすさのために導入される書き方）である。

タプルでは、含まれる要素が同じでも要素の順番が異なる場合は別の値として扱われる（(1, 2)と(2, 1)など）。構造体はより意味のある形の要素の集合というニュアンスを持つが、タプルは単なる要素の寄せ集めというニュアンスを持つ。タプルは配列とは違って順序対で、含まれる要素が変化しないというニュアンスを持たせたいときに使う。ただその場合にも配列を使う人もいるので、そこまで厳密に使い分けられているわけではない。２要素の時は2-tuple、３要素の時は3-tuple、n要素の時はn-tapleと呼ばれる。

オブジェクトはメソッドを持つことができる。言語によってはクラスと呼ばれることもある。また文脈によってはインスタンスやクラスなどをまとめてオブジェクトと呼ぶこともある。

連結リスト

何個データが来るかわからなくて、どこにデータを挿入するかわからないという場面で使われる。今でもよく使われているデータ構造で、他のデータ構造の内部構造として連結リストが使われていたり、Linuxカーネルの中の構造体でよく連結リストが使われていたりする（ユーザーが何個プロセスを立ち上げるかはわからないし、ページアロケーションなどや、ハッシュテーブルなどでも使われる）。

各操作の時間計算量は探索が$O(n)$、挿入/削除が$O(1)$だが、削除の場合はその前に探索が必要であり、挿入の場合も重複を避けるために探索が必要になることが多い。先頭に要素を追加する操作については$O(1)$でできる。前のオブジェクトにアクセスすることは絶対ないとかでなければ、末尾の要素にすぐにアクセスしたい場合も多いので、普通は双方向循環連結リストを使う。

リストを使う場合、データの移動はポインタの付け替えだけで済むため、配列に比べて容易である。このことを利用して探索を高速化する方法をとるリストのことを自己再構成リスト（self re-organizing list）と呼ぶ。例えば実際の状況では、短い時間に繰り返し同じノードにアクセスが行われるこ場合が多いため、探索によってノードを見つけてくるたびにそのノードをリストの先頭に移すという方法が取られることがある。これにより通常は平均的に$\frac{n}{2}$回の探索が必要なところをより少ない回数で済むことが期待できる。

関数型言語では連結リストの実装時にCARやCDRなどが使われる。連結リストのノードをコンスセルと呼び、コンスセルにはCARとCDRという２つのフィールドがある。CARに要素が格納され、CDRに次のコンスセルへのポインタが格納される。最後のCDRにはポインタではなくnilが格納されることでリストの終端を表す。

CARとCDR 【AutoLISP】car部とcdr部を取得する関数「car」「cdr」

LeetCode - Linked List Cycle

スタック

push/popの時間計算量は$O(1)$である。典型的には配列を使って実装される。ただし、連結リストを使う場合もあり、例えばリアルタイムシステムではある一定の時間内に処理を終わらせる必要があるので、その場合はダブリングが起こってしまう配列よりも、連結リストが使われる。

例えば算術式の評価をスタックを用いて行うことができる。$4 \times 7 - (5 + 3)$という数式があるとき、これを逆ポーランド記法にすると$4 7 \times 5 3 + -$になり、順にスタックに積んでいくことで、最初に4と7が積まれ、$\times$が来たら4と7をpopして計算した結果（28）を積んで、次に5と3が積まれ、$+$が来たら5と3をpopして足して結果（8）を積み、最後に$-$が来たら積まれている数（28と8）をpopして引くことで結果を求めることができる。

LeetCode - Valid Parentheses

キュー、デック

キューは、末尾に要素を追加するエンキュー（enqueue）という操作と、先頭から要素を取り出すデキュー（dequeue）という操作を持つ。どちらも$O(1)$の時間計算量で実行できる。

キューを配列を用いて実装する場合、先頭からpopするたびに残りの要素を前に移していくようにしてしまうと$O(n)$の時間計算量になってしまうため、先頭と末尾が論理的に繋がっているデータ構造であるリングバッファを用いることが多い。例えば[a, b, c, d]とあるとき、popしたら[nil, b, c, d]となり、先頭を指すポインタをbを指すように変更し、次にeがpushされたら先頭を指すポインタがbを指したまま[e, b, c, d]となる。次にfがpushされたらダブリングされて[b, c, d, e, f]となる。このようにすることでデキューを$O(1)$で実行できる。またはスタックを２つ使うことで同様のことを実現できる。

デック（deque）は両端キューとも呼ばれ、両端から要素の追加および削除ができるデータ構造である。双方向連結リストか、両方向に成長できる動的配列を使って実装されることが多い。どちらも先頭と末尾に対する挿入/削除は$O(1)$の時間計算量になる。両方向に成長できる動的配列は、リングバッファを使うか、配列の真ん中から要素を配置する方法で実装されることが多い。

LeetCode - Implement Queue using Stacks

プライオリティキュー

探索操作を必要とせず、最小値（または最大値）を取り出す操作と挿入、削除のみを行うデータ構造をプライオリティキュー（優先順位付き待ち行列）と呼ぶ。挿入と削除と最小値（または最大値）を取り出す操作はすべて$O(\log n)$で実行できる。プライオリティキューは平衡木やB木でも実現できるが、これらを用いるのはやや大袈裟で、通常は探索の必要がないのであれば部分順序付き木やヒープなどで実現できる。特にヒープベースプライオリティキューがよく使われる。

例えば平衡木を用いてプライオリティキューを実現する場合、木の右端（または左端）のノードをとれば$O(\log n)$で最大値（または最小値）を求めることができ、その値を木から取り除いた後で木をバランスさせるための作り替えも$O(\log n)$でできる。しかし、この方法では最大値を取る操作ばかりを行うので、木は常に同じ方向に偏ろうとし、バランスを取り戻すための操作が頻繁に行われることになるため、オーダー自体は$O(\log n)$だがあまり効率的ではない。このように平衡木などを使えば、与えられた値を探す探索や、削除、最大値（または最小値）を求める操作を全て$O(\log n)$でできるが、このような構造は贅沢であり、効率が悪くなる。

同じ二分木であっても、ノードの間に成立する大小関係の式を変えることによって、最大値（または最小値）だけを効率よく求めるデータ構造が得られる。最大値（または最小値）をルートに置き、各ノードの値がその左右のどちらの子ノードの値よりも小さく（または大きく）ならないようにすることで、最大値（または最小値）を求めるだけの操作なら（ルートを取り除き木の再構築をしないなら）$O(1)$で行うことができる。このようなデータ構造を部分順序付き木（partially ordered tree）と呼ぶ。

二分探索木と部分順序付き木は大小関係の式を横方向に持つか、縦方向に持つかの違いがある。二分探索木の場合は、ノードの左に小さな値、右側に大きな値を持つのに対し、部分順序付き木の場合は縦方向に大小関係のわかっている値を並べる。各ノードの値はその下の左右の子ノードの値よりも大きい（または小さい）が、左右の子ノードの値の大小関係はわからない。そのため、一方の子ノードの値が他方の孫ノードの値より小さい（または大きい）ということも起こりうる。二分探索木は任意のノード間の大小関係を改めて比較しなくても木の形だけからわかるが、部分順序付き木は直系の関係にあるノード間の大小関係しかわからない。情報量が少ないということだが、それだけ管理の手間が省けるため、効率が良くなる。

部分順序付き木では、ルートにある最大値（または最小値）を取り除いた後、再び部分順序付き木の条件を満たすように木を作り直す必要がある。そのためには左右の子ノードのうち値の大きい（または小さい）方を新たにルートに移し、その子ノードのいた場所にも同様に左右の子ノードのうち値の大きい（または小さい）方を移すという操作を繰り返していき、これを木の一番下の段に達するまで続ける。

部分順序付き木は、プライオリティキューを実現する１つの選択肢にはなるが、まだ複雑すぎる。特にポインターを使って木を表現するために余分の記憶域を必要とし、またルートを取り除いた後の組み替え操作を木の左右のバランスを考慮せずに行うので、バランスを崩し、挿入や削除の計算量が増えてしまう可能性がある。そのため、プライオリティキューを実装する際はこれらの欠点が解消されたヒープ（後述）がよく使われる。

ただし、ヒープを使う場合は２つのプライオリティキューを合併して１つの大きなプライオリティキューを作る操作（２つの集合の集合和に当たる）を効率よく行うことができない。これを効率よく行う方法がいろいろと考えられているが、これらの方法の多くが普通のポインタを使ったデータ構造で部分順序付き木を使う。しかしこの場合は前述したように左右のバランスをいかにして確保するのかが問題になる。

なお、普通の二分探索木も、各要素の挿入の順序の観点から見ると親の方が子よりも古いという関係が成り立っているため、挿入順序を値と見れば部分順序付き木と言える。

ハッシュテーブル、マップ

ハッシュテーブルについては説明が長くなってしまったので、別ページにまとめた。

LeetCode - Two Sum

グラフ

グラフの種類

有向（directed）グラフとは、エッジ（辺）に方向があるグラフで、エッジは一方向にのみ進むことができる。対して、無向（undirected）グラフとはエッジに方向がないグラフであり、エッジは両方向に進むことができる。

巡回（cyclic）グラフとは、少なくとも１つの閉路（サイクル）が存在するグラフであり、非巡回（acyclic）グラフとは、閉路が１つも存在しないグラフである。

連結（connected）グラフとは、任意の２つの頂点間に経路が存在するグラフであり、非連結（disconnected）グラフとは、少なくとも１組の頂点間に経路が存在しないグラフである。

重み付き（weighted）グラフとは、エッジに重み（コスト）が割り当てられているグラフであり、非重み付き（unweighted）グラフとは、エッジに重みが割り当てられていないグラフである。

ノード数に比べてエッジ数が比較的少ないグラフを疎グラフ（sparse graph）、対してエッジ数が比較的多いグラフを密グラフ（dense graph）と呼ぶ。

グラフの表現方法

グラフを表現する方法として、隣接リストと隣接行列の２つがよく使われる。隣接リストとは、それぞれの頂点が隣接する頂点のリストを保持するデータ構造である。対して隣接行列とは、頂点間の接続を２次元配列（行列）で保持するデータ構造である。行と列が頂点を表し、セルの値がエッジの存在や重みを表す。

例えば、下記のようなグラフがあるとき、隣接行列で表現するには、この場合は頂点０と頂点１は直接繋がっており、コストが10なので、表では{0, 1}と{1, 0}の値は10になっているのがわかる。また頂点０と頂点３のように直接繋がっていない場合は値は$inf$となっているがわかる。

グラフ

隣接行列

隣接リストはメモリをあまり使わないため、特にエッジの数が少ない疎グラフ（sparse graph）に対して有効であり、隣接頂点の列挙が容易である。ただ、エッジの存在を確認するのにリストの探索が必要であり、時間がかかるという欠点がある。

隣接行列はエッジの存在を$O(1)$の時間計算量で確認可能であり、エッジの重みも簡単に管理できる。ただ、メモリを多く使うのと、隣接頂点を列挙するのに時間がかかるという欠点がある。

隣接行列の乗算

隣接行列表現の場合は行列の乗算をすることができる。一般的に、隣接行列を$n$乗することで、グラフ内の各頂点間の長さ$n$のパスの数を得ることができる。例えばある非重み付きグラフの隣接行列を２乗すると、2歩で到達できる頂点の数を表す行列が得られる（行列の乗算のやり方については行列の積（掛け算）の求め方をわかりやすく解説します！を参照）。

例えば、下記のような非重み付きグラフの隣接行列があるとする。ここで1はエッジが存在することを表し、0はエッジが存在しないことを表す。

$A = \begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}$

この隣接行列$A$の2乗を計算すると、行列$A^2$の各要素$(i, j)$は、頂点$i$から頂点$j$への長さ2のパスの数を表す。

例えば、下記のように実際に計算してみると、結果の行列$A^2$では、例えば要素$(0, 2)= 1$であるため、頂点0から頂点2への長さ2のパスが1本存在することが分かる。

$$A^2 = A \times A = \begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix} \times \begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$$

木

木の走査

走査の手順としてよく使われるのは、前順走査（pre-order traversal）、間順走査（in-order traversal）、後順走査（post-order traversal）の３つである。前順走査は親ノードを調べてから子ノードを調べ、間順走査は最初の子ノードを調べてから親ノードを調べて残りの子ノードを調べ、後順走査は子ノードを全部調べてから親ノードを調べる。前順走査、間順走査、後順走査は全てDFSである。

ルートから全てのノードを反時計回りするように一筆書きしたとき、前順走査はノードの左側を通った順番、間順走査はノードの下側を通った順番、後順走査はノードの右側を通った順番になる。詳細はうさぎでもわかる2分探索木　後編　2分探索木における4つの走査方法を参照。

前順走査は数式の構文木からポーランド記法の表現を求める際に利用されることがある。二分探索木を間順走査すると、ちょうど昇順ソートされた順にノードを訪れることになるため、間順走査を使うことで二分探索木を使ってデータをソートすることができる。後順走査はノード全体を順番に削除するような処理を行う際に、リーフノードから順に削除できるため利用されることがある。

実装例

二分探索木、$n$分探索木

線形探索の場合、連結リストを使えば、挿入は$O(1)$で実現できるが、探索は$O(n)$かかる。一方で、二分探索の場合、配列を使えば、探索は$O(\log n)$で実現できるが、挿入は$O(n)$かかる。つまり配列や連結リストのような単純なデータ構造を使っている限り、挿入か探索のどちらかの計算量が$O(n)$になることは避けられない。探索、挿入、削除の全てを$O(\log n)$以下の計算量で処理するにはデータ構造を工夫する必要がある。その１つに二分探索木がある。

二分探索木は、各ノードが最大２つの子ノードを持つ木構造であり、各ノードの左部分木の値はそのノードの値よりも小さく、右部分木の値はそのノードの値よりも大きいという性質を持つ。この性質により、探索、挿入、削除の全てを平均$O(\log n)$の計算量で実現できる。

計算量の点で理想的なのは、ルートからリーフまでの距離がどこでも等しくなっている二分木である。これを完全二分木と呼ぶ。一方で、最悪なのはどのノードにも子ノードが１つしかない場合であり、この場合の探索の計算量は$O(n)$になる。そのため二分探索木の探索は、最善計算量$O(\log n)$、最悪計算量$O(n)$である。平均計算量についてはここでは証明することは難しいが、$O(\log n)$になることが知られている。

LeetCode - Invert Binary Tree

平衡木（バランス木）

前述したように二分探索木による探索は最悪の場合は$O(n)$になる可能性があるため、これを解消するために、二分探索木が偏った形になったら左右のバランスが取れた形に直すことで性能を向上させる平衡木（バランス木）と呼ばれるデータ構造がある。

木の左右をバランスさせることが望ましいが、木を作り直すのに時間がかかりすぎては意味がない。木の作り直しは、データの挿入や削除の際に行われるため、その計算量が$O(\log n)$以下であることが望ましく、$O(n)$になってしまうと二分木を使わずに配列を使って二分探索を行う方が良くなってしまう。

二分探索木で最も効率が良いのは完全二分木だが、常に木を完全二分木の形に保つのは木の作り直しに最悪$O(n)$の計算量がかかるため、望ましくない。そのため、完全にバランスさせるのではなく、適度にバランスさせつつ、挿入や削除の計算量を$O(\log n)$以下に抑えることができる平衡木が使われる。

左右の部分木の高さの差が正の定数$k$以下であるような平衡木を、高さ平衡木（height balanced tree）と呼ぶ。$k$としてどの程度の値を取れば良いかについては様々な研究がある。

左右の部分木のノード数の比を一定限度以内に制限することでバランスを取るという考えもある。これを重さ平衡木（weight balanced tree）という。重さ平衡木は、部分木に含まれるノード数やそのノードのデータの出現頻度をもとに重さを決め、その重さを基準に、AVL木と同様に１重回転と２重回転を使って木をバランスさせるため、各ノードのデータの出現頻度まで考えに入れて探索の効率向上を目指す際には、重さ平衡木が有利である。

アルゴリズム	探索（平均）	探索（最善）	探索（最悪）	挿入	削除	構築	空間計算量	Pros	Cons
AVL木	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$	$O(n \log n)$	探索は平均・最悪の場合の両方で二分探索木や赤黒木よりも速い	挿入や削除は遅い
赤黒木	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$	$O(n \log n)$	AVL木より挿入や削除が速い	探索はAVL木より遅い
ヒープ	-	-	-	$O(\log n)$	$O(\log n)$	$O(n)$	$O(n)$	最大値（または最小値）の取り出しが効率的（オーダー自体は同じ）	探索はできない

AVL木

どのノードにおいても左右の部分木の高さの差が1以下であるような二分探索木をAVL木と呼ぶ。AVL木は最初に考案された平衡二分探索木で、挿入や削除の際に木の再構築を行うことでバランスを保つ。二分探索木であることに変わりはないので、探索についてはすでに前述したとおりである。そのためAVL木の制約により、探索の最悪計算量は$O(\log n)$に収まる。挿入や削除の際に制約を満たすために木の回転を行うが、この回転に要する時間は$O(1)$であるため、木の高さは$O(\log n)$であることから、挿入や削除の計算量は$0(\log n)$に収まる。理論的な観点からは、探索と挿入を同時に$O(\log n)$の計算量で処理できることを初めて示した点でAVL木の価値は大きい。AVL木の構築は挿入操作を$n$回繰り返すことでできるため、計算量は$O(n \log n)$である。

AVL木は最悪の場合、理論上は完全二分木の1.44倍の高さになり、つまり完全二分木と比べて探索が1.44倍遅くなる可能性があるわけだが、実際はこれほど高くなることは少なく、ほとんどの場合は同じ個数のノードからなる完全二分木の高さより１だけ高い程度で収まることが知られている。つまり、AVL木の制約条件を守ることで、ほとんど完全二分木と同じ探索性能を得られる。

また、ランダムなデータを与えたときのAVL木の振る舞いを調べた実験があり、それによると挿入の際に回転操作が必要になる確率は約47%で、このとき１重回転が使われる確率と２重回転の確率はほとんど同じである。削除は１回の操作で回転が繰り返される可能性がある分だけ挿入よりも大変に見えるが、実験的評価では逆の結果が出ており、削除の際の回転の回数は、削除の回数の約21%である。

このことから、AVL木は探索に要する計算量が平均的にも最悪の場合にも普通の二分探索木より少なく、また挿入や削除には余分な手間がかかるが、計算量のオーダーは変わらないため、十分実用的なアルゴリズムだと考えられる。特に挿入や削除に比べて探索の回数が多い場合に特に適しているアルゴリズムだと言える。挿入や削除が多い場合には単純な二分探索木とどちらを採用すべきかは一概には決められない。

AVL木は、赤黒木に比べて平衡性についての条件が厳しいため、探索は速くなるが、一方で最悪のケースを想定すると挿入や削除の際の回転操作の回数が赤黒木より多くなってしまう。

LeetCode - Balanced Binary Tree

赤黒木

赤黒木はAVL木よりも平衡性についての条件が緩いため、探索は遅くなるが、挿入や削除は速くなる。赤黒木は常におおよそ平衡な状態を保ち、探索、挿入、削除の各操作を最悪の場合でも$O(\log n)$の時間で実行できる（木の構築はAVL木と同様に$O(n \log n)$）。そのため、リアルタイムシステムのような時間センシティブなアプリケーションにおいて価値があるのと、最悪のケースを保証する他のデータ構造における価値ある部品となっている。例えば、計算幾何学で用いられる多くのデータ構造は最悪のケースでの計算量を保証する必要のあるため赤黒木をベースとしているし、LinuxカーネルのCFS（Completely Fair Scheduler）も赤黒木を使用している。

赤黒木

ヒープ

ヒープは部分順序付き木を配列上に表現したデータ構造であり、ノード同士の親子関係をポインタを用いずに、要素の添字の間の算術的な関係によって表す点が大きな特徴である。そのためヒープの構築は$O(n)$でできる。人によってはヒープという言葉を一般の部分順序付き木を指すのに使うこともある。ヒープは配列を用いて表現されるという特性上、常に完全二分木になる（ここでは二分ヒープを前提としている）。最大値（または最小値）を取り除いた後、末尾の要素を先頭に持ってきて、部分順序付き木の条件を満たすように親子を入れ替える操作を行う。挿入の場合は、要素を末尾に追加し、同様に条件を満たすように親子を入れ替える。

各操作の計算量についての詳細は前述のプライオリティキューの項目を参照。

ちなみに上から下に親子を入れ替える場合は、すべての子ノードとの値の比較が必要だが、下から上に親子を入れ替える場合は、親ノードとの値の比較だけで済む。そのため、下から上に親子を入れ替える操作が多くなる場合は、二分木ではなく$d$分木のヒープを用いることで計算量のオーダーを下げられる場合がある（その代わり上から下に親子を入れ替える操作の計算量は増える）。具体的には、上から下に親子を入れ替える操作の計算量は$O(d \log_d n)$になるのに対し、下から上に親子を入れ替える操作の計算量は$O(\log_d n)$になる。

Top K Frequent Elements - LeetCode

セット

セット（集合）は順序と重複のないデータの集まりを表現するADTである。ただし何をもってデータが同一であるとみなすかは使用する比較関数の実装依存である。例えば大文字と小文字を区別するなら"HOGE"と"hoge"は同一と見做せるし、区別しないなら異なるデータと見做せる。

重複するデータを処理する方法はいくつかあり、狭義のセットでは無視するか、新しいデータで置き換える。一方でマルチセット（多重集合）と呼ばれるものがあり、その場合はデータの重複が許容される。マルチセットは、データの出現回数をカウントする際などに使われ、Javaなどで定義されている。

他にもデータの順序を保持する順序集合（ordered set）と、データの順序を保持しない非順序集合（unordered set）がある。順序集合は、データの挿入順序やソート順序を保持する。順序集合は木構造を使って実装されることが多く、非順序集合はハッシュテーブルを使って実装されることが多い。

探索アルゴリズム

ここでは示さないが、比較のみを使った探索ではどんなにアルゴリズムを工夫しても$O(\log n)$の最悪時間計算量を要する。ハッシュを使った探索などの比較を伴わない探索についてはその限りではない。

線形探索

探索が失敗する場合は$n$回、成功する場合は平均$n / 2$回の探索が必要である。いずれにしても計算量は$O(n)$である。

二分探索

探索の時間計算量は$O(\log n)$である。ただし、二分探索はソートされた配列に対してのみ有効であるため、ソートするためにかかる時間計算量を考慮すると、最悪計算量は$O(n \log n)$になる。二分探索の実装についての詳細は別ページを参照。

LeetCode - Binary Search LeetCode - First Bad Version

知識なし深さ優先/幅優先探索

知識なし探索（uninformed search）とは、与えられた探索空間の性質について特別な知識がないことを前提とした探索である。幅優先探索（BFS）や深さ優先探索（DFS）などがuninformed search algorithmに該当する。

実際は深さの方が幅よりも小さいことが多く、BFSの方がよりメモリを使うことになるため、DFSの方がBFSよりも空間計算量は良くなる。一方で、地球から近い住める惑星を探すとなったとき、DFSだと深さが終わるまで探索が一向に終わらないという事態に陥る可能性がある。BFSの良いところは答えが複数ある場合は、一番rootに近い（深さが浅い）答えを見つけることができることである。

深さ優先で探すが、例えば距離２まで探して見つからなかったら戻り、全部探索し終えたら次は距離３まで探すみたいなことをするのが反復深化（Iterative Deepning）探索である。BFSではなくDFSを使っているのであまりメモリを使わずに、かつBFSのように一番深さが浅い答えをDFSで求めることができるという利点がある。

一般的な二分木を探索する場合、ノードの数を$n$とすると、BFSとDFSの時間計算量はどちらも$O(n)$になる。また空間計算量は、木の最大の高さを$h$、最大幅を$w$とすると、DFSは$O(h)$、BFSは$O(w)$になる。平衡二分木の場合、$h = \log n$、$w = n / 2$である。

ソートアルゴリズム

ここでは示さないが、データ同士の比較を利用してソートを行う限り、どんなにアルゴリズムを工夫してもソートには$O(n \log n)$の最悪時間計算量を要することが証明できる。そのため、基本的にはソートアルゴリズムは$O(n \log n)$が最悪時間計算量のオーダーとしては最速である。

インプレースアルゴリズムとは、入力サイズに比例した追加の記憶域を必要とせずに（データ構造の別のコピーを作成せずに）入力をその場で変更するアルゴリズムである。インプレースでないアルゴリズムは、非インプレースまたはアウトオブプレースと呼ばれる。ここで紹介する主要なソートアルゴリズムの中では、マージソートとマージソートを利用するティムソートのみがインプレースでない。

安定（stable）ソートとは同じ値を持つ要素の相対的な順序がソート後も保持されるソートであり、不安定（unstable）ソートとは同じ値を持つ要素の相対的な順序がソート後に変わる可能性があるソートである。挿入ソート、マージソート、ティムソートは安定ソートであり、選択ソートとクイックソートとヒープソートは不安定ソートである。

アルゴリズム	最悪計算量	平均計算量	最良計算量	空間計算量	最悪空間計算量	インプレース	安定性	Pros	Cons
挿入ソート	$O(n^2)$	-	$O(n)$	$O(1)$	$O(1)$	YES	安定	ソート済み・小さいデータセットに対して高速	ランダム・大きいデータセットに対して遅い
選択ソート	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	$O(1)$	YES	不安定	メモリ使用量が少ない	遅い
クイックソート	$O(n^2)$	$O(n \log n)$	$O(n \log n)$	$O(\log n)$	$O(n)$	YES	不安定	多くの問題に対して最高速	最悪計算量が$O(n^2)$になる可能性がある
マージソート	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	$O(n)$	NO	安定	外部記憶装置上のデータ・連結リストのソートに適している	必要な作業用の記憶域が多い
ティムソート	$O(n \log n)$	$O(n \log n)$	$O(n)$	$O(n)$	$O(n)$	NO	安定	実際のデータに対して効率的	ランダムなデータに対してはクイックソートより遅い
ヒープソート	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	$O(1)$	YES	不安定	計算時間の変動が少なく、インプレース	クイックソートやマージソートより遅い

挿入ソート

挿入ソートは、自分の値とそれより前の値を比較して、適切な位置に挿入していくアルゴリズムである。最悪計算量は$O(n^2)$になるが、ソート対象がほとんどソートされている場合は内側のループを回る回数が少なくて済むので、時間計算量は$O(n)$に近づく。実際のデータはほとんどソートされている場合が多く、その場合に挿入ソートは高速に動作するため、実用的なアルゴリズムである。データサイズが大きくなるほどソート済みでない部分が多くなり、時間計算量は$O(n^2)$に近づくため、大規模データには向かない。

例えば{5, 2, 4, 7, 2'}という配列があるとき、下記のようにソートされる。2と2'の相対的な順序が変わっていないことから、挿入ソートは安定ソートであることがわかる。

1. {5, 2, 4, 7, 2'}

2. {2, 5, 4, 7, 2'}

3. {2, 4, 5, 7, 2'}

4. {2, 4, 5, 7, 2'}

5. {2, 2', 4, 5, 7}

実装例

選択ソート

選択ソートは、配列を走査して最小値を見つけ、それを先頭に持ってくるという操作を繰り返すことでソートを行うアルゴリズムである。最小値を見つけるために配列を走査するため、最悪計算量は$O(n^2)$になる。

例えば{2, 1, 2', 1}という配列があるとき、下記のようにソートされる。2と2'の相対的な順序が変わっていることから、選択ソートは不安定ソートであることがわかる。

1. {2, 1, 2', 1}

2. {1, 2, 2', 1}

3. {1, 1, 2', 2}

実装例

クイックソート

平均して$O(n \log n)$の時間計算量でソートを行う。多くの問題に対して、最高速のソートアルゴリズムであると言われている。後述するヒープソートやマージソートも$O(n \log n)$だが、クイックソートは、再帰をしていく中で短い範囲のデータを繰り返しみていく（深さ優先探索になる）ため、キャッシュの効果を受けやすいのに対して、マージソートは全体を見てマージしていく必要があるため、キャッシュの効果を受けにくい（ヒープソートもランダムアクセスを行うため同様）。そのため、クイックソートはマージソートやヒープソートに比べてメモリ局所性が高いので、オーダーが同じでもクイックソートの方が速くなると言われている。またクイックソートはヒープソートやマージソートに比べて基本操作が簡単で、実際の計算時間は少なくなるため、それも速くなる理由の１つである。欠点は、最悪の場合に性能が極端に悪くなる（$O(n^2)$の時間計算量になる）ことである。ただ適切にピボットを選べばほとんど問題ないため、実際にソートを必要とする問題では、クイックソートの適用をまず考えるべきである。

クイックソートでは、ソート対象から適当な値（ピボットと呼ぶ）を１つ選び、次に配列内の要素を１つずつ調べて、ピボットより小さい値をピボットの左側に、大きい値を右側に移動する。最後にピボットより小さい部分と大きい部分をそれぞれ同様に再帰的にソートする。クイックソートのように問題をいくつかの部分に分解して、それぞれを解き、その結果を組み合わせて全体の解を得る方式を分割統治法という。

ピボットを基準に分割した際に、片方の部分が常に空になるような場合、最悪の計算量（$O(n^2)$）になる。これを避けるために、ランダムにピボットを選ぶか、中央値を選ぶなどの工夫がされる。また、スタックオーバーフローを避けるために、再帰の代わりにループを使うこともある。ピボットの取り方が理想的だった場合、スタックフレームは$O(\log n)$個に収まるが、最悪の場合は$O(n)$になる。

最悪の場合でも計算時間が$O(n log n)$を超えないようにするための技法として安全クイックソートと呼ばれるものがある。これは、再帰呼び出しの段数がある一定の限界を超えたら、クイックソートを使ったソートをやめ、ヒープソートを使ったソートに切り替えるというものである。

実装例

マージソート

時間計算量は$O(n \log n)$で、ヒープソートと同様に最悪の場合でもオーダーが変わらない安全なアルゴリズムであり、実際的な速度ではヒープソートよりやや速いことが多い。ただし、マージソートで難しいのはマージの途中で作られるデータの列をどこに置くかということであり、マージの入力と出力は別の場所に置く必要がある（同じ場所でマージする方法もあるが複雑かつ遅い）ため、ソート対象の配列と同程度の大きさの作業用の記憶域を必要とするのが大きな欠点である。そのため、配列のソートにマージソートが使われることは少ない。

マージソートは２次（外部）記憶装置上にある大きなデータのソートによく使われる（後述する外部ソートを参照）。これは、データの参照が列の先頭から順番に行われるというマージソートの性質が二次記憶装置へのアクセスに適しているためである。この参照方法を順（シーケンシャル）アクセスと呼び、ランダムアクセスと対比される概念である。二次記憶中のデータのアクセスはブロックと呼ぶ単位ごとに行われるが、ヒープソートのようにランダムアクセスを行うアルゴリズムだと、毎回別のブロックに属するデータを調べることになるため、その度に二次記憶装置へのアクセスが発生する。一方でマージソートは、シーケンシャルアクセスを行うため、同じブロック内のデータを処理し終わるまで他のブロックへのアクセスが必要なくなるため、二次記憶装置へのアクセスが少なくて済む。

ただし、連結リストをソートする場合は、ポインタを変更するだけで済み、追加の記憶域を必要としないため、マージソートがよく使われる。ヒープソートはランダムアクセスが必要なため、連結リストのソートを行うことができない。また、クイックソートの場合も列の真ん中を見つけるなどして、ピボットを選ぶことが難しいため、同様に連結リストのソートには向かない。そのため、マージソートが一番無難な方法である。

マージソートの実装方法には、ボトムアップ方式とトップダウン方式がある。ボトムアップ方式は小さなサブリストを先にソートし、徐々に大きなサブリストにマージしていく方法で、トップダウン方式は配列を再帰的に半分に分割していき、1要素になるまで分割を続け、分割されたサブリストをマージソートしていく方法である。そのため、トップダウン方式は二次記憶中のデータのソートには適さない。

単純マージソートは、必ず要素１個ずつに分解してからマージを行う方法である。しかし、実際の配列はすでにソートされている部分（ラン、run、連）を含んでいることが多く、このような区画はそのままマージの単位となりうるはずで、これを長さ１の列にまで分解するのは無駄である。分解するのはランまでにし、そこからマージを始める方法を自然マージソートと呼ぶ。自然マージソートは単純マージソートに比べてマージの回数は減るが、処理は複雑になるため、全体的にパフォーマンスが良くなるかはわからない。

また自然マージソートではたまたま隣同士のランが連続していて１つになるということが発生して、アンバランスなマージを多く行いがちになってしまうことに注意が必要である。マージは２つの列の長さがほぼ等しい時に最も効率的である。２つの列の長さが大きく違っていると、計算量が増える。例えば、長さ10, 20, 40の３つの列をマージする際、10と20をマージしてからその結果を40とマージすると、$(10+20)+(30+40)=100$の計算量がかかるが、、20と40をマージしてから10とマージすると、$(20+40)+(60+10)=130$の計算量がかかる。そのため効率化を図るには、マージの入力の長さがバランスするように配慮する必要がある。

実装例

外部ソート

メインメモリに収まらず、外部記憶装置に格納されているデータをソートするアルゴリズムを外部ソートと呼ぶ。外部ソートは主に２つのフェーズから成る。まず、データをメモリに収まる小さなチャンクに分割し、それぞれのチャンクをメモリ内でクイックソートなどを用いてソートする。ソートされた各チャンクは一時ファイルとしてディスクに保存される。次に、これらの一時ファイルをマージソートを用いてマージする。複数のソート済みファイルからデータを小さな部分ずつ読み込み、それらを一つのソート済みファイルに結合していくことでマージを行う。

対して内部ソートは、メインメモリ内に収まるデータをソートするアルゴリズムである。挿入ソート、クイックソート、ヒープソートなどの

External sorting - Wikipedia Internal sort - Wikipedia

ティムソート

挿入ソートはほぼソートされている場合や小規模なデータに対しては高速に動作し、またマージソートは最悪でも時間計算量が一定で、並列処理に適しているため、メモリ外（ディスク）にデータがある場合でも効率的にソートできることから、ティムソート（Timsort）は、実際のデータセットは部分的にソート済みであることが多いという事実を活かし、これらのソートの強みを組み合わせた実用的なソートアルゴリズムである。小さな部分配列を挿入ソートでソートし、それらをマージソートで統合する。ランダムなデータに対してはクイックソート（IntroSort）ほど速くない。

まず最初に、入力列を小さなソート済み列（ラン）へと分解する。入力列を前から順番になめ、単調非減少（<=）している最大の接頭辞を求める。それがある程度大きければ（ランの大きさは挿入ソートが最速になる要素数32未満の範囲でできる限り大きくする）それでひとつのランとする。単調非減少列のサイズが小さすぎる場合は、挿入ソートを用い拡張する。この際に行う挿入ソートは、前方の要素がソート済みなので、途中から行うことができる。入力列が（ほぼ）ソート済みの場合、この時点で一度データをなめるだけでソートが終わってしまうので非常に高速である。

最後にこれらのランがマージされる。このとき、下記のようにスタックを使って必ず隣り合ったラン同士をマージする。こうすることでキャッシュの局所性を高めるとともに、アンバランスなマージを防ぎ、長さがほぼ等しいラン同士をマージできるため、マージの計算量を効率化できる。

ティムソートのマージ順序

少ない要素数(要素数32未満)では計算量のオーダが大きくてもシンプルでオーバーヘッドの少ない、挿入ソートや選択ソートのようなアルゴリズムのほうが高速になることが知られている。ティムソートでは単純な挿入ソートではなく、2分挿入ソートが用いられている。これは要素の挿入位置の決定のために、ソート済み部分を2分探索するものである。

ティムソートは、要素数が少ない場合はオーバーヘッドによりクイックソートと同様に遅くなるが、最悪計算量$O(n \log n)$の安定ソートで、クイックソートのような最悪計算量の問題は起こらないため、セキュリティーの観点からこれを標準に採用するのには利点がある。そのため、Pythonで最初に採用され、Javaでも使われている。また、Rustで使われているソートアルゴリズムにも影響を与えた。

Timsort - Wikipedia 高速な安定ソートアルゴリズム “TimSort” の解説

下記の動画でティムソートの挙動を確認することができる。

Tim Sort - YouTube

ヒープソート

時間計算量は$O(n \log n)$で、マージソートと同様に最悪の場合でもオーダーが変わらない安全なアルゴリズムだが、ループ中の基本操作がより複雑なので、実際には平均的な計算速度ではクイックソートに劣る。マージソートにもやや劣る。しかし、クイックソートと異なり、最悪の場合でもオーダーが変わらず、またマージソートと異なりインプレースなので空間計算量が$O(1)$である。なお、同じ個数のデータであれば、ヒープソートの計算時間は、データの与え方による変動が少ないことが知られている。

ヒープソートは選択ソートの改良版と捉えることができる。選択ソートでは単純に最大値（または最小値）を見つけるのに配列を線形探索する必要があり、この部分で$O(n)$かかるために全体では$O(n^2)$になる。しかし、（ヒープベース）プライオリティキューを使って$O(\log n)$の時間計算量で最大値（または最小値）を取り出すことができれば、それを要素数（$n$）分繰り返せば良いため、$0(n \log n)$の計算量でソートができる。これがヒープソートである。