二分探索木 (BST) について理解する

二分探索木に関連する問題をいくつか解いていたので、記憶を修正して、学んだことをフォロワーと共有するのは面白いかもしれないと思いました。それでは、行きましょう:

二分探索木 (BST) とは何ですか

二分探索ツリー (BST) は、データの効率的な検索、挿入、削除を可能にするコンピューター サイエンスの基礎的なデータ構造です。これはツリーベースの構造で、すべてのノードに最大 2 つの子があり、左 の子は常に親ノードよりも 小さく、右 の子は親ノードよりも大きくなります。 大きい.

BST の主な機能

1.効率的な検索: バランスのとれたツリーの時間計算量は O(log n) です。

2.動的構造: ノードは動的に追加または削除できます。

3.階層表現: ファイルシステムや家系図などの階層データ表現で役立ちます。

---

TypeScript を使用した二分探索ツリーの実際的な実装を見てみましょう。

class Node {
    value: number;
    left: Node | null;
    right: Node | null;

    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    root: Node | null;

    constructor() {
        this.root = null;
    }

    insert(value: number): void {
        const newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
            return;
        }

        let currentNode = this.root;
        while (true) {
            if (value < currentNode.value) {
                if (currentNode.left === null) {
                    currentNode.left = newNode;
                    return;
                }
                currentNode = currentNode.left;
            } else {
                if (currentNode.right === null) {
                    currentNode.right = newNode;
                    return;
                }
                currentNode = currentNode.right;
            }
        }
    }

    contains(value: number): boolean {
        let currentNode = this.root;

        while (currentNode !== null) {
            if (value === currentNode.value) return true;
            currentNode = value < currentNode.value ? currentNode.left : currentNode.right;
        }

        return false;
    }

    // In-order Traversal: Left -> Root -> Right
    inOrderTraversal(node: Node | null = this.root): void {
        if (node !== null) {
            this.inOrderTraversal(node.left);
            console.log(node.value);
            this.inOrderTraversal(node.right);
        }
    }
}

// Usage
const bst = new BinarySearchTree();
bst.insert(47);
bst.insert(21);
bst.insert(76);
bst.insert(18);
bst.insert(52);
bst.insert(82);

console.log("Contains 21:", bst.contains(21)); // true
console.log("Contains 99:", bst.contains(99)); // false

console.log("In-order Traversal:");
bst.inOrderTraversal();

---

BSTの図表現

値 47、21、76、18、52、82 を挿入した後の二分探索ツリーは次のようになります。

:

---

仕組み

1. 挿入:

   新しい値は比較に基づいて配置されます。小さい値は左に、大きい値は右に移動します。

2. 検索 (含む):

   ノードが見つかるまで、または走査が null ノードで終了するまで、値に応じて左または右に走査します。

3. トラバーサル: インオーダートラバーサルは、ソートされた順序でノードを訪問します (左 ->ルート ->右

   )。

---

二分探索木を使用する理由

1. 効率的な検索:

   ツリーのバランスが取れている場合、BST での検索は非常に効率的になります。

2. 動的サイズ:

   配列のサイズを変更したり要素を移動したりすることなく、要素を追加または削除できます。

3. ソートされたデータ:

   トラバーサルはソートされた順序でデータを提供し、優先キューやメモリ内データベースなどのシナリオで役立ちます。

---

留意すべきエッジケース

1. 重複:

   標準 BST は、デフォルトでは重複値を処理しません。各ノードにカウントを保存したり、重複挿入をスキップしたりするなど、重複を許可または拒否するロジックを実装する必要がある場合があります。

2. アンバランス ツリー: 値がソートされた順序 (例: 1、2、3、4、...

   ) で挿入されると、BST が歪んで劣化します。演算時間 O(n) のリンク リストに変換します。自己バランス BST (AVL ツリー、赤黒ツリーなど) を使用すると、この問題を軽減できます。

3. 空のツリー: コンテナーやトラバーサルなどの操作中の実行時エラーを防ぐために、ツリーが空である場合 (つまり、this.root === null) を常に確認します。

4. エッジ ノード: ノードの削除などのシナリオでは、子が 1 つだけあるノード、子がないノード、またはルート ノードであるノードなどのエッジ ケースを考慮します。

5. パフォーマンス: データセットが大きい場合、またはソートされたチャンクに分かれている場合は、効率的な検索のためにバランスを調整するか、より適切なデータ構造を使用することを検討してください。

効率を確保するには、BST のバランスを維持する必要があります。バランスの取れていないツリーでは、パフォーマンスが O(n) まで低下する可能性があります。一貫して最適化されたパフォーマンスを得るには、AVL や Red-Black Tree などの自己バランス ツリーの使用を検討してください。他の木については、後ほど別の記事で説明します。

---

ソフトウェア アプリケーションにおける BST の使用例

二分探索木 (BST) は、教科書で出てくる単なるデータ構造ではありません。実際の応用例がたくさんあります。 BST がコンピューター サイエンスで使用される実際的な方法をいくつか紹介します。

• データベースとインデックス作成: バランス BST (AVL や Red-Black Tree など) は、データベースのインデックス作成の舞台裏で行われることがよくあります。範囲クエリとルックアップが非常に効率的になります。

• メモリ内でソートされたデータ: 動的に追加および検索する際にデータをソートしたままにする必要がありますか? BST は頼りになります。リアルタイム分析や監視システムを思い浮かべてください。

• コンパイラーのシンボル テーブル: コンパイラーは、BST に依存して、識別子とその属性を保存し、迅速にアクセスするためのシンボル テーブルを実装します。

• オートコンプリートとスペル チェッカー: オートコンプリートがどのように機能するか考えたことはありますか?三分探索ツリーなどの BST バリエーションは、単語の辞書を効率的に編成するために使用されます。

• 優先順位スケジューリング: ヒープの方が一般的ですが、BST は優先順位が常に変化する動的スケジューリング システムでも使用できます。

• 地理データ (GIS): BST は、近くの場所の検索や範囲によるフィルター処理など、空間データの保存と取得によって GIS システムに役立ちます。

• データ圧縮: データ圧縮アルゴリズムの重要な部分であるハフマン エンコードでは、特別な種類のバイナリ ツリーを使用して可変長コードをデータ シンボルに割り当てます。

• ゲーム システム: BST は、スコアを並べ替えてリアルタイムでランキングを取得することにより、動的なリーダーボードとスコアボードを可能にします。

• ネットワーキングとルーティング: ルーティング テーブルは、データ転送の効率的なパスを決定するために BST のような構造に依存することがあります。

• バージョン管理システム: Git のようなシステムは、ツリー状の構造 (BST からインスピレーションを得た) を使用して、有向非巡回グラフ (DAG) 内でコミットとバージョンを効率的に管理します。

BST は、私たちが日常的に使用するツールの強化から複雑な計算問題の解決に至るまで、あらゆる場所に存在します。かなりクールですね?

しかし、その制限と特殊なケースに留意することが不可欠です。これらのニュアンスを理解すると、より効率的で信頼性の高いシステムを設計するのに役立ちます。

BST と協力しているときに、興味深い課題や解決策に遭遇したことがありますか?以下で話し合いましょう！ ?

以上が二分探索木 (BST) について理解するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。