Implementazione di un Albero Binario di Ricerca Concorrente in C#

Introduzione

Questo articolo presenta un’implementazione di un albero binario di ricerca concorrente in C#, progettato per essere conciso e facile da capire. Discuteremo la definizione dell’interfaccia, seguita dall’implementazione delle operazioni concorrenti di ricerca, inserimento, cancellazione 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 e cancellazione. 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 padre, mentre il figlio destro è maggiore del nodo padre.

La complessità temporale per le operazioni di ricerca, inserimento e cancellazione è 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 o condizioni di gara.

Definizione dell’interfaccia dell’albero binario di ricerca concorrente in C#

Per implementare un albero binario di ricerca concorrente in C#, definiamo prima un’interfaccia IConcurrentBinarySearchTree<T> che estende l’interfaccia IComparable per il tipo generico 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 (Ricerca), Insert (Inserimento), Delete (Cancellazione) e Update (Aggiornamento).

public interface IConcurrentBinarySearchTree<T> where T : IComparable<T>
{
    bool Search(T item);
    bool Insert(T item);
    bool Delete(T item);
    bool Update(T oldItem, T newItem);
}

/// <summary>
/// Concurrent Binary Search Tree implementation.
/// </summary>
public class ConcurrentBinarySearchTree<T> : IConcurrentBinarySearchTree<T> where T : IComparable<T>
{
    private Node<T> _root;
    private readonly object _lock = new object();
// Scroll down for methods implementation
// ...
}

L’operazione Search verifica se un elemento è presente nell’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 Insert 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 Delete rimuove un elemento dall’albero e riorganizza l’albero per mantenere le sue proprietà. La complessità temporale dell’operazione di cancellazione è O(h), dove h è l’altezza dell’albero.
L’operazione Update 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’elevata efficienza 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 simultaneamente senza causare corruzione dei dati. L’operazione di ricerca non modifica la struttura dell’albero, quindi la sicurezza del thread viene raggiunta senza la necessità 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.

public bool 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 quando modifichiamo la struttura dell’albero. Ciò impedisce a più thread di inserire nodi simultaneamente, il che potrebbe portare alla corruzione dei dati. Nell’operazione di inserimento, attraversiamo l’albero per trovare la posizione per il 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 evitare che altri thread lo modifichino mentre inseriamo il nuovo nodo. La complessità temporale dell’operazione di inserimento è O(h), dove h è l’altezza dell’albero.

public bool Insert(T item)
    {
        // Inserts a new node by finding its position in the tree.
        // Uses a lock to ensure thread-safety during the process.
        Node<T> newNode = new Node<T>(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;
        }

        lock (_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 cancellazione concorrente

L’operazione di cancellazione 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 quando modifichiamo la struttura dell’albero. L’operazione di cancellazione prevede 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 solo 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 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 cancellazione è O(h), dove h è l’altezza dell’albero.

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 ?? 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 quando modifichiamo la struttura dell’albero. Nell’operazione di aggiornamento, prima eliminiamo il vecchio elemento dall’albero e poi inseriamo il nuovo elemento. Utilizzando un blocco, garantiamo 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 una cancellazione seguita da un inserimento, la complessità rimane la stessa delle singole operazioni di cancellazione e inserimento.

public bool Update(T oldItem, T newItem)
{
    // Updates a node by deleting the old item and inserting the new one.
    // Uses locks to ensure thread-safety.
    lock (_lock)
    {
        if (Delete(oldItem))
            return Insert(newItem);
    }

    return false;
}
}

Testare l’albero binario di ricerca concorrente

using System;
using System.Threading.Tasks;

class Program
{
    static void Main()
    {
        IConcurrentBinarySearchTree<int> tree = new ConcurrentBinarySearchTree<int>();
        int elementCount = 50000;

        // Concurrent insertions
        var insertTask1 = Task.Run(() => InsertElements(tree, 1, elementCount / 2));
        var insertTask2 = Task.Run(() => InsertElements(tree, elementCount / 2 + 1, elementCount));

        Task.WaitAll(insertTask1, insertTask2);

        // Concurrent deletions
        var deleteTask1 = Task.Run(() => DeleteElements(tree, 1, elementCount / 4));
        var deleteTask2 = Task.Run(() => DeleteElements(tree, elementCount / 4 + 1, elementCount / 2));

        Task.WaitAll(deleteTask1, deleteTask2);

        // Concurrent updates
        var updateTask1 = Task.Run(() => UpdateElements(tree, 1, elementCount / 4, elementCount));
        var updateTask2 = Task.Run(() => UpdateElements(tree, elementCount / 4 + 1, elementCount / 2, elementCount));

        Task.WaitAll(updateTask1, updateTask2);

        Console.WriteLine("Processing completed.");
    }

    static void InsertElements(IConcurrentBinarySearchTree<int> tree, int start, int end)
    {
        for (int i = start; i <= end; i++)
        {
            tree.Insert(i);
        }
    }

    static void DeleteElements(IConcurrentBinarySearchTree<int> tree, int start, int end)
    {
        for (int i = start; i <= end; i++)
        {
            tree.Delete(i);
        }
    }

    static void UpdateElements(IConcurrentBinarySearchTree<int> tree, int start, int end, int offset)
    {
        for (int i = start; i <= end; i++)
        {
            tree.Update(i, i + offset);
        }
    }
}

Conclusione

In questo articolo, abbiamo presentato un’implementazione di un albero binario di ricerca concorrente in C#, progettata per essere concisa e facile da capire. Abbiamo discusso la definizione dell’interfaccia e fornito un’implementazione thread-safe delle operazioni concorrenti di ricerca, inserimento, cancellazione e aggiornamento, mantenendo le proprietà dell’albero binario di ricerca. L’albero binario di ricerca concorrente consente una manipolazione efficiente e sicura della struttura dati in un ambiente multithread, con complessità temporali di O(h) per ciascuna operazione, dove h è l’altezza dell’albero.

GMB-API.com