Qual è il nome dell'algoritmo per bilanciare un grafico aciclico?

2

La classe Algorithms è stata così tanto tempo fa e non ricordo il nome dell'algoritmo per bilanciare un grafico aciclico.

Iniziamo con un grafico simile al seguente:

        1
        |
        2
        |
        3
      /   \
     4     7
    / \    |
   5   6   8

La soluzione per bilanciare questo sarebbe:

        2                             3
       /  \                         / |  \
      1    3                       2  4   7 
          /  \        =>          /  / \  |
        4     7                  1  5   6 8
      /   \   |
     5     6  8

Ruota finché non hai un nodo radice il cui ramo ha la stessa lunghezza e il tuo albero ha un'altezza minima.

Quale algoritmo sto descrivendo?

    
posta Luminous 20.10.2015 - 20:49
fonte

1 risposta

2

Potresti voler fornire ulteriori dettagli nella tua descrizione. Inoltre, l'esempio che fornisci non sembra coerente (ad esempio, il nodo 3 prende improvvisamente tre bambini), mentre tutti gli altri nodi sembrano mantenere al massimo due bambini.

Sulla base dei piccoli dettagli forniti, le operazioni di rotazione sono simili a quanto descritto nelle rotazioni dell'albero AVL. Vedi per es. la pagina wikipedia per ulteriori dettagli.

    
risposta data 22.10.2015 - 22:52
fonte

Leggi altre domande sui tag