마인드 맵 갤러리 【学習ノート】データ構造-ツリー
ハフマン ツリー、ツリー テーブル検索、手がかりバイナリ ツリー、バイナリ ツリー トラバーサル手法、最小スパニング ツリーなど、データ構造内のツリーに関する知識。誰でも学習できます。
データとデータ構造
ソフトウェア開発プロジェクト管理プロセス V5.0
プリセールス技術ソリューション
UNIMESシステム
第 6 章 - ブロック暗号の操作
ソフトウェア システム ライブラリのシステム要件分析
ニニクス
ソフトウェア システム テストの知識ポイントの概要
Photoshop パンツのアイデア
コンピュータの一般的な基本
木
ハフマンツリー
重み付き経路長 WPL
バイナリ ツリーに n 個の重み付きリーフ ノードがあると仮定すると、ルート ノードから各リーフ ノードまでのパス長の合計と、対応するノードの重みの積をバイナリ ツリーの重み付きパス長 WPL (weighted Path Length) と呼びます。 。
同じ葉ノードが異なる二分木を構築する
重みが大きいリーフ ノードはルートに近くなり、wpl の値は小さくなります。
意味
最小の重み付きパス長を持つバイナリ ツリーはハフマン ツリーと呼ばれます (最適ツリーとも呼ばれます)。
どのように構築するか?
原則として
重みが大きいリーフ ノードはルート ノードに近くなります。
重みが小さいほど、リーフ ノードはルート ノードから遠くなります。
小さい値を見つけます (合成されたノードも一緒に比較する必要があります)
プロセス
重みのある葉ノードが n0 個あります
応用
ハフマン符号化(プレフィックス符号化)
ハフマン符号化の特徴: 重みが大きいほど文字コードは短くなり、その逆も同様です。
文字セットのハフマン エンコーディングでは、ある文字のハフマン エンコーディングが別の文字のハフマン エンコーディングのプレフィックスになることは不可能です。
文字コード
機械命令
ツリーテーブルのルックアップ
バイナリソートツリー
左<根元<右
バランスの取れたバイナリ ツリー AVL
バイナリ ソート ツリーの改良版 (特殊なバイナリ ソート ツリー)。ツリーをできるだけ短くするようにしてください。
木が正常に成長しているかどうかを確認するにはどうすればよいですか?
バランス係数 = 左のサブツリーの高さ - 右のサブツリーの高さ
バランス係数 <= 1 のバイナリ ソート ツリー
バイナリ ツリーの最大深さと最小ノード数のバランスを取る
B ツリー (バランスの取れたバイナリ ツリーの拡張)
入れる
B ツリーの作成は、継続的な挿入操作のプロセスです
手がかり二分木
左の空のチェーン フィールドの条件: シーケンスの左端にあり、元の左ポインターが空である。
右の空のチェーン ドメインの条件: シーケンスの右端にあり、元の右ポインタが空である。
二分木走査法
ルートノードの場合
プロローグ
ルート-左-右
中程度の
左-ルート-右
あとがき
左右ルート
レベル
一行ずつ走査する
最小スパニングツリー
プリムのアルゴリズム
必要とする
重さが最小でサイクルを形成できません。
ノード数が少ない質問の場合
Prime アルゴリズムのコア ステップは次のとおりです。重み付き接続グラフでは、V はすべての頂点を含むセットです。このとき、U はグラフ内の任意の頂点 v から始まる最小スパニング ツリーのノードです。 ={v}、次の操作を繰り返します。すべての u∈U,w∈V-U のすべてのエッジ (u,w)∈E の中から最小の重みを持つエッジを見つけ、そのエッジ (u,w) を次のセットに追加します。見つかったエッジを集合 U に追加します。U=V のとき、最小スパニング ツリーが見つかります。
クラスカルアルゴリズム
まずノードを決定し、最短パスを持つノードを順番に選択します。
リングを形成できない
辺の数が少ない質問の場合
基本的なアイデア: エッジ主導。重み付き接続グラフでは、U はすべてのエッジのセット、N は頂点の数、SU を最小スパニング ツリー上に既に存在するエッジのセットとします。以下の操作を繰り返します。毎回、重みが最小の辺 e∈U-SU と、SU 内の辺と循環を形成しない辺を選択し、SU に追加します。 SU 内のエッジの数が N-1 に等しい場合、最小スパニング ツリーが見つかります。
質問
ノードがリーフ ノードでない場合、そのノードには子があり、これらの子は兄弟のグループになります。
右ポインタのないノードの数は次のとおりです。 ルート ノード 非リーフ ノードの数
対称的なものを除外し、数を数えて、常に左側が少なく、右側が多い、または左側が多く、右側が少ないことを確認します。
ASL の平均検索長
木の高さに関係する
第 5 章 ツリーと二分木
バイナリツリートラバーサルとハフマンツリー
難易度: バイナリ ツリーとツリーとフォレストの間の変換
ほとんどのテストは多肢選択問題の形式であり、ツリー トラバーサルおよびハフマン ツリー アルゴリズムも含まれます。
n 個のノードの有限集合
ルートノードは一意です
サブツリーの数に制限はありませんが、サブツリーは互いに交差しません。
次数: ノードが所有するサブツリーの数
二分木: 次数 <=2
自然
二分木の i 番目のレベルには最大 2^i-1 個のノードがあります。
バイナリ ツリーの深さが k の場合、ノードは最大 2^k-1 個あります。 (k>=1)
n0=n2 1、n0 は次数 0 のノードの数を表し、n2 は次数 2 のノードの数を表します。
完全なバイナリ ツリーでは、n 個のノードを持つ完全なバイナリ ツリーの深さは [log2n] 1 になります。ただし、[log2n] は切り捨てられます。
【二分木】ノード計算式 N = n0 n1 n2
ノードの総数 = 総次数 1=0xn0 1xn1 2xn2 ..
完全なバイナリツリー
すべてのノードには左右のサブツリーがあり、すべてのリーフ ノードは同じレベルにあります。
完全な二分木
リーフ ノードは、最下位レベルとその 1 つ下のレベルにのみ表示されます。
そして、最下層のノードは、二分木において層の左端の位置に集中している。
ツリー、フォレスト、バイナリ ツリー間の横断対応
ヒープ
完全なバイナリ ツリーである必要があります
完全なバイナリ ツリーでは、最後の行が満杯未満であることのみが許可されます。そして最後の行は左から右に並べ替える必要があります。最後の行の要素間にスペースがあってはなりません
ヒープの秩序性
ダゲンドゥイ
小さな根の山
基本操作
ヒープストレージ
1. 1 次元配列で表されるレイヤー シーケンスに従って数値をトラバースします。
親ノードは i、左の子ノードの添字は 2i 1、右の子ノードは 2i 2 (このルールはアルゴリズムでよく使用されます)
上部フィルター
ツリーの最後の要素のみがヒープの順序に違反します
主にヒープに新しい要素を挿入するために使用されます。
複雑さ: O(logN)
フィルターダウン
ルートノードのみがヒープの順序に違反します
ルートノードを下方向に調整します
山を築く
順序なし配列をヒープに変換するにはどうすればよいですか?
トップダウン
ヒープに挿入し、フィルターを適用します
複雑さ: O(NlogN)
ボトムアップ
まず要素をヒープに調整し、最後から 2 番目の行から始めて、親ノードでフィルター ダウン操作を実行します。
複雑さ: O(N)
アプリケーション: 優先キュー
2つの操作
キューの挿入
ポップアップの最小限の要素
小さなルートヒープを使用して実装可能
小さなルート ヒープのルート ノードは min であるため、ポップアップ後、残りの要素がヒープに調整されます (最後の要素をルート ノードに配置し、フィルターを下に置きます)。
ヒープソート: 優先キューから要素を順番にポップします。