VYHĽADÁVANIE V BINÁRNOM VYHĽADÁVACOM STROME (BST)

Vzhľadom na a BST , úlohou je vyhľadať uzol v tomto BST .

Ak chcete hľadať hodnotu v BST, považujte ju za zoradené pole. Teraz môžeme jednoducho vykonať operáciu vyhľadávania v BST pomocou Binárny vyhľadávací algoritmus .

Algoritmus na vyhľadanie kľúča v danom strome binárneho vyhľadávania:

Povedzme, že chceme vyhľadať číslo X, Začíname pri koreni. potom:

Hľadanú hodnotu porovnávame s hodnotou koreňa.
- Ak je rovnaký, skončili sme s hľadaním, ak je menší, vieme, že musíme prejsť do ľavého podstromu, pretože v binárnom vyhľadávacom strome sú všetky prvky v ľavom podstrome menšie a všetky prvky v pravom podstrome sú väčšie.
Opakujte vyššie uvedený krok, kým už nebude možné prechádzať
Ak sa pri ktorejkoľvek iterácii nájde kľúč, vráťte hodnotu True. Inak Nepravda.

Ilustrácia vyhľadávania v BST:

Pre lepšie pochopenie si pozrite nižšie uvedený obrázok:

Odporúčaný postupVyhľadajte uzol v BSTTry It!

Program na implementáciu vyhľadávania v BST:

C++

// C++ function to search a given key in a given BST> #include> using> namespace> std;> struct> node {> > int> key;> > struct> node *left, *right;> };> // A utility function to create a new BST node> struct> node* newNode(> int> item)> {> > struct> node* temp> > => new> struct> node;> > temp->kľúč = položka;> > temp->vľavo = teplota->vpravo = NULL;> > return> temp;> }> // A utility function to insert> // a new node with given key in BST> struct> node* insert(> struct> node* node,> int> key)> {> > // If the tree is empty, return a new node> > if> (node == NULL)> > return> newNode(key);> > // Otherwise, recur down the tree> > if> (key key)> > node->left = insert(node->left, key);> > else> if> (key>uzol->kľúč)> > node->vpravo = vložiť(uzol->vpravo, kľúč);> > // Return the (unchanged) node pointer> > return> node;> }> // Utility function to search a key in a BST> struct> node* search(> struct> node* root,> int> key)> > > // Base Cases: root is null or key is present at root> > if> (root == NULL> // Driver Code> int> main()> {> > struct> node* root = NULL;> > root = insert(root, 50);> > insert(root, 30);> > insert(root, 20);> > insert(root, 40);> > insert(root, 70);> > insert(root, 60);> > insert(root, 80);> > // Key to be found> > int> key = 6;> > // Searching in a BST> > if> (search(root, key) == NULL)> > cout < < key < <> ' not found'> < < endl;> > else> > cout < < key < <> ' found'> < < endl;> > key = 60;> > // Searching in a BST> > if> (search(root, key) == NULL)> > cout < < key < <> ' not found'> < < endl;> > else> > cout < < key < <> ' found'> < < endl;> > return> 0;> }>

C

// C function to search a given key in a given BST> #include> #include> struct> node {> > int> key;> > struct> node *left, *right;> };> // A utility function to create a new BST node> struct> node* newNode(> int> item)> {> > struct> node* temp> > = (> struct> node*)> malloc> (> sizeof> (> struct> node));> > temp->kľúč = položka;> > temp->vľavo = teplota->vpravo = NULL;> > return> temp;> }> // A utility function to insert> // a new node with given key in BST> struct> node* insert(> struct> node* node,> int> key)> {> > // If the tree is empty, return a new node> > if> (node == NULL)> > return> newNode(key);> > // Otherwise, recur down the tree> > if> (key key)> > node->left = insert(node->left, key);> > else> if> (key>uzol->kľúč)> > node->vpravo = vložiť(uzol->vpravo, kľúč);> > // Return the (unchanged) node pointer> > return> node;> }> // Utility function to search a key in a BST> struct> node* search(> struct> node* root,> int> key)> > // Driver Code> int> main()> {> > struct> node* root = NULL;> > root = insert(root, 50);> > insert(root, 30);> > insert(root, 20);> > insert(root, 40);> > insert(root, 70);> > insert(root, 60);> > insert(root, 80);> > // Key to be found> > int> key = 6;> > // Searching in a BST> > if> (search(root, key) == NULL)> > printf> (>

'%d not found
'>

, key);> > else> > printf> (>

'%d found
'>

, key);> > key = 60;> > // Searching in a BST> > if> (search(root, key) == NULL)> > printf> (>

'%d not found
'>

, key);> > else> > printf> (>

'%d found
'>

, key);> > return> 0;> }>

Java

// Java program to search a given key in a given BST> class> Node {> > int> key;> > Node left, right;> > public> Node(> int> item) {> > key = item;> > left = right => null> ;> > }> }> class> BinarySearchTree {> > Node root;> > // Constructor> > BinarySearchTree() {> > root => null> ;> > }> > // A utility function to insert> > // a new node with given key in BST> > Node insert(Node node,> int> key) {> > // If the tree is empty, return a new node> > if> (node ==> null> ) {> > node => new> Node(key);> > return> node;> > }> > // Otherwise, recur down the tree> > if>

(key   node.left = insert(node.left, key);  else if (key>node.key) node.right = insert(uzol.right, key);  // Vráti (nezmenený) ukazovateľ uzla return node;  } // Funkcia pomôcky na vyhľadávanie kľúča pri vyhľadávaní uzla BST (koreň uzla, kľúč int) // Kód ovládača public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree();  // Vloženie uzlov tree.root = tree.insert(tree.root, 50);  tree.insert(tree.root, 30);  tree.insert(tree.root, 20);  tree.insert(tree.root, 40);  tree.insert(tree.root, 70);  tree.insert(tree.root, 60);  tree.insert(tree.root, 80);  // Kľúč, ktorý sa má nájsť int key = 6;  // Hľadanie v BST if (tree.search(tree.root, key) == null) System.out.println(key + ' not found');  else System.out.println(kláves + ' nájdené');  kľúč = 60;  // Hľadanie v BST if (tree.search(tree.root, key) == null) System.out.println(key + ' not found');  else System.out.println(kláves + ' nájdené');  } }>

Python3

# Python3 function to search a given key in a given BST> class> Node:> > # Constructor to create a new node> > def> __init__(> self> , key):> > self> .key> => key> > self> .left> => None> > self> .right> => None> # A utility function to insert> # a new node with the given key in BST> def> insert(node, key):> > # If the tree is empty, return a new node> > if> node> is> None> :> > return> Node(key)> > # Otherwise, recur down the tree> > if>

key   node.left = insert(node.left, key)  elif key>node.key: node.right = insert(node.right, key) # Vráti (nezmenený) ukazovateľ uzla návratový uzol # Funkcia pomôcky na vyhľadávanie kľúča v BST def search(root, key): # Základné prípady: root je null alebo kľúč je prítomný v koreni, ak root je None alebo root.key == kľúč: return root # Kľúč je väčší ako root, ak root.key return search(root.right, key) # Kľúč je menší ako root 's key return search(root.left, key) # Driver Code if __name__ == '__main__': root = Žiadny root = insert(root, 50) insert(root, 30) insert(root, 20) insert (koreň, 40) insert(koreň, 70) insert(koreň, 60) insert(koreň, 80) # Kľúč, ktorý sa má nájsť kľúč = 6 # Vyhľadávanie v BST, ak je vyhľadávanie (koreň, kľúč) Žiadne: print(kľúč, 'nenájdené') else: print(kľúč, 'nájdený') kľúč = 60 # Vyhľadávanie v BST, ak je search(koreň, kľúč) Žiadne: print(kľúč, 'nenájdené') else: print(key, 'found')>

C#

// C# function to search a given key in a given BST> using> System;> public> class> Node {> > public> int> key;> > public> Node left, right;> }> public> class> BinaryTree {> > // A utility function to create a new BST node> > public> Node NewNode(> int> item)> > {> > Node temp => new> Node();> > temp.key = item;> > temp.left = temp.right => null> ;> > return> temp;> > }> > // A utility function to insert> > // a new node with given key in BST> > public> Node Insert(Node node,> int> key)> > {> > // If the tree is empty, return a new node> > if> (node ==> null> )> > return> NewNode(key);> > // Otherwise, recur down the tree> > if>

(key   node.left = Insert(node.left, key);  else if (key>node.key) node.right = Insert(uzol.right, key);  // Vráti (nezmenený) ukazovateľ uzla return node;  } // Funkcia pomôcky na vyhľadávanie kľúča vo verejnom uzle BST (koreň uzla, kľúč int) // Základné prípady: root je null alebo kľúč je prítomný v koreni, ak (root == null // Driver Code public static void Main () { koreň uzla = null; bt , 40 bt.Insert(koreň, 60); bt.Vložiť(koreň, 80); bt.Search(root, key) == null) Console.WriteLine(key + ' not found' else Console.WriteLine(key + ' found'); // Hľadanie v BST if (bt.Search(koreň, kľúč) == null) Console.WriteLine(key + ' not found' else Console.WriteLine(key + ' found');

>    
      
      
       
   
       
       
     
     
   
          // 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>uzol.kľúč) { uzol.vpravo = vložiť(uzol.vpravo, kľúč);  } // Vráti (nezmenený) ukazovateľ uzla return node; } // Pomôcka funkcia na vyhľadávanie kľúča vo funkcii BST search(root, key) { // Základné prípady: root má hodnotu null alebo kľúč je prítomný v koreňovom adresári if (root === null || root.key === kľúč ) { return root;  } // Kľúč je väčší ako root's key if (root.key return search(root.right, key); } // Key je menší ako root's key return search(root.left, key); } // Kód ovládača nech root = vlož(koreň, 30); vlož(koreň, 70); 60); // kľúč, ktorý sa má nájsť, nech kľúč = 6; nájdené'); } else { console.log(key + ' found'); } key = 60; key + ' not found' } else { console.log(key + ' found'); }>    
  
  
   
      
    
      
    
  Výkon    
  6 not found 60 found 
      Časová zložitosť:     O(h), kde h je výška BST.   
    Pomocný priestor:     O(h), kde h je výška BST. Je to preto, že maximálne množstvo priestoru potrebného na uloženie zásobníka rekurzie by bolo     h     .  
      Súvisiace odkazy:        
       Operácia vloženia binárneho vyhľadávacieho stromu    
    Operácia odstránenia binárneho vyhľadávacieho stromu