Quando aggiungi 7, 3 e 1 in un albero rosso-nero, devo eseguire una rotazione corretta?

Naviga le tue risposte
1

Se aggiungo quanto segue in quest'ordine in un albero rosso-nero: 

tree.Put(7)
tree.Put(3)
tree.Put(1)

         7                  3
        /   rotate(3)      / \
       3    ----->        1   7
      /
     1

dovrei eseguire una rotazione a destra dopo l'inserimento di 1 ?

Sto leggendo la Bibbia degli algoritmi ma lo pseudocodice non indica cosa fare.

    
posta Jacques René Mesrine 02.05.2014 - 04:41
fonte

1 risposta

1

Alla radice, 7 è nero. Dopo aver inserito il 3, è rosso (perché tutti i nodi inseriti sono rossi).

Quando inserisci 1, è anche rosso, quindi hai violato una proprietà (il figlio di un nodo rosso deve essere nero). Poiché devi anche mantenere il fatto che tutti i percorsi hanno lo stesso numero di nodi neri, non puoi semplicemente colorare il 3 in nero.

Quindi è necessario eseguire una rotazione.

Dopo aver controllato il libro : credo che questo sia il caso 3: colora il nonno rosso & eseguire la rotazione a destra.

    
risposta data 02.05.2014 - 15:37
fonte

Leggi altre domande sui tag

Progettare il ponte tra il livello REST e il livello di servizio Come dovrei connettermi al mio framework php per usare metodi scritti nel framework, in un ambiente agnostico framework?