与えられた BST 、タスクはこの中でノードを検索することです BST 。

BST で値を検索する場合は、それをソートされた配列とみなしてください。これで、次を使用して BST で検索操作を簡単に実行できるようになりました。 二分探索アルゴリズム 。

指定された二分探索ツリーでキーを検索するアルゴリズム:

番号を検索したいとしましょう バツ、 根元から始めます。それから：

• 検索する値とルートの値を比較します。
  • 等しい場合、検索は終了します。小さい場合、二分探索ツリーでは、左側のサブツリーのすべての要素が小さく、右側のサブツリーのすべての要素が大きいため、左側のサブツリーに進む必要があることがわかります。
• 横断が不可能になるまで上記の手順を繰り返します
• いずれかの反復でキーが見つかった場合は、True を返します。それ以外の場合は偽です。

BST での検索の図:

よりよく理解するには、以下の図を参照してください。

BST で検索を実装するプログラム:

C++

>

>

C

>

ラム俳優

>

ジャワ

>

>

Python3

>

>

C#

CSSを中央に配置するボタン

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // Javascript function to search a given key in a given BST> class Node {> >constructor(key) {> >this>.key = key;> >this>.left =>null>;> >this>.right =>null>;> >}> }> // A utility function to insert> // a new node with given key in BST> function> insert(node, key) {> >// If the tree is empty, return a new node> >if> (node ===>null>) {> >return> new> Node(key);> >}> >// Otherwise, recur down the tree> >if> (key   node.left = insert(node.left, key);  } else if (key>ノード.キー) { ノード.右 = 挿入(ノード.右, キー);  } // (変更されていない) ノード ポインタを返します return node; } // BST 関数でキーを検索するユーティリティ関数 search(root, key) { // 基本ケース: ルートが null またはキーがルートに存在する if (root === null || root.key === key ) { ルートを返す;  } // キーがルートのキーより大きい if (root.key return search(root.right, key); } // キーがルートのキーより小さい return search(root.left, key); } // ドライバー コード let root = null; insert(root, 30); insert(root, 70); 60); insert(root, 80); // 検索するキー let key = 6 // BST での検索 if (search(root, key) === null) { console.log(key + ' not) found'); } else { console.log(key + ' found') } key = 60; // BST での検索 if (search(root, key) === null) { console.log(キー + ' 見つかりません'); } else { console.log(key + ' 見つかりません') }>
 
 
 
 
    
 
>
 
    
 
>
 
  出力  
 
6 not found 60 found>
 
    時間計算量:    O(h)、ここで h は BST の高さです。  
    補助スペース:    O(h)、ここで h は BST の高さです。これは、再帰スタックを保存するために必要な最大スペース量が次のとおりであるためです。    h    。
 
    関連リンク：     
 
 
  二分探索ツリー挿入操作  
 
 二分探索木の削除操作