binary search tree java implementation code examples
Questo tutorial copre l'albero di ricerca binario in Java. Imparerai a creare un BST, inserire, rimuovere e cercare un elemento, attraversare e implementare un BST in Java:
Un albero di ricerca binario (di seguito denominato BST) è un tipo di albero binario. Può anche essere definito come un albero binario basato su nodi. BST è anche denominato 'albero binario ordinato'. In BST, tutti i nodi nella sottostruttura sinistra hanno valori inferiori al valore del nodo radice.
Allo stesso modo, tutti i nodi del sottoalbero destro del BST hanno valori che sono maggiori del valore del nodo radice. Questo ordine dei nodi deve essere vero anche per i rispettivi sottoalberi.
=> Visita qui per l'esclusiva serie di tutorial di formazione Java.
Cosa imparerai:
- Albero di ricerca binario in Java
- Conclusione
Albero di ricerca binario in Java
Un BST non consente i nodi duplicati.
Il diagramma seguente mostra una rappresentazione BST:
Sopra è mostrato un esempio di BST. Vediamo che 20 è il nodo radice di questo albero. La sottostruttura di sinistra ha tutti i valori dei nodi inferiori a 20. La sottostruttura di destra ha tutti i nodi maggiori di 20. Possiamo dire che l'albero sopra soddisfa le proprietà BST.
La struttura dei dati BST è considerata molto efficiente rispetto agli array e all'elenco collegato quando si tratta di inserimento / cancellazione e ricerca di elementi.
BST impiega O (log n) tempo per cercare un elemento. Man mano che gli elementi vengono ordinati, metà del sottoalbero viene scartato ad ogni passaggio durante la ricerca di un elemento. Ciò diventa possibile perché possiamo facilmente determinare la posizione approssimativa dell'elemento da cercare.
Allo stesso modo, le operazioni di inserimento e cancellazione sono più efficienti in BST. Quando vogliamo inserire un nuovo elemento, sappiamo approssimativamente in quale sottostruttura (sinistra o destra) inseriremo l'elemento.
Creazione di un albero di ricerca binario (BST)
Dato un array di elementi, dobbiamo costruire un BST.
Facciamolo come mostrato di seguito:
Matrice data: 45, 10, 7, 90, 12, 50, 13, 39, 57
Consideriamo prima l'elemento superiore, ovvero 45 come nodo radice. Da qui andremo avanti nella creazione del BST considerando le proprietà già discusse.
Per creare un albero, confronteremo ogni elemento dell'array con la radice. Quindi posizioneremo l'elemento in una posizione appropriata nell'albero.
L'intero processo di creazione per BST è mostrato di seguito.
Operazioni dell'albero di ricerca binaria
BST supporta varie operazioni. La tabella seguente mostra i metodi supportati da BST in Java. Discuteremo ciascuno di questi metodi separatamente.
Metodo / operazione | Descrizione |
---|---|
Inserire | Aggiungere un elemento al BST non violando le proprietà BST. |
Elimina | Rimuovere un dato nodo dal BST. Il nodo può essere il nodo radice, non foglia o foglia. |
Ricerca | Cerca la posizione dell'elemento specificato nella BST. Questa operazione controlla se l'albero contiene la chiave specificata. |
Inserisci un elemento in BST
Un elemento viene sempre inserito come nodo foglia in BST.
Di seguito sono riportati i passaggi per inserire un elemento.
- Inizia dalla radice.
- Confronta l'elemento da inserire con il nodo radice. Se è minore di root, attraversa il sottoalbero sinistro o attraversa il sottoalbero destro.
- Attraversa la sottostruttura fino alla fine della sottostruttura desiderata. Inserire il nodo nella sottostruttura appropriata come nodo foglia.
Vediamo un'illustrazione dell'operazione di inserimento di BST.
Considera il seguente BST e inseriamo l'elemento 2 nell'albero.
L'operazione di inserimento per BST è mostrata sopra. Nella fig (1), mostriamo il percorso che percorriamo per inserire l'elemento 2 nel BST. Abbiamo anche mostrato le condizioni che vengono verificate in ogni nodo. Come risultato del confronto ricorsivo, l'elemento 2 viene inserito come figlio destro di 1 come mostrato in fig (2).
Operazione di ricerca in BST
Per cercare se un elemento è presente nel BST, si ricomincia dalla radice e quindi si attraversa la sottostruttura sinistra o destra a seconda che l'elemento da cercare sia minore o maggiore della radice.
Di seguito sono elencati i passaggi che dobbiamo seguire.
- Confronta l'elemento da cercare con il nodo radice.
- Se la chiave (elemento da cercare) = root, restituisce root node.
- Altrimenti se chiave
- Altrimenti, attraversa la sottostruttura destra.
- Confronta ripetutamente gli elementi della sottostruttura finché non viene trovata la chiave o viene raggiunta la fine dell'albero.
Illustriamo l'operazione di ricerca con un esempio. Considera che dobbiamo cercare la chiave = 12.
Nella figura sottostante, tracceremo il percorso che seguiremo per cercare questo elemento.
Come mostrato nella figura sopra, confrontiamo prima la chiave con la radice. Poiché la chiave è maggiore, attraversiamo la sottostruttura destra. Nella sottostruttura destra, confrontiamo nuovamente la chiave con il primo nodo nella sottostruttura destra.
Troviamo che la chiave è minore di 15. Quindi ci spostiamo alla sottostruttura sinistra del nodo 15. Il nodo sinistro immediato di 15 è 12 che corrisponde alla chiave. A questo punto, interrompiamo la ricerca e restituiamo il risultato.
Rimuovi elemento dal BST
Quando cancelliamo un nodo dal BST, ci sono tre possibilità come discusso di seguito:
Il nodo è un nodo foglia
Se un nodo da eliminare è un nodo foglia, possiamo eliminare direttamente questo nodo poiché non ha nodi figlio. Questo è mostrato nell'immagine sottostante.
Come mostrato sopra, il nodo 12 è un nodo foglia e può essere eliminato immediatamente.
Il nodo ha un solo figlio
Quando dobbiamo eliminare il nodo che ha un figlio, copiamo il valore del figlio nel nodo e quindi eliminiamo il figlio.
Nel diagramma sopra, vogliamo eliminare il nodo 90 che ha un figlio 50. Quindi scambiamo il valore 50 con 90 e quindi eliminiamo il nodo 90 che ora è un nodo figlio.
Il nodo ha due figli
Quando un nodo da eliminare ha due figli, sostituiamo il nodo con il successore inordine (sinistra-radice-destra) del nodo o semplicemente diciamo il nodo minimo nel sottoalbero destro se il sottoalbero destro del nodo non è vuoto. Sostituiamo il nodo con questo nodo minimo ed eliminiamo il nodo.
Nel diagramma sopra, vogliamo eliminare il nodo 45 che è il nodo radice di BST. Troviamo che la sottostruttura destra di questo nodo non è vuota. Quindi attraversiamo la sottostruttura destra e troviamo che il nodo 50 è il nodo minimo qui. Quindi sostituiamo questo valore al posto di 45 e quindi eliminiamo 45.
Se controlliamo l'albero, vediamo che soddisfa le proprietà di un BST. Quindi la sostituzione del nodo era corretta.
Implementazione BST (Binary Search Tree) in Java
Il seguente programma in Java fornisce una dimostrazione di tutte le operazioni BST di cui sopra utilizzando lo stesso albero utilizzato nell'illustrazione come esempio.
software di backup gratuito per Windows 8.1
class BST_class { //node class that defines BST node class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } // BST root node Node root; // Constructor for BST =>initial empty tree BST_class(){ root = null; } //delete a node from BST void deleteKey(int key) { root = delete_Recursive(root, key); } //recursive delete function Node delete_Recursive(Node root, int key) { //tree is empty if (root == null) return root; //traverse the tree if (key root.key) //traverse right subtree root.right = delete_Recursive(root.right, key); else { // node contains only one child if (root.left == null) return root.right; else if (root.right == null) return root.left; // node has two children; //get inorder successor (min value in the right subtree) root.key = minValue(root.right); // Delete the inorder successor root.right = delete_Recursive(root.right, root.key); } return root; } int minValue(Node root) { //initially minval = root int minval = root.key; //find minval while (root.left != null) { minval = root.left.key; root = root.left; } return minval; } // insert a node in BST void insert(int key) { root = insert_Recursive(root, key); } //recursive insert function Node insert_Recursive(Node root, int key) { //tree is empty if (root == null) { root = new Node(key); return root; } //traverse the tree if (key root.key) //insert in the right subtree root.right = insert_Recursive(root.right, key); // return pointer return root; } // method for inorder traversal of BST void inorder() { inorder_Recursive(root); } // recursively traverse the BST void inorder_Recursive(Node root) { if (root != null) { inorder_Recursive(root.left); System.out.print(root.key + ' '); inorder_Recursive(root.right); } } boolean search(int key) { root = search_Recursive(root, key); if (root!= null) return true; else return false; } //recursive insert function Node search_Recursive(Node root, int key) // Base Cases: root is null or key is present at root if (root==null } class Main{ public static void main(String[] args) { //create a BST object BST_class bst = new BST_class(); /* BST tree example 45 / 10 90 / / 7 12 50 */ //insert data into BST bst.insert(45); bst.insert(10); bst.insert(7); bst.insert(12); bst.insert(90); bst.insert(50); //print the BST System.out.println('The BST Created with input data(Left-root-right):'); bst.inorder(); //delete leaf node System.out.println('
The BST after Delete 12(leaf node):'); bst.deleteKey(12); bst.inorder(); //delete the node with one child System.out.println('
The BST after Delete 90 (node with 1 child):'); bst.deleteKey(90); bst.inorder(); //delete node with two children System.out.println('
The BST after Delete 45 (Node with two children):'); bst.deleteKey(45); bst.inorder(); //search a key in the BST boolean ret_val = bst.search (50); System.out.println('
Key 50 found in BST:' + ret_val ); ret_val = bst.search (12); System.out.println('
Key 12 found in BST:' + ret_val ); } }
Produzione:
Attraversamento dell'albero di ricerca binario (BST) in Java
Un albero è una struttura gerarchica, quindi non possiamo attraversarlo linearmente come altre strutture di dati come gli array. Qualsiasi tipo di albero deve essere attraversato in modo speciale in modo che tutti i suoi sottoalberi e nodi vengano visitati almeno una volta.
A seconda dell'ordine in cui il nodo radice, il sottoalbero sinistro e il sottoalbero destro vengono attraversati in un albero, ci sono alcuni attraversamenti come mostrato di seguito:
- Attraversamento in ordine
- Preordina Traversal
- PostOrder Traversal
Tutti gli attraversamenti di cui sopra utilizzano la tecnica della profondità prima, ovvero l'albero viene attraversato in profondità.
Gli alberi usano anche la tecnica dell'ampiezza per l'attraversamento. Viene chiamato l'approccio che utilizza questa tecnica 'Ordine di livello' attraversamento.
In questa sezione, dimostreremo ciascuna delle traversate utilizzando il seguente BST come esempio.
Con il BST come mostrato nel diagramma sopra, l'attraversamento dell'ordine dei livelli per l'albero sopra è:
Attraversamento ordine di livello: 10 6 12 4 8
Attraversamento in ordine
L'approccio di attraversamento in ordine ha attraversato la BST nell'ordine, Sottostruttura sinistra => RootNode => Sottostruttura destra . L'attraversamento in ordine fornisce una sequenza decrescente di nodi di un BST.
Di seguito viene fornito l'algoritmo InOrder (bstTree) per InOrder Traversal.
- Attraversa la sottostruttura sinistra usando InOrder (left_subtree)
- Visita il nodo radice.
- Attraversa la sottostruttura destra usando InOrder (right_subtree)
L'attraversamento in ordine dell'albero sopra è:
4 6 8 10 12
Come visto, la sequenza dei nodi come risultato dell'attraversamento in ordine è in ordine decrescente.
Preordina Traversal
Nell'attraversamento del preordine, la radice viene visitata per prima, seguita dalla sottostruttura sinistra e dalla sottostruttura destra. L'attraversamento del preordine crea una copia dell'albero. Può anche essere utilizzato negli alberi delle espressioni per ottenere l'espressione del prefisso.
L'algoritmo per l'attraversamento PreOrder (bst_tree) è fornito di seguito:
- Visita il nodo radice
- Attraversa la sottostruttura sinistra con PreOrder (left_subtree).
- Attraversa la sottostruttura destra con PreOrder (right_subtree).
L'attraversamento del preordine per la BST sopra indicato è:
10 6 4 8 12
PostOrder Traversal
L'attraversamento postOrder attraversa il BST nell'ordine: Sottostruttura sinistra-> Sottostruttura destra-> Nodo radice . PostOrder traversal viene utilizzato per eliminare l'albero o ottenere l'espressione postfissa in caso di alberi delle espressioni.
L'algoritmo per l'attraversamento postOrder (bst_tree) è il seguente:
- Attraversa la sottostruttura sinistra con postOrder (left_subtree).
- Attraversa la sottostruttura destra con postOrder (right_subtree).
- Visita il nodo radice
L'attraversamento postOrder per l'esempio precedente BST è:
4 8 6 12 10
Successivamente, implementeremo questi attraversamenti utilizzando la tecnica di approfondimento in un'implementazione Java.
//define node of the BST class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } //BST class class BST_class { // BST root node Node root; BST_class(){ root = null; } //PostOrder Traversal - Left:Right:rootNode (LRn) void postOrder(Node node) { if (node == null) return; // first traverse left subtree recursively postOrder(node.left); // then traverse right subtree recursively postOrder(node.right); // now process root node System.out.print(node.key + ' '); } // InOrder Traversal - Left:rootNode:Right (LnR) void inOrder(Node node) { if (node == null) return; //first traverse left subtree recursively inOrder(node.left); //then go for root node System.out.print(node.key + ' '); //next traverse right subtree recursively inOrder(node.right); } //PreOrder Traversal - rootNode:Left:Right (nLR) void preOrder(Node node) { if (node == null) return; //first print root node first System.out.print(node.key + ' '); // then traverse left subtree recursively preOrder(node.left); // next traverse right subtree recursively preOrder(node.right); } // Wrappers for recursive functions void postOrder_traversal() { postOrder(root); } void inOrder_traversal() { inOrder(root); } void preOrder_traversal() { preOrder(root); } } class Main{ public static void main(String[] args) { //construct a BST BST_class tree = new BST_class(); /* 45 // \ 10 90 // \ 7 12 */ tree.root = new Node(45); tree.root.left = new Node(10); tree.root.right = new Node(90); tree.root.left.left = new Node(7); tree.root.left.right = new Node(12); //PreOrder Traversal System.out.println('BST => PreOrder Traversal:'); tree.preOrder_traversal(); //InOrder Traversal System.out.println('
BST => InOrder Traversal:'); tree.inOrder_traversal(); //PostOrder Traversal System.out.println('
BST => PostOrder Traversal:'); tree.postOrder_traversal(); } }
Produzione:
Domande frequenti
D # 1) Perché abbiamo bisogno di un albero di ricerca binario?
Risposta : Il modo in cui cerchiamo elementi nella struttura dati lineare come array utilizzando la tecnica di ricerca binaria, essendo l'albero una struttura gerarchica, abbiamo bisogno di una struttura che possa essere utilizzata per individuare gli elementi in un albero.
È qui che arriva l'albero di ricerca binario che ci aiuta nella ricerca efficiente degli elementi nell'immagine.
D # 2) Quali sono le proprietà di un albero di ricerca binario?
Risposta : Un albero di ricerca binario che appartiene alla categoria albero binario ha le seguenti proprietà:
- I dati memorizzati in un albero di ricerca binario sono unici. Non consente valori duplicati.
- I nodi della sottostruttura sinistra sono inferiori al nodo radice.
- I nodi della sottostruttura destra sono maggiori del nodo radice.
D # 3) Quali sono le applicazioni di un albero di ricerca binario?
Risposta : Possiamo usare gli alberi di ricerca binari per risolvere alcune funzioni continue in matematica. La ricerca dei dati in strutture gerarchiche diventa più efficiente con gli alberi di ricerca binari. Ad ogni passaggio, riduciamo la ricerca di metà sottostruttura.
D # 4) Qual è la differenza tra un albero binario e un albero di ricerca binario?
Risposta: Un albero binario è una struttura ad albero gerarchica in cui ogni nodo noto come genitore può avere al massimo due figli. Un albero di ricerca binario soddisfa tutte le proprietà dell'albero binario e ha anche le sue proprietà uniche.
In un albero di ricerca binario, le sottostrutture di sinistra contengono nodi minori o uguali al nodo radice e la sottostruttura di destra ha nodi maggiori del nodo radice.
D # 5) L'albero di ricerca binario è unico?
Risposta : Un albero di ricerca binario appartiene a una categoria di albero binario. È unico nel senso che non consente valori duplicati e anche tutti i suoi elementi sono ordinati secondo un ordine specifico.
Conclusione
Gli alberi di ricerca binari fanno parte della categoria degli alberi binari e vengono utilizzati principalmente per la ricerca di dati gerarchici. Viene anche utilizzato per risolvere alcuni problemi matematici.
In questo tutorial, abbiamo visto l'implementazione di un albero di ricerca binario. Abbiamo anche visto varie operazioni eseguite su BST con la loro illustrazione e abbiamo anche esplorato le traversate per BST.
=> Guarda qui la serie di formazione su Java semplice.
Lettura consigliata
- Albero di ricerca binario C ++: implementazione BST e operazioni con esempi
- Algoritmo di ricerca binaria in Java - implementazione ed esempi
- Struttura dei dati dell'albero binario in C ++
- Alberi in C ++: terminologia di base, tecniche di attraversamento e tipi di alberi C ++
- TreeMap in Java - Tutorial con esempi di Java TreeMap
- TreeSet in Java: tutorial con esempi di programmazione
- Tutorial JAVA per principianti: oltre 100 tutorial video Java pratici
- Elenco collegato in Java - Implementazione di elenchi collegati ed esempi Java