Implementazione di un Albero Binario di Ricerca Concorrente in Python

Introduzione

Questo articolo presenta un’implementazione concorrente di un albero binario di ricerca in Python, progettata per essere concisa e facile da capire. Discuteremo la definizione della classe, 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 efficienti capacità di ricerca, inserimento ed eliminazione. Un BST è una struttura dati simile ad un 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.

Implementazione di un Albero Binario di Ricerca Concorrente in Python

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 sicure per i thread, consentendo a più thread di accedere e modificare l’albero senza causare corruzione dei dati.

Definizione della classe Concurrent Binary Search Tree in Python

Per implementare un albero binario di ricerca concorrente in Python, definiamo prima una classe ConcurrentBinarySearchTree con un parametro di tipo generico T. Questa classe richiede che gli elementi memorizzati nell’albero siano confrontabili, il che è un requisito fondamentale per le operazioni di un albero binario di ricerca. La classe espone quattro metodi principali: ricerca, inserimento, eliminazione e aggiornamento.

L’operazione di ricerca 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 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 riallinea 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 la sicurezza dei thread e prestazioni efficienti mantenendo le proprietà dell’albero binario di ricerca.

from threading import Lock

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class ConcurrentBinarySearchTree:
    def __init__(self):
        self.root = None
        self.lock = Lock()
        # Scroll down for methods implementation
        # ...

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 è garantita 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 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.

def search(self, item):
    # Traverses the tree, comparing each node's value with the target item.
    # If found, it returns True. Otherwise, it returns False.
    current = self.root

    while current is not None:
        comparison = self._compare(item, current.value)

        if comparison == 0:
            return True
        current = current.left if comparison < 0 else 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 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 per il nuovo elemento. Quindi, blocciamo 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.

def insert(self, item):
    # Inserts a new node by finding its position in the tree.
    # Uses a lock to ensure thread-safety during the process.
    new_node = Node(item)
    parent = None
    current = self.root

    while current is not None:
        parent = current
        comparison = self._compare(item, current.value)

        if comparison == 0:
            return False
        current = current.left if comparison < 0 else current.right

    with self.lock:
        if parent is None:
            self.root = new_node
        elif self._compare(item, parent.value) < 0:
            parent.left = new_node
        else:
            parent.right = new_node

    return True

Implementazione dell’operazione di eliminazione concorrente nell’albero binario di ricerca

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

def delete(self, item):
    # Deletes a node with the given item from the tree.
    # Uses a lock to ensure thread-safety during the process.
    parent, node = self._find_node_and_parent(item)
    if node is None:
        return False

    with self.lock:
        self._delete_node(node, parent)

    return True

def _delete_node(self, node, parent):
    if node.left is None and node.right is None:
        self._replace_node_in_parent(parent, node, None)
    elif node.left is not None and node.right is not None:
min_right = self._find_min_node(node.right)
node.value = min_right.value
self._delete_node(min_right, node)
else:
child = node.left if node.left is not None else node.right
self._replace_node_in_parent(parent, node, child)

def _replace_node_in_parent(self, parent, node, new_node):
if parent is None:
self.root = new_node
elif parent.left == node:
parent.left = new_node
else:
parent.right = new_node

def _find_min_node(self, node):
while node.left is not None:
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, 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.

def update(self, old_item, new_item):
    # Updates a node by deleting the old item and inserting the new one.
    # Uses a lock to ensure thread-safety.
    with self.lock:
        if self.delete(old_item):
            return self.insert(new_item)

    return False

Testing the Concurrent Binary Search Tree

import threading

def main():
    tree = ConcurrentBST()
    element_count = 50000

    # Concurrent insertions
    t1 = threading.Thread(target=insert_elements, args=(tree, 1, element_count // 2))
    t2 = threading.Thread(target=insert_elements, args=(tree, element_count // 2 + 1, element_count))

    # Concurrent deletions
    t3 = threading.Thread(target=delete_elements, args=(tree, 1, element_count // 4))
    t4 = threading.Thread(target=delete_elements, args=(tree, element_count // 4 + 1, element_count // 2))

    # Concurrent updates
    t5 = threading.Thread(target=update_elements, args=(tree, 1, element_count // 4, element_count))
    t6 = threading.Thread(target=update_elements, args=(tree, element_count // 4 + 1, element_count // 2, element_count))

    t1.start()
    t2.start()
    t3.start()
    t4.start()
    t5.start()
    t6.start()

    t1.join()
    t2.join()
    t3.join()
    t4.join()
    t5.join()
    t6.join()

    print("Processing completed.")

def insert_elements(tree, start, end):
    for i in range(start, end + 1):
        tree.insert(i)

def delete_elements(tree, start, end):
    for i in range(start, end + 1):
        tree.delete(i)

def update_elements(tree, start, end, offset):
    for i in range(start, end + 1):
        tree.update(i, i + offset)

if __name__ == "__main__":
    main()

Conclusione

Questo articolo ha presentato un’implementazione concorrente di un albero binario di ricerca in Python, progettata per essere chiara e facile da capire. Abbiamo discusso la definizione della classe e fornito un’implementazione sicura per i thread delle operazioni concorrenti di ricerca, inserimento, eliminazione e aggiornamento mantenendo le proprietà dell’albero binario di ricerca. Utilizzando una combinazione di blocchi 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’uso in scenari di programmazione concorrente. Con l’implementazione fornita, gli sviluppatori possono sfruttare il potere della concorrenza per ottimizzare le prestazioni delle loro applicazioni, soprattutto quando si lavora con grandi set di dati e più thread che accedono alla stessa struttura dati. L’albero binario di ricerca concorrente è un’ottima scelta per gli scenari in cui i dati devono essere acceduti, modificati o eliminati da più thread senza causare corruzione dei dati.

GMB-API.com