Ordine di inserimento nel caso peggiore altezza nera di un albero nero rosso

Diciamo che abbiamo a che fare con i tasti 1-15. Per ottenere le peggiori prestazioni di un BST normale, inserire le chiavi in ordine crescente o decrescente come segue:Ordine di inserimento nel caso peggiore altezza nera di un albero nero rosso

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Quindi il BST sarebbe essenzialmente diventato un elenco collegato.

Per il caso migliore di un BST si inseriscono le chiavi nel seguente ordine, sono disposte in modo che la chiave successiva inserita sia la metà dell'intervallo totale da inserire, quindi il primo è 15/2 = 8, quindi 8/2 = 4 ecc ...

8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15

poi il BST sarebbe un albero ben bilanciato con altezza ottimale 3.

Il caso migliore per un albero nero rosso può anche essere costruito con il caso migliore da un BST. Ma come possiamo costruire il caso peggiore per un albero nero rosso? È lo stesso del caso peggiore per un BST? C'è uno schema specifico che produrrà il caso peggiore?

fonte

2013-02-27 Jordan

Ehi questa è una bella domanda, penso. E sono particolarmente interessato a conoscere la risposta. Forse le persone al cstheory stackexchange possono aiutare qui. Quindi se puoi postarlo lì? – sukunrt

Mi sono imbattuto in questo documento: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.16.66458 – sukunrt

Potresti chiarire "metà dell'intervallo totale da inserire"? Solo curioso, e non riuscivo a capirlo – keyser

Non sarà possibile. Un albero rosso-nero si mantiene "cespuglioso", quindi ruoterebbe per correggere lo squilibrio. La lunghezza del caso peggiore per un albero rosso-nero è limitata a due elementi, ma non è ancora un caso "cattivo"; è ciò che è previsto, come lg (2) = 1, e hai 1 livello oltre la radice con due elementi. Non appena aggiungi il terzo elemento, ottieni questo:

B     B 
\    /\ 
    R  =>  R R 
    \ 
    R

fonte

2013-05-16 21:27:56

solo perché l'albero si equilibra da solo, non significa che non ci sia il caso peggiore. nell'istanza dell'albero rb, il caso peggiore probabilmente implica una sequenza di inserimenti che le regole di auto bilanciamento funzionano male attorno a – Jordan

Questo è vero, c'è un caso peggiore, ma non sarà un array lineare come hai postato. Ho frainteso la tua domanda? Modifica: c'è un caso peggiore per una determinata raccolta di elementi. –

I numeri separati da virgole intendono rappresentare l'ordine di inserimento non un array. Questo chiarisce le cose? – Jordan

Stai cercando un albero magro, giusto? Questo può essere prodotto inserendo [1 ... , 2^(n+1)-2] in ordine inverso.

fonte

2013-08-02 18:51:01 user2561873

Ordine di inserimento nel caso peggiore altezza nera di un albero nero rosso

risposta

Problemi correlati