logo

TechCodeview

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:

bst1

bst2

bst3

bst4

dva k jednému multiplexeru
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


výmena pamäte



// 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




d žabka
// 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');

stiahnite si video z youtube pomocou vlc 

> 
    
   
horný index v ilustrátore

 
     
  
 
    
 
     
     
    
 
 
  
  // 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: