Esercizio 3.6: Manuale di progettazione dell'algoritmo di Skiena

Le operazioni tipiche su un albero sono l'inserimento, la cancellazione e l'attraversamento - incluso il successore e il predecessore. Quando un albero è bilanciato, ci sarà un'operazione di ribilanciamento interno, quindi la risposta su quali operazioni devono essere modificate dipende dal fatto che si voglia interpretare "operazione" rispetto all'interfaccia esterna o interna.

La risposta, in generale, è affermativa: è necessario mantenere un puntatore al successore (l'elemento successivo maggiore di quello corrente) e il predecessore.

Di quale domanda si tratta davvero, è come mantenere aggiornati questi puntatori appena proposti in relazione a inserimenti, eliminazioni e ribilanciamenti. Puoi ragionare su questo per induzione - dato un albero equilibrato T tale che le condizioni date nella domanda si applicano rispetto a T , come l'inserimento di un nuovo nodo V influirà su tutti altri nodi dell'albero, in particolare quelli per cui V diventerà il nuovo successore e predecessore. Dovrai mostrare che solo i O(log n) nodi saranno interessati, localizzati e modificati, altrimenti non puoi mantenere le operazioni discusse in questo ambito della necessaria complessità.

'void delete( root, val ) 
{
    node = findNode( root, &par );
    nodePred = node->pred;
    nodeSucc = node->succ;
    if ( nodeSucc )
        nodeSucc->pred = nodePred;
    if( nodePred )
        nodePred->succ = nodeSucc;
    // Node delete the node as usual as only parent child relation changes and
    // succ pred relation will still remain intact
}

void insert( root, node ) 
{
    if ( root == NULL ) {
        root = node;
        node->succ = node->pred = NULL;
        return;
    }
    curr = root;
    while ( curr ) {
        par = curr;
        curr = node->val < curr->val ?  curr->left : curr->right;
    }
    if ( node->val < par->val ) {
        par->left = node;
        parPred = par->pred;
        node->succ = par;
        node->pred = parPred;
        par->pred = node;
        if ( oldPred )
            oldPred->succ = node;
    } else {
        par->right = node;
        oldSucc = par->succ;
        node->pred = par;
        node->succ = oldSucc;
        par->succ = node;
        if ( oldSucc )
            oldSucc->pred = node;
    }
}'