Albero binario indicizzabile

Mi è stata proposta una sfida di questo tipo. È necessario implementare un contenitore per la memorizzazione dei dati che garantisca la seguente funzionalità:

• inserire un nuovo elemento
• rimuovere un elemento per numero di indice
• ottenere un elemento per numero di indice
• i dati sono memorizzati in ordine

I dati vengono aggiunti e rimossi continuamente, la struttura deve garantire una velocità di funzionamento rapida. Inizialmente ho cercato di realizzare qualcosa del genere utilizzando i contenitori standard di std. Questo approccio non ha avuto successo e ho capito che dovevo implementare qualcosa di personalizzato. L'unica cosa che mi è venuta in mente è stata usare un albero binario di ricerca. Poiché soddisfa il requisito di rapida inserzione, rimozione e memorizzazione dei dati in ordine. Resta solo da trovare un modo per indicizzare tutti gli elementi e aggiornare gli indici quando l'albero cambia.

struct node_s {    
    data_t data;

    uint64_t weight; // peso del nodo

    node_t *left;
    node_t *right;

    node_t *parent;
};

Nell'articolo ci saranno più immagini e teoria che codice. Il codice potrà essere visualizzato tramite il link in fondo.

Peso

Per questo, l'albero ha subito una piccola modifica, è stata aggiunta un'informazione supplementare sul peso nodo. Il peso del nodo è il numero di discendenti di questo nodo + 1 (peso di un singolo elemento).

Funzione per ottenere il peso del nodo:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

Per una foglia, il peso è quindi 0.

Passiamo ora alla rappresentazione visiva di un esempio di tale albero. In nero verrà mostrata la chiave del nodo (il valore non verrà mostrato, poiché non è necessario), in rosso — il peso del nodo, in verde — l'indice del nodo.

Quando l'albero è vuoto, il suo peso è 0. Aggiungiamo l'elemento radice:

Il peso dell'albero diventa 1, il peso dell'elemento radice è 1. Il peso dell'elemento radice è il peso dell'albero.

Aggiungiamo altri elementi:

Ogni volta che viene aggiunto un nuovo elemento, scendiamo attraverso i nodi e aumentiamo il contatore del peso di ciascun nodo attraversato. Quando si crea un nuovo nodo, gli viene assegnato un peso 1. Se un nodo con questa chiave esiste già, sovrascriveremo il valore e torneremo indietro fino alla radice, annullando le modifiche ai pesi di tutti i nodi che abbiamo attraversato.
Se si elimina un nodo, scendiamo e decrementiamo i pesi dei nodi attraversati.

Indici

Passiamo ora a come indicizzare i nodi. I nodi non memorizzano esplicitamente il proprio indice, esso viene calcolato in base al peso dei nodi. Se memorizzassero il proprio indice, ci vorrebbe del tempo per aggiornare gli indici di tutti i nodi dopo ogni modifica dell'albero. O(n) Per passare a una rappresentazione visiva. Il nostro albero è vuoto, aggiungiamo il primo nodo:
Il primo nodo ha indice

, e ora si possono presentare due casi. Nel primo, l'indice dell'elemento radice cambierà, nel secondo non cambierà. 0La radice ha un sottoalbero sinistro con peso 1.

Secondo caso:

L'indice della radice non è cambiato, poiché il peso del suo sottoalbero sinistro è rimasto 0.

Come viene calcolato l'indice di un nodo, è il peso del suo sottoalbero sinistro più il numero passato dal genitore. Cos'è questo numero?, Questo è il contatore degli indici, inizialmente è uguale a

, poiché la radice non ha genitori. Successivamente, tutto dipende da dove scendiamo, a sinistra o a destra. Se a sinistra, non si aggiunge nulla al contatore. Se a destra, si aggiunge l'indice del nodo corrente. 0Ad esempio, come viene calcolato l'indice dell'elemento con chiave 8 (figlio destro della radice). È "Indice della radice" + "peso del sottoalbero sinistro del nodo con chiave 8" + "1" == 3 + 2 + 1 =

Ad esempio, come viene calcolato l'indice dell'elemento con chiave 8 (figlio destro della radice). È "Indice della radice" + "peso del sottoalbero sinistro del nodo con chiave 8" + "1" == 3 + 2 + 1 == 6
L'indice dell'elemento con chiave 6 sarà «Indice della radice» + 1 == 3 + 1 == 4

Di conseguenza, per ottenere, rimuovere un elemento all'indice richiede tempo O(log n), poiché per ottenere l'elemento desiderato dobbiamo prima trovarlo (scendere dalla radice fino a quell'elemento).

Profondità

Sulla base del peso si può anche calcolare la profondità dell'albero. Necessaria per il bilanciamento.
Per fare ciò, il peso dell'attuale nodo deve essere arrotondato al primo numero in potenza di 2 che è maggiore o uguale al peso dato e prendere il logaritmo binario di esso. In questo modo otteniamo la profondità dell'albero, a condizione che sia bilanciato. L'albero si bilancia dopo l'inserimento di un nuovo elemento. Non fornirò la teoria su come bilanciare gli alberi. Nelle codifiche sorgente è presentata la funzione di bilanciamento.

Codice per convertire il peso in profondità.

/*
 * Возвращает первое число в степени 2, которое больше или ровно x
 */
uint64_t bntree::cpl2(uint64_t x) {
    x = x - 1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    x = x | (x >> 32);

    return x + 1;
}

/*
 * Двоичный логарифм от числа
 */
long bntree::ilog2(long d) {
    int result;
    std::frexp(d, &result);
    return result - 1;
}

/*
 * Вес к глубине
 */
uint64_t bntree::weight_to_depth(node_t *p) {
    if (p == NULL) {
        return 0;
    }

    if (p->weight == 1) {
        return 1;
    } else if (p->weight == 2) {
        return 2;
    }

    return this->ilog2(this->cpl2(p->weight));
}

Risultati

• l'inserimento di un nuovo elemento avviene in O(log n)
• la rimozione di un elemento per numero di ordine avviene in O(log n)
• il recupero di un elemento per numero di ordine avviene in O(log n)

Velocità O(log n) paghiamo per il fatto che tutti i dati sono memorizzati in ordine.

Dove possa essere utile una tale struttura, non lo so. È semplicemente un esercizio per comprendere meglio come funzionano gli alberi. Grazie per l'attenzione.

Link

• Codice sorgente dell'albero

Nel progetto sono presenti dati di test per verificare la velocità di esecuzione. L'albero viene popolato 1000000 elementi. E avviene l'eliminazione sequenziale, l'inserimento e l'ottenimento degli elementi 1000000 volte. Cioè 3000000 operazioni. Il risultato si è rivelato piuttosto buono ~ 8 secondi.

Fonte: habr.com