あ 二分探索木 コンピューター サイエンスでデータを整理して保存するために使用されるデータ構造です。内の各ノード 二分探索木 子供は多くても2人、 左 子供と 右 子供と、 左 親ノードより小さい値を含む子と、 右 親ノードよりも大きい値を含む子。この階層構造により、効率的な 探しています 、 挿入 、 そして 削除 ツリーに格納されたデータに対する操作。
二分探索木
二分探索の概要:
- BSTの応用例
- 二分探索木の応用とメリット・デメリット
BST の基本操作:
BST の簡単な標準問題:
- 二分探索木での反復検索
- バイナリツリーがBSTかどうかをチェックするプログラム
- 二分木から二分探索木への変換
- 二分探索木で最小値を持つノードを見つける
- 配列が二分探索木の順序を表しているかどうかを確認する
- 二分木の高さのバランスが取れているかどうかを判断するにはどうすればよいでしょうか?
- ソートされた配列からバランスの取れた BST へ
- ツリーを構築せずに同一の BST をチェックする
- BST を最小ヒープに変換
- BST で 2 番目に大きい要素
- 指定された BST 内のすべてのノードに、より大きな値をすべて追加します。
- 2 つの BST に同じ要素セットが含まれているかどうかを確認する
- BST の k 個の最小要素の合計
BSTの中程度の標準問題:
- 指定された事前順序トラバーサルから BST を構築する |セット1
- ソートされたリンクリストからバランスのとれたBSTへ
- BST をより大きな合計ツリーに変換する
- すべての小さいキーの合計を含むツリーへの BST
- 指定されたレベル順序のトラバーサルから BST を構築する
- 指定された配列が二分探索木のレベル順トラバーサルを表現できるかどうかを確認します。
- 二分探索木における最下位共通祖先
- BST で k 番目に小さい要素を見つける (BST の順序統計)
- 一定の追加スペースを使用する BST の K 番目に大きい要素
- BST 内の N 以下の最大の数
- 二分探索木の 2 つのノード間の距離を求める
- バイナリ ツリーで最大の BST |セット2
- 二分探索木からすべての葉ノードを削除します。
- 二分探索木の順序後続
- BST で指定された合計を持つペアを見つける
- BST の 2 つのノード間の最大要素
- 指定されたバイナリ ツリー内で最大の BST サブツリーを検索します。
- Balanced BST で指定された合計を持つペアを見つける
- BST の 2 つのノードが交換されています。BST を修正してください
- 二分探索ツリーで重複を処理するにはどうすればよいですか?
- 二分探索木の事前順序からの葉ノード (再帰を使用)
BST の難しい標準問題:
- キー 1 ～ N に対して可能なすべての BST を構築する
- BST を最小ヒープにインプレース変換する
- サイズ n の指定された配列が n レベルの BST を表現できるかどうかを確認します。
- 限られた追加スペースで 2 つの BST をマージする
- BST への変更が許可されていない場合の BST 内の K 番目に大きい要素
- 指定されたソートされたサブシーケンスが二分探索ツリーに存在するかどうかを確認します
- サイズ K の各部分配列内の最大の一意の要素
- 合計が指定された値 x に等しい 2 つの BST のペアをカウントします。
- 指定された範囲内の BST キーを出力します | O(1) スペース
- BST の特定のキーの先行キーと後続キーを並べ替えます。
- Balanced BST にゼロに加算するトリプレットがあるかどうかを確認します。
- すべての要素をその右側の最も小さい要素に置き換えます
- 配列内の反転をカウントする |セット 2 (セルフバランシング BST を使用)
- 二分探索木の Preorder からのリーフ ノード
- |ai + aj – k| の可能な最小値指定された配列と k について。
- 二分探索木における特殊な 2 桁の数字
- 2 つのバランスのとれた二分探索ツリーをマージする
いくつかのクイズ:
- 二分探索ツリーの「クイズ」
- 平衡二分探索木の「クイズ」
クイックリンク ：
- 二分探索木に関するビデオ
推奨：
- データ構造とアルゴリズムを学ぶ | DSA チュートリアル