プログラミング

動的な指検索データ構造は、指検索に加えて、指で指定された位置で要素の挿入と削除も実行する必要があります。 指検索ツリーは、O（1）の可動指のみが維持されると仮定して、O（log d）時間での指検索とO（1）時間での更新をサポートするBツリーのバリアントとして定義されます。 指のd位置を移動するには、O（log d）時間が必要です。 フィンガーサーチツリー（つまり、AVLツリー、赤黒木）構造は、固定された一定数のフィンガーを考慮するか、償却された一定時間の更新のみをサポートします。 任意の数の指をサポートし、最悪の場合の更新を伴う構造が作成されました。 最悪の場合O（1）時間の任意の位置での更新

このセクションでは、レベルリンクを導入することにより、（2,4）ツリーが効率的な指検索をサポートする方法について説明します。このセクションで説明するアイデアは、b≥2aの場合、（a、b）-treesで示されるより一般的なクラスの高さバランスの取れたツリーにも実装されます。 （2,4）ツリーは、すべての葉が同じ深さを持ち、すべての内部ノードが2、3、または4次である高さバランスのとれた探索木として定義されます。要素はリーフに保存され、内部ノードは検索をガイドするための検索キーのみを保存します。各内部ノードの次数は少なくとも2であるため、（2,4）ツリーの高さはO（log n）であり、O（log

決定論的探索木の2つのランダム化された代替案は、ランダム化された二分探索木、treaps、およびスキップリストです。 treapとスキップリストはどちらも洗練されたデータ構造として定義されており、ランダム化によってシンプルで効率的な更新操作が容易になります。 このセクションでは、データ構造を変更せずに、treapとスキップリストの両方を効率的なフィンガーサーチツリーとして実装する方法について説明します。どちらのデータ構造も、予想されるO（log d）時間を消費することでフィンガー検索をサポートします。この場合、データ構造の構築中にアルゴリズムによって作成されたランダムな選択に対して予想が引き

スキップリストでは、このポイントaから検索を続行するだけで、要素bを含むノードから要素aを指で検索できます。 a bの場合、検索は順方向に進むことに注意してください。 後方の場合はスキップリストでの通常の検索と対称的ですが、前方の場合は実際にはもっと複雑です。 通常、スキップリストでの検索は、リストの先頭にある番兵が最も高いノードと見なされるため、高速であると予想されます。 ただし、指を高さ1のノードに関連付けることができます。このため、検索中に登ることはめったにありません。通常は発生しない何か。 スキップリストの最も重要なプロパティは、期待される線形空間を必要とし、期待されるO（

アダプティブマージソート アダプティブマージソートは、ソートされたサブリストのマージソートを実行します。ただし、最初のサブリストのサイズは、サイズ1のサブリストではなく、要素のリスト間の順序の存在に依存します。たとえば、図のリストについて考えてみます。 2つのソートされたサブリストで構成されています。 要素16、15、14、13を含むサブリスト1。 要素9、10、11、12のサブリスト2。 サブリスト1はソートされていますが、逆の順序になっています。したがって、サブリスト1は、図に示すように逆になります。 サブリストが見つかると、マージプロセスが

プレイツリーは、最近アクセスした要素がすぐに再びアクセスできるという追加のプロパティを備えた、自己平衡型のバイナリ検索ツリーとして定義されます。挿入、検索、削除などの基本的な操作は、O（log n）償却時間のスプレーツリーによって実行されます。非ランダム操作の多くのシーケンスでは、シーケンスの特定のパターンが不明な場合でも、スプレーツリーは他の検索ツリーよりもうまく機能します。二分探索木の通常の操作はすべて、スプレイと呼ばれる1つの基本的な操作に結合されます。 ノードaごとに、実数キー（a）を格納するとします。 任意の二分探索木では、任意のノードaの左側のサブツリーにはkey（a）の値より

動的最適性予想 スプレー木の証明された性能保証に加えて、大きな関心を持った証明されていない推測があります。動的最適性予想はこの予想を示します。 Bなどの任意の二分探索木アルゴリズムがd（y）+1のコストでルートからyへのパスをトラバースすることによって要素yにアクセスし、アクセス間で1回のコストでツリー内の任意の回転を行うことができます。回転。 Bがアクセスのシーケンスを実行するためのコストをB（s）とします。その場合、スプレーツリーが同じアクセスを実行するためのコストはO [n + B（s）]です。 証明されていない動的最適性予想の結果は非常にたくさんあります トラバーサル予想 同じ要

静的な指の定理 −fをfingerと呼ばれる特定の要素として扱うようにします。 次に、以下の式は、シーケンスを表示するコストの限界です O(m + n log(n) + Σ Sum log (|f - i[j]| + 1))j 注 − | f-i |指とアイテムiの間のアイテムの対称的な順序での距離として示されます。 ここで、mは、最大n個のノードを持つツリーでの更新またはアクセス操作の数として示されます。 少なくとも償却の意味では、nノードを超えないツリーでの最初のm回の操作にかかる時間は、AVLツリーや2〜3ツリーなどの平衡二分探索ツリーにかかる時間と同じであることに注意

指定されたフォレストに対して、指定されたエッジの一部を「破線」で作成し、残りのエッジはソリッドに保たれます。各非リーフノードは、その子の1つに対して1つの「ソリッド」エッジにのみ関連付けられます。他のすべての子供たちは、破線のエッジの助けを借りて接続されます。 より具体的には、どのツリーでも、（その子への）右端のリンクを固定し、他の子への他のすべてのリンクを「破線」で作成する必要があります。 その結果、ツリーはソリッドパスのコレクションに分割されます。ソリッドパスのルートは、破線のエッジによって他のソリッドパスに結合されます。 「仮想ツリー」と呼ばれる新しいデータ構造が構築されます。各リン

仮想ツリーでは、一部のエッジは実線として扱われ、一部は破線として扱われます。通常のスプレイは、堅い木でのみ実行されます。仮想ツリーのノードyで表示するには、次の方法を実装します。 アルゴリズムは、パスごとに1回ずつ、ツリーを3回調べ、それを変更します。最初のパスでは、ノードyから開始して、ソリッドツリーのみでスプレイすることにより、yからツリー全体のルートへのパスが破線になります。このパスは、スプライシングによって確実に作成されます。ノードyでの最後のスプレイにより、yがツリーのルートになります。非公式ではありませんが、アルゴリズムは次のように説明されています Splay（y）のアルゴリズ

ハフマンコード ハフマンコードは、ロスレスデータ圧縮に一般的に使用される特定のタイプの最適なプレフィックスコードとして定義されます。 このようなコードを見つけたり実装したりするプロセスは、ハフマンコーディングによって進行します。ハフマンコーディングは、デビッドA.ハフマンが理学博士号を取得しているときに開発したアルゴリズムです。 MITの学生であり、1952年の論文「最小冗長コードの構築方法」に掲載されました。 ハフマンのアルゴリズムからの出力は、ソースシンボル（ファイル内の文字など）をエンコードするための可変長コードテーブルとして表示できます。アルゴリズムは、ソースシンボルの可能な値ご

単純なアルゴリズム n個の初期ハフマンツリーのコレクションが準備され、それぞれが単一の葉ノードです。 n本の木を重み（頻度）で整理された優先キューに保持します。 最初の2つのツリー（重みが最も小さいツリー）を削除または削除します。これらの2つのツリーを組み合わせて、ルートが子として2つのツリーに関連付けられ、重みが2つの子ツリーの重みの合計である新しいツリーを作成します。 この新しいツリーを優先キューに入れておきます。 すべての部分的なハフマンツリーが1つに結合されるまで、ステップ2〜3を繰り返します。 これは欲張りアルゴリズムです。各反復で、アルゴリズムは「欲張り」決定を作成して、重

高さ制限または深さ制限のハフマンツリーの図を以下に示します ツリーの深さの制限は、ほとんどの実際のハフマンの実装が対処しなければならない重要な問題です。 ハフマン構造は高さや深さを制限しません。もしそうなら、それが「最適」である可能性はありません。確かに、ハフマンツリーの最大の深さはフィボナッチ数列によって制限されますが、それは必要以上の深さのための十分な余地を残します。 ハフマンツリーの深さを制限する理由は何ですか？高速ハフマンデコーダーはルックアップテーブルを実装します。メモリコストを軽減するために複数のテーブルレベルを実装することは可能ですが、Huff0などの非常に高速なデコ

不等文字コストに最適なプレフィックスフリーコードを見つける問題は、エンコーディングアルファベットが長さαとβの不等コスト（長さ）文字で構成され、α≤βである最小コストのプレフィックスフリーコードを計算することです。二分木に限定します。 ハフマンツリーがハフマンコーディング問題の解を表すのと同じように、コードは偏ったツリーで表されます。類似性にもかかわらず、文字のコストが等しくない場合は、古典的なハフマンの問題よりもはるかに困難です。問題に関する豊富な文献があるにもかかわらず、一般的な文字のコストについては、多項式時間アルゴリズムは知られていないか、利用できません。 ただし、利用可能な既知の

Bucketingは、ハッシュテーブルを1次元配列ではなく2D配列として構築します。配列内のすべてのエントリは大きく、M個のアイテムを保持するのに十分です（Mはデータの量ではなく、定数です）。 問題 多くの無駄なスペースが作成されます。 Mを超える場合は、別の戦略を実行する必要があります。 メモリベースの実装ではあまりパフォーマンスが良くありませんが、バケットがディスクベースの場合は実行可能です。 1は、最小1回の衝突があることを保証します（鳩の巣原理）。これにより、実行時間とバケットが不足する可能性の両方が向上します。 M個の場所と各場所のY個のバケットのハッシュテーブルの場合

多変量クロスセクションデータ（つまり、時系列または反復測定ではない）は、各列が変数（特徴）であり、各行がケースまたはレコードである長方形のデータによって示されます。 長方形データを表す最初の手順は、それを高次元のポイントデータにマッピングし、グリッドファイル、PRクワッドツリー、ポイントクワッドツリー、k-dツリーなどのポイントベースのデータ構造手順を使用することです。長方形データの4次元ポイントへのプロシージャマッピングは、反対側のコーナーのx座標とy座標、または1つのコーナーのx座標とy座標、および幅と高さなどの数値手法で実行できます。ポイントベースの欠点長方形のデータの表現には、ストレ

計算幾何学の場合、平面直線グラフ、略してPSLG（または直線平面グラフ、または平面直線グラフ）は、平面に平面グラフを埋め込むために実装される用語として定義されます。そのエッジは直線セグメントにマッピングされます。 Fáryの定理（1948）のステートメントは、すべての平面グラフにこの種の埋め込みがあるというものです。 計算幾何学の場合、PSLGは平面細分割と呼ばれることが多く、細分割は多角形であるという仮定または主張があります。 次数1の頂点がない場合、PSLGは平面の細分割を多角形領域に定義します。その逆も同様です。次数1の頂点がないため、さまざまなアルゴリズムの説明が簡単になりますが、

はじめに テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。 ハーフエッジデ

範囲ツリーは、ポイントのリストを保持するための順序付けられたツリーデータ構造として定義されます。これにより、特定の範囲内のすべてのポイントを効率的に取得でき、通常は2次元以上で実装されます。 O（log d のクエリ時間が速いことを除いて、kdツリーと同じです。 n + k）が、O（n log d-1 のストレージが悪い n）、dはスペースの次元を示し、nはツリー内のポイントの数を示し、kは特定のクエリで取得されたポイントの数を示します。範囲ツリーは、間隔ツリーで区別できます。ポイントを格納して特定の範囲内のポイントを効率的に取得できるようにする代わりに、間隔ツリーは間隔を保存し、特定のポ

四分木は、2次元空間上の点のデータを効率的に格納するために実装されたツリーです。このツリーでは、各ノードに最大4つの子があります。 次の手順を実行して、2次元領域から四分木を構築できます 現在の2次元空間は4つのボックスに分割されています。 ボックスが1つ以上のポイントで構成されている場合は、子オブジェクトを作成し、ボックスの2次元空間を格納します。 ボックスにポイントが含まれていない場合は、その子を作成しないでください。 各子に対して再帰を実行します。 四分木は画像圧縮で実装され、各ノードはその子のそれぞれの平均色で構成されます。 ツリーの奥深くに行くほど、画像の詳細がわかります。