JavaScript 初心者のための二分探索木アルゴリズムのチュートリアル

この記事では、コーディング面接の前に学ぶべきコアアルゴリズムのいくつかをできるだけ詳しく説明したいと思います。

バイナリ検索木 (BST) とは何ですか?

コーディング面接でよく見られる BST は、最上部にルートがあるツリーのようなデータ構造です。順序付けられた性質により高速な検索と参照が可能になるため、数値を保存するのに最適な方法です。

通常のツリーと比較して、BST には次の特性があります。

• 左の子の値は親の値より小さい
• 右の子はそれぞれ親よりも大きい値を持ちます
• 各ノードには 0 ～ 2 個の子ノードを含めることができます。

次の図を見ると、より明確になるはずです。

バイナリツリーノードの定義

通常、Javascript では次の関数を使用してバイナリ ツリー ノードを定義します。

 関数 TreeNode(val, left, right) {
     this.val = val
     this.left = 左
     this.right = 右
 }

バイナリツリーの基本的な走査（インオーダー、ポストオーダー、プレオーダー）

まず、BST の各ノードをどのようにトラバースするかを知る必要があります。これにより、BST のすべてのノードで関数を実行できるようになります。たとえば、BST で値 x を見つけたい場合は、ノードが必要です。

これを行うには主に 3 つの方法があります。幸いなことに、それらは共通のテーマを共有しています。

順序通りの走査

再帰アルゴリズムは、バイナリ ツリーの順序どおりのトラバーサルを開始するための最も簡単な方法です。考え方は次のとおりです。

• ノードが空の場合は何も行いません。それ以外の場合は、ノードの左の子に対して関数を再帰的に呼び出します。
• 次に、すべての左の子ノードをトラバースした後、ノードに対していくつかの操作を実行します。現在のノードは、最も左のノードであることが保証されます。
• 最後に、node.right の関数が呼び出されます。

Inorder アルゴリズムは、ツリー ノードを左、中央、右の順に走査します。

const inorder = (ルート) => {
    定数ノード = []
    if (ルート) {
        inorder(ルート.左)
        ノードをプッシュします(ルート.val)
        inorder(ルート.right)
    }
    ノードを返す
}
// この例のツリーでは、[1,2,3,4,5,6] が返されます

後順序トラバーサル

再帰アルゴリズムは、後順序トラバーサルを開始する最も簡単な方法です。

• ノードが空の場合は何も行いません。それ以外の場合は、ノードの左の子に対して関数を再帰的に呼び出します。
• 左の子がなくなったら、node.right の関数を呼び出します。
• 最後に、ノードに対していくつかの操作を実行します。

後順トラバーサルは、ツリー ノードを左、右、中央から訪問します。

const postorder = (ルート) => {
    定数ノード = []
    if (ルート) {
        postorder(ルート.左)
        postorder(ルート.right)
        ノードをプッシュします(ルート.val)
    }
    ノードを返す
}
// この例のツリーでは、[1,3,2,6,5,4] が返されます

事前順序トラバーサル

事前順序トラバーサルを開始する最も簡単な方法は、再帰アルゴリズムを使用することです。

• ノードが空の場合は何も行いません。それ以外の場合はノードに対して何かを実行します。
• ノードの左の子ノードをトラバースして繰り返します。
• ノードの右の子まで移動して繰り返します。

後順トラバーサルは、ツリー ノードを中央、左、右から訪問します。

const preorder = (ルート) => {
    定数ノード = []
    if (ルート) {
        ノードをプッシュします(ルート.val)
        preorder(ルート.left)
        事前注文(ルート.right)
    }
    ノードを返す
}
// この例のツリーでは、[4,2,1,3,5,6] が返されます

有効な二分探索木とは何ですか?

有効なバイナリ検索ツリー (BST) には、値が親ノードより小さいすべての左の子と、値が親ノードより大きいすべての右の子が含まれます。
ツリーが有効な二分探索ツリーであるかどうかを確認するには:

• 現在のノードが持つことができる最小値と最大値を定義します
• ノードの値がこれらの範囲内にない場合は、falseを返します。
• ノードの左の子を再帰的に検証し、最大値をノードの値に設定します。
• ノードの右の子を再帰的に検証し、最小境界をノードの値に設定します。

const isValidBST = (ルート) => {
    const ヘルパー = (ノード、最小値、最大値) => {
        if (!node) が true を返す
        node.val <= min || node.val >= max の場合、false を返します。
        ヘルパー(node.left, min, node.val) && ヘルパー(node.right, node.val, max) を返します
    }
    ヘルパーを返します(ルート、Number.MIN_SAFE_INTEGER、Number.MAX_SAFE_INTEGER)
}

二分木の最大深さを見つける方法

ここで、アルゴリズムは BST の高さ/深さを見つけようとします。言い換えれば、BST にいくつの「レベル」が含まれているかを調べていることになります。

• ノードが空の場合は、深さを追加しないので0を返します。
• それ以外の場合は、現在の深さに + 1 を追加します（1 つのレベルを通過しました）。
• ノードの子の深さを再帰的に計算し、node.leftとnode.rightの間の最大合計を返します。

定数maxDepth = function(root) {
    const calc = (ノード) => {
        if (!node) が 0 を返す
        Math.max(1 + calc(node.left), 1 + calc(node.right)) を返します
    }
    calc(root)を返す
};

2つのツリーノード間の最小共通祖先を見つける方法

難易度を上げてみましょう。バイナリツリー内の 2 つのツリーノード間の共通祖先をどのように見つけるのでしょうか?いくつか例を見てみましょう。

このツリーでは、3 と 1 の最小共通祖先は 2 です。3 と 2 の LCA は 2 です。6 と 1 と 6 の LCA は 4 です。

ここにパターンが見えますか? 2 つのツリー ノード間の LCA は、いずれかのノード自体 (ケース 3 および 2)、または最初の子が左のサブツリーのどこかにあり、2 番目の子が右のサブツリーのどこかにある親ノードのいずれかです。

2 つのツリー ノード p と q 間の最小共通祖先 (LCA) を見つけるアルゴリズムは次のとおりです。

• p または q が左または右のサブツリーに見つかるかどうかを確認します。
• 次に、現在のノードがpかqかを確認します。
• 左または右のサブツリーにpまたはqのいずれかが見つかり、pまたはqのいずれかがノード自体である場合、LCAが見つかったことになります。
• 左または右のサブツリーにpとqの両方が見つかった場合、LCAが見つかったことになります。

const lowestCommonAncestor = function(root, p, q) {
    lca = null とします
    const isCommonPath = (ノード) => {
        if (!node) が false を返す
        var isLeft = isCommonPath(node.left)
        var isRight = isCommonPath(node.right)
        var isMid = ノード == p || ノード == q
        if (isMid && isLeft || isMid && isRight || isLeft && isRight) {
            lca = ノード
        }
        isLeft || isRight || isMid を返します
    }
    isCommonPath(ルート)
    リターンLCA
};

😊 終わり

これまで、BST の深さをトラバース、検証、計算する方法を学習しました。

これで、JavaScript 初心者向けのバイナリ サーチ ツリー アルゴリズム チュートリアルに関するこの記事は終了です。JavaScript バイナリ サーチ ツリー アルゴリズムに関するより関連性の高いコンテンツについては、123WORDPRESS.COM の以前の記事を検索するか、以下の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。