Cart is empty Introduzione
Questo articolo presenta un’implementazione concorrente di un albero binario di ricerca in C++, progettata per essere concisa e facile da capire. 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 simile a un albero in cui ogni nodo ha al massimo due figli e, per tutti i nodi, il figlio sinistro è minore del nodo genitore e il figlio destro è maggiore del nodo genitore.
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 gestiti correttamente. Un albero binario di ricerca concorrente garantisce che queste operazioni siano thread-safe, consentendo a più thread di accedere e modificare l’albero senza causare corruzione dei dati.
Definizione dell’interfaccia di un albero binario di ricerca concorrente in C++
Per implementare un albero binario di ricerca concorrente in C++, definiamo prima una classe template ConcurrentBinarySearchTree con un parametro di tipo T che supporta l’operatore minore di (<). Questo vincolo garantisce che gli elementi memorizzati nell’albero possano essere confrontati, che è un requisito fondamentale per le operazioni di un albero binario di ricerca. La classe espone quattro metodi principali: ricerca, inserimento, eliminazione e aggiornamento.
#include <memory>
#include <mutex>
using std::unique_ptr;
using std::mutex;
template <typename T>
class ConcurrentBinarySearchTree {
public:
bool search(const T& item) const;
bool insert(const T& item);
bool remove(const T& item);
bool update(const T& oldItem, const T& newItem);
private:
struct Node {
T value;
unique_ptr<Node> left;
unique_ptr<Node> right;
};
unique_ptr<Node> root;
mutable mutex mtx;
};
- 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 riassegna l’albero per mantenere le sue 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 sicurezza del thread e prestazioni efficienti pur mantenendo le proprietà dell’albero binario di ricerca.
Implementazione dell’operazione di ricerca concorrente in un albero binario di ricerca
L’operazione di ricerca concorrente consente a più thread di cercare contemporaneamente elementi all’interno dell’albero binario di ricerca senza causare corruzione dei dati. L’operazione di ricerca non modifica la struttura dell’albero, quindi la sicurezza del thread viene raggiunta senza bisogno di blocchi o altri meccanismi di sincronizzazione. Nell’operazione di ricerca, attraversiamo l’albero partendo dal nodo radice, confrontando l’elemento target con il valore di ogni 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.
template <typename T>
bool ConcurrentBinarySearchTree<T>::search(const T& item) const {
// Traverses the tree, comparing each node's value with the target item.
// If found, it returns true. Otherwise, it returns false.
const Node* current = root.get();
while (current != nullptr) {
if (item == current->value) {
return true;
}
current = (item < current->value) ? current->left.get() : current->right.get();
}
return false;
}
Implementazione dell’operazione di inserimento concorrente in un 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 lock_guard per bloccare il mutex 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 ogni 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 per il 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.
template <typename T>
bool ConcurrentBinarySearchTree<T>::insert(const T& item) {
// Inserts a new node by finding its position in the tree.
// Uses a lock_guard to ensure thread-safety during the process.
std::unique_lock<std::mutex> lock(mtx);
Node* parent = nullptr;
Node* current = root.get();
while (current != nullptr) {
parent = current;
if (item == current->value) {
return false;
}
current = (item < current->value) ? current->left.get() : current->right.get();
}
std::unique_ptr<Node> newNode = std::make_unique<Node>();
newNode->value = item;
newNode->left = nullptr;
newNode->right = nullptr;
if (parent == nullptr) {
root = std::move(newNode);
} else if (item < parent->value) {
parent->left = std::move(newNode);
} else {
parent->right = std::move(newNode);
}
return true;
}
Implementazione dell’operazione di eliminazione concorrente
L’operazione di eliminazione concorrente rimuove un elemento dall’albero e riassegna l’albero per mantenere la proprietà dell’albero binario di ricerca. Per garantire la sicurezza del thread, utilizziamo un lock_guard per bloccare il mutex 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 genitore.
- Il nodo da eliminare ha un solo figlio: rimuoviamo il nodo dall’albero e aggiorniamo il riferimento del genitore 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 in ordine), sostituiamo il nodo da eliminare con il valore del successore in ordine e poi eliminiamo il successore in ordine.
- La complessità temporale dell’operazione di eliminazione è O(h), dove h è l’altezza dell’albero.
template <typename T>
bool ConcurrentBinarySearchTree<T>::deleteItem(const T& item) {
// Deletes an item 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.
// Uses a lock_guard to ensure thread-safety during the process.
std::unique_lock<std::mutex> lock(mtx);
Node* parent = nullptr;
Node* current = root.get();
while (current != nullptr && current->value != item) {
parent = current;
current = (item < current->value) ? current->left.get() : current->right.get();
}
if (current == nullptr) {
return false;
}
// Case 1: Node with no children
if (current->left == nullptr && current->right == nullptr) {
deleteNode(parent, current);
}
// Case 2: Node with one child
else if (current->left == nullptr || current->right == nullptr) {
Node* child = (current->left != nullptr) ? current->left.get() : current->right.get();
deleteNode(parent, current, child);
}
// Case 3: Node with two children
else {
Node* inorderSuccessorParent = current;
Node* inorderSuccessor = current->right.get();
while (inorderSuccessor->left != nullptr) {
inorderSuccessorParent = inorderSuccessor;
inorderSuccessor = inorderSuccessor->left.get();
}
current->value = inorderSuccessor->value;
deleteNode(inorderSuccessorParent, inorderSuccessor);
}
return true;
}
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 lock_guard per bloccare il mutex durante la modifica della struttura dell’albero. Nell’operazione di aggiornamento, prima eliminiamo il vecchio elemento dall’albero e poi inseriamo il nuovo elemento. Utilizzando un lock_guard, 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 singole operazioni di eliminazione e inserimento.
template <typename T>
bool ConcurrentBinarySearchTree<T>::update(const T& oldItem, const T& newItem) {
// Updates a node by deleting the old item and inserting the new one.
// Uses a lock_guard to ensure thread-safety.
std::unique_lock<std::mutex> lock(mtx);
if (deleteItem(oldItem)) {
return insert(newItem);
}
return false;
}
Conclusione
In conclusione, questo articolo ha presentato un’implementazione concorrente di un albero binario di ricerca in C++, progettata per essere chiara e facile da capire. Abbiamo discusso la definizione della classe e fornito un’implementazione thread-safe delle operazioni concorrenti di ricerca, inserimento, eliminazione e aggiornamento, mantenendo le proprietà dell’albero binario di ricerca. Utilizzando una combinazione di mutex, lock_guard e un’attenta considerazione delle aree che richiedono sincronizzazione, abbiamo ottenuto una manipolazione efficiente e sicura della struttura dati in un ambiente multithread. 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’utilizzo in scenari di programmazione concorrente.