UN Albero di ricerca binaria è una struttura dati utilizzata in informatica per organizzare e archiviare i dati in modo ordinato. Ogni nodo in a Albero di ricerca binaria ha al massimo due figli, a Sinistra bambino e a Giusto bambino, con il Sinistra figlio contenente valori inferiori al nodo genitore e al Giusto figlio contenente 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

Introduzione alla ricerca binaria:

• Applicazioni della BST
• Applicazione, vantaggi e svantaggi dell'albero di ricerca binario

Operazioni di base sulla BST:

• Inserimento nell'albero di ricerca binario
• Ricerca nell'albero di ricerca binario
• Cancellazione nell'albero di ricerca binaria
• Attraversamenti dell'albero di ricerca binario (BST): Inorder, Preorder, Post Order
• Converti un BST normale in BST bilanciato

Problemi standard facili su BST:

• Ricerca iterativa nell'albero di ricerca binaria
• Un programma per verificare se un albero binario è BST o meno
• Conversione da albero binario a albero di ricerca binario
• Trova il nodo con il valore minimo in un albero di ricerca binario
• Controlla se un array rappresenta o meno l'ordine dell'albero di ricerca binaria
• Come determinare se un albero binario è bilanciato in altezza?
• Array ordinato su BST bilanciato
• Verifica la presenza di BST identici senza costruire gli alberi
• Converti BST in Heap minimo
• Il secondo elemento più grande della BST
• Aggiungi tutti i valori maggiori a ogni nodo in un dato BST
• Controlla se due BST contengono lo stesso set di elementi
• Somma di k elementi più piccoli in BST

Problemi standard medi su BST:

• Costruisci BST da un dato attraversamento del preordine | Insieme 1
• Elenco collegato ordinato a BST bilanciato
• Trasforma un BST in un albero di somma maggiore
• BST in un albero con la somma di tutte le chiavi più piccole
• Costruisci BST dal suo attraversamento dell'ordine di livello dato
• Controlla se l'array fornito può rappresentare l'attraversamento dell'ordine di livello dell'albero di ricerca binario
• Antenato comune più basso in un albero di ricerca binario
• Trova il k-esimo elemento più piccolo in BST (Statistiche ordine in BST)
• K'th Elemento più grande in BST che utilizza spazio aggiuntivo costante
• Numero più grande in BST che è inferiore o uguale a N
• Trova la distanza tra due nodi di un albero di ricerca binario
• Il BST più grande in un albero binario | Insieme 2
• Rimuovi tutti i nodi foglia dall'albero di ricerca binario
• Successore in ordine nell'albero di ricerca binaria
• Trova una coppia con una determinata somma in BST
• Elemento massimo tra due nodi di BST
• Trova il sottoalbero BST più grande in un dato albero binario
• Trova una coppia con una determinata somma in un BST bilanciato
• Due nodi di un BST vengono scambiati, correggere il BST
• Come gestire i duplicati nell'albero di ricerca binaria?
• Nodi foglia dal preordine di un albero di ricerca binario (utilizzando la ricorsione)

Problemi standard difficili sulla BST:

• Costruisci tutti i possibili BST per le chiavi da 1 a N
• Converti BST sul posto in un Min-Heap
• Controlla che un dato array di dimensione n possa rappresentare BST di n livelli o meno
• Unisci due BST con spazio extra limitato
• K'th Elemento più grande nella BST quando la modifica alla BST non è consentita
• Controlla se esiste una sottosequenza ordinata nell'albero di ricerca binario
• Elemento univoco massimo in ogni sottoarray di dimensione K
• Contare le coppie di due BST la cui somma è uguale a un dato valore x
• Stampa le chiavi BST nell'intervallo specificato | O(1) Spazio
• Predecessore e successore in ordine per una determinata chiave in BST
• Trova se c'è una tripletta in un BST bilanciato che aggiunge a zero
• Sostituisci ogni elemento con l'elemento meno grande alla sua destra
• Contare le inversioni in un array | Set 2 (utilizzando il BST autobilanciante)
• Nodi foglia dal preordine di un albero di ricerca binario
• Valore minimo possibile di |ai + aj – k| per un dato array e k.
• Numeri speciali a due cifre in un albero di ricerca binario
• Unisci due alberi di ricerca binaria bilanciata

Alcuni quiz:

• 'Quiz' sull'albero di ricerca binaria
• “Quiz” sugli alberi di ricerca binari bilanciati

Link veloci :

• Video sull'albero di ricerca binaria

Consigliato:

• Impara la struttura dei dati e gli algoritmi | Tutorial DSA