Cart is empty Introduzione
Questo articolo presenta un’implementazione di un albero binario di ricerca concorrente in Java, progettata per essere concisa e facile da comprendere. Discuteremo la definizione dell’interfaccia, seguita dall’implementazione delle operazioni concorrenti di ricerca, inserimento, eliminazione e aggiornamento. Infine, forniremo un esempio di esecuzione di queste operazioni in modo concorrente. Gli alberi binari di ricerca (BST) sono una struttura dati ampiamente utilizzata grazie alle loro capacità efficienti di ricerca, inserimento ed eliminazione. Un BST è una struttura dati ad albero in cui ogni nodo ha al massimo due figli e, per tutti i nodi, il figlio sinistro è minore del nodo padre e il figlio destro è maggiore del nodo padre.
La complessità temporale per le operazioni di ricerca, inserimento ed eliminazione è generalmente O(h), dove h è l’altezza dell’albero. In un albero bilanciato, l’altezza è O(log n), dove n è il numero di nodi. Nella programmazione concorrente, più thread vengono eseguiti simultaneamente e l’accesso concorrente a strutture dati condivise, come un albero binario di ricerca, può portare a risultati imprevedibili se non gestito correttamente. Un albero binario di ricerca concorrente garantisce che queste operazioni siano protette dai thread, consentendo a più thread di accedere e modificare l’albero senza causare corruzione dei dati o condizioni di gara.
Definizione dell’interfaccia Java Concurrent Binary Search Tree
Per implementare un albero binario di ricerca concorrente in Java, definiamo prima un’interfaccia ConcurrentBinarySearchTree con un parametro di tipo generico T che estende l’interfaccia Comparable per il tipo T. Questo vincolo garantisce che gli elementi memorizzati nell’albero possano essere confrontati, il che è un requisito fondamentale per le operazioni di un albero binario di ricerca. L’interfaccia espone quattro metodi principali: search, insert, delete e update.
public interface ConcurrentBinarySearchTree<T extends Comparable<T>> {
boolean search(T item);
boolean insert(T item);
boolean delete(T item);
boolean update(T oldItem, T newItem);
}
public class ConcurrentBST<T extends Comparable<T>> implements ConcurrentBinarySearchTree<T> {
private Node<T> root;
private final Object lock = new Object();
// Scroll down for methods implementation
// ...
}
- L’operazione di ricerca verifica se un elemento esiste all’interno dell’albero e restituisce true se trovato, altrimenti false. La complessità temporale dell’operazione di ricerca è O(h), dove h è l’altezza dell’albero.
- L’operazione di inserimento aggiunge un nuovo elemento all’albero mantenendo la proprietà dell’albero binario di ricerca. La complessità temporale dell’operazione di inserimento è O(h), dove h è l’altezza dell’albero.
- L’operazione di eliminazione rimuove un elemento dall’albero e riorganizza l’albero per mantenerne le proprietà. La complessità temporale dell’operazione di eliminazione è O(h), dove h è l’altezza dell’albero.
- L’operazione di aggiornamento aggiorna un elemento esistente nell’albero con un nuovo elemento mantenendo la proprietà dell’albero binario di ricerca.
La complessità temporale dell’operazione di aggiornamento è O(h), dove h è l’altezza dell’albero. Le sezioni successive di questo articolo spiegheranno le implementazioni concorrenti di queste operazioni, garantendo la sicurezza dei thread e un’efficace performance mantenendo le proprietà dell’albero binario di ricerca.
Implementazione dell’operazione di ricerca concorrente nell’albero binario di ricerca
L’operazione di ricerca concorrente consente a più thread di cercare elementi all’interno dell’albero binario di ricerca contemporaneamente senza causare corruzione dei dati. L’operazione di ricerca non modifica la struttura dell’albero, quindi la sicurezza del thread è garantita senza la necessità di blocchi o altri meccanismi di sincronizzazione. Nell’operazione di ricerca, attraversiamo l’albero a partire dal nodo radice, confrontando l’elemento target con il valore di ciascun nodo. Se l’elemento target è minore del valore del nodo corrente, ci spostiamo sul figlio sinistro; altrimenti, ci spostiamo sul figlio destro. Quando raggiungiamo un riferimento nullo, l’elemento non è nell’albero e restituiamo false. Se troviamo un nodo con lo stesso valore dell’elemento target, restituiamo true. La complessità temporale dell’operazione di ricerca è O(h), dove h è l’altezza dell’albero. Nel caso peggiore, dobbiamo attraversare l’intera altezza dell’albero.
public boolean search(T item) {
// Traverses the tree, comparing each node's value with the target item.
// If found, it returns true. Otherwise, it returns false.
Node<T> current = root;
while (current != null) {
int comparison = item.compareTo(current.value);
if (comparison == 0)
return true;
current = comparison < 0 ? current.left : current.right;
}
return false;
}
Implementazione dell’operazione di inserimento concorrente nell’albero binario di ricerca
L’operazione di inserimento concorrente aggiunge un nuovo elemento all’albero mantenendo la proprietà dell’albero binario di ricerca. Per garantire la sicurezza del thread, utilizziamo un blocco sincronizzato durante la modifica della struttura dell’albero. Ciò impedisce a più thread di inserire nodi contemporaneamente, il che potrebbe portare alla corruzione dei dati. Nell’operazione di inserimento, attraversiamo l’albero per trovare la posizione del nuovo elemento. Confrontiamo il nuovo elemento con il valore di ciascun nodo durante l’attraversamento. Se il nuovo elemento è minore del valore del nodo corrente, ci spostiamo sul figlio sinistro; altrimenti, ci spostiamo sul figlio destro. Se troviamo un nodo con lo stesso valore del nuovo elemento, l’inserimento è un duplicato e restituiamo false. Una volta raggiunto un riferimento nullo, abbiamo trovato la posizione del nuovo elemento. Quindi blocchiamo l’albero per impedire ad altri thread di modificarlo mentre inseriamo il nuovo nodo. La complessità temporale dell’operazione di inserimento è O(h), dove h è l’altezza dell’albero.
public boolean insert(T item) {
// Inserts a new node by finding its position in the tree.
// Uses a synchronized block to ensure thread-safety during the process.
Node<T> newNode = new Node<>(item);
Node<T> parent = null;
Node<T> current = root;
while (current != null) {
parent = current;
int comparison = item.compareTo(current.value);
if (comparison == 0)
return false;
current = comparison < 0 ? current.left : current.right;
}
synchronized (lock) {
if (parent == null)
root = newNode;
else if (item.compareTo(parent.value) < 0)
parent.left = newNode;
else
parent.right = newNode;
}
return true;
}
Implementazione dell’operazione di eliminazione concorrente
L’operazione di eliminazione concorrente rimuove un elemento dall’albero e riorganizza l’albero per mantenere la proprietà dell’albero binario di ricerca. Per garantire la sicurezza del thread, utilizziamo un blocco sincronizzato durante la modifica della struttura dell’albero. L’operazione di eliminazione coinvolge tre scenari principali:
- Il nodo da eliminare non ha figli: in questo caso, rimuoviamo semplicemente il nodo dall’albero e aggiorniamo il riferimento del nodo padre.
- Il nodo da eliminare ha un figlio: rimuoviamo il nodo dall’albero e aggiorniamo il riferimento del nodo padre per puntare al singolo figlio del nodo.
- Il nodo da eliminare ha due figli: troviamo il nodo con il valore minimo nel sottoalbero destro (il successore inorder), sostituiamo il nodo da eliminare con il valore del successore inorder e quindi eliminiamo il successore inorder.
private void deleteNode(Node<T> node, Node<T> parent) {
// Deletes a node from the tree and handles three scenarios:
// 1. The node has no children.
// 2. The node has one child.
// 3. The node has two children.
if (node.left == null && node.right == null) {
replaceNodeInParent(parent, node, null);
} else if (node.left != null && node.right != null) {
Node<T> minRight = findMinNode(node.right);
node.value = minRight.value;
deleteNode(minRight, node);
} else {
Node<T> child = node.left != null ? node.left : node.right;
replaceNodeInParent(parent, node, child);
}
}
private void replaceNodeInParent(Node<T> parent, Node<T> node, Node<T> newNode) {
if (parent == null) {
root = newNode;
} else if (parent.left == node) {
parent.left = newNode;
} else {
parent.right = newNode;
}
}
private Node<T> findMinNode(Node<T> node) {
while (node.left != null) {
node = node.left;
}
return node;
}
Implementazione dell’operazione di aggiornamento concorrente
L’operazione di aggiornamento concorrente aggiorna un elemento esistente nell’albero con un nuovo elemento mantenendo la proprietà dell’albero binario di ricerca. Per garantire la sicurezza del thread, utilizziamo un blocco sincronizzato durante la modifica della struttura dell’albero. Nell’operazione di aggiornamento, prima eliminiamo il vecchio elemento dall’albero, poi inseriamo il nuovo elemento. Utilizzando un blocco sincronizzato, ci assicuriamo che nessun altro thread possa modificare l’albero tra le operazioni di eliminazione e inserimento. La complessità temporale dell’operazione di aggiornamento è O(h), dove h è l’altezza dell’albero. Poiché l’operazione di aggiornamento coinvolge un’eliminazione seguita da un inserimento, la complessità rimane la stessa delle operazioni di eliminazione e inserimento individuali.
public boolean update(T oldItem, T newItem) {
// Updates a node by deleting the old item and inserting the new one.
// Uses a synchronized block to ensure thread-safety.
synchronized (lock) {
if (delete(oldItem))
return insert(newItem);
}
return false;
}
Testare l’albero binario di ricerca concorrente
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class Main {
public static void main(String[] args) {
ConcurrentBinarySearchTree<Integer> tree = new ConcurrentBinarySearchTree<>();
int elementCount = 50000;
// Concurrent insertions
ExecutorService executor = Executors.newFixedThreadPool(2);
executor.submit(() -> insertElements(tree, 1, elementCount / 2));
executor.submit(() -> insertElements(tree, elementCount / 2 + 1, elementCount));
// Concurrent deletions
executor.submit(() -> deleteElements(tree, 1, elementCount / 4));
executor.submit(() -> deleteElements(tree, elementCount / 4 + 1, elementCount / 2));
// Concurrent updates
executor.submit(() -> updateElements(tree, 1, elementCount / 4, elementCount));
executor.submit(() -> updateElements(tree, elementCount / 4 + 1, elementCount / 2, elementCount));
executor.shutdown();
System.out.println("Processing completed.");
}
static void insertElements(ConcurrentBinarySearchTree<Integer> tree, int start, int end) {
for (int i = start; i <= end; i++) {
tree.insert(i);
}
}
static void deleteElements(ConcurrentBinarySearchTree<Integer> tree, int start, int end) {
for (int i = start; i <= end; i++) {
tree.delete(i);
}
}
static void updateElements(ConcurrentBinarySearchTree<Integer> tree, int start, int end, int offset) {
for (int i = start; i <= end; i++) {
tree.update(i, i + offset);
}
}
}
Conclusione
In conclusione, questo articolo ha presentato un’implementazione di un albero binario di ricerca concorrente in Java, progettata per essere chiara e facile da comprendere. Abbiamo discusso la definizione dell’interfaccia e fornito un’implementazione protetta dai thread delle operazioni concorrenti di ricerca, inserimento, eliminazione e aggiornamento mantenendo le proprietà dell’albero binario di ricerca. Utilizzando una combinazione di blocchi sincronizzati e una attenta considerazione delle aree che richiedono sincronizzazione, abbiamo ottenuto una manipolazione efficiente e sicura della struttura dati in un ambiente multi-thread. L’albero binario di ricerca concorrente offre complessità temporali di O(h) per ciascuna operazione, dove h è l’altezza dell’albero, rendendolo una struttura dati preziosa per l’uso in scenari di programmazione concorrente.