Questo pseudocodice di inserimento albero rosso-nero da Introduzione agli algoritmi (CLRS) è corretto?

Question

Questo pseudocodice di inserimento albero rosso-nero da Introduzione agli algoritmi (CLRS) è corretto?

#1 da (7 voti)

6

Per il fix di inserimento dell'albero rosso-nero il libro distingue tra 6 casi, di cui 3 simmetrici. I casi sono (z è il nodo che viene inserito):

Caso 1: z's z è rosso
Caso 2: z's z è nero e z è un figlio destro
Caso 3: z's z è nero e z è un figlio sinistro

Il caso 2 è un sottoinsieme del caso 3, poiché possiamo trasformare Case 2 in 3 con una rotazione sinistra.

Tuttavia nello pseudocodice del libro che puoi vedere qui o qui scrivono come segue:

if uncle.color == red:
  # Handle case
else if z == z.p.right:
  # Handle case 2
  # Handle case 3

Non dovrebbe essere questo:

if uncle.color == red:
  # Handle case
else:
  if z == z.p.right:
    # Handle case 2
  # Handle case 3

Mi manca qualcosa? Il libro usa else if in un modo diverso rispetto a quello che dice Python? L'implementazione C ++ ha fornito qui utilizza la seconda versione come mi aspettavo.

algorithms trees binary-tree

posta Bar 12.01.2016 - 16:54

fonte

1 risposta

Leggi altre domande sui tag algorithms trees binary-tree

TCP - Handshake a tre vie, quale porta? schema del database con dati gerarchici illimitati che vengono modificati molto

score 7 · Accepted Answer

Il rientro nel codice è importante:

if uncle.color == red:
     # Handle case
else if z == z.p.right:
          # Handle case 2
     # Handle case 3

La sintassi è un po 'strana, perché hanno schiacciato il if per apparire sulla stessa riga del else , ma il caso 2 è rientrato ulteriormente verso l'interno rispetto al caso 3 rimanente, a indicare che non appartengono a lo stesso gruppo.

Questo è ciò che penso abbia inteso l'autore:

if (uncle.color == red) 
{
   # Handle case
} 
else 
{ 
    if (z == z.p.right) 
    {
         # Handle case 2 
    }
    # Handle case 3 
}