In questo tutorial, discuteremo la Struttura Dati dell’Albero di Ricerca Binaria. Implementeremo le funzioni per cercare, inserire e rimuovere valori da un Albero di Ricerca Binaria. Implementeremo queste operazioni sia ricorsivamente che iterativamente.
Albero di Ricerca Binaria
A Binary Search tree has the following property:
- Tutti i nodi devono essere tali che il figlio sinistro sia sempre minore del nodo genitore.
- Il figlio destro è sempre maggiore del nodo genitore.
Nelle sezioni seguenti, vedremo come cercare, inserire ed eliminare in modo ricorsivo e iterativo in un BST. Creiamo prima la nostra Struttura Dati Albero Binario:
public class BinaryTree {
public TreeNode root;
public static class TreeNode {
public TreeNode left;
public TreeNode right;
public Object data;
public TreeNode(Object data) {
this.data = data;
left = right = null;
}
}
}
Nota che l’implementazione sopra non è un albero di ricerca binario perché non c’è alcuna restrizione nell’inserimento degli elementi nell’albero.
Ricerca BST Ricorsiva
Il seguente programma Java contiene la funzione per cercare un valore in un BST in modo ricorsivo.
public class SearchInsertRemoveFromTree {
public static void main(String[] args) {
/**
* Our Example Binary Search Tree
* 10
* 5 20
* 4 8 15 25
*/
BinaryTree tree = new BinaryTree();
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(5);
tree.root.right = new TreeNode(20);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(8);
tree.root.right.left = new TreeNode(15);
tree.root.right.right = new TreeNode(25);
System.out.println("Search Value 2 is in tree? " + searchRecursively(tree.root, 2));
System.out.println("Search Value 10 in tree? " + searchRecursively(tree.root, 10));
}
public static boolean searchRecursively(TreeNode root, int value) {
if (root == null)
return false;
if ((int) root.data == value)
return true;
if (value < (int) root.data)
return searchRecursively(root.left, value);
else if (value > (int) root.data)
return searchRecursively(root.right, value);
return false;
}
}
L’output è: 
Ricerca BST in modo iterativo
Per cercare in modo iterativo, utilizza il seguente metodo al posto di:
public static boolean searchIteratively(TreeNode root, int value) {
while (root != null) {
if ((int) root.data == value)
return true;
if (value < (int) root.data)
root = root.left;
else
root = root.right;
}
return false;
}
Scopriamo come inserire un nuovo nodo in un Albero di Ricerca Binaria.
Inserimento BST in modo ricorsivo
public static TreeNode insertionRecursive(TreeNode root, int value) {
if (root == null)
return new TreeNode(value);
if (value < (int) root.data) {
root.left = insertionRecursive(root.left, value);
} else if (value > (int) root.data) {
root.right = insertionRecursive(root.right, value);
}
return root;
}
public static void printInorderTraversal(TreeNode root) {
if (root != null) {
printInorderTraversal(root.left);
System.out.print(root.data + " ");
printInorderTraversal(root.right);
}
}
Chiama il metodo sopra nel metodo principale:
tree.root = insertionRecursive(tree.root, 24);
tree.root = insertionRecursive(tree.root, 2);
printInorderTraversal(tree.root);
L’albero viene stampato nel formato di attraversamento in ordine. 
Inserimento BST in modo iterativo
Per inserire un nodo in modo iterativo in un albero BST, dovremo attraversare l’albero utilizzando due puntatori.
public static TreeNode insertionIterative(TreeNode root, int value) {
TreeNode current, parent;
TreeNode tempNode = new TreeNode(value);
if (root == null) {
root = tempNode;
return root;
} else {
current = root;
}
while (true) {
parent = current;
if (value < (int) current.data) {
current = current.left;
if (current == null) {
parent.left = tempNode;
return root;
}
} else if (value > (int) current.data) {
current = current.right;
if (current == null) {
parent.right = tempNode;
return root;
}
}
}
}
Rimozione elemento BST in modo ricorsivo
Rimuovere un elemento da un BST è un po’ più complesso rispetto alla ricerca e all’inserimento, poiché dobbiamo assicurarci che la proprietà del BST sia conservata. Per eliminare un nodo, è necessario cercarlo prima. Successivamente, dobbiamo determinare se quel nodo ha figli o meno.
- Se non ha figli – Elimina semplicemente.
- Se ha un singolo figlio – Copia quel figlio nel nodo.
- Se ha due figli – Determina il prossimo elemento più alto (successore in ordine) nel sottoalbero destro. Sostituisci il nodo da rimuovere con il successore in ordine. Elimina il duplicato del successore in ordine.
Il successore in ordine può essere ottenuto trovando il valore minimo nel figlio destro del nodo.
Il seguente programma Java rimuove elementi da un BST:
public static TreeNode deleteRecursively(TreeNode root, int value) {
if (root == null)
return root;
if (value < (int) root.data) {
root.left = deleteRecursively(root.left, value);
} else if (value > (int) root.data) {
root.right = deleteRecursively(root.right, value);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null)
return root.left;
root.data = inOrderSuccessor(root.right);
root.right = deleteRecursively(root.right, (int) root.data);
}
return root;
}
public static int inOrderSuccessor(TreeNode root) {
int minimum = (int) root.data;
while (root.left != null) {
minimum = (int) root.left.data;
root = root.left;
}
return minimum;
}
Chiama il metodo di eliminazione sopra nel metodo main:
tree.root = deleteRecursively(tree.root, 4);
tree.root = deleteRecursively(tree.root, 20);
printInorderTraversal(tree.root);
L’output è: 2 5 8 10 15 24 25 Eseguiamo la stessa operazione in modo iterativo.
Rimozione Elemento BST in modo Iterativo
public static TreeNode deleteNodeIteratively(TreeNode root, int value) {
TreeNode parent = null, current = root;
boolean hasLeft = false;
if (root == null)
return root;
while (current != null) {
if ((int) current.data == value) {
break;
}
parent = current;
if (value < (int) current.data) {
hasLeft = true;
current = current.left;
} else {
hasLeft = false;
current = current.right;
}
}
if (parent == null) {
return deleteNodeIteratively(current);
}
if (hasLeft) {
parent.left = deleteNodeIteratively(current);
} else {
parent.right = deleteNodeIteratively(current);
}
return root;
}
private static TreeNode deleteNodeIteratively(TreeNode node) {
if (node != null) {
if (node.left == null && node.right == null) {
return null;
}
if (node.left != null && node.right != null) {
TreeNode inOrderSuccessor = deleteInOrderSuccessorDuplicate(node);
node.data = inOrderSuccessor.data;
} else if (node.left != null) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
private static TreeNode deleteInOrderSuccessorDuplicate(TreeNode node) {
TreeNode parent = node;
node = node.right;
boolean rightChild = node.left == null;
while (node.left != null) {
parent = node;
node = node.left;
}
if (rightChild) {
parent.right = node.right;
} else {
parent.left = node.right;
}
node.right = null;
return node;
}
La complessità temporale delle operazioni BST è O(h). h è l’altezza dell’albero.
Questo conclude il tutorial.
Puoi consultare il codice completo e altri esempi di strutture dati e algoritmi dal nostro Repository GitHub.
Source:
https://www.digitalocean.com/community/tutorials/binary-search-tree-bst-search-insert-remove