Può esistere ogni albero rosso-nero valido?

Question

Supponiamo di avere un red-black tree che è una valida binary search tree e non viola nessuna di queste regole:

• Un nodo è rosso o nero.
• La radice è nera.
• Tutte le foglie (NIL) sono nere.
• Entrambi i bambini di ogni nodo rosso sono neri.
• Ogni semplice percorso da un determinato nodo a una qualsiasi delle sue foglie discendenti contiene lo stesso numero di nodi neri.

Tale un albero rosso-nero sembra questo:

Vuol ogni possibile albero che soddisfa queste restrizioni hanno una sequenza di inserimenti e cancellazioni in modo che l'albero rosso-nero è generato?

_{Sto facendo questa domanda, perché penso di scrivere un articolo di blog su alberi di colore rosso-nero e vorrei dare alcuni esempi.}

Se si desidera testare un contro-esempio: Qui è a red-black tree implementation in python con una funzione implementata per generare l'immagine.

Per chiarire la domanda: Facciamo un gioco.

• Disegno un albero rosso-nero, che soddisfa tutte le restrizioni.
• Devi trovare una sequenza di inserimenti e cancellazioni, in modo da finire con il mio albero nero rosso.

Posso disegnare un albero rosso-nero in modo da non poter vincere?

I colori sono importanti! Se l'albero ha una forma diversa o colori diversi, non è lo stesso albero rosso-nero.

Si dovrebbe almeno sapere come generare questi due rosso-nero-alberi:

Si noti che questo è solo un assegno per voi se potesse funzionare. Se sai solo come ottenere questi due alberi rosso-neri, non puoi rispondere a questa domanda!

Answer 1

Penso che la branca della matematica che si occupa di quel tipo di problema è la teoria dei grafi e, esaminando alcuni documenti di teoria dei grafi che verificano la correttezza del nero rosso e di altri alberi equilibrati, sono portato a questo documento: http://www.math.unipd.it/~baldan/Papers/Soft-copy-pdf/cosmicah05.pdf e http://www.math.unipd.it/~baldan/Papers/Soft-copy-pdf/cosmicah05.pdf e questo documento http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.1161&rep=rep1&type=pdf, dovrebbero essere in grado di rispondere alle vostre domande sulle proprietà astratte. O almeno aiutarti a esprimere la tua domanda in un modo che porti a risorse ancora migliori.

Answer 2

se un albero seguire queste regole:

• Un nodo è rosso o nero.
• La radice è nera.
• Tutte le foglie (NIL) sono nere.
• Entrambi i bambini di ogni nodo rosso sono neri.
• Ogni semplice percorso da un determinato nodo a una qualsiasi delle sue foglie discendenti contiene lo stesso numero di nodi neri.

Sarà un albero binario bilanciato e può essere chiamato albero rosso-nero.

L'inserimento e la cancellazione di albero rosso-nero sono condizioni e regole speciali. Se l'albero come nel tuo esempio segue l'algoritmo di inserimento e cancellazione dell'albero RB, sarà sempre un albero RB. Durante l'inserimento e la cancellazione, un albero binario sbilanciato viene sempre ripristinato su un albero bilanciato cambiando il colore del nodo, il nodo rotante o il ramo.

Answer 3

Penso che quello che stai chiedendo qui è una prova formale di se un albero rosso-nero arbitrario, legittimo può essere costruito da una serie di inserzioni e cancellazioni a condizione che l'albero sia ribilanciato dopo ogni operazione. Non ho intenzione di tentare una simile prova, ma penso di avere un'idea di come potresti costruire una prova del genere.

Vorrei coprire in modo esaustivo tutti i possibili sotto-alberi che coinvolgono tutte le permutazioni legali attorno al nodo singolo e dimostrare che può essere costruito.Quindi:

• nodo nero
  • nessun genitore
    • figlio sinistro nullo
      • figlio destro nullo
      • figlio destro non nullo
    • figlio sinistro non nullo
      • figlio destro nullo
      • figlio destro non nullo
  • è il figlio sinistro
    • come sopra
  • è il figlio destro
    • come sopra
• nodo rosso (non può avere nessun genitore)
  • è il figlio sinistro
    • come sopra
  • è il figlio destro
    • come sopra

E quindi si deve creare un passo induttivo che mostri che qualsiasi albero arbitrario è una permutazione dei casi mostrati sopra. Sembra piuttosto semplice, quando la metto in questo modo, ma come ho detto nel mio commento, sono troppo arrugginito per affrontare la prova vera e propria.

Answer 4

Credo che l'inserimento dei nodi in attraversamento di larghezza (ordine di livello) produrrà qualsiasi albero rosso-nero.

http://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal

Perché li si inserisce in modo livello non si può avere un albero che è meno equilibrata rispetto dell'albero originale. Non sono necessarie cancellazioni e non sono necessarie rotazioni durante l'inserimento. Nel tuo esempio li si dovrebbe inserire nel seguente ordine:

13,8,17,1,11,15,25,6,22,27 

Edit: Anche se questo genererà un albero binario di ricerca con i valori corretti e modellare questo non può generare i colori appropriati ... dipende sull'attuazione della funzione di inserimento.Il motivo è la definizione di alberi rosso-neri che consentono variazioni nel colore dei nodi quando l'albero ha più di un nodo ed è pieno e tutte le foglie sono alla stessa profondità - seguendo la definizione di Wikipedia questo è un albero binario "perfetto":

http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

Supponiamo che l'albero ha tre nodi con valori {1,2,3} dove "2" è la radice ed è, per definizione, il nero. I nodi {1,3} potrebbero essere sia neri che entrambi rossi senza violare le regole rosso-nere. Quindi un'implementazione perfettamente valida di un inserto rosso-nero potrebbe rilevare quando l'albero è "perfetto" e colorare ogni nodo nero. Una tale implementazione impedirebbe di essere in grado di costruire un albero che, ad esempio, alterna il nero e il rosso ad ogni livello.

Edit 2: Dato che entrambi gli alberi red-black sono possibili input (tutti e tre i nodi neri e nodi 1 e 3 rossi) questo risolve la domanda se le eliminazioni sono necessarie, se c'è una soluzione allora le eliminazioni sono necessarie. La domanda nella mia mente ora è se c'è un solo modo per implementare un inserimento/cancellazione di un albero rosso-nero. Se ce n'è più di uno e se producono alberi diversi, il giocatore del gioco dovrebbe comprendere l'implementazione per specificare l'ordine di inserzioni e cancellazioni per costruire un albero rosso-nero. Non ne so abbastanza sull'implementazione di alberi rosso-neri per rispondere alla domanda se esiste un solo modo per implementarli o se ce ne sono più di uno.