Please enable JavaScript.

Coggle requires JavaScript to display documents.

B - Alberi e varianti - Coggle Diagram

- - - - k1<...<k_c(v)
      - t-1<=c(v)<= 2t-1
    - - h<= log_t (N+1)/2
    - - n chiavi B albero altezza h:
        2t^h -1 <= N <= (2t)^(h+1) -1
      - il fattore di caricamento di un B albero vale mediamente alpha =0.7
        
        fattore di caricamento:
        rapporto n° chiavi presenti e n° chiavi che potrebbero essere allocate
  - - - T(N,M,B) = O(log_B N)
      - W(N,M,B)= O(log_2 N)
      - al generico passo, trovandosi nel nodo v,
        verifichiamo se la chiave k si trovi nel nodo v
        
        se k=k_i si restituisce elem_i
        e la ricerca termina con sucesso
        
        Se non la si trova e v è una foglia,
        allora la ricerca termina senza successo
        
        Altrimenti si cerca la più piccola chiave k_j di v maggiore di k: se non esiste si prosegue la ricerca nel sottoalbero p_c(v), se no si prosegue la ricerca sul sottoalbero indicato da p_j-1
    - - ricerca senza successo fino a determinare foglia f in cui
        viene inserito nuovo elemento di chiave k
        
        Se la foglia non è piena, si inserisce la chiave k ordinatamente con le chiavi presenti
        
        O(log_t N) I/O
        O(t log_t N) operazioni elementari
        
        Se la foglia è piena si esegue uno Split
        
        si fa salire la t-esima chiave k' al livello superiore.
        si inserisce nel padre della foglia f con i due puntatori a sinistra e destra che puntano ai due nuovi nodi creati dallo split
        
        caso pessimo: si aggiunge una nuova radice contenente una sola chiave e incrementando di uno l'altezza dell'albero
        
        I/O O(1)
        op. elementari O(t)
    - - Se la foglia F ha almeno t chiavi si cancella l'elemento
      - Se F è quasi vuota esaminiamo fratello sinistro e destro
        
        se almeno dei due fratelli ha almeno t chiavi, ridistribuzione elementi tra i due fratelli (modificando chiave separatrice contenuta nel padre)
        
        se entrambi i fratelli sono quasi vuoti operazione fuse:
        aggiungiamo ai due fratelli sia le chiavi di F sia la chiave separatrice. Eliminiamo poi F
        
        in questo modo il numero delle chiavi ed il numero dei figli diminuisce di 1.
        caso pessimo: le operazioni si ripeteranno fino alla radice e l'altezza dell'albero diminuisce di 1
      - Fuse: O(1) I/O
        O(t) op elementari
        Delete: O(log_t N) I/O
        O(t log_t N) op. elementari
- - - - w1 contiene record con chiave < k1
      - sottoalbero con radice wi contiene record con chiave nell'intervallo [k_i-1, k_i)
      - sottoalbero con radice w_delta+1 contiene record con chiave >= k_delta
    - - B+ albero con t grado minimo nodi interni e b capienza minima foglie contenente N record ha n° livelli Theta(1+log_t (N/b))
  - - - attraverso albero seguendo per ogni nodo il sottoalbero wi t.c. k_i-1 <= k <= k_i (i=0,...,delta+1)
        
        arrivati a una foglia u, si cerca k tra i suoi record
        
        se k viene trovata, si restituisce il record associato, altresì la ricerca termina senza sucesso
      - T(N,t,b): Tehta(1+log_t (N/b) )
        W(N,t,b): O(log_2 (N/b) +log_2 b)
    - - ricerca senza successo fino ala foglia u
        
        u ha meno di 2b record: inserisco r ordinatamente
        
        altrimenti: bisogna dividere la foglia
        
        u1: r1,..., rb
        u2: r_b+1, ...,r_2b+1
        
        chiave k_b+1 del record r_b+1 viene inserita nel nodo padre di u con i due puntatori a u1 e u2
        
        se il nodo u era radice, viene creato un nuovo nodo radice contenente k_b+1 e i due puntatori a u1 e u2
      - T(N,t,b): theta(1+log_t(N/b))
        W(N,t,b): O(b+t*log_t(N/b))
    - - cercare foglia u in cui si trova r e cancellare r da u
        
        u radice oppure in u rimangono + di b record: la cancellazione termina
        
        altrimenti:
        
        se fratello u' a destra ha esattamente b record
        
        porto tutti i record di u' in u ed elimino la chiave k_hat, separatrice di u ed u', dal nodo padre
        
        se nel nodo padre rimangono almeno t-1 chiavi o è la radice
        
        Stop
        (altrimenti la procedura si ripete)
        
        se fratello u' a destra ha + di b record:
        
        redistribuisco i record tra u e u' e cambio la chiave separatrice nel padre
      - T(N,t,b) : Theta(1+log_t (N/b))
        W(N,t,b) : O(b+ t log_t (N/b))
    - - ricerca tutti i record compresi tra k1 e k2
        
        cerco k1, scorro le foglie fino a k2
      - T(N,t,b) : Theta(1+ log_t (N/b) + R/b )
        W(N,t,b) : O(log(N/b) +log b + R)
    - - ricerca record chiave successiva a k
        
        se record r con chiave k è l'ultimo elemento della foglia, r' sarà il primo record del suo fratello destro
        
        altrimenti è il record successivo ad r nello stesso modo
      - Se conosciamo la foglia e la posizione di r
        O(1) I/O
        O(1) operazioni elementari
        
        se conosciamo solo la foglia:
        O(1) I/O
        O(log_2 b) operazioni elementari
- - - - non piena:
        rotazione chiavi
        spostando elementi di v in u
        
        anche k0 chiave che separa u e v dal nodo padre deve ruotare
        
        si possono memorizzare link
        alla pagina sinsitra e destra
        
        semplifica rotazione
        semplifica scansione sequenziale (B+ alberi)
      - se è piena controllo la pagina destra