二分探索木 (BST) について理解する-jsチュートリアル-php.cn

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

二分探索木 (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 を挿入した後の二分探索ツリーは次のようになります。

Understanding Binary Search Trees (BST)

仕組み

挿入:
新しい値は比較に基づいて配置されます。小さい値は左に、大きい値は右に移動します。
検索 (含む):
ノードが見つかるまで、または走査が null ノードで終了するまで、値に応じて左または右に走査します。
トラバーサル: インオーダートラバーサルは、ソートされた順序でノードを訪問します (左 ->ルート ->右
)。

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

効率的な検索:
ツリーのバランスが取れている場合、BST での検索は非常に効率的になります。
動的サイズ:
配列のサイズを変更したり要素を移動したりすることなく、要素を追加または削除できます。
ソートされたデータ:
トラバーサルはソートされた順序でデータを提供し、優先キューやメモリ内データベースなどのシナリオで役立ちます。

留意すべきエッジケース

重複:
標準 BST は、デフォルトでは重複値を処理しません。各ノードにカウントを保存したり、重複挿入をスキップしたりするなど、重複を許可または拒否するロジックを実装する必要がある場合があります。
アンバランスツリー: 値がソートされた順序 (例: 1、2、3、4、...
) で挿入されると、BST が歪んで劣化します。演算時間 O(n) のリンクリストに変換します。自己バランス BST (AVL ツリー、赤黒ツリーなど) を使用すると、この問題を軽減できます。
空のツリー: コンテナーやトラバーサルなどの操作中の実行時エラーを防ぐために、ツリーが空である場合 (つまり、this.root === null) を常に確認します。
エッジノード: ノードの削除などのシナリオでは、子が 1 つだけあるノード、子がないノード、またはルートノードであるノードなどのエッジケースを考慮します。
パフォーマンス: データセットが大きい場合、またはソートされたチャンクに分かれている場合は、効率的な検索のためにバランスを調整するか、より適切なデータ構造を使用することを検討してください。

効率を確保するには、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) 内でコミットとバージョンを効率的に管理します。