Intuizione dietro Splay Tree (alberi auto -bilancianti)

Question

Sto leggendo le basi degli alberi di splay. Il costo ammortizzato di un'operazione è O (log n) su n operazioni. Un'idea di base approssimativa è che quando si accede a un nodo, lo si spieghi, cioè lo fai root, quindi la prossima volta che si accede rapidamente e anche se il nodo era profondo, migliora l'equilibrio dell'albero.

Non capisco come l'albero possa eseguire O (Log N) per questo input di esempio:

Supponiamo che un albero di N nodi è già costruito. Le mie prossime operazioni N sono N Reads. Accedo a un nodo profondo dire a profondità n. Questo richiede o (n). È vero che dopo questo accesso, l'albero diventerà equilibrato. Ma dì ogni volta che accedo al nodo profondo più attuale. Questo non sarà mai inferiore a O (log n). Quindi come possiamo mai compensare la prima operazione costosa di O (n) e portare il costo ammortizzato di ogni lettura come O (log n)?

Grazie.

Answer 1

Supponendo che l'analisi sia corretta e le operazioni lo sono O(log(n)) per accesso e O(n) la prima volta...

Se accedi sempre all'elemento Bottomost (usando una sorta di oracolo peggiore), una sequenza di a Gli accessi richiederanno O(a*log(n) + n). E quindi il costo ammortizzato per operazione è O((a*log(n) + n)/a)=O(log(n) + n/a) o solo O(log(n)) Man mano che il numero di accessi diventa grande.

Questa è la definizione di prestazioni/spazio/spazio del caso medio asintotico, chiamata anche "prestazioni/spazio/spazio ammortizzato". Stai pensando accidentalmente che un singolo O(n) Passaggio significa almeno che tutti i passaggi sono O(n); Uno di questi passaggi è solo una quantità costante di lavoro a lungo termine; il O(...) sta nascondendo ciò che sta realmente accadendo, che sta prendendo il limite di [total amount of work]/[queries]=[average ("amortized") work per query].

Questo non sarà mai inferiore a O (log n).

Deve essere per ottenere O(log n) prestazioni medie. Per ottenere l'intuizione, il seguente sito Web potrebbe essere buono: http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml in particolare l'immagine http://users.informatik.uni-halle.de/~jopsi/dinf504/splay_example.gif - Sembra che durante l'esecuzione del O(n) Operazioni, si muove il percorso che hai cercato di scagliare verso la parte superiore dell'albero. Probabilmente hai solo un numero finito di tale O(n) Operazioni da eseguire fino a quando l'intero albero è bilanciato.

Ecco un altro modo per pensarci:

Prendi in considerazione un albero di ricerca binaria sbilanciato. Puoi spendere O(n) Tempo bilanciandolo. Supponendo che non aggiungi elementi ad esso*, ci vuole O(log(n)) tempo ammortizzato per query per recuperare un elemento. Il costo di configurazione del bilanciamento è incluso nel costo ammortizzato perché è effettivamente una costante che, come dimostrato nelle equazioni nella risposta, scompare (è nano) dalla quantità infinita di lavoro che stai svolgendo. (*Se aggiungi elementi ad esso, hai bisogno di un albero di ricerca binaria auto-bilanciante, uno dei quali è un albero di splay)