プログラミング

ここでは、Height Balanced Leftist Trees（HBLT）とは何かを確認します。 外部ノードと呼ばれる特別なノードがある二分木を考えてみましょう。 空の各サブツリーを置き換えます。他のすべてのノードは内部ノードと呼ばれます 。いくつかの外部ノードがいくつかのバイナリツリーとともに追加される場合、それは拡張バイナリツリーと呼ばれます。 。 このツリーの葉の端を考慮しない場合、それは実際の二分木です。これは拡張された二分木です。 ここで、 s（x） ノードxからそのサブツリー内の外部ノードまでの最短経路の長さです。 xが外部ノードの場合、その s（x） 値は0です。

Max HBLTへの挿入は、MaxMeld操作を使用して実行できます。この操作は、2つのMaxHBLTを1つのMaxHBLTにマージするために使用されます。 xをHと呼ばれる1つの最大HBLTに挿入するとします。xを使用して小さなHBLTを作成し、これをHとマージします。次に、マージ後、Hはxを含むすべての要素を保持します。したがって、HBLTの挿入操作を実行するには、融合操作が必要です。

Max HBLTでは、ルートはルートに配置されます。ルートが削除されると、2つの最大HBLT、つまり左と右が分離されます。これら2つのMaxHBLTを再度マージすることにより、これらを1つにマージできます。したがって、マージした後、削除された要素を除くすべての要素がそこにあります。

メルド戦略は、再帰を使用して簡単に実行できます。 AとBが2つのHBLTであり、それらが融合するとします。それらの1つが空の場合は、最終結果として別の1つを作成するだけです。空のHBLTがない場合は、2つのルートの要素を比較する必要があります。より大きな要素を持つルートは、融合したHBLTのルートになります。 Aのルートが大きいとします。そして、それはその左側のサブツリーがLです。Cが最大HBLTであると仮定します。これは、AとHBLT Bの右側のサブツリーをマージした結果です。最終的なHBLTは、ルートとしてAを持ち、サブツリーとしてLとCを持ちます。 Lのs値がCの値よりも小さい場合、C

配列表現は、時間の経過とともに変化するデータを格納する場合、基本的にスペースを浪費します。一部のデータを格納するために、配列に複数の値を格納するのに十分な大きさのスペースを割り当てます。配列のサイズを大きくするために、配列の倍増基準を使用するとします。 現在のアレイサイズが8192であると考えてください。これはいっぱいです。したがって、配列ダブリング手法を使用してそれを増やす必要があります。したがって、新しい配列サイズは16384になります。次に、8192要素を古い配列から新しい配列にコピーしてから、古い配列の割り当てを解除します。これで、古い配列のスペースの割り当てを解除する前に、配列サイ

最大または最小HBLTから任意のノードを削除することは標準的な操作ではありません。優先キューまたはHBLTの場合。 HBLTからKなどのノードを削除する場合は、次のルールに従う必要があります。 Kをルートとするサブツリーをツリーから切り離し、ノードKのサブツリーの融合に置き換えます。 Kからルートへのパスからsの値を更新し、必要に応じてこのパスのサブツリーを交換して、HBLTのプロパティを維持します。 sの値をKからrootに更新するには、各ノードの親ポインターが必要です。 s値が変更されていないことがわかると、s値を上位ノードに更新するためのこの操作は停止します。変更された

ここでは、レフティストツリーの別のバリエーションが表示されます。ここでは、ルートから外部ノードへの最短パスの長さではなく、サブツリー内のノードの数を検討します。ここでは、ノードxの重みw（x）を、ルートxを持つサブツリー内の内部ノードの数として定義します。 xが外部ノードの場合、重みは0です。xが内部ノードの場合、重みはその子の重みの合計より1つ大きくなります。 これは、重みバイアス左翼ツリー（WBLT）の例です- 二分木が次のようになっていると仮定します- 各ノードのw（x）値を計算すると、次のようになります- これで、WBLTの定義は次のようになります- 二分木は、す

ここでは、さまざまなMax-WBLT操作について説明します。 HBLTには、挿入、削除、初期化などのさまざまな操作があります。それらもWBLTと非常によく似ています。ただし、融合操作は1回の上から下へのパスで実行できます。 WBLTではシングルパスメルド操作が可能です。 w値を見つけることができるので、途中で。必要に応じて、w値を更新し、サブツリーを交換できます。 HBLTの場合、ツリーに到達する途中でsの値を見つけることができません。 融合は1回の上から下へのパスで実行できるため、挿入と削除も効率的に実行できます。したがって、挿入と削除は一定の係数で高速になります。ここでは、任意に配置さ

このセクションでは、ロビンフッドハッシュスキームとは何かを説明します。このハッシュは、オープンアドレス法の手法の1つです。これは、より公平な衝突解決戦略を使用して、要素の検索時間を均等化しようとします。挿入しようとしているときに、要素xを位置xiに挿入したいが、すでに要素yがy jに配置されている場合 =x i 、次に2つの要素のうち若い方が先に進む必要があります。したがって、i≤jの場合、位置x i + 1にxを挿入しようとします。 、x i + 2 等々。それ以外の場合は、xを位置x iに格納します 、y j + 1の位置にyを挿入してみます 、y j + 2 など。

抽象データ型Dictionaryを実装しようとすると、ノードは値に関連付けられます。辞書は基本的にキーのセットであり、全順序から抽出された要素である必要があります。各キーに関連付けられている追加情報がある場合がありますが、概念的な理解にはつながりません。 辞書がツリーを使用して実装されている場合、各ノードは一意のキーを保持します。ここで、ツリー内の各ノードuについて、すべてのキーはu.lであり、厳密にu.kよりも小さくなっています。そして、u.rのすべてのキーは、厳密にu.kよりも大きくなっています。ツリーは、バイナリ検索ツリーと呼ばれるこの不変条件に従って編成されます。 この不変条件の主

マージアルゴリズムは、2つの並べ替えられたリストを1つのリストにマージするために使用されます。このアルゴリズムはさまざまな場合に使用されます。マージソートを実行する場合は、ソーターリストをより大きなリストにマージする必要があります。 アプローチは簡単です。 2つのリストを取ります。2つのポインタがあります。最初のものは最初のリストの要素を指し、2番目のものは2番目のリストの要素を指します。それらの値に基づいて、これら2つのリストのいずれかから小さい要素が取得され、対応するリストのポインターが増加します。この操作は、1つのリストがなくなるまで実行されます。その後、最後にマージされたリストの最後

ここでは、Bツリーとは何かを確認します。 Bツリーは特殊なm-way探索木です。これは、ディスクアクセスに広く使用できます。次数mのBツリーは、最大m-1個のキーとm個の子を持つことができます。これにより、1つのノードに多数の要素を格納できます。そのため、高さは比較的小さいです。これは、Bツリーの大きな利点の1つです。 B-Treeには、1つのm-wayツリーのすべてのプロパティがあります。他にもいくつかのプロパティがあります。 Bツリーのすべてのノードは最大m個の子を保持します ルートとリーフを除くすべてのノードは、少なくともm/2の子を保持できます ルートノードには少な

ここにR-Treesデータ構造が表示されます。 Rツリーは、特別なデータインデックスを効率的に格納するために使用されます。この構造は、特別なデータクエリとストレージを保持するのに非常に役立ちます。このRツリーには実際のアプリケーションがいくつかあります。これらは以下のようなものです- 多次元情報の索引付け ゲームデータの処理 地理空間座標を保持する 仮想マップの実装 Rツリーの一例は以下のようなものです。 対応するRツリーは次のようになります- Rツリーのプロパティ Rツリーは、単一のルート、内部、およびリーフノードで構成されています ル

このセクションでは、赤黒木とは何かを見ていきます。赤黒木は、自己平衡二分探索木です。各ノードにはいくつかの条件があります。これらは以下のようなものです- 各ノードには色があります。赤か黒のどちらか ルートは常に黒になります 隣接する2つのRedノードはありません ノード（ルートを含む）からその子孫のNULLノードへのすべてのパスには、同じ数のブラックノードがあります。 赤黒木の例 葉にヌルノードがある赤黒木 AVLツリーとの比較 AVL木は、赤黒木よりもバランスが取れています。ただし、主な欠点は、挿入および削除中のローテーションが増えることです。複数の

算術式の記述方法は表記法として知られています。算術式は、式の本質や出力を変更せずに、3つの異なるが同等の表記法で記述できます。これらの表記は– 中置 プレフィックス 接尾辞 中置記法は通常の記法であり、さまざまな数式を書くときに使用されます。接頭辞と後置記法はまったく異なります。 プレフィックス表記 この表記では、演算子はプレフィックスです。 オペランドに、つまり演算子はオペランドの前に書き込まれます。たとえば、 + ab 。これは、中置記法 a + bと同等です。 。プレフィックス表記は、ポーランド記法とも呼ばれます。 。 後置表記 この表記スタイルは、逆ポー

ここでは、トーナメントツリー、勝者ツリー、ルーザーツリーが表示されます。トーナメントツリーは、n個の外部ノードとn –1個の内部ノードを持つ完全なバイナリツリーです。外部ノードはプレーヤーを表し、内部ノードは2人のプレーヤー間の試合の勝者を表します。このツリーは、選択ツリーとも呼ばれます。 トーナメントツリーにはいくつかのプロパティがあります。これらは以下のようなものです- この木は根付いています。したがって、ツリー内のリンクと親から子への方向付けられたパス、および親のない一意の要素があります 親の値は、一般的な比較演算子のノード以下であり、親と子の相対値がツリー全体で不変である

ここでは、根なし二分木とは何かを確認します。これらのツリーは、サイクルのない無向グラフに接続されています。隣接する頂点が1つある頂点は、木の葉です。残りの頂点は内部ノードです。頂点の次数は、隣接する頂点の数です。複数のノードを持つツリーでは、葉は1次の頂点です。 フリーツリーはバイナリツリーの一種であり、すべての内部ノードの次数は正確に3です。コンピュータサイエンスでは、データ構造として使用される場合、バイナリツリーはルート化され、順序付けられることがよくありますが、階層的クラスタリングおよび進化的ツリー再構築におけるルート化されていないバイナリツリーのアプリケーションは重要です。 根なしツ

このセクションでは、根付きの木と根なしの木の違いを確認します。最初に、根付きの木と根なしの木の例をいくつか見ていきます。 ルートツリーの例 − 根なしツリーの例 − 根付きの木と根なしの木の基本的な違い ルートツリーでは、子孫を持つ各ノードは、子孫の推定された最新の共通祖先を表します。一部のツリーでは、エッジの長さが時間の見積もりとして解釈される場合があります。 根なしの木には、祖先の根はありません。根なしツリーは分岐順序を表しますが、最後の共通祖先の場所のルートを示すものではありません。

任意のハッシュ関数の場合、テーブルサイズmがユニバースサイズuよりもはるかに小さい場合、任意のハッシュ関数hの場合、同じUの大きなサブセットがいくつかあると言えます。ハッシュ値。 この問題を取り除くには、ハッシュ関数のセットが必要です。そこから、Sに適したものを選択できます。ほとんどのハッシュ関数がSに適している場合は、ランダムハッシュ関数を選択できます ℌがハッシュ関数のセットであると仮定します。各x、y∈Uについて、h（x）=h（y）が最大で|ℌ| /𝑚となるようなh∈ℌの数である場合、ℌは普遍的であると言えます。言い換えれば、ℌからランダムに選択されたハッシュ関数hを使用すると、異

このセクションでは、連鎖によるハッシュとは何かを説明します。連鎖は、衝突解決手法の1つです。衝突を回避することはできませんが、衝突を減らし、同じハッシュ値に対して複数の要素を格納することを試みることはできます。 この手法では、0から6の範囲のハッシュ関数h（x）を想定しています。したがって、7つを超える要素の場合、同じ部屋内に配置されるいくつかの要素が必要です。そのために、それに応じてそれらを保存するためのリストを作成します。毎回、リストの先頭に追加して、O（1）時間で挿入を実行します より良いアイデアを得るために、次の例を見てみましょう。 {15、47、23、34、85、97、65、89