logo

TechCodeview

Introduzione all'albero di ricerca binario: tutorial sulla struttura dei dati e sugli algoritmi

Albero di ricerca binaria è una struttura dati utilizzata in informatica per organizzare e archiviare i dati in modo ordinato. L'albero di ricerca binario segue tutte le proprietà dell'albero binario e dei suoi Sinistra child contiene valori inferiori al nodo genitore e al Giusto child contiene valori maggiori del nodo genitore. Questa struttura gerarchica consente un efficiente Ricerca , Inserimento , E Cancellazione operazioni sui dati memorizzati nell'albero.

Albero di ricerca binaria




Tabella dei contenuti

Il processo Android acore continua a fermarsi

Cos'è l'albero di ricerca binario?

Albero di ricerca binario (BST) è un tipo speciale di albero binario in cui il figlio sinistro di un nodo ha un valore inferiore al valore del nodo e il figlio destro ha un valore maggiore del valore del nodo. Questa proprietà è chiamata proprietà BST e rende possibile cercare, inserire ed eliminare in modo efficiente gli elementi nell'albero.



Proprietà dell'albero di ricerca binario:

  • Il sottoalbero sinistro di un nodo contiene solo nodi con chiavi inferiori alla chiave del nodo.
  • Il sottoalbero destro di un nodo contiene solo nodi con chiavi maggiori della chiave del nodo.
  • Ciò significa che tutto a sinistra della radice è inferiore al valore della radice e tutto a destra della radice è maggiore del valore della radice. Grazie a questa prestazione, una ricerca binaria è molto semplice.
  • Anche i sottoalberi sinistro e destro devono essere un albero di ricerca binario.
  • Non devono esserci nodi duplicati (BST può avere valori duplicati con approcci di gestione diversi)

Gestione dei valori duplicati nell'albero di ricerca binaria:

  • Dobbiamo seguire un processo coerente, ad esempio memorizzare il valore duplicato a sinistra o memorizzare il valore duplicato a destra della radice, ma essere coerenti con il proprio approccio.

Operazioni di base sull'albero di ricerca binario:

1. Ricerca di un nodo in BST:

Cercare nel BST significa individuare un nodo specifico nella struttura dati. Nell'albero di ricerca binario, la ricerca di un nodo è semplice grazie al suo ordine specifico. I passaggi per la ricerca di un nodo nell'albero di ricerca binaria sono elencati come segue:

  1. Innanzitutto, confronta l'elemento da cercare con l'elemento radice dell'albero.
    • Se root corrisponde all'elemento di destinazione, restituisce la posizione del nodo.
    • Se non corrisponde, controlla se l'elemento è inferiore all'elemento radice, se è più piccolo dell'elemento radice, spostati al sottoalbero sinistro.
    • Se è più grande dell'elemento radice, spostati al sottoalbero destro.
  2. Ripetere la procedura precedente in modo ricorsivo finché non viene trovata la corrispondenza.
  3. Se l'elemento non viene trovato o non è presente nell'albero, restituisce NULL.

Ora capiamo la ricerca nell'albero binario usando un esempio:

Di seguito viene fornito un BST e dobbiamo cercare l'elemento 6.




Codice:

Di seguito è riportata l'implementazione della ricerca in 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->chiave = oggetto;  temp->sinistra = temp->destra = NULL;  temperatura di ritorno; } // Una funzione di utilità per inserire // un nuovo nodo con la chiave specificata in BST struct node* insert(struct node* node, int key) { // Se l'albero è vuoto, restituisce un nuovo nodo if (node ​​== NULL ) restituisce nuovoNodo(chiave);  // Altrimenti, ricorre lungo l'albero if (key< node->chiave) nodo->sinistra = inserisci(nodo->sinistra, chiave);  else if (chiave> nodo->chiave) nodo->destra = insert(nodo->destra, chiave);  // Restituisce il puntatore del nodo (invariato) return node; } // Funzione di utilità per cercare una chiave in un BST struct node* search(struct node* root, int key) root->key == key) return root;  // La chiave è maggiore della chiave di root se (root->key< key)  return search(root->destra, chiave);  // La chiave è più piccola della chiave di root return search(root->left, key);>
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->chiave = oggetto;  temp->sinistra = temp->destra = NULL;  temperatura di ritorno; } // Una funzione di utilità per inserire // un nuovo nodo con la chiave specificata in BST struct node* insert(struct node* node, int key) { // Se l'albero è vuoto, restituisce un nuovo nodo if (node ​​== NULL ) restituisce nuovoNodo(chiave);  // Altrimenti, ricorre lungo l'albero if (key< node->chiave) nodo->sinistra = inserisci(nodo->sinistra, chiave);  else if (chiave> nodo->chiave) nodo->destra = insert(nodo->destra, chiave);  // Restituisce il puntatore del nodo (invariato) return node; } // Funzione di utilità per cercare una chiave in una BST struct node* search(struct node* root, int key)>
Giava 
// 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.key)  node.left = insert(node.left, key);  else if (key>nodo.chiave) nodo.destra = insert(nodo.destra, chiave);  // Restituisce il puntatore del nodo (invariato) return node;  } // Funzione di utilità per cercare una chiave in una ricerca di nodo BST (root del nodo, chiave int) // Casi base: root è null o la chiave è presente alla root se (root == null>
Pitone 
# 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.key: node.left = insert(node.left, key) elif key>node.key: node.right = insert(node.right, key) # Restituisce il puntatore del nodo (invariato) return node # Funzione di utilità per cercare una chiave in un BST def search(root, key): # Base Cases: root is null o chiave è presente su root se root è None o root.key == chiave: return root # La chiave è maggiore della chiave di root se root.key< key: return search(root.right, key) # Key is smaller than root's key return search(root.left, key)>
JavaScript 
// 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.key) {  node.left = insert(node.left, key); } else if (key>nodo.chiave) { nodo.destra = insert(nodo.destra, chiave); } // Restituisce il puntatore del nodo (invariato) return node; } // Funzione di utilità per cercare una chiave in una funzione BST search(root, key) { // Casi base: root è null o la chiave è presente alla root se (root === null || root.key === key ) { restituisce radice; } // La chiave è maggiore della chiave di root se (root.key< key) {  return search(root.right, key); } // Key is smaller than root's key return search(root.left, key); }>


2. Inserisci un nodo in un BST :

All'anta viene sempre inserita una nuova chiave. Inizia a cercare una chiave dalla radice fino a un nodo foglia. Una volta trovato un nodo foglia, il nuovo nodo viene aggiunto come figlio del nodo foglia.


errore: impossibile trovare o caricare la classe principale

Codice:

Di seguito è riportata l'implementazione dell'Inserimento di un singolo nodo nell'Albero di Ricerca Binario:

C++ 
// Given Node Structure struct node {  int key;  struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) {  struct node* temp = (struct node*)malloc(  sizeof(struct node));  temp->chiave = oggetto;  temp->sinistra = temp->destra = NULL;  temperatura di ritorno; } // Funzione per inserire un nuovo nodo con // la chiave data in BST struct node* insert(struct node* node, int key) { // Se l'albero è vuoto, restituisce un nuovo nodo if (node ​​== NULL) return nuovoNodo(chiave);  // Altrimenti, ricorre lungo l'albero if (key< node->chiave) { nodo->sinistra = insert(nodo->sinistra, chiave);  } else if (chiave> nodo->chiave) { nodo->destra = insert(nodo->destra, chiave);  } // Restituisce il puntatore del nodo return node; }>
C 
// Given Node Structure struct node {  int key;  struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) {  struct node* temp  = (struct node*)malloc(  sizeof(struct node));  temp->chiave = oggetto;  temp->sinistra = temp->destra = NULL;  temperatura di ritorno; } // Funzione per inserire un nuovo nodo con // la chiave data in BST struct node* insert(struct node* node, int key) { // Se l'albero è vuoto, restituisce un nuovo nodo if (node ​​== NULL) return nuovoNodo(chiave);  // Altrimenti, ricorre lungo l'albero if (key< node->chiave) { nodo->sinistra = insert(nodo->sinistra, chiave);  } else if (chiave> nodo->chiave) { nodo->destra = insert(nodo->destra, chiave);  } // Restituisce il puntatore del nodo return node; }>
Giava 
class GFG {  // Given Node Structure  static class node {  int key;  node left, right;  };  // Function to create a new BST node  static node newNode(int item)  {  node temp = new node();  temp.key = item;  temp.left = temp.right = null;  return temp;  }  // Function to insert a new node with  // given key in BST  static 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.key) {  node.left = insert(node.left, key);  }  else if (key>nodo.chiave) { nodo.destra = insert(nodo.destra, chiave);  } // Restituisce il nodo return node;  } }>
Python3 
# Given Node Structure class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to insert a new node with # 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.key: node.left = insert(node.left, key) elif key>nodo.chiave: nodo.destra = insert(nodo.destra, chiave) # Restituisce il puntatore del nodo return nodo>
Javascript 
// Given Node Structure class Node {  constructor(key){  this.key = key;  this.left = null;  this.right = null;  } } // 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.key)  {  node.left = insert(node.left, key);  }  else if (key>nodo.chiave) { nodo.destra = insert(nodo.destra, chiave);  } // Restituisce il puntatore del nodo return node; }>

Complessità temporale: O(N), dove N è il numero di nodi del BST
Spazio ausiliario: O(1)

Attore Rekha

3. Elimina un nodo di BST :

Viene utilizzato per eliminare un nodo con chiave specifica dal BST e restituire il nuovo BST.

Diversi scenari per l'eliminazione del nodo:

Il nodo da eliminare è il nodo foglia :

È semplice, puoi semplicemente annullarlo.

d1

Il nodo da eliminare ha un figlio :

Puoi semplicemente sostituire il nodo con il nodo figlio.

file

Il nodo da eliminare ha due figli :

Qui dobbiamo farlo eliminare il nodo è tale che l'albero risultante segua le proprietà di un BST. Il trucco è trovare il successore in ordine del nodo. Copia il contenuto del successore in ordine nel nodo ed elimina il successore in ordine.

d3

Prenditi cura delle seguenti cose durante l'eliminazione di un nodo di un BST:

  1. Bisogna capire quale sarà la sostituzione del nodo da eliminare.
  2. Desideri un'interruzione minima della struttura ad albero esistente
  3. Può prendere il nodo sostitutivo dal sottoalbero sinistro o destro dei nodi eliminati.
  4. Se lo prendiamo dal sottoalbero di sinistra, dobbiamo prendere il valore più grande nel sottoalbero di sinistra.
  5. Se prendiamo se dal sottoalbero di destra, dobbiamo prendere il valore più piccolo nel sottoalbero di destra.

Codice:

Di seguito è riportata l'implementazione della cancellazione in BST:

forzatura cache pulita npm
C++ 
// C++ program to delete // a node of BST // Given Node node struct node {  int key;  struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) {  struct node* temp  = (struct node*)malloc(  sizeof(struct node));  temp->chiave = oggetto;  temp->sinistra = temp->destra = NULL;  temperatura di ritorno; } // Funzione per inserire un nuovo nodo con // la chiave data in BST struct node* insert(struct node* node, int key) { // Se l'albero è vuoto, restituisce un nuovo nodo if (node ​​== NULL) return nuovoNodo(chiave);  // Altrimenti, ricorre lungo l'albero if (key< node->chiave) { nodo->sinistra = insert(nodo->sinistra, chiave);  } else if (chiave> nodo->chiave) { nodo->destra = insert(nodo->destra, chiave);  } // Restituisce il puntatore del nodo return node; } // Funzione che restituisce il nodo con il // valore chiave minimo trovato nell'albero struct node* minValueNode(struct node* node) { struct node* current = node;  // Ciclo in basso per trovare la foglia più a sinistra while (current && current->left != NULL) current = current->left;  corrente di ritorno; } // Funzione che cancella la chiave e // restituisce la nuova root struct node* deleteNode(struct node* root, int key) { // base Case if (root == NULL) return root;  // Se la chiave da eliminare è // più piccola della chiave di root, // allora si trova nel sottoalbero sinistro if (key< root->chiave) { root->sinistra = deleteNode(root->sinistra, chiave);  } // Se la chiave da eliminare è // maggiore della chiave di root, // allora si trova nel sottoalbero destro else if (key> root->key) { root->right = deleteNode(root-> destra, chiave);  } // Se la chiave è uguale a quella di root, // allora questo è il nodo // da eliminare else { // Nodo con un solo figlio // o nessun figlio if (root->left == NULL) { struct nodo* temp = root->destra;  libero(radice);  temperatura di ritorno;  } else if (root->right == NULL) { struct node* temp = root->left;  libero(radice);  temperatura di ritorno;  } // Nodo con due figli: // Ottieni il successore in ordine (il più piccolo // nel sottoalbero di destra) struct node* temp = minValueNode(root->right);  // Copia il contenuto // del successore in ordine su questo nodo root->key = temp->key;  // Elimina il successore in ordine root->right = deleteNode(root->right, temp->key);  } restituisce root; }>
C 
// C program to delete // a node of BST // Given Node node struct node {  int key;  struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) {  struct node* temp  = (struct node*)malloc(  sizeof(struct node));  temp->chiave = oggetto;  temp->sinistra = temp->destra = NULL;  temperatura di ritorno; } // Funzione per inserire un nuovo nodo con // la chiave data in BST struct node* insert(struct node* node, int key) { // Se l'albero è vuoto, restituisce un nuovo nodo if (node ​​== NULL) return nuovoNodo(chiave);  // Altrimenti, ricorre lungo l'albero if (key< node->chiave) { nodo->sinistra = insert(nodo->sinistra, chiave);  } else if (chiave> nodo->chiave) { nodo->destra = insert(nodo->destra, chiave);  } // Restituisce il puntatore del nodo return node; } // Funzione che restituisce il nodo con il // valore chiave minimo trovato nell'albero struct node* minValueNode(struct node* node) { struct node* current = node;  // Ciclo in basso per trovare la foglia più a sinistra while (current && current->left != NULL) current = current->left;  corrente di ritorno; } // Funzione che cancella la chiave e // restituisce la nuova root struct node* deleteNode(struct node* root, int key) { // base Case if (root == NULL) return root;  // Se la chiave da eliminare è // più piccola della chiave di root, // allora si trova nel sottoalbero sinistro if (key< root->chiave) { root->sinistra = deleteNode(root->sinistra, chiave);  } // Se la chiave da eliminare è // maggiore della chiave di root, // allora si trova nel sottoalbero destro else if (key> root->key) { root->right = deleteNode(root-> destra, chiave);  } // Se la chiave è uguale a quella di root, // allora questo è il nodo // da eliminare else { // Nodo con un solo figlio // o nessun figlio if (root->left == NULL) { struct nodo* temp = root->destra;  libero(radice);  temperatura di ritorno;  } else if (root->right == NULL) { struct node* temp = root->left;  libero(radice);  temperatura di ritorno;  } // Nodo con due figli: // Ottieni il successore in ordine (il più piccolo // nel sottoalbero di destra) struct node* temp = minValueNode(root->right);  // Copia il contenuto // del successore in ordine su questo nodo root->key = temp->key;  // Elimina il successore in ordine root->right = deleteNode(root->right, temp->key);  } restituisce root; }>
Giava 
// Java program for Delete a Node of BST class GFG {  // Given Node node  static class node {  int key;  node left, right;  };  // Function to create a new BST node  static node newNode(int item)  {  node temp = new node();  temp.key = item;  temp.left = temp.right = null;  return temp;  }  // Function to insert a new node with  // given key in BST  static 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.key) {  node.left = insert(node.left, key);  }  else if (key>nodo.chiave) { nodo.destra = insert(nodo.destra, chiave);  } // Restituisce il nodo return node;  } // Funzione che restituisce il nodo con il // valore chiave minimo trovato nell'albero static node minValueNode(node ​​node) { node current = node;  // Ciclo indietro per trovare la foglia più a sinistra while (current != null && current.left != null) current = current.left;  corrente di ritorno;  } // Funzione che cancella la chiave e // restituisce la nuova root static node deleteNode(node ​​root, int key) { // base Case if (root == null) return root;  // Se la chiave da eliminare è // più piccola della chiave di root, // allora si trova nel sottoalbero sinistro if (key< root.key) {  root.left = deleteNode(root.left, key);  }  // If the key to be deleted is  // greater than the root's key,  // then it lies in right subtree  else if (key>root.key) { root.right = deleteNode(root.right, key);  } // Se la chiave è uguale alla chiave di root, // allora questo è il nodo // da eliminare else { // Nodo con un solo figlio // o nessun figlio if (root.left == null) { nodo temp = root.right;  temperatura di ritorno;  } else if (root.right == null) { nodo temp = root.left;  temperatura di ritorno;  } // Nodo con due figli: // Ottieni il successore in ordine (il più piccolo // nel sottoalbero di destra) node temp = minValueNode(root.right);  // Copia il contenuto // del successore in ordine su questo nodo root.key = temp.key;  // Elimina il successore in ordine root.right = deleteNode(root.right, temp.key);  } restituisce root;  }>
Pitone 
# Python program to delete a node of BST # Given Node node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to insert a new node with # given key in BST def insert(root, key): # If the tree is empty, return a new node if root is None: return Node(key) # Otherwise, recur down the tree if key < root.key: root.left = insert(root.left, key) elif key>root.key: root.right = insert(root.right, key) # Restituisce il puntatore del nodo return root # Funzione per eseguire l'attraversamento in ordine di BST def inorder(root): if root: inorder(root.left) print(root. key, end=' ') inorder(root.right) # Funzione che restituisce il nodo con il # valore chiave minimo trovato nell'albero def minValueNode(node): current = node # Effettua un ciclo verso il basso per trovare la foglia più a sinistra while current e current.left non è None: current = current.left return current # Funzione che cancella la chiave e # restituisce la nuova radice def deleteNode(root, key): # base Case se root è None: return root # Se la chiave deve essere cancellato è # più piccolo della chiave di root, # quindi si trova nel sottoalbero sinistro se chiave< root.key: root.left = deleteNode(root.left, key) # If the key to be deleted is # greater than the root's key, # then it lies in right subtree elif key>root.key: root.right = deleteNode(root.right, key) # Se la chiave è uguale alla chiave di root, # allora questo è il nodo # da eliminare altrimenti: # Nodo con un solo figlio # o nessun figlio se root.left è None: temp = root.right root = None return temp elif root.right è None: temp = root.left root = None return temp # Nodo con due figli: # Ottieni il successore in ordine(più piccolo # nel sottoalbero destro) temp = minValueNode(root.right) # Copia il contenuto del successore in ordine # in questo nodo root.key = temp.key # Elimina il successore in ordine root.right = deleteNode(root.right, temp.key) restituisce radice>

4. Attraversamento (attraversamento in ordine di BST) :

Nel caso degli alberi di ricerca binari (BST), l'attraversamento in ordine fornisce i nodi in ordine non decrescente. Visitiamo prima il figlio sinistro, poi la radice e infine il figlio destro.

Di seguito è riportata l'implementazione di come eseguire l'attraversamento in ordine di un albero di ricerca binario:

C++ 
// C++ program to implement // inorder traversal of BST #include  using namespace std; // Given Node node struct node {  int key;  struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) {  struct node* temp = (struct node*)malloc(  sizeof(struct node));  temp->chiave = oggetto;  temp->sinistra = temp->destra = NULL;  temperatura di ritorno; } // Funzione per inserire un nuovo nodo con // la chiave data in BST struct node* insert(struct node* node, int key) { // Se l'albero è vuoto, restituisce un nuovo nodo if (node ​​== NULL) return nuovoNodo(chiave);  // Altrimenti, ricorre lungo l'albero if (key< node->chiave) { nodo->sinistra = insert(nodo->sinistra, chiave);  } else if (chiave> nodo->chiave) { nodo->destra = insert(nodo->destra, chiave);  } // Restituisce il puntatore del nodo return node; } // Funzione per eseguire l'attraversamento in ordine del BST void inorder(struct node* root) { if (root != NULL) { inorder(root->left);  cout<< ' ' << root->chiave;  ordine(radice->destra);  } } // Driver Code int main() { /* Creiamo il seguente BST 50 /  30 70 /  /  20 40 60 80 */ struct node* root = NULL;  // Creazione della radice BST = insert(root, 50);  inserisci(radice, 30);  inserisci(radice, 20);  inserisci(radice, 40);  inserisci(radice, 70);  inserisci(radice, 60);  inserisci(radice, 80);  // Chiamata di funzione inorder(root);  restituire 0; } // Questo codice è un contributo di shivanisinghss2110>
C 
// C program to implement // inorder traversal of BST #include  #include  // Given Node node struct node {  int key;  struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) {  struct node* temp  = (struct node*)malloc(  sizeof(struct node));  temp->chiave = oggetto;  temp->sinistra = temp->destra = NULL;  temperatura di ritorno; } // Funzione per inserire un nuovo nodo con // la chiave data in BST struct node* insert(struct node* node, int key) { // Se l'albero è vuoto, restituisce un nuovo nodo if (node ​​== NULL) return nuovoNodo(chiave);  // Altrimenti, ricorre lungo l'albero if (key< node->chiave) { nodo->sinistra = insert(nodo->sinistra, chiave);  } else if (chiave> nodo->chiave) { nodo->destra = insert(nodo->destra, chiave);  } // Restituisce il puntatore del nodo return node; } // Funzione per eseguire l'attraversamento in ordine del BST void inorder(struct node* root) { if (root != NULL) { inorder(root->left);  printf('%d ', root->chiave);  ordine(radice->destra);  } } // Driver Code int main() { /* Creiamo il seguente BST 50 /  30 70 /  /  20 40 60 80 */ struct node* root = NULL;  // Creazione della radice BST = insert(root, 50);  inserisci(radice, 30);  inserisci(radice, 20);  inserisci(radice, 40);  inserisci(radice, 70);  inserisci(radice, 60);  inserisci(radice, 80);  // Chiamata di funzione inorder(root);  restituire 0; }>
Giava 
import java.io.*; // Java program for Inorder Traversal class GFG {  // Given Node node  static class node {  int key;  node left, right;  };  // Function to create a new BST node  static node newNode(int item)  {  node temp = new node();  temp.key = item;  temp.left = temp.right = null;  return temp;  }  // Function to insert a new node with  // given key in BST  static 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.key) {  node.left = insert(node.left, key);  }  else if (key>nodo.chiave) { nodo.destra = insert(nodo.destra, chiave);  } // Restituisce il nodo return node;  } // Funzione per eseguire l'attraversamento in ordine del BST static void inorder(node ​​root) { if (root!= null) { inorder(root.left);  System.out.print(' ' + root.key);  ordine(root.right);  } } // Codice driver public static void main(String[] args) { /* Creiamo il seguente BST 50 /  30 70 /  /  20 40 60 80 */ node root = null;  // inserendo il valore 50 root = insert(root, 50);  // inserendo il valore 30 insert(root, 30);  // inserendo il valore 20 insert(root, 20);  // inserendo il valore 40 insert(root, 40);  // inserendo il valore 70 insert(root, 70);  // inserendo il valore 60 insert(root, 60);  // inserendo il valore 80 insert(root, 80);  // stampa il BST inorder(root);  } } // Questo codice è un contributo di abhijitjadhav1998>
Python3 
# Python program to implement # inorder traversal of BST # Given Node node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to create a new BST node def newNode(item): temp = Node(item) temp.key = item temp.left = temp.right = None return temp # Function to insert a new node with # given key in BST def insert(node, key): # If the tree is empty, return a new node if node is None: return newNode(key) # Otherwise, recur down the tree if key < node.key: node.left = insert(node.left, key) elif key>node.key: node.right = insert(node.right, key) # Restituisce il puntatore del nodo return node # Funzione per eseguire l'attraversamento in ordine di BST def inorder(root): if root: inorder(root.left) print(root. key, end=' ') inorder(root.right) # Codice driver if __name__ == '__main__': # Creiamo il seguente BST # 50 # /  # 30 70 # /  /  # 20 40 60 80 root = Nessuno # Creazione del BST root = insert(root, 50) insert(root, 30) insert(root, 20) insert(root, 40) insert(root, 70) insert(root, 60) insert(root , 80) # Funzione Chiama inorder(root) #Questo codice è fornito da japmeet01>
Produzione 
 20 30 40 50 60 70 80>

Complessità temporale: O(N), dove N è il numero di nodi del BST
Spazio ausiliario: O(1)

Applicazioni della BST:

  • Algoritmi grafici: I BST possono essere utilizzati per implementare algoritmi grafici, come negli algoritmi di spanning tree minimo.
  • Code prioritarie: I BST possono essere utilizzati per implementare code di priorità, dove l'elemento con la priorità più alta si trova alla radice dell'albero e gli elementi con priorità inferiore sono archiviati nei sottoalberi.
  • Albero binario di ricerca autobilanciante: I BST possono essere utilizzati come strutture dati autobilanciate come l'albero AVL e l'albero rosso-nero.
  • Archiviazione e recupero dei dati: I BST possono essere utilizzati per archiviare e recuperare rapidamente i dati, come nei database, dove la ricerca di un record specifico può essere eseguita in tempo logaritmico.

Vantaggi:

  • Ricerca veloce: La ricerca di un valore specifico in un BST ha una complessità temporale media di O(log n), dove n è il numero di nodi nell'albero. Questo è molto più veloce della ricerca di un elemento in un array o in una lista concatenata, che hanno una complessità temporale di O(n) nel caso peggiore.
  • Attraversamento in ordine: I BST possono essere attraversati in ordine, visitando il sottoalbero sinistro, la radice e il sottoalbero destro. Questo può essere utilizzato per ordinare un set di dati.
  • Efficienza in termini di spazio: I BST sono efficienti in termini di spazio poiché non memorizzano informazioni ridondanti, a differenza degli array e degli elenchi collegati.

Svantaggi:

  • Alberi inclinati: Se un albero viene distorto, la complessità temporale delle operazioni di ricerca, inserimento ed eliminazione sarà O(n) anziché O(log n), il che può rendere l'albero inefficiente.
  • Tempo aggiuntivo richiesto: Gli alberi autobilancianti necessitano di tempo aggiuntivo per mantenere l'equilibrio durante le operazioni di inserimento e cancellazione.
  • Efficienza: I BST non sono efficienti per set di dati con molti duplicati poiché sprecheranno spazio.

Domande frequenti(Domande frequenti)sull'albero di ricerca binario:

1. Cos'è un albero di ricerca binario?

Un albero di ricerca binario (BST) lo è un albero binario in cui ogni nodo nel sottoalbero di sinistra è inferiore alla radice e ogni nodo nel sottoalbero di destra ha un valore maggiore della radice . Le proprietà di un albero binario di ricerca sono ricorsive: se consideriamo un nodo qualsiasi come radice, queste proprietà rimarranno vere.

2. Cos'è l'operazione dell'albero di ricerca binario?

Ci sono tre operazioni principali nell'albero di ricerca binaria: 1. Inserimento, 2. Cancellazione, 3. Ricerca. Grazie alle sue proprietà è efficiente cercare qualsiasi elemento nell'albero di ricerca binaria.

3. Cos'è l'albero di ricerca binario e l'albero AVL?

Albero di ricerca binaria : Un albero di ricerca binario (BST) è un albero binario in cui ogni nodo nel sottoalbero di sinistra è inferiore alla radice e ogni nodo nel sottoalbero di destra ha un valore maggiore della radice.

Albero AVL : Gli alberi di ricerca binaria (BST) che si autobilanciano e ruotano automaticamente sono noti come alberi AVL.

4. Quali sono gli usi dell'albero di ricerca binario?

Gli alberi di ricerca binari possono essere utilizzati per implementare tipi di dati astratti come insiemi dinamici, tabelle di ricerca e code di priorità, e utilizzato in algoritmi di ordinamento come l'ordinamento degli alberi.

5. Qual è la differenza tra albero di ricerca binario e albero binario?

Un albero di ricerca binario è un albero che segue un ordine per disporre gli elementi, mentre l'albero binario non segue alcun ordine.

nome utente

Articoli Correlati:

  • Applicazione della BST
  • Applicazioni, vantaggi e svantaggi dell'albero di ricerca binario
  • Inserimento nell'albero binario di ricerca (BST)
  • Ricerca nell'albero di ricerca binario (BST)
  • Cancellazione nell'albero di ricerca binario (BST)